nancygold's Journal

Pathfinding algorithm to go with ECS
Like the entity systems and the procedural terrain generation, pathfinding has its own ugly pitfall.
It starts with a naive person googling "good pathfinding algorithm".
Such search leads to articles advertising exclusively A*.
Yet A* is neither good, nor simple, nor suitable for good video games.
A* has a fuckload of issues
* Requires binary tree to housekeep the priority queue of non-visited cells.
* Depends on nonsense like the heuristics function, which is obvious only for euclidean spaces.
* Convoluted even with the lambda functions.
* Fails on compressed spaces and doesn't work with advanced unit abilities, like teleport.
* Can't be easily parallelized.
* Non-incremental.
* Doesn't integrate the multigoal and inverted goal spaces.
* Really inefficient on larger spaces.
* Really inefficient for larger number of agents.
* Really hard to use with the Sims style smart objects.
* Invites ugly hacks, like path sharing and caching, which lead to inconsistencies.
* Pure A* is never used in practice. For example, Starcraft did the dirichlet tessellation into convex polygon zones, which have simple line paths inside of them. Other games use it only inside very small hierarchically organized subspaces. Or something like https://en.wikipedia.org/wiki/Rapidly_exploring_random_tree

Inexperienced people wont even be able to see these issues until they have polluted their project with the nigger A* degeneracy.

So why do the retards promote A*, if there are much better and easier to implement approaches like the data-driven gradient ascend and hierarchical gradient ascend, which can be run within the ECS framework? No idea. Academic conservatism? Obscurantism? Afro-centrism?

Anyway, here is the actually working algorithm
https://home.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

It doesn't require complex data structures or logic, works on 3d space, and doesn't have any of the A*'s deficiencies. It is incremental. It handless smart objects like nothing, works with both unexplored territory (the unexplored territory itself generates the fading gradient) as well as fog of war scouting. With the with 2 overlayed gradient maps trick and a tokenized propagation, one can integrate it with several different goals types, if one goals is allowed to depend on another. I.e. it can implicitly perform the dirichlet tesselation.

Current Mood: annoyed
Current Music: Hitoshi Sakimoto - The Eastern Front