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