VB: A* Pathfinding [Source]

[alkatran]

Here's a nice example of A* pathfinding. Includes:
-Three tiles (wow! three!), grass, mud and tree.
Mud is harder to walk through than grass, and trees are unwalkable.
-Ability to change "spread factor" (the value the estimated cost is divided by, increasing the "spread factor" increases search time etc...)
-Ability to change terrain settings... basicly chance stuff
-Resize terrain from 8x8 to 256x256
-Show the pathing while it happens
-A heap class (basically a very fast list for getting the best element)
-A functionals module with most of the functions I use normally
-A DX7 module with (very) simple drawing functions

Comments and suggestions are welcome.


The zip file is attached to post #4

[alkatran]

And here's a screenshot.
http://www.vbforums.com/attachment.php?s=&postid=1767655

Red squares are obviously ones that have been "touched"
Green squares are areas to which a better path was found
*This is only possible because diagonal movement has a higher cost
The numbers are the total cost of each square
The lines show which squares were found from which square (duh)

Oh, and the reason the last search timei is 2.32 seconds on a 16x16 map is because the option "search slowly" is selected. I wanted to get a screenshot in mid-search alright??

[alkatran]

And another screenshot, with a larger map and large spread factor. (a 6.2 factor has the effect of turning this into a floodfill algorythm)http://www.vbforums.com/attachment.php?s=&postid=1767658

[alkatran]

Oh. No wonder. When I edited my message it must have deleted the attachment.

Or maybe it was the fact that it was 2 am...

Anyways here's the code.

[Electroman]

Looks really good. Mind I think there is some kind of bug? it doesn't go diagonal always? Like the screen shot shows it could get to the end position by going diagonal but doesn't, instead it goes off the side of the screen :confused:.

http://www.vbforums.com/attachment.php?s=&postid=1767794




EDIT: Testing it a bit more I see it only goes diagonal if the adjacent ones are not blocked. Guess does kinda make sense.

[alkatran]

That's because you can't walk through a tree. (The path must be clear on boths sides to move diagonally, it just makes sense)

Here, look at this picture:
http://www.vbforums.com/attachment.php?s=&postid=1767796
As you can see, instead of passing diagonally by the tree, it went around it. Since to go diagonal there you would have to shave off an arm...


*edit* The end is always highlighted in blue when the search is finished. It doesn't mean a path was found.

[alkatran]

Actually, for proof that it is working, look at your own picture. Blocks which are just before corners only check the adjacent blocks but not the block "around the corner" (there is no line in between them).

Note that a lack of a line doesn't always mean unreachable from that tile... lines usually 'go outwards' from the center and not sideways.

[Pino]

ok thats pretty cool, but could you explain how a* path finding works? maybe a guide?

[alkatran]

A* pathfinding works by:

-Add the starting spot to the "Open" list
-calculate its cost
(loop starting here until end)
-take the lowest cost spot in the open list
-remove this spot from the open list and place it in the closed list
-add all adjacent spots which are not in the closed list by:
(a) if an adjacent spot is on the the open list, see if you've found a better path to it (this is show by a green highlight in this program)
(b) if an adjacent spot is not in the open list, just add it
Calculate the cost of all adjacent spots as you add them
(repeat)

Calculate the cost of a spot by adding the cost it took to get there, and estimating the cost to reach the end (I sum the X and Y tile position differences, for an estimate which is slightly too large)

The cost of each spot is shown in this program by the white text.

[dsheller]

That sounds kind of like the djistrkas (sp?) algorithm I saw in a math book once.

[alkatran]

http://encyclopedia.thefreedictionary.com/A-star%20search%20algorithm

I guess A* comes from it. There's a much better description of what the algorythm does there, too.

[Arie]

Very cool stuff!!! :) ;)
Can be used for AI in games!

Arie.