Alice Community

Alice Community (http://www.alice.org/community/index.php)
-   Works-In-Progress (http://www.alice.org/community/forumdisplay.php?f=14)
-   -   A* pathfinding demo (http://www.alice.org/community/showthread.php?t=4111)

Niteshifter 03-22-2010 09: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 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 :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 10:39 PM

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

King Gamer(gorit) 03-23-2010 10: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 12:31 AM

Uploaded first version.

jediaction 03-24-2010 09:05 AM

i did not get what to do

Niteshifter 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).

jediaction 03-24-2010 05:14 PM

thanks

Niteshifter 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".

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

zenteo 04-03-2010 12:06 PM

That's pretty nice : D
I never thought that the A* algorithm would be possible in Alice!
This is damn amazing!
Go on! ; D

zonedabone 04-04-2010 04:49 PM

Be sure to change do in orders to do together if it will still work! That always speeds it up! Also, do I smell a snake with java attached to it's tail? Smells like Jython! I'm looking into it, and since Jython can have nested lists and dictionaries and queues, it's the perfect thing. I predict that it can calculate a path in an instant!:p

zenteo 04-04-2010 07:09 PM

[QUOTE=zonedabone;19432]Be sure to change do in orders to do together if it will still work! That always speeds it up! Also, do I smell a snake with java attached to it's tail? Smells like Jython! I'm looking into it, and since Jython can have nested lists and dictionaries and queues, it's the perfect thing. I predict that it can calculate a path in an instant!:p[/QUOTE]

Yeye, but it's much cooler that such things can be done in pure Alice : D

King Gamer(gorit) 04-04-2010 08:35 PM

Zonedabone and his Jython. Tsk Tsk Tsk. No, I am just kiding I bet he is right.

zenteo 04-04-2010 10:22 PM

[QUOTE=King Gamer(gorit);19439]Zonedabone and his Jython. Tsk Tsk Tsk. No, I am just kiding I bet he is right.[/QUOTE]

He is! ; )

Niteshifter 04-05-2010 12:48 AM

I first try to get it running in Alice to see if the basics will work. Getting it to run in Jython is pretty much on the to-do list, so it might not be implemented for a while :p.

zenteo 04-06-2010 08:07 AM

1 Attachment(s)
I got inspired! :p
So I made my own version of A* in Alice based on an older A* project I made in VB.net.
It can go diagonally, but it won't cross edges diagonally, that would've hurt!
It is sable and I haven't seen any bugs so far.
I do also think that it is abit faster that your version.

Hope you'll get the use of it ;)

Niteshifter 04-06-2010 08:40 PM

[QUOTE=zenteo;19508]I got inspired! :p
So I made my own version of A* in Alice based on an older A* project I made in VB.net.
It can go diagonally, but it won't cross edges diagonally, that would've hurt!
It is sable and I haven't seen any bugs so far.
I do also think that it is abit faster that your version.

Hope you'll get the use of it ;)[/QUOTE]

I tested yours against my new one and here are the results:

Zenteo: 45s
Niteshifter: 18s

Yours would definitely beat my old one since my old one has faulty search techniques. I might actually make use of your reconstructing method though (mine is still a bit bugged :p), so that's a plus :)

zenteo 04-07-2010 03:20 AM

[QUOTE=x2495iiii;19540]Goodbye, Mr. Allen.

"User lanceA has been banned permanently."[/QUOTE]

Ey! Come on... He is trying to help (some) people and he isn't always rude.
Please give him a chance and give him temp bans instead.
He can act normal and maybe he will, someday.

[QUOTE=Niteshifter;19533]I tested yours against my new one and here are the results:

Zenteo: 45s
Niteshifter: 18s

Yours would definitely beat my old one since my old one has faulty search techniques. I might actually make use of your reconstructing method though (mine is still a bit bugged :p), so that's a plus :)[/QUOTE]

Just 18 second O.O
Wow! That's a huge improvement!
I'm trembling with excitement for the final result. :D

Niteshifter 04-07-2010 11:45 PM

[QUOTE=zenteo;19548]
Just 18 second O.O
Wow! That's a huge improvement!
I'm trembling with excitement for the final result. :D[/QUOTE]

I'm trying to fit in binary heaps to get it faster. My main plan is to remove all iterative loops (or at least as many as possible).

x2495iiii 04-08-2010 12:43 AM

There you go, 26 posts removed (and good riddance).

Gotta say, I'm surprised there weren't any happy shouts, any dancing in the streets, any joyous renditions of "Ding, Dong, the Witch is Dead." C'mon guys, he's finally irritated me into banning him forever, let me hear it!

King Gamer(gorit) 04-08-2010 07:56 PM

[QUOTE=x2495iiii;19565]There you go, 26 posts removed (and good riddance).

Gotta say, I'm surprised there weren't any happy shouts, any dancing in the streets, any joyous renditions of "Ding, Dong, the Witch is Dead." C'mon guys, he's finally irritated me into banning him forever, let me hear it![/QUOTE]

YOu said the word and it shall be!
[SIZE="4"]Ding, DOng, the Witch is Dead!![/SIZE]
Or, LanceA at least.

jediaction 04-08-2010 08:05 PM

Ding dang dong, the sun is out and out forever!!!!!!!!!!

But hes probably going to make a new account and start all over again

zonedabone 04-08-2010 08:14 PM

We need to make a jython script that automatically finds him.
[PHP]if post.contains('idiot',['notinquote']):
user.postuser.ban('permanant')
forum.throwawaykey()[/PHP]
</BLOCKQUOTE>

jediaction 04-08-2010 08:43 PM

lol

zonedabone 04-08-2010 09:23 PM

[QUOTE=zonedabone;19597]We need to make a jython script that automatically finds him.
[PHP]if post.contains('idiot',['notinquote']):
user.postuser.ban('permanant')
forum.throwawaykey()[/PHP]
</BLOCKQUOTE>[/QUOTE]
hah!

bjia56 04-08-2010 10:14 PM

Um, who exactly did we throw out? :confused:

zonedabone 04-09-2010 06:39 AM

LanceA has left the building!

jediaction 04-09-2010 08:09 AM

hmm, the biulding
? more like the city

x2495iiii 04-10-2010 03:06 AM

I just realised we sort of hijacked poor Niteshifter's thread again. If you want me to re-clean it, let me know. I just wanted to make sure everyone wasn't shocked to see him go or something (which would be like a freaky twilight zone type thing).

jediaction 04-11-2010 10:47 PM

Oh yah, if you could clean it up that would be nise, thsi thread is leading up the wrong way. I would appreciate that and lets forget about this conversation and get back to what this threads about

Niteshifter 04-12-2010 12:01 AM

Good news and bad news:

Bad news: My flash drive got corrupted, so I had to revert to the most recent file which was about a week and a half ago (before trying to insert binary heaps).

Good news: I was actually going to revert to this file anyways for various reasons. I've updated it (haven't got binary heaps in yet) and have found a faster time. Apparently, I was referring to a deprecated function quite a few times in the background for some reason, so I removed the function and it works faster.

