Hacker News Reader

> This might make sense if a bunch of assumptions hold: the chunk-graph does not change during gameplay, map sizes aren't much bigger than the one shared in the post so the number of vertices in the chunk graph is pretty small, land units share the same costs for traversing terrain (i.e. same chunk graph with same edge cost shared by all units).

The first assumption is mildly violated; the second one is tremendously violated--100,000+-chunk graphs are going to be quite routine, and million-chunk ones definitely plausible.

> Time to precompute full chunk-graph distance matrix by repeatedly dijkstra-ing from each chunk to all chunks

It’s faster to use an all-pairs shortest paths algorithm, of which there are several with better performance than what you’re suggesting.

> the chunk-graph does not change during gameplay

We mean the chunk component graph, right?

That does technically change, because you can use https://wiki.factorio.com/Landfill to fill up water and modify which positions a chunk component takes up (and also potentially merge two chunk components), but I think that happens rarely compared to pathfinding.

> chunk component graph

yes. thanks for helping to clarify.

> > the chunk-graph does not change during gameplay

> that does technically change, because you can use landfill to fill up water and modify which positions a chunk component takes up

Yep, that might be a dealbreaker.

If the terrain only changes from impassable -> passable, not the other way around (e.g. flooding disconnecting bits), then the distances computed for the old map should be valid lower bounds for the distances on the new modified (by landfill) map, so it might be possible to use the old distances as an admissible a* heuristic to guide search to recompute new distances on the new modified map, but that's getting a bit fiddly.

This caching is likely the kind of thing that is probably not worth adding to the codebase unless you get a significant performance boost, as it adds a number of constraints from the required assumptions that impede you from changing the game rules in future

You can add walls which biters try to move around. I think they add an extra cost since they don't move around them perfectly, and often they try to attack the thinner parts of the walls.

Not to mention cliff explosives (for removing the other major landscape-induced impediment).

And there are some mods that let you go in the opposite direction, creating cliffs and water.

>A small tweak to this approach would be to precompute and cache the entire chunk-graph distance matrix, so the chunk-distance between any two chunks can be computed by a lookup, instead of searching.

Doesn't this just move the intensive search work to the precompute that calculates distances?

you got it. not feasible to precompute the fine detail full graph, since it has far too many vertices, arguably feasible for the chunk-graph, since it is small.

there'd still be search cost at runtime doing the fine-detail searches since the distance heuristic defined by the chunk-graph is an approximation and misleads the fine-detail search some of the time.

need to profile & run experiments to see if this was anything like a win.

in practice it might be better to increase the accuracy of the chunk-graph heuristic by making it consider more factors, which would make it harder to precompute and cache everything, but might further reduce the number of nodes the fine-detail search needs to expand

edit: another variation of this would be to just start with an empty cache for chunk-graph distance matrix and fill it incrementally at runtime the time whenever you run a chunk-graph distance query as part of the heuristic. Then there isn't any up front time to precompute anything. Might be better if (source_chunk, dest_chunk) pathfinding queries at runtime aren't uniformly distributed but somewhat correlated, which is plausible, since some chunks are likely to be far more interesting locations to travel from/to than others.

Your calculations are for a tiny piece of the map. Factorio worlds are infinite. So "the chunk-distance between any two chunks" cannot be precomputed.

And Factorio worlds are not static. So even if you could precompute, you'd have to recalculate the whole thing every time a player places a wall, destroys cliffs, fills water, puts a new building, destroys a biter nest or a biter builds a new nest.

factorio generates terrain on the fly so this isnt possible. also you alter the terrain by placing stuff on it.

And now i have my next weekend project keyyed up :)