Live data from Hacker News

Improving Heuristics for A* Pathfinding

redblobgames.com

41–42 of 42 posts

Re: Improving Heuristics for A* Pathfinding

#41
post #12
post #10

It uses df as an example, but it (unlike the others) has the problem that the set of valid paths between any two points can be constantly changing.

One of the big questions for an algorithm is - when do you recalculate the path? A real "human" doesn't recalculate until they receive information that the chosen bath is blocked/changed (they see the road closed sign, etc). But many games recalculate distance to target (one ping only) over and over again each step, so moving a single block half a map away causes an entire army to repath immediately.

Real humans also don't have perfect knowledge of the map and have additional concerns besides the path length so A* should only be part of the whole solution if you want realistic movement.

Re: Improving Heuristics for A* Pathfinding

#42

Incredible write-up, as usual. I still fondly remember discovering Red Blob Games' Hexagonal Grids [1] guide while building an implementation of the Tzaar board game [2]. The illustrations are enormously helpful! [1] https://www.redblobgames.com/grids/hexagons [2] https://boardgamegeek.com/boardgame/31999/tzaar

I remember reading it in 2006 or so to better understand pathfinding algorithms for my data structures and algorithms class.
Post reply on HN