Factorio New pathfinding algorithm
A simple choice for this function is simply the straight-line distance from the node to the goal position – this is what we have been using in Factorio since forever, and it’s what makes the algorithm initially go straight. It’s not the only choice, however – if the heuristic function knew about some of the obstacles, it could steer the algorithm around them, which would result in a faster search, since it wouldn’t have to explore extra nodes. Obviously, the smarter the heuristic, the more difficult it is to implement.
The simple straight-line heuristic function is fine for pathfinding over relatively short distances. This was okay in past versions of Factorio – about the only long distance pathfinding was done by biters made angry by pollution, and that doesn’t happen very often, relatively speaking. These days, however, we have artillery. Artillery can easily shoot – and aggro – massive numbers of biters on the far end of a large lake, who will then all try to pathfind around the lake. The video below shows what it looks like when the simple A* algorithm we’ve been using until now tries to go around a lake.