4 ms·

Pathfinding Demystified

77 points by iKlsR 12y ago

muhuk 12y ago
Very cool series of articles. My take-away, from the last part: The state represented by each search node doesn’t have to be limited to a position; on the contrary, it can include an arbitrarly complex set of values. For example, if turning 90 degrees takes the same time as walking from one square to the next, the state of your character can be [position, heading]. Each node now represents not only the position of the character, but also its heading; and the new edges of the graph (implicit or explicit) reflect that. Going back to the original 5x5 grid, the starting position of the search now may be [A, East]. The adjacent nodes are now [B, East] and [A, South] - if you want to reach F, you need to correct your heading first, so the path would be [A, East], [A, South], [F, South]. First-person shooter? At least four dimensions: [X, Y, Z, Heading]. Maybe even [X, Y, Z, Heading, Health, Ammo].
- ggambetta 12y ago
  It's even more than that. You can get great results from A* on any graph search problem where you can find a good heuristic for the distance to the goal from some node, which may not be related to position at all. For example, I once did this with nodes that represented sets of database attributes and arcs that represented table joins.
  - Vaskivo 12y ago
    A* is not only a pathfinding algorithm, but a search algorithm. In my AI classes I used it for pathfinding, solving sudokus and other puzzles, and even to solve a job shop scheduling problem[1]. If you can translate your problem into a graph, you can use A* with it. In these classes, we had a problem to solve, and we had to solve it using different algorithms and in the end submit a report in wich we compared the result and efficiency of each. The ones that used heuristics, we had to implement about three different heuristics, analyze each and mix them up. [1] https://en.wikipedia.org/wiki/Job_shop_scheduling https://en.wikipedia.org/wiki/Job_shop_scheduling
- psycovic23 12y ago
  If you're curious about some cool domains, check this out. http://victor.hwanger.com/a-technical-peek-into-motion-planning-for-humanoid-robots/ http://victor.hwanger.com/a-technical-peek-into-motion-plann...
ichinaski 12y ago
> # If we just got to the goal node, build and return the path. if adjacent == goal_node: return build_path(goal_node) If you want to ensure the path is optimal, you'll have to wait until you 'expand' the goal node, as there might exist goal states in the open set with lower costs.
- ggambetta 12y ago
  Fixed. It's a copy-paste artifact from Part I, where the algorithm is looking for a path, not the optimal path, so it didn't matter. Thanks!
Kiro 12y ago
Maybe I misunderstand how this works but I want to find a pathfinding algorithm that is super fast and only calculates the first few steps toward a target. The target is moving and the calculation needs to happen several times every second so calculating the whole path is not feasible. It doesn't really matter if it gets stuck or doesn't find the optimal path, just that it looks like it's trying to move closer to the target. Any ideas?
- conjectures 12y ago
  Guesses more than ideas but. Have the distance estimation function take time as an argument? Actually move along the current best n-step path then start again?
- ggambetta 12y ago
  If "trying to move closer" is enough, maybe you don't even need a pathfinding algorithm - if the target is to the right move one step to the right, if the target is above move one step up, and so on?
  - datashaman 12y ago
    What if there are obstacles in the path? You'll need a more complex algorithm to deal with the possibility of getting stuck in corners.
    - ggambetta 12y ago
      Well, he did say "It doesn't really matter if it gets stuck".
      - datashaman 12y ago
        puts glasses on ah. :-$
  - Kiro 12y ago
    That's basically what I have with the addition of a small collision check. If there is a collision tile between the seeker and the target it tries to move sideways but this has the effect that it only takes three adjacent tiles to stop the seeker from reaching the target. I would like something smarter than that but still preserve the efficiency.
conjectures 12y ago
These articles are very well structured. Excellent delivery.
- ggambetta 12y ago
  Thank you!
jokoon 12y ago
found this a while ago http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/ http://code.activestate.com/recipes/577457-a-star-shortest-p... For those who prefer to read code...
royjacobs 12y ago
Cool article! If you're interested in how to do pathfinding in 3d, there's a very interesting library called Recast that does this [0]. The author also has a blog where he wrote about his progress, but that seems to have gone quiet. [1] [0] https://github.com/memononen/recastnavigation https://github.com/memononen/recastnavigation [1] http://digestingduck.blogspot.com/ http://digestingduck.blogspot.com/
pjmlp 12y ago
Great article! Just in time, as I am tracking down some A* implementation issues on an old codebase I am trying to revive.

