Sewer generation

[Antsan]

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".

[Tzan]

Are you representing vertical levels, water levels, water falls?
Do things need to float down stream?

If not, then you don't need sources and sinks.
Just make wide corridors as normal and make the middle tiles water.
If you do it the easy way have you accomplished 100% of what you want?

[Antsan]

I wouldn't accomplish what I want because this way the capacity of the streams isn't consistent. I think overflowing due to heavy rain might be an interesting addition to the game mechanics later.

[Krice]

That capacity thing is called overdoing it. You are probably creating a game with magic and other non-realistic nonsense in it and then worry about realistic capacity and flow of sewers. Possibly not worth the trouble.

[Antsan]

I am specifically not interested in posts telling me not to write an algorithm for this. If you think I'm overdoing it that's fine, but there is no point in writing a post about it.

It's not about realism, it is about suspension of disbelief. The whole game will take place in a sewer system, don't you maybe think that I should get that aspect at least partially right?

Look at this sewer network:

Code: [Select]

#####~~~######
#####~~~######
#####~~~~~~~~~
~~~~~~~~~~~~~~
######~#######
######~#######
######~~~~~~~~
######~~~~~~~~
##############
It looks wrong. It isn't believable. It's obvious that this doesn't work.


My original idea is quite code-heavy. It's hard to split it into different functions and the two functions I could extract are monstrous. That is, they've got more vertical lines than my monitor, which is not acceptable.
I'm now trying to use a kind-of Huffman encoding on the feeds and sinks to generate the abstract structure of the network before painting it onto the map.

[Krice]

If you think I'm overdoing it that's fine, but there is no point in writing a post about it.

That's the point actually, because you see this happening sometimes in game design.

[Antsan]

This is not a topic about game design, it is about solving a programming problem.

More practically: Every time there is an new post here I am happy to get an answer. Instead I now have not one (which was fine) but three posts telling me that solving this problem may not be a worthy endeavor.

Unless you have something to add regarding writing and algorithm which does what I specified earlier I ask you to refrain from posting here anymore.

In more constructive news, I implemented the solution with first building the tree. It still needs some polish to be more efficient and retain more valuable information (why did I decide to screw both of these up at once?), but it works.

[sokol815]

Cool idea!

I might try using a 2d array initialized with zeroes, and then plotting your canals along the 2d array by increasing the values as each canal passes through the cell.

Then perhaps you could come up with a tile system that is able to pick from a set of 6x6(or whatever size) tiles that would correspond with the data in each cell + it's neighbors.

7x7 tiles might be even easier to use if you are looking to have large variances in amount of water flowing.

Code: [Select]

this tile has a small amount of water running east-west
######     
......
~~..~~
..~~.~
......
######

this tile has a medium amount of water running east-west
######     
......
~~~~~~
~~~~~~
......
######

this tile has a large amount of water running east-west, it's even overflowing onto the path
######     
..~...
≈≈≈≈≈≈
≈≈≈≈≈≈
....~.
######

some water coming from all four directions
#.~~.#           
..~~..
~~~~~~
~~~~~~
..~~..
#.~~.#

by composing these tiles into a map using the 2d canal-map array, you could build a realistic looking map. You would either require a decent amount of tiles (not ideal), or a method of generating all the types of tiles you might need...

Code: [Select]

Here is a multi-use East-West tile... the numbers here indicate the water level at which they turn from a . to a ~ or ≈
######
444344
212221
222122
443444
######

if you use this method, you will only need to make 16 tiles or so + variants (if you need them)

How to number tiles:
assume water can come from NESW directions... give each direction a worth 1,2,4,8.
for any individual cell on the map, determine which directions water is coming from.
If it comes from the north and south, it is a NS tile, which gives it a value of 5 (N:1, S:4)
You now know you need to grab a NS(5) tile and populate it into your world, switching out the water-depth-allocated cells as appropriate.

Code: [Select]

      1
   ------
  |      |
  |      |
8 |      | 2
  |      |
  |      |
   ------
      4

I'm interested to see how your project works out. Keep us posted!

[Antsan]

The Huffman solution looks quite good, but is not sufficient. Generating believable positions for feeds and sinks is necessary, too, otherwise feeds/sinks being too close to each other leads to undesirable clumping of canals. Also all canals still have a width of 1 in my code, but that should be easy to fix.

One problem of the Huffman solution is that the distance check (which determines the cost of connecting to elements) needs to run across a whole canal if one of the elements to be connected is a canal. That's quite expensive.

Also there is a memory leak either in my implementation or in sbcl. Running the generation 3 to ~100 times (depending on the number of feeds/sinks) leads to sbcl crashing with an exhausted heap. That shouldn't be happening – the results of the tests I did all were thrown away and shouldn't impact memory usage at all.