Updated speed with the 'U-wall': 7 sec.

Reconstructing the path has gotten seriously buggy, so I need to fix this first before moving on.

zenteo 04-13-2010 04:07 AM

[QUOTE=Niteshifter;19714]Good news and bad news:

Bad news: My flash drive got corrupted, so I had to revert to the most recent file which was about a week and a half ago (before trying to insert binary heaps).

Good news: I was actually going to revert to this file anyways for various reasons. I've updated it (haven't got binary heaps in yet) and have found a faster time. Apparently, I was referring to a deprecated function quite a few times in the background for some reason, so I removed the function and it works faster.

Updated speed with the 'U-wall': 7 sec.

Reconstructing the path has gotten seriously buggy, so I need to fix this first before moving on.[/QUOTE]

7 SECondS?! ThAt's crasy man! I would've believed it if it was in jython, but in pure Alice? I want to test it out now! :D

Niteshifter 04-13-2010 10:48 PM

[QUOTE=zenteo;19781]7 SECondS?! ThAt's crasy man! I would've believed it if it was in jython, but in pure Alice? I want to test it out now! :D[/QUOTE]

It's basically in a heavy development state, so I'm unable to release it until I get it into a "more stable" release. This is basically a list of what I need to do so far:
[LIST][*]Debug node problems[*]Debug path reconstruction[*]Insert/debug new functions/methods for binary heaps[*]Remove old functions/methods[*]Check and remove redundancies[/LIST]
There's also a lot of research/reference checking that goes in between all of that (luckily, I have two monitors :D), which makes this go longer.


All times are GMT -5. The time now is 04:12 AM.

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