77 points by iKlsR 12y ago

muhuk 12y ago

Very cool series of articles. My take-away, from the last part: The state represented by each search node doesn’t have to be limited to a position; on the contrary, it can include an arbitrarly complex set of values. For example, if turning 90 degrees takes the same time as walking from one square to the next, the state of your character can be [position, heading]. Each node now represents not only the position of the character, but also its heading; and the new edges of the graph (implicit or explicit) reflect that. Going back to the original 5x5 grid, the starting position of the search now may be [A, East]. The adjacent nodes are now [B, East] and [A, South] - if you want to reach F, you need to correct your heading first, so the path would be [A, East], [A, South], [F, South]. First-person shooter? At least four dimensions: [X, Y, Z, Heading]. Maybe even [X, Y, Z, Heading, Health, Ammo].

ggambetta 12y ago
It's even more than that. You can get great results from A* on any graph search problem where you can find a good heuristic for the distance to the goal from some node, which may not be related to position at all. For example, I once did this with nodes that represented sets of database attributes and arcs that represented table joins.
- Vaskivo 12y ago
  A* is not only a pathfinding algorithm, but a search algorithm. In my AI classes I used it for pathfinding, solving sudokus and other puzzles, and even to solve a job shop scheduling problem[1]. If you can translate your problem into a graph, you can use A* with it. In these classes, we had a problem to solve, and we had to solve it using different algorithms and in the end submit a report in wich we compared the result and efficiency of each. The ones that used heuristics, we had to implement about three different heuristics, analyze each and mix them up. [1] https://en.wikipedia.org/wiki/Job_shop_scheduling https://en.wikipedia.org/wiki/Job_shop_scheduling
psycovic23 12y ago
If you're curious about some cool domains, check this out. http://victor.hwanger.com/a-technical-peek-into-motion-planning-for-humanoid-robots/ http://victor.hwanger.com/a-technical-peek-into-motion-plann...

ichinaski 12y ago

> # If we just got to the goal node, build and return the path. if adjacent == goal_node: return build_path(goal_node) If you want to ensure the path is optimal, you'll have to wait until you 'expand' the goal node, as there might exist goal states in the open set with lower costs.

ggambetta 12y ago
Fixed. It's a copy-paste artifact from Part I, where the algorithm is looking for a path, not the optimal path, so it didn't matter. Thanks!

Kiro 12y ago

Maybe I misunderstand how this works but I want to find a pathfinding algorithm that is super fast and only calculates the first few steps toward a target. The target is moving and the calculation needs to happen several times every second so calculating the whole path is not feasible. It doesn't really matter if it gets stuck or doesn't find the optimal path, just that it looks like it's trying to move closer to the target. Any ideas?

conjectures 12y ago
Guesses more than ideas but. Have the distance estimation function take time as an argument? Actually move along the current best n-step path then start again?
ggambetta 12y ago
If "trying to move closer" is enough, maybe you don't even need a pathfinding algorithm - if the target is to the right move one step to the right, if the target is above move one step up, and so on?
- datashaman 12y ago
  What if there are obstacles in the path? You'll need a more complex algorithm to deal with the possibility of getting stuck in corners.
  - ggambetta 12y ago
    Well, he did say "It doesn't really matter if it gets stuck".
    - datashaman 12y ago
      puts glasses on ah. :-$
- Kiro 12y ago
  That's basically what I have with the addition of a small collision check. If there is a collision tile between the seeker and the target it tries to move sideways but this has the effect that it only takes three adjacent tiles to stop the seeker from reaching the target. I would like something smarter than that but still preserve the efficiency.

conjectures 12y ago

These articles are very well structured. Excellent delivery.

ggambetta 12y ago
Thank you!

jokoon 12y ago

found this a while ago http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/ http://code.activestate.com/recipes/577457-a-star-shortest-p... For those who prefer to read code...

royjacobs 12y ago

Cool article! If you're interested in how to do pathfinding in 3d, there's a very interesting library called Recast that does this [0]. The author also has a blog where he wrote about his progress, but that seems to have gone quiet. [1] [0] https://github.com/memononen/recastnavigation https://github.com/memononen/recastnavigation [1] http://digestingduck.blogspot.com/ http://digestingduck.blogspot.com/

pjmlp 12y ago

Great article! Just in time, as I am tracking down some A* implementation issues on an old codebase I am trying to revive.