6 ms·

Not to take anything away from the work but I think the title is misleading. A* is an optimal algorithm for graph search so you cannot make it 100x faster. What

Not to take anything away from the work but I think the title is misleading. A* is an optimal algorithm for graph search so you cannot make it 100x faster. What this does is make path finding faster by changing the structure of the graph.

chrisseaton 10y ago
I'm sure you're right in this case, but I wonder if it would be possible for an 'optimal' algorithm, where the optimality is in terms of high-level operations like compares required, to be out-performed by a non-optimal algorithm due to practical considerations such as cache utilisation. An order of magnitude more loads but in a cache oblivious pattern could be a win compared to a pathological pattern.
- mcguire 10y ago
  Certainly. Jon Bentley had an article on two string reversal algorithms with the same algorithmic complexity. On a very large string, one would finish almost immediately; the other was pessimal for paged virtual memory and wouldn't finish for hours.
fao_ 10y ago
FTA: "It has been said that "pathfinding is a solved problem." Just because something is "solved" doesn't mean it can't be improved especially with regards to execution time."
simias 10y ago
It's a very practical optimization (not just a theoretical algorithm) so I don't think it's really misleading in the context of game development. That being said there's an important gotcha, those techniques require a significant amount of precomputations (especially the bounding box one) so it might not be practical if you have very dynamic maps.
- Kiro 10y ago
  The map in my game is completely dynamic and every pathfinding technique I've tried is way too slow. I've had to resort to a really stupid path finding algorithm where the enemies just looks a few tiles ahead (meaning they get stuck very easily). Any pointers?
  - chrisseaton 10y ago
    Are you path-finding every frame? Can you take a snapshot of the game state and run full-path finding on a background core just once every second?
    - Kiro 10y ago
      It's not on every frame but depends on how often the enemy moves (every 150 ms or so). That's a good suggestion anyway!
      - stefs 10y ago
        calculate the path once and cache it. only recalculate it if the agent runs into an obstacle or maybe in a random time interval to make it cheaper.
  - dirtyaura 10y ago
    Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
    - Kiro 10y ago
      Maybe I misunderstood you but the players can change the map during gameplay so I don't think that will work.
      - Elrac 10y ago
        I'm assuming that changes to any given position X on the map happen much less frequently than pathfinding operations that touch on said position X. Is this the case? If so, then investing the pre-calculation effort (updating the precalc matrix, not re-generating the whole thing) at map update time, limited to only those areas potentially benefiting, might be an effective strategy.
andrewstuart2 10y ago
100x faster means improving the coefficients. A* is optimal in terms of asymptotic execution time, but that doesn't mean you can't improve the overall running time.
- semi-extrinsic 10y ago
  The classic example is matrix multiplication, where we know of incresingly sophisticated algorithms with increasingly better asymptotic performance, but in practice most matrix multiplications are for sub-100x100 (IIRC) matrices where the naive algorithm we all learned as undergrads is fastest.
  - derefr 10y ago
    > in practice most matrix multiplications are for sub-100x100 (IIRC) matrices I would say that you have the causation reversed: we just don't bother doing large matrix multiplications, because they're so expensive (and yet still don't usually cross the intercepts into making the "better" algorithms worth it, due to those algorithms having ridiculous constant coefficients.) I would love to run Floyd-Warshall on my 40-million point network graph—but it just ain't gonna happen.
    - semi-extrinsic 10y ago
      > we just don't bother doing large matrix multiplications, because they're so expensive Sure, I agree. I'm not a specialist in numerical lin.alg., but I've heard it said that if you're spending a lot of time on large dense matrix multiplications, you're probably approaching the problem in the wrong way.
raghavkhanna 10y ago
A* is optimal in the sense that it is guaranteed to find the optimal solution (shortest path), there are no guarantees in terms of speed IIRC.

chrisseaton 10y ago

I'm sure you're right in this case, but I wonder if it would be possible for an 'optimal' algorithm, where the optimality is in terms of high-level operations like compares required, to be out-performed by a non-optimal algorithm due to practical considerations such as cache utilisation. An order of magnitude more loads but in a cache oblivious pattern could be a win compared to a pathological pattern.

mcguire 10y ago
Certainly. Jon Bentley had an article on two string reversal algorithms with the same algorithmic complexity. On a very large string, one would finish almost immediately; the other was pessimal for paged virtual memory and wouldn't finish for hours.

fao_ 10y ago

FTA: "It has been said that "pathfinding is a solved problem." Just because something is "solved" doesn't mean it can't be improved especially with regards to execution time."

simias 10y ago

It's a very practical optimization (not just a theoretical algorithm) so I don't think it's really misleading in the context of game development. That being said there's an important gotcha, those techniques require a significant amount of precomputations (especially the bounding box one) so it might not be practical if you have very dynamic maps.

Kiro 10y ago
The map in my game is completely dynamic and every pathfinding technique I've tried is way too slow. I've had to resort to a really stupid path finding algorithm where the enemies just looks a few tiles ahead (meaning they get stuck very easily). Any pointers?
- chrisseaton 10y ago
  Are you path-finding every frame? Can you take a snapshot of the game state and run full-path finding on a background core just once every second?
  - Kiro 10y ago
    It's not on every frame but depends on how often the enemy moves (every 150 ms or so). That's a good suggestion anyway!
    - stefs 10y ago
      calculate the path once and cache it. only recalculate it if the agent runs into an obstacle or maybe in a random time interval to make it cheaper.
- dirtyaura 10y ago
  Change your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
  - Kiro 10y ago
    Maybe I misunderstood you but the players can change the map during gameplay so I don't think that will work.
    - Elrac 10y ago
      I'm assuming that changes to any given position X on the map happen much less frequently than pathfinding operations that touch on said position X. Is this the case? If so, then investing the pre-calculation effort (updating the precalc matrix, not re-generating the whole thing) at map update time, limited to only those areas potentially benefiting, might be an effective strategy.

andrewstuart2 10y ago

100x faster means improving the coefficients. A* is optimal in terms of asymptotic execution time, but that doesn't mean you can't improve the overall running time.

semi-extrinsic 10y ago
The classic example is matrix multiplication, where we know of incresingly sophisticated algorithms with increasingly better asymptotic performance, but in practice most matrix multiplications are for sub-100x100 (IIRC) matrices where the naive algorithm we all learned as undergrads is fastest.
- derefr 10y ago
  > in practice most matrix multiplications are for sub-100x100 (IIRC) matrices I would say that you have the causation reversed: we just don't bother doing large matrix multiplications, because they're so expensive (and yet still don't usually cross the intercepts into making the "better" algorithms worth it, due to those algorithms having ridiculous constant coefficients.) I would love to run Floyd-Warshall on my 40-million point network graph—but it just ain't gonna happen.
  - semi-extrinsic 10y ago
    > we just don't bother doing large matrix multiplications, because they're so expensive Sure, I agree. I'm not a specialist in numerical lin.alg., but I've heard it said that if you're spending a lot of time on large dense matrix multiplications, you're probably approaching the problem in the wrong way.

raghavkhanna 10y ago

A* is optimal in the sense that it is guaranteed to find the optimal solution (shortest path), there are no guarantees in terms of speed IIRC.