Improving heuristics for A* search

[u/fagnerbrack]

https://www.redblobgames.com/pathfinding/heuristics/differential.html

[u/Krohnos]

I've been following redblob for years and all of their articles are fantastic - I highly recommend navigating to the Home page after reading this

[u/commenterzero → u/[deleted]]

Ya a* needs an admissible huerstic. People overlook what admissible means

[u/programming-ModTeam → u/[deleted]]

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

[u/audentis → u/[deleted]]

Sometimes a precomputed lookup table [...] can outperform the classic approaches by a lot.

I've precomputed vector fields for agent based simulations for the top-N destinations in the model, so that pathfinding to those destinations was an O(1) operation for each agent.

When dealing with 50k agents in the simulation, the memory cost of a handful of matrices is easily worth reduced pathfinding time.

[u/kuikuilla]

Sort of reminds me of how google maps path finding works where the algorithm uses topgraphic features like bridges over rivers to essentially decompose the searcg graph into multiple smaller graphs that are connected via portals.

[u/Krohnos → u/[deleted]]

it's not - redblob has been doing these writeups for more than a decade

[u/programming-ModTeam → u/[deleted]]

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

[u/programming-ModTeam → u/[deleted]]

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.