Hi, I think I have an optimization for your algorithm which wouldn't require you to periodically scan tiles on a map. I don't know how your alrogithm curently works under the hood, but I think I got an idea from the description of the mod. Take a look at this proposiion for improvement:

https://imgur.com/dq7YD6Y

I hope I explained everything in the graphic pretty thoroughly. The idea is to offload processing to startup (map creation/map load) by detecting water volumes on given depth range, create a static map of them (revalidate on map change) and then make pumps track currently connected water body and drain only from that level, until it completely drains. Then, advance to the next one. It would then require only a single update per tick for deducing a given amount of water from tracked volume. Then, when the whole level is drained, update the whole level. This realistically follows how the water would be drained in real life and would run in O(1) and be deterministic for each pump in tick.

In case of any question I am open to explain. I'll try to edit this first message when I notice some vital info is missing from it or something, so keep track of that. I'll be appending to the bottom to make it easier to understand.

• I don't know factorio modding API well, so I will just guess some ways of implementing it for real.
• water body IDs could be stored per tile as a continuous array. For example [a1, b1], they track a single column. If IDs are lightweight, this shouldn't be much of a problem, but several optimizations could be made, such as doing a multi-headed linked list, or NOT storing that per tile and doing a query over some kind of map which stores spatial structure (so for a query of kind [x, y] returns list of regions -> imo a better option although more algorithmically complicated -> need to create some "contour map" or something with box cover).
• when talking about water body map I have contour map in mind: https://en.wikipedia.org/wiki/Contour_line
• the amount of depth levels should not be a problem, although more granular ones (e.g. increasing by 10) would probably work better than totally random ones (which would create a lot of possible single-tile islands if the randomness is noisy)
• If you also want to support depth > 0 (i.e. mountains), then probably two tree data structures would be a good idea-> one storing positive heights (peaks are leafs) and the other negative heights (pits are leafs)
• going further with the tree structure, you could use it to efficiently store the connected island per tile: just store the lowest depth for each tile. Then a single pump placement would directly use that value.
• You can use UNION-FIND algorithm to efficiently find connected islands. It would then efficiently connect islands from newly generated chunks (probably). It should also probably help in dynamically creating the depth tree structure.
• revalidation of region maps would probably have to happen on terrain change (landfil mine/build). I am not certain for now how to approach it, probably some chunk-based caching and recalculation would be a good idea (and storing region IDs for chunk borders)
• When it comes to splitting islands (on waterfill placement), for now I don't have a good idea how to do it, this seems hard. I am looking into algorithms and data structures like Link-Cut trees or others, although they are hard. An alternative could be to try floodfill from edges of a placed waterfill and revalidate it based on that, but maybe for speed keep it in chunk boundaries (and think of a way to link that information across chunk boundaries). I have one observation when it comes to contour lines: a tile can split a body of water only when it neighbors two contour lines. If we have some "counter" for tiles on contours (so probably number of neighbors with different height), then island can be split only when that count = 2. This could be used to skip recalculation when it's not needed or something?
• Split can be propagated downward the tree. If a shallower region has been detected to be split, then any deeper region passing through that tile has also been split. That is a logical conclusion from deeper regions being subsets of tiles of shallower regions.

Hi,

I’ve thought about grouping water tiles into water bodies. The main difficulty is splitting and merging them when landfill is placed or removed. But you’ve gone much further — maintaining “iso-islands” is a really original idea. I think I’ve understood your explanations well, but I’ll need some time to digest the details. I also understand that the implementation will take a lot of work to account for everything properly.

My per-tile simulation is far from efficient (it’s O(n)), and it works fairly well only with a small number of tiles (~40–50k) and about 1k tiles processed per tick. I think I’ll use your algorithm in the next optimization stage of the mod. For now, I’m focusing on non-optimization issues.

Thanks for your time — your illustrations are real works of art :)

If you want to try implementing it in Lua, I’ll be glad to prepare my GitHub repo with what I have so far.

Thanks for taking the time to read it ^^
I am thinking for now how to make merging/splitting effectively, this problem looks to be pretty difficult for now, but maybe some simple way is hiding in the plain sight I am not aware of. For now I think chunk-based recalculations could be pretty efficient. I am exploring some ways like splitting/merging contours, using some kind of spatial data structure like quad tree for quick revalidation or doing something as crazy as looking into advanced algorithms (link-cut trees or HDLT algorithm), but they all seem to be pretty hard. Possibly a chunk-bounded flood-fill on tile change in the tile would be a perfect balance between efficiency and simplicity, but I don't know yet. If I have a clear idea and time to test it I may try implementing some experiment like that :P
The idea for now is pretty rough around the edges and would probably work the best in case of static map. In case of dynamic one, union-find would be pretty nice for case where waterfill is removed (so joining water bodies), but splitting them (on waterfil place) would need another approach and probably recalculation of islands. If I find something good I'll try to update this post :D

