A* (AStar) pathfinding algorithm

[princec]

An A* algorithm now lives up in the shaven puppy game library. Find it on the sourceforge cvs:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/spgl/spgl/src/com/shavenpuppy/jglib/algorithms/

(You'll also find Bresenham's line drawing algorithm, a hacked Perlin noise generator, and a radix sorter)

Cas

[larth]

An A* algorithm now lives up in the shaven puppy game library. Find it on the sourceforge cvs:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/spgl/spgl/src/com/shavenpuppy/jglib/algorithms/

(You'll also find Bresenham's line drawing algorithm, a hacked Perlin noise generator, and a radix sorter)

Cas :)

Kewl! What's the license for the files without any license mentioned, f.x. the A star files?


/Lars

[whome]

Life-After-Bresenham
2-step linedrawing algorithm beats them all 10-0:
http://escience.anu.edu.au/lecture/cg/Line/lifeAfterBresenham.en.html
Browse down to see a full pseudocode.

Games published by our own members! Check 'em out!

[swpalmer]

How is line drawing applied to the more complicated problem of pathfinding?  Drawing a straight line between two points is much simpler than general pathfinding.

[zparticle]

I'm considering using the A* algo in a game I've almost got finished. However I'm concerned that the algo will cause an enormous amount of garbage collection making the game jerky.  

Has anyone actually used A* in a 2D platformer type game?

What effects did you see if any?

[princec]

Have a look at the A* code I've released. No allocation.

Cas

[tom]

Anyone tried the AStarInt class?

I'm having some problems with it. I've narrowed it down to the AStarInt.NodeList class. Profiling shows that it spends a lot of time in java.util.Arrays.mergeSort. The problems went away when I rewrote the NodeList class to use an ArrayList with brute force pop, remove and get functions. Also the rewritten class uses less steps to complete the search. Which makes me wonder if there is a bug.

[princec]

Well, I didn't have any problems when I was testing it but as I never got to use it in anger I couldn't really say...

Cas

[tom]

Well it might be just me. I do have the ability to mess things up now and then