Newbie Problems - A Star and drawing

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller

Post Reply
K1ngMX
Posts: 5
Joined: Sat May 10, 2014 5:16 pm

Newbie Problems - A Star and drawing

Post by K1ngMX » Sat May 10, 2014 5:33 pm

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
Attachments
astar.jpg
astar.jpg

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: Newbie Problems - A Star and drawing

Post by FourthWorld » Sat May 10, 2014 5:38 pm

With just 100 boxes, you may find your code simpler and the runtime performance faster to use vector graphic objects instead.
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

Klaus
Posts: 13806
Joined: Sat Apr 08, 2006 8:41 am
Location: Germany
Contact:

Re: Newbie Problems - A Star and drawing

Post by Klaus » Sat May 10, 2014 5:41 pm

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

K1ngMX
Posts: 5
Joined: Sat May 10, 2014 5:16 pm

Re: Newbie Problems - A Star and drawing

Post by K1ngMX » Sat May 10, 2014 5:45 pm

@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 :)

jacque
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 7215
Joined: Sat Apr 08, 2006 8:31 pm
Location: Minneapolis MN
Contact:

Re: Newbie Problems - A Star and drawing

Post by jacque » Sat May 10, 2014 6:41 pm

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.
Jacqueline Landman Gay | jacque at hyperactivesw dot com
HyperActive Software | http://www.hyperactivesw.com

K1ngMX
Posts: 5
Joined: Sat May 10, 2014 5:16 pm

Re: Newbie Problems - A Star and drawing

Post by K1ngMX » Sat May 10, 2014 6:55 pm

@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.

jacque
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 7215
Joined: Sat Apr 08, 2006 8:31 pm
Location: Minneapolis MN
Contact:

Re: Newbie Problems - A Star and drawing

Post by jacque » Sat May 10, 2014 7:48 pm

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.
Jacqueline Landman Gay | jacque at hyperactivesw dot com
HyperActive Software | http://www.hyperactivesw.com

K1ngMX
Posts: 5
Joined: Sat May 10, 2014 5:16 pm

Re: Newbie Problems - A Star and drawing

Post by K1ngMX » Sat May 10, 2014 9:29 pm

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 :)

FourthWorld
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 9802
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: Newbie Problems - A Star and drawing

Post by FourthWorld » Sat May 10, 2014 10:11 pm

It's cheating, but there's an A* example that Björnke made on this page:
http://bjoernke.com/?target=games
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn

K1ngMX
Posts: 5
Joined: Sat May 10, 2014 5:16 pm

Re: Newbie Problems - A Star and drawing

Post by K1ngMX » Sat May 10, 2014 10:27 pm

okay, if im not able to create A* by myself i will have a look at his implementation, thanks :)

BvG
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 1236
Joined: Sat Apr 08, 2006 1:10 pm
Location: Zurich
Contact:

Re: Newbie Problems - A Star and drawing

Post by BvG » Mon May 12, 2014 11:09 pm

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
Various teststacks and stuff:
http://bjoernke.com

Chat with other RunRev developers:
chat.freenode.net:6666 #livecode

BvG
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 1236
Joined: Sat Apr 08, 2006 1:10 pm
Location: Zurich
Contact:

Re: Newbie Problems - A Star and drawing

Post by BvG » Mon May 12, 2014 11:23 pm

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.
Various teststacks and stuff:
http://bjoernke.com

Chat with other RunRev developers:
chat.freenode.net:6666 #livecode

Post Reply

Return to “Getting Started with LiveCode - Complete Beginners”