I am working on a roguelike that's supposed to take place in a sewer system.
My idea is to first generate the underground canals themselves, border them with walkways and then let a dungeon builder plan out some dwelling places for denizens in the sewers.
Unfortunately I am quite stumped on how to generate the system of canals in the first place.
Canals should either begin at a feed or another canal and should end either at a sink or a canal. The graph of canals should be a forest.
Every feed and every sink has a capacity and the sum of capacities of sinks in a given tree should be at least as large as the sum of the capacities of feeds in the same tree.
One idea I have is to keep a list of all feeds, ordered in capacity from highest to lowest. Take the feed with the highest capacity, do a Dijkstra search for the nearest sink, substract the minimum of the capacities of the feed and sink from their respective capacities, if the capacity of the feed is still not 0, reinsert it into the list of feeds, if the sink has a capacity of 0 remove it as a valid target, repeat.
The Dijkstra search could be cheaper across tiles where there already is water. Also it needs to be tuned somehow to prefer straight lines – keeping track of the direction of the last step and making a step in any other direction more costly should do the trick.
This seems kind of nice for my purposes, but it has one large flaw: All of the canals end up with a width of exactly one tile. I had the idea of making canal tiles blocking for the Dijkstra search and making tiles next to a canal cheaper instead, but that means that canals will end up winding around sinks/feeds and will also path to different sinks than if they could just path straight through the canal.
Different idea: Every canal tile is represented by a canal ID and it's distance from the source of the canal of that ID. Every canal ID is also associated with a capacity.
The Dijkstra search runs as normal, but steps between tiles with the same canal ID can only happen downstream, that is, to tiles with ha higher distance to the source of that canal. When a canal is created, all the tiles it crosses are appropriately set, only that any tile with an existing canal ID downstream from where the canal enters that old canal and upstream from where the canal leaves the old canal gets a new canal ID. The capacity of the new canal is checked to decide whether it needs to be widened. The tiles created by widening get their distance value from the lowest distance neighbor tile of the same ID.
That seems awfully complex. Does anybody have experience with generating something like this? Or ideas how to simplify what I tried to describe here? Questions for clarification? Some pointers how the previous may fail spectacularly?
If it is of any consequence: I am writing this in Common Lisp with the help of "defenum", "fset" and "croatoan".