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. Use a bit of memory and make the time to generate the world a bit slower, but could be viable if the chunk-graph pathfinding calls are still slowing things down a bit at runtime.
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).
Rough back of the envelope: number of vertices, V = 20 chunks high * 20 chunks wide = 400. Chunk graph is sparse, each chunk connected to 8 neighbours by undirected edges, so number edges, E = (1/2) * 8 * V .
Memory required to store chunk-graph distance matrix: V^2 * sizeof(distance) = 400^2 * sizeof(float) = 640,000 bytes. Could use +inf for disconnected chunks due to islands.
Time to precompute full chunk-graph distance matrix by repeatedly dijkstra-ing from each chunk to all chunks in the chunk graph: V * T(dijkstra(E, V)) = V * O(E + V log V) = O(V E + V^2 log(V)) = O(V^2 + V^2 log(V)) = O(V^2 log(V)) , which won't scale due to the quadratic-ish V^2 log(V) term, but probably fine if V <= 400 .
> 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.
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.
> > 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.
>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.
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).
Rough back of the envelope: number of vertices, V = 20 chunks high * 20 chunks wide = 400. Chunk graph is sparse, each chunk connected to 8 neighbours by undirected edges, so number edges, E = (1/2) * 8 * V .
Memory required to store chunk-graph distance matrix: V^2 * sizeof(distance) = 400^2 * sizeof(float) = 640,000 bytes. Could use +inf for disconnected chunks due to islands.
Time to precompute full chunk-graph distance matrix by repeatedly dijkstra-ing from each chunk to all chunks in the chunk graph: V * T(dijkstra(E, V)) = V * O(E + V log V) = O(V E + V^2 log(V)) = O(V^2 + V^2 log(V)) = O(V^2 log(V)) , which won't scale due to the quadratic-ish V^2 log(V) term, but probably fine if V <= 400 .