What does /sci think of the A-Star algorithm? Is it truly the best algorithm for finding paths, especially in complex scenarios like video games?
A star is garbage because there are often more optimized modifications you can make taking advantage of precisely what your game needs.
>>16802690You can't prove A* (or any other) is the best psthfinsing algorithm without solving P?=NP
>>16802690The best algorithm is no algorithm. You should really read something like Programming Pearls or Backhouse’s Algorithmic Problem Solving.
The real answer is it depends on the application and variables: Number of AI agents, complexity of the navigable environment, pre-calculated navmesh vs. dynamic pathing, limits on resources due to other systems etc.A* can work fine for a simple FPS with constrained maps but would not be able to handle like an RTS or city builder with thousands of AI agents navigating a complex world.
>>16802690>>16803034>The real answer is it depends on the application and variableThis.For example in uniform-cost grids A-Star has been obsolete since 2011 when Jump Point Search was discovered and there is not much reason one would reach for A-Star in such a scenario (since JPS in its worst case situations just drops back down to A-Star levels).
>>16802690Why not Dijkstra?
>>16802829N = 1
>>16807705A* and Dijkstra are a Variation of the same thing.There is a new fastes boy in town anyway:https://arxiv.org/abs/2504.17033
>>16802690A* suffers from dimensionality problems very quickly. Most practical global path planners in video games are going to have to deal with that problem somehow. You could do a continuous graphical method like RRT or PRM's and avert a lot of those dimensionality problems in exchange for questionable completeness. You could also do some kind of map decomposition and essentially decide the general section of the action space you need to be in before you actually solve for the path.
>>16802690Why should zombies be able to perfectly pathfind through an opaque maze that they have no prior knowledge of? I dislike a* not only for its computational cost, but for its simulation not matching the application.
