Page 1 of 1

Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 5:33 pm
by K1ngMX
Hello everyone.

I have a course at my university where we are encouraged to work with LiveCode.
So naturally, i just started with simple things - how to use global variables, how to change properties of thing and so on.

Now im at the point where i wanted to do something more "advanced". So i started to write a simple A Star implementation. The interface and everything works - no problem here (see picture). However i have two Problems:

(1) drawing is really slow, im drawing lines and try to fill them with the bucket tool, but its really, really slow. Am I doing something wrong or is there a faster method of drawing ? Im basically choosing the pencil tool and the bucket tool to draw lines and fill them. (you can see the in the picture what im doing, i was careful to not draw a line two times etc... it gets horrobly slow when there are some on the grid used)

(2) for the a* algorithm i need some kind of List - in java i usually use a PriorityQueue or whatever. However, LiveCode seems to not have a list structure. So i need help regarding this. Just need an example of how to store items for the open/closed list of A Star.

So far, LiveCode looks great, im still a bit confused of the syntax, but hey, it will get better as im doing more small programs.

Thanks for help in advance and sorry for my english, im not a native speaker.

Greetings, K1ngMX

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 5:38 pm
by FourthWorld
With just 100 boxes, you may find your code simpler and the runtime performance faster to use vector graphic objects instead.

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 5:41 pm
by Klaus
Hi KingMX (Du deutsch? 8) )

1. welcome to the forum!

2. Since i have no idea what "A star" means, I also have no idea why and what your are trying to draw.
Could you please give a short explanation?

3. Same for -> the a* algorithm (?) and "list structure" 8)

Thank you!


Best

Klaus

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 5:45 pm
by K1ngMX
@FourthWorld
yeah well the thing is we need to write a System which helps regarding to some choices (so it does calculate things for you and gives you a hint which is/might be the best). We also need to use animations in our application - so im trying to find a good way of drawing things (and later move them). I guess when using vector graphics im able to move them right ? Thanks for the really (really !) fast answer.

@Klaus
(yes ich deutsch ;D)
A Star is an algorithm to find the shortest path in a given environment, so you can see in my second picture ive declared a start point (green) and an end point (red) aswell as obstacles - when i hit "go" the algorithm would find the shortest path between those two without using walls (gray). A List is something like an array but without boundries, so you can just say list.add(object) in java, and it stores them for later use.
(im not allowed to post links, but see the wikipedia page of "A Star")

thanks :)

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 6:41 pm
by jacque
If you are using the drag command to draw with paint tools, you can control the speed using the dragspeed property. But I would use graphic objects as Richard suggested, they are much more versatile. Vector objects are easily moved like any other object. If you need an animation for the project, then I would lock the screen, create the graphic, and then unlock the screen with one of the animated visual effects. See "lock screen for visual effect" and "visual effect" in the dictionary for info on how that type of lock is used and what visual effects are available.

BTW your English is excellent.

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 6:55 pm
by K1ngMX
@Jacque
yes im using the drag command, but the dragspeed is already set to 0. Well i thought there is a faster way to draw things, and vector objects seem to be the answer.


so the only question is now: how to implement lists or how to work-around them to get A* to run properly. Im confused as there seem to be no "real" datatypes in LiveCode, as far i have discovered variables (which can hold anything) and arrays of variables. So the way i think "normally" (working in java since years) with encapsulating everything in objects doesnt work :)

But hey, i love learning a new language and im excited to be able to work with it :)

thank you for the help.

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 7:48 pm
by jacque
What will you store in the list? If it contains values for the contents of the grid then you can use either an array or a plain text list. LiveCode's text chunking is extremely fast and is its greatest asset. You can parse a text list using any of the many chunking types (character, word, item, line) to retrieve the values you need. You are right there are no data types in LC, that's one of the advantages. The engine handles that for you.

Here is a simple list in LC. It has five lines, five words, and one item:

brown
red
green
blue
yellow

Here is another list:

brown,red
green,blue
yellow,orange

This list has three lines, three words, and four items. A "line" is any text delimited by carriage returns. An "item" is any text delimited by commas (which means item 2 of this list is "red" and a return and "green") and a "word" is anything delimited by white space (so word 2 of this list is "brown,red".) You can change the delimiters for lines or items by setting the lineDelimiter or itemDelimiter if you don't want the default values.

You can create a "grid" variable for your project where each square is stored as an item in the text and each row is a return-delimited line. To get the value of the third square of the second row, you would do this:

put item 3 of line 2 of gridVar into tValue

If you would rather use arrays, let us know. For a grid this small, I think text is easier to work with when you're learning.

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 9:29 pm
by K1ngMX
okay that sounds pretty cool. Will definitly give it a try.

As ive said, i want to write the A* algorithm (path finding), so the purpose of the list i mentioned is to sort all possible fields (of the grid) with a so called heuristic. For example, if my grid is 3x3 and the start is at the buttom left while the end is at the upper right, the heuristic for the middle field (2,2) would give me a two, because i would need at least 2 steps from the center to the end (assuming diagonal movement is not allowed). So the list would sort me all possible fields (that is not exactly true, but not really important for now, if you want to use an efficient implementation of A* too, i would say wikipedia has a much better explanation of the algorithm) with their heuristical value, to find the first "most likely" field which is correct in terms of an optimal path (=point with smallest heuristic).

[Just a side note: in Java this is realized with a so called PriorityQueue which is based on a heap, so it sorts the item to the correct position when added. That is what im trying to get because i want to implement A* effectivly. i guess you hear such things relativly often from new people here experienced in other languages :roll: ]

I think i will just work with the text features of LiveCode for know because its sounds really powerful and i need to get a feel for it before i can judge. Also, my grid is only 10x10 for now, so even if i do not sort the heuristic values and iterate over every (item/line/...) i think i will get acceptable results.

Thank you very much :)

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 10:11 pm
by FourthWorld
It's cheating, but there's an A* example that Björnke made on this page:
http://bjoernke.com/?target=games

Re: Newbie Problems - A Star and drawing

Posted: Sat May 10, 2014 10:27 pm
by K1ngMX
okay, if im not able to create A* by myself i will have a look at his implementation, thanks :)

Re: Newbie Problems - A Star and drawing

Posted: Mon May 12, 2014 11:09 pm
by BvG
Oh dear my implementation is so... old and weird and crufty...

But I had an amazing tutorial that really was able to explain to my stupid brain how it is supposed to work: http://www.policyalmanac.org/games/aStarTutorial.htm

Re: Newbie Problems - A Star and drawing

Posted: Mon May 12, 2014 11:23 pm
by BvG
Oh right in regards to the original question, I usually store data in arrays that are named by their grid coordinate, for example:

array[1,1]
array[1,2]
...

And it seems this is also what I did for my stack. So I'd run step 1 (scoring) and 2 (nearest neighbour) of A*, and finally i have something like this:

array[1,1] -> "1,2"
array[1,2] -> "2,2"
...

Then I simply start at the target and repeat until reaching the starting point, backwards to get the final path. This way reduces sorting operations to a minimum (one sort on the open list per roundtrip). It would be possible to pre-sort the variable, so only one sort would ever be needed, but this way the code is more readable.