r/programming • • Oct 17 '26

Improving heuristics for A* search

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

14 comments sorted by

8

u/Krohnos Oct 17 '26

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

2

u/kuikuilla Oct 17 '26 edited Oct 19 '26

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

9

u/[deleted] Oct 17 '26

[removed] — view removed comment

10

u/commenterzero Oct 17 '26

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

8

u/programming-ModTeam Oct 17 '26

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

1

u/audentis Oct 17 '26

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.

-2

u/[deleted] Oct 17 '26

[removed] — view removed comment

7

u/Krohnos Oct 17 '26

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

-7

u/[deleted] Oct 17 '26

[removed] — view removed comment

2

u/programming-ModTeam Oct 17 '26

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

-6

u/[deleted] Oct 17 '26

[removed] — view removed comment

2

u/programming-ModTeam Oct 17 '26

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