Flood-filling seems expensive, but it’s probably the closest we can get to an optimal way to split water bodies — at least without storing additional information about the geometry of the water body (like a contour polygon).

It takes O(n), and the compromise would be to run the wave in the background (like pumps do now). Anyway, it’s still better than my current approach, because we’d only need to start flood-filling once, when a landfill is placed.

I am experimenting with some demo to check if the idea works and is viable. You can find it in here: https://t3st3ro.github.io/permalinks/factorio-prototype-water-basins

For now I am mostly vibe coding this stuff, I'll be reviewing and correcting it by hand later on and when I'm done I'll post an update in here :)

<network error duped my message>

Wow! Great job! It looks cool — and almost works correctly!

I noticed that different levels merged after I split the reservoir horizontally from right to left:

I also saw the same thing happen when I split the first contour:

Anyway, I played around a bit with your demo and noticed that the contour system looks great for visualizing gradual water loss, contour by contour. I believe that would be really nice to have in the game!

I’ve thought a lot about the splitting waterfills feature, and frankly, I realized I couldn’t come up with any interesting gameplay ideas that could be based on it...

Maybe building a dam with hydroelectricity would make sense, but only as an electricity storage — because you’d still need to spend the same amount of energy to create a water level difference using pumps.

So I think we can interpret landfill as a drainage culvert and simply ignore it in the simulation. Alternatively, we could disallow placing landfill on water. If you want to build on a water area, you should deplete it first :)

As for the algorithm’s correctness — right now it’s definitely not valid, since most of it is just AI hallucination 😉. I’ll need to go through it manually to make sure it actually works (e.g. diagonal connectivity) and has the performance I’m aiming for. At this stage, it’s mainly useful as a tool for visualizing and generating test terrain data, which lets me prototype algorithms quickly in JS (doing the same in Lua would take much longer, since I don’t know the API well). Currently, things like volume, water levels, and overflow calculations are still off, but at least it serves as a solid generator for test cases. I can also add a button to export the data (tiles, depths, pumps, reservoirs) if that would be helpful.

Regarding splitting waterways — I think there’s still some potential there, especially on island worlds (I like playing those and using cargo ships). It might also pair nicely with the pit mine idea I mentioned, where you’d dig down to uncover ores. In the future, if above-ground height ever gets added, a “flood” scenario could be fun — water levels rising (or receding, and you’d have to build reservoirs until the ocean is drained 😅).

One concept I really like is accumulative landfill: placing landfill would require support underneath (e.g. land at depth -1 and around), so building it would be more like constructing a pyramid. That would make landfilling much more expensive and strategic. In that context, splitting waterways could actually become a viable tactic for partially draining large bodies of water — you’d strategically separate sections with landfill walls, then pump them down one at a time.

On top of that, mechanics like “flooding accidents” could add tension, where water breaks through and machines underwater get destroyed.

Hydroelectric dam idea is very interesting and could also pair well with pumped storage hydroelectricity where potentially doing a water based "accumulator" would be much more space efficient than placing regular accumulators.

But for now, I think just the single mechanic of pumping water from one pit to another is already fun enough to experiment with 😄.

BTW I am out for the weekend so I'll get back to demo after monday :)

Thank you for sharing your thoughts on splitting waterways.

A “flood” scenario sounds really fun, and I think it’s definitely possible to implement. We have a height map, and we can emulate elevation by drawing tiles like this:

The same approach can be applied in the opposite direction — using landfill to build upwards.

Since we have full control over water filling, we’ll be able to flood areas while taking height into account.

Also, I looked at your AI's code — it looks quite decent to me.
It might be helpful to add some more advanced drawing tools, like brush size and a depth picker. That would give more control for testing edge cases.

Can’t wait to see how it evolves :)

Thanks for the idea, I changed controls and added brush and pipette :) Also added export/save/load, not tested thoroughly for now, but should be good if you want to generate some data for yourself and operate on it. The tree structure which gets serialized and basins detected are for now invalid, I'll try to do fix that next. If you don't see changes, you might have to hard reload the page and clear it's cache (open devtools -> RMB on refresh icon)

Looks nice! I'm going to play around with it and give you some feedback

I have implemented the version with those basins, but it turns out that the logic if a bit more complicated in several edge cases.

