Simple pathfinding Help
Author
I need someone to write a simple 2d shortest path pathfinder either in php or c++ or c
There is a 11 by 11 grid, you have to get from the middle to any other squair onli by traveling up down left right and diagonals between the squairs.
it needs to count the number of squairs it passes through and will have to run quick.
HERE IS THE CATCH.
Some of the squairs you cant travel all the paths eg.
[ ]--[ ]-[ ] S= Start
| | X | D=Destination
[ ]-[ ]-[ ]-[ ] [ ]=a Squair
| \
[ ]-[ ]-[ ]-[D]
quote:Original post by AtomicMike
I need someone to write a simple 2d shortest path pathfinder either in php or c++ or c
There is a 11 by 11 grid, you have to get from the middle to any other squair onli by traveling up down left right and diagonals between the squairs.
it needs to count the number of squairs it passes through and will have to run quick.
HERE IS THE CATCH.
Some of the squairs you cant travel all the paths eg.
[ ]--[ ]-[ ] S= Start<br> | | X | D=Destination<br> [ ]-[ ]-[ ]-[ ] [ ]=a Squair<br> | \ <br> [ ]-[ ]-[ ]-[D] <hr height=1 noshade></SPAN></BLOCKQUOTE> <br><br> This sounds like a straightforward A* problem to me. Check out http://www.gdmag.com/backissue1996.htm for a definitive article on the subject.<br><br> <br><br><font color="green"><br>Ferretman<br><br>ferretman@gameai.com<br><href="http://www.gameai.com" target="_new">www.gameai.com</a><br><br>From the High Mountains of Colorado<BR><br></font>
Here's Bryan Stout's pseudocode from that article:
I'm working on implementing this myself, but I've run into a problem. Above, where is it says "priorityque Open", I created a binary tree with each node that is added to the list is sorted by it's f(n) score. However, the items that are added to the list never seem to have a lower f(n) than the starting node. (I'm using simple euclidian distance between the points to determine h(n) ).
Also, I haven't implemented the code that removes the node from the open list and puts it on the closed list, as I don't quite understand the importance of that part. What good is having a priority que for popping items off of OpenList, that will be accessible at speed Log n, if your searches in OpenList and ClosedList will be at n each time you create a new node?
I know these are pretty ultra-newb questions, but I wasn't able to understand those parts of the algorithm from that article or the others I have found on the web.
Edited by - Dolamite on September 21, 2001 3:47:09 PM
Edited by - Dolamite on September 21, 2001 3:47:42 PM
This heuristic search ranks each node by an estimate of the best route that goes through that node. The typical formula is expressed as:f(n) = g(n) + h(n)Pseudocodepriorityqueue Openlist ClosedAStarSearch s.g = 0 // s is the start node s.h = GoalDistEstimate( s ) s.f = s.g + s.h s.parent = null push s on Open while Open is not empty pop node n from Open // n has the lowest f if n is a goal node construct path return success for each successor n' of n newg = n.g + cost(n,n') if n' is in Open or Closed, and n'.g < = newg skip n'.parent = n n'.g = newg n'.h = GoalDistEstimate( n' ) n'.f = n'.g + n'.h if n' is in Closed remove it from Closed if n' is not yet in Open push n' on Open push n onto Closed return failure // if no path found I'm working on implementing this myself, but I've run into a problem. Above, where is it says "priorityque Open", I created a binary tree with each node that is added to the list is sorted by it's f(n) score. However, the items that are added to the list never seem to have a lower f(n) than the starting node. (I'm using simple euclidian distance between the points to determine h(n) ).
Also, I haven't implemented the code that removes the node from the open list and puts it on the closed list, as I don't quite understand the importance of that part. What good is having a priority que for popping items off of OpenList, that will be accessible at speed Log n, if your searches in OpenList and ClosedList will be at n each time you create a new node?
I know these are pretty ultra-newb questions, but I wasn't able to understand those parts of the algorithm from that article or the others I have found on the web.
Edited by - Dolamite on September 21, 2001 3:47:09 PM
Edited by - Dolamite on September 21, 2001 3:47:42 PM
quote:Original post by AtomicMike
I dont understand any of this. Can someone help???
The book "Game Programming Gems" will clarify.
Regards,
Mathematix.
quote:Original post by AtomicMike
I dont understand any of this. Can someone help???
Here is a link to an excellent tutorial on A*. Study this, and check out
some of the other links he has made available, and then if you still
have specific questions, then post them here and someone will help you.
http://www.geocities.com/jheyesjones/astar.html
Good luck,
Eric
Why is everbody talking about A*?
I answerd more or less exactly the same question in ths forum some time ago...
I can mail you some sample code if this doesn't help you out
Then my answer were
>>
Point A: Start location
Point B: End location
You want to find the shortest way from A to B. The algorithm works the other way around though, that is, starting at point B and finding its way to A.
First: You need a buffer equal to the size of your map where you can define a tile to point to a tile next to it...
Second: The main function is called recursivly numerous times through the algorithm
The steps...
1. Are tile(x,y) point A?
If yes goto (4)
2. Make all the free tiles next to the tile(x,y) to point to tile(x,y) (in your buffer)
If no free tiles return;
3. For each free tile next to tile(x,y), call your function recursively... (Here goto (1) with new (x,y) values).
When done return;
4. Now you just have to check in your buffer where tile A is pointing, move there and check where this tile is pointing and so on until you reach point B.
Note that these steps does not handle the case if point B is unreachable from A.
You can greatly enhance the speed of the algorithm by making a smart choise at (3). Choose the tiles that is closest to point A first...
<<
// Javelin
-- Why do something today when you can do it tomorrow... --
Edited by - Javelin on September 30, 2001 3:56:34 AM
I answerd more or less exactly the same question in ths forum some time ago...
I can mail you some sample code if this doesn't help you out
Then my answer were
>>
Point A: Start location
Point B: End location
You want to find the shortest way from A to B. The algorithm works the other way around though, that is, starting at point B and finding its way to A.
First: You need a buffer equal to the size of your map where you can define a tile to point to a tile next to it...
Second: The main function is called recursivly numerous times through the algorithm
The steps...
1. Are tile(x,y) point A?
If yes goto (4)
2. Make all the free tiles next to the tile(x,y) to point to tile(x,y) (in your buffer)
If no free tiles return;
3. For each free tile next to tile(x,y), call your function recursively... (Here goto (1) with new (x,y) values).
When done return;
4. Now you just have to check in your buffer where tile A is pointing, move there and check where this tile is pointing and so on until you reach point B.
Note that these steps does not handle the case if point B is unreachable from A.
You can greatly enhance the speed of the algorithm by making a smart choise at (3). Choose the tiles that is closest to point A first...
<<
// Javelin
-- Why do something today when you can do it tomorrow... --
Edited by - Javelin on September 30, 2001 3:56:34 AM
quote:Original post by Javelin
Why is everbody talking about A*?
Generally, A* is considered the optimum pathfinding algorithm for several reasons.
1) It has been mathmatically proven to always find the optimum path with the
fewest number of nodes expanded (when the heuristic is admissible). And in
practice, this proves out (see Bryan Stout''s path demo program at gamasutra
for a comparison with other algorithms).
2) It is a well documented algorithm with plenty of tutorials and its versitility
has been demonstrated in a number of commercial computer games.
All that being said, if you are happy with your own algorithm and performance is
not an issue for your game, then use whatever you want.
Eric
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
