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
Last edited by alkatran; Aug 21st, 2004 at 10:35 AM.
Don't pay attention to this signature, it's contradictory.
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??
Last edited by Electroman; Aug 21st, 2004 at 07:01 AM.
Don't pay attention to this signature, it's contradictory.
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 .
EDIT: Testing it a bit more I see it only goes diagonal if the adjacent ones are not blocked. Guess does kinda make sense.
Last edited by Electroman; Aug 21st, 2004 at 10:13 AM.
When your thread has been resolved please edit the original post in the thread ()
and amend "-[RESOLVED]-" to the end of the title and change the icon to , Thank you.
When posting Code use the [VBCode]Code Here[/VBCode] tags to be able to use the code highlighting.
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:
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.
Don't pay attention to this signature, it's contradictory.
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.
Don't pay attention to this signature, it's contradictory.
-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.
Don't pay attention to this signature, it's contradictory.
Reply With Quote
.
)
, Thank you.
