I've been curious for a while as to how path-finding gets implemented in real world games.
For example, the common algorithm appears to be A* where you use some heuristic to guess the most efficient path but update the path when you find another is more efficient (for example you hit a large wall on the first path).
This is easy enough when you have only one moving object (because you can just compute that path at the start and then follow it), however in a real game there are likely many moving colideable objects and you might choose a path that causes you to get stuck or have to take a very suboptimal path.
The most "correct" way to do it would be to recalculate the path for each moving object on each frame, but this would probably lead to unacceptably poor performance.
So you can wait until you get stuck and then try and find a path out (which may be impossible). Or you can divide your path into recursive sub-paths and compute different sub-paths as you move.
Now for simulation this is interesting, for example if you order a military unit to move to some location in real life then you would expect them to at least consult a map before setting off however there may be unanticipated situations on the ground which mean that they have to take a suboptimal path. So pathfinding inefficiency might add realism.
I have noticed that overall path finding is much improved in modern games, especially RTS. So curious roughly how their implementation works.
For example, the common algorithm appears to be A* where you use some heuristic to guess the most efficient path but update the path when you find another is more efficient (for example you hit a large wall on the first path).
This is easy enough when you have only one moving object (because you can just compute that path at the start and then follow it), however in a real game there are likely many moving colideable objects and you might choose a path that causes you to get stuck or have to take a very suboptimal path.
The most "correct" way to do it would be to recalculate the path for each moving object on each frame, but this would probably lead to unacceptably poor performance.
So you can wait until you get stuck and then try and find a path out (which may be impossible). Or you can divide your path into recursive sub-paths and compute different sub-paths as you move.
Now for simulation this is interesting, for example if you order a military unit to move to some location in real life then you would expect them to at least consult a map before setting off however there may be unanticipated situations on the ground which mean that they have to take a suboptimal path. So pathfinding inefficiency might add realism.
I have noticed that overall path finding is much improved in modern games, especially RTS. So curious roughly how their implementation works.