Processing 1.0 - Processing Discourse - A* or A Star Path Finding Algorithm

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Discussion › Exhibition › A* or A Star Path Finding Algorithm

‹ Previous Topic | Next Topic ›

Pages: 1

A* or A Star Path Finding Algorithm (Read 2747 times)

st33d

A* or A Star Path Finding Algorithm
Jun 4^th, 2006, 11:29pm

I've put off learning this for a while, but since learning how to use Vector with my last project I'm confident to give it a go. I like a bit of A.I. in my art so this was something I needed to learn.

I've taken the instructions from the tutorial below and cobbled together some code. I've yet to look at the C++ examples as I wanted to make my own logical journey to the answer before being set straight.

http://www.policyalmanac.org/games/aStarTutorial.htm

I found this next link less helpful but there's a number of references at the bottom.

http://www.geocities.com/jheyesjones/astar.html

My own code is not yet packed into a class but I hope to do so and bring it back to this thread (I also need to fit an option for diagonal travel and to get the bot to move as close as possible, even when the pathfinder throws an exception). I've laid everything out in the applet with diagrams in the applet of all that is happening. This was to sort out my teething troubles as well as to illustrate what the algorithm was supposed to do.

http://www.robotacid.com/PBeta/astar/index.html

The code I'm sure could run a hell of a lot faster and would need to if it were to run on Processing Mobile. Suggestions are very welcome as are related links and code. Thankee.

blprnt YaBB Newbies Offline Posts: 45	*Re: A or A Star Path Finding Algorithm Reply #1 -** Jun 5^th, 2006, 12:04am Cool. I always enjoy reading your posts. They are full of juicy links and interesting ideas. I wish I was more organized when I am working on projects. Thanks!
	http://blprnt.com > Digital curiosities in Flash and Processing&&

mflux Senior Member Offline Posts: 388	*Re: A or A Star Path Finding Algorithm Reply #2 -** Jun 5^th, 2006, 1:04am Nice! I love the presentation so as to show the inner workings. This is how programming ideas SHOULD be taught!
	Portfolio

st33d

Re: A* or A Star Path Finding Algorithm
Reply #3 - Jun 6^th, 2006, 6:47pm

mflux wrote on Jun 5^th, 2006, 1:04am:

I love the presentation so as to show the inner workings.

This is how programming ideas SHOULD be taught!

Actually I was having severe trouble getting it to work. I illustrated the inner workings because of all the bugs I had to iron out.

I've updated the code to a static class. It's too big to post here and leave the comments in so I've just updated the link above with the new version. The drawing is now handled by outside functions so the whole thing can be a static class with static methods. However it leaves the last few nodes searched for on because I inserted a clause to return from the search if the distance to the target is zero before any calculations are performed. I've also switched to a boolean grid for checking if nodes have been placed (much quicker than checking the lists each time you want to add a node) and added the option of terrain modifiers (going uphill etc.) and of course it handles corners now as well. I should mention it supports multiple bots and targets too (but not in a swarm fashion - yet that is what the grid modifiers are there for - to add aversion to certain paths already being taken).

Oh, and another thing. If it can't find a complete route it will move to the lowest cost node (so the bots can anticipate now as well).

I've got one niggling problem with the minimum pathway length being 2. Can't figure out what it is. It still works but I'd like to make the code a bit cleaner. Any help would be appreciated. I'm also interested in any suggestions.

st33d

Re: A* or A Star Path Finding Algorithm
Reply #4 - Jun 7^th, 2006, 3:51pm

I wanted to develop A* for the game snake and to see what would happen. The results are a little weird. There's a fairly high mortality rate. I've also effected the terrain effect so the snakes all try to find the path of least resistance, usually a part they've already tunnelled through. There's 10 snakes in the guise of earthworms hunting out the red squares.

http://www.robotacid.com/PBeta/snakeAI3/index.html

I managed up to 50 snakes on a terrain 200x200. But as soon as I added difficult terrain things slowed down a lot.

TomC Full Member Offline Posts: 146	*Re: A or A Star Path Finding Algorithm Reply #5 -** Jun 7^th, 2006, 4:39pm Tron meets Snake - nice! Do you know the evolved Tron player project out of Brandeis? Check it out: http://demo.cs.brandeis.edu/tron/ All I can think of now is 'Snakes on a Plane'
	{sketches,links,blogs,hacks}

seltar Senior Member Offline Posts: 475	*Re: A or A Star Path Finding Algorithm Reply #6 -** Jun 7^th, 2006, 9:30pm Love it! allthough it was a bit hard to tell the snakes apart from time to time.. good luck evolving it, as i'm sure you will best -seltar
	I'm bored, therefore I program http://seltar.org > seltar's special place http://snippet.seltar.org > seltar's snippet palace http://libraries.seltar.org > seltar's libraries

st33d

Re: A* or A Star Path Finding Algorithm
Reply #7 - Jun 8^th, 2006, 4:12pm

Thanks for the positive feedback guys. I've updated the A* link and added a new function for the next best move now, seeing as the snakes needed something like that, and I've made the class unstatic as it was causing a few problems when transferring values. It's still a bit buggy though. I also took Seltar's advice and changed the look of the snakes from square to round. The worms are distiguishable now from each other and look a lot more squirmy!

That Tron thing I'll be sure to blog, right up my street that is.

I'm a bit stuck for inspiration after getting the snakes up and running. Perhaps I might look for some more AI stuff.

st33d God Member Offline Posts: 666	*Re: A or A Star Path Finding Algorithm Reply #8 -** Jun 9^th, 2006, 2:45pm Bam! 3D

seltar Senior Member Offline Posts: 475	*Re: A or A Star Path Finding Algorithm Reply #9 -** Jun 9^th, 2006, 4:49pm haha Wicked! great job mate keep up the good work
	I'm bored, therefore I program http://seltar.org > seltar's special place http://snippet.seltar.org > seltar's snippet palace http://libraries.seltar.org > seltar's libraries

st33d

Re: A* or A Star Path Finding Algorithm
Reply #10 - Jun 11^th, 2006, 8:47pm

I wanted to get a nice polygon snake for this next one but I haven't got my brain around 3D yet so I just left it as lines.

I tried to conquer 26 direction diagonal cube movement some time ago and couldn't think of a logical sequence to work my way around the cube. Today I hit on the idea of a spiral and I was able to walk round the whole cube without crossing my path. Unfortunately I also wrote 26 conditions for each direction. I pray this code is reusable.

I applied this to the pathfinder and the snakes. To keep the lines relatively straight I added a terrain penalty of 14 for 2D corners (based on square root of 2) and 17 3D corners (based on square root of 3). If you don't do this you get some wigglyness.

Pages: 1

‹ Previous Topic | Next Topic ›