Alice Community  

Go Back   Alice Community > Alice 2 > Works-In-Progress

Reply
 
Thread Tools Display Modes
A* pathfinding demo
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Thumbs up A* pathfinding demo - 03-22-2010, 09:37 PM

Thanks to zenteo's idea of merging a 2D array into a 1D list, I can now do pathfinding with nodes

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 . 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).
Attached Files
File Type: a2w AStarDemo.a2w (864.2 KB, 36 views)

Last edited by Niteshifter; 03-24-2010 at 12:34 AM.
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 03-23-2010, 12: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 )

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 .
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 03-23-2010, 10:39 PM

Finished! Just got to do some testing and cleaning up and then I'll upload
   
Reply With Quote
Old
King Gamer(gorit)
Guest
 
Status:
Posts: n/a
Default 03-23-2010, 10:40 PM

Quote:
Originally Posted by Niteshifter View Post
Finished! Just got to do some testing and cleaning up and then I'll upload
Sounds cool.
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 03-24-2010, 12:31 AM

Uploaded first version.
   
Reply With Quote
Old
jediaction
Senior Member
 
jediaction's Avatar
 
Status: Offline
Posts: 5,064
Join Date: Jul 2009
Location: Bel Air, Maryland
Default 03-24-2010, 09:05 AM

i did not get what to do


Website: www.salokingames.com
FaceBook: www.facebook.com/SalokinGames

Last edited by jediaction; 04-09-2010 at 08:08 AM.
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 03-24-2010, 05: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).
   
Reply With Quote
Old
jediaction
Senior Member
 
jediaction's Avatar
 
Status: Offline
Posts: 5,064
Join Date: Jul 2009
Location: Bel Air, Maryland
Default 03-24-2010, 05:14 PM

thanks


Website: www.salokingames.com
FaceBook: www.facebook.com/SalokinGames
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 03-26-2010, 01: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".

Last edited by Niteshifter; 03-26-2010 at 01:24 PM.
   
Reply With Quote
Old
Niteshifter
Guest
 
Status:
Posts: n/a
Default 04-02-2010, 01: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.
   
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



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