Alice Community

Alice Community (
-   Works-In-Progress (
-   -   A* pathfinding demo (

Niteshifter 03-22-2010 10:37 PM

A* pathfinding demo
1 Attachment(s)
Thanks to zenteo's idea of merging a 2D array into a 1D list, I can now do pathfinding with nodes :D

The A* (pronounced A star) pathfinding algorithm basically has the computer calculate a path from one position to another by itself AND have it avoid obstacles :o. It's not all that complicated, however in Alice it is (because I have a limited use of arrays, classes, etc.).

First version is out. It's got a few bugs in it and is very slow, so I doubt anyone would want to implement it into something at the moment. This one shows an example of a bug and it's slowness (it should complete in about 105 seconds from the time play is pressed).

Niteshifter 03-23-2010 01:44 AM

Finished the main search algorithm, now I need to modify how it reconstructs the path it's made (the way I did it didn't work the way it was supposed to :p)

Unfortunately, I had to deprecate a few things in order to make it work properly, including the array merging. Apparently, there's a bug with the "last item in list" function; it always returns NaN or null.

Now I just need to figure out where I put my reference for reconstructing :p.

Niteshifter 03-23-2010 11:39 PM

Finished! Just got to do some testing and cleaning up and then I'll upload :D

King Gamer(gorit) 03-23-2010 11:40 PM

[QUOTE=Niteshifter;18959]Finished! Just got to do some testing and cleaning up and then I'll upload :D[/QUOTE]

Sounds cool.

Niteshifter 03-24-2010 01:31 AM

Uploaded first version.

jediaction 03-24-2010 10:05 AM

i did not get what to do

Niteshifter 03-24-2010 06:11 PM

All you need to do is press play, then wait and it'll start up once it's finished loading (it should be about 2 min before it'll start moving because of the calculations it needs to do).

jediaction 03-24-2010 06:14 PM


Niteshifter 03-26-2010 02:16 PM

You can also move the blocks around to make a different obstical map for it. It may take from 5 seconds to 5 minutes depending on the map.

There are some bugs in it like sometimes the moving block will go through the obstical blocks (I'm still working on a fix for this), also the reason why it goes so slow is because the search algorithm iterates through the entire thing from the first entry to the last for matches, so I'm currently researching different search algorithms and variations on the A* such as iterative deepening depth-first search (IDDFS) and D*, since they seem promising.

I may also implement something to show it's process rather than having the person wait the entire time. I have done some minor updates to my initial program, but it's nothing "upload worthy".

Niteshifter 04-02-2010 02:10 AM

I've fixed up a few bugs and made it about 18 times faster. There's still a bit more work to be done on it before I can make my second release though.

All times are GMT -5. The time now is 09:15 AM.

Copyright ©2021, Carnegie Mellon University
Alice 2.x 1999-2012, Alice 3.x 2008-2012, Carnegie Mellon University. All rights reserved.