Demo: https://T3sT3ro.github.io/demo-factorio-water-basins
Source: https://github.com/T3sT3ro/demo-factorio-water-basins

There are still probably some bugs (IIRC with rendering pointers to active basins for pumps?)

For a static map, this algorithm can be very performant, but I have noticed some difficulties:
- overflow mechanic, because it's not obvious what basin to start filling if parent becomes "active basin" but some of it's children are still empty. A case like that is for example a tree A1: A2, B2, C2 (letter is ID, number is depth, this notation means A1 contains 3 deeper basins: A2, B2, C2). When there is an outlet pump in A2 and the basin is filled, which other basin should now be filling? Both? Random child? Closest one? If closest, how to determine it so it doesn't perform recalculations?
- "Downflow" mechanic: When a pump is in A1, how to determine where the water "flows down" to determine which basin is beeing filled? This is similar to previous point. Somehow determine the gradient? Cache for each tile it's closes deepest basin?
- Caching and tiling of the map: Considering big oceans or massive lakes, an important thing is caching and avoiding the needless recalculations. Right now the implementation determines all basin trees in O(n), where n is the size of the biggest basin, because it performs a single prioritized flood fill and creates the tree of basins dynamically. Recalculations while drawing also seem to be very fast, but I wonder if it can be optimized for the case where for example a large patch of landfill is build over the water and construction bots rapidly change tile after tile. I was thinking about caching the basins per chunk, invalidating them only for changed chunks and have transient "final basin tree" which is constructed from cached info from chunks, but it becomes increasingly more complex.

A problematic case could be when a bunch of pipes pump in and out repeatedly tick after tick into linked basins, changing parent water level between 0 and 1. If it has disjoined children basins, then tick after tick it would need to determine which children basins are "active". Generally speaking it would still be a huge performance gain for sensibly looking maps (e.g. not a checkerboard). since a single parent basin can expect <10 direct children basins, so the cost of switching the pointers and filling children basins may be imperceivable. To solve that case a "histeresis" could be added to the water levels, i.e. different water levels to make basin active/inactive based on to values: HIGH > LOW, where HIGH is the water content needed to make basin "active" (have water) when pumping in, LOW to make it drained again. This way there would be no fluctuations (water level needs to reach HIGH to become active but when it's active it needs to fall below LOW to become inactive again)

Thanks for keeping me updated!

Yeah, edge cases are always a pain in the neck.

overflow / downflow mechanics

Fortunately, we are not building a realistic physical simulation of water flow here. So I would choose one of the simpler solutions. For example, just fill both child basins evenly, or something like that.

I also had the idea of using preinstalled hidden inlet and outlet pumps when I was thinking about refilling basins with rain.

Since our last discussion, I tried to come up with an approach to deal with dynamic splitting of water and ground bodies effectively. I kept your idea about island type terrain in mind and the idea of defending your base from global flooding with landfill. But unfortunately, it seems there is no-one-size-fits-all solution. You need to use a full BFS to make it absolutely correct.

I also thought about a double buffering or page flipping approach that is used in computer graphics. The main front buffer would be our actual map, and the second buffer would be modified in the background asynchronously. Once the BFS is finished, the background map becomes the main one. The BFS would be reinitialized from scratch every time you place or remove landfill, or dig a canal.

Of course, the trade off is update lag. For large maps, it can take tens of seconds or even minutes to traverse everything. So I am not sure this would provide a good player experience.

Right now, I am leaning towards implementing only a static map.

I was playing with your demo for a bit, it is a nice sandbox. Great job!

Yup, filling all of the children basins is one way to do it. Assuming the water bodies look rather normal, there wouldn't even be many very distant children nodes, so it could still look pretty realistic (you could always argument that the world has connected aquifier layers xd).

For the recalculation I was thinking of coming up with some acceleration structure for each chunk, which can connect with others on it's edges. For example run BFS over 32x32 chunks and for each tile on the edge store some edge structure which can accelerate creating a read-only world-global map by stiching info from chunks. Conceptually it would be siilar to how HPA* pathfinding algorithm works.. Then — for the whole map — you would just have to keep a "read only" basin tree — it could even be a hierarchical structure like a quad tree. During tilemap changes, you only invalidate trees in the chunks which have been modified and recreate the stitched tree. Depending on how the stich operation works (for example union-find by traversing the basin tree upwards?)

For the double buffering I do not know how it would work in factorio since I don't really know it's API. I wonder if it is even possible to have a second buffer for an updated map, since at any tick the map could change, so I assume it could invalidate the whole calculation of back-buffer.