ID:50823
 
http://www.byond.com/developer/Jp/jp_DungeonGenerator

It's got, like, a helpfile and everything! Amazing!

Anyway, this is the first stab at it. I intend to take it somewhat further. The following features are on my wishlist, and I will be implementing the vast majority of them:

- Make get/setDoAccurateRoomPlacementCheck() do something. Currently, it's not even listed in the helpfile, because it just gets and sets a boolean parameter that makes no difference. The check it's referring to is collision detection - making sure I don't drop one room on top of another. At the moment, that's done using axis-aligned bounding boxes. I can certainly imagine situations where this would be undesirable (Indeed, one of them is coming up in a moment), but doing more thorough detection is much slower. So, this flag indicates whether it should just do AABB, or AABB followed up with a tile-by-tile test. I've already got what is probably pretty close to an optimal algorithm worked out, I just need to implement it - first I need to figure out how to get the rectangle of overlap between two squares. Anyone got any ideas/links to website that describes how to do it? I'm sure I can figure it out given enough time, anyway.

- Make get/setUsePreexistingRegions() do something. Another currently undocumented flag, this is intended to allow you to generate 'on top of' features you've already placed. The idea is that when the flag is enabled, the generator will, before placing any rooms, scan the area you're generating in for open regions. If it finds any, it uses them as regions in the generation - doing such things as collision-detecting with them so rooms aren't dropped on top of them, and linking them up with the other regions, so that reachability is ensured. This would allow you to draw a river through the centre of a z-level, for example, specify the entire z-level for the generator, set the flag, and then go for it, and links to the river will be made as appropriate. This shouldn't be too tricky - the hardest part is working out which bits are regions and what the borders should be - but I thought I should probably get better collision detection first. The biggest degenerate case is a large ring - no rooms will be placed 'inside' the ring, because AABB thinks they collide - obviously this isn't the desired behaviour. This'll be the second thing I implement.

- Finally, I'd like to set up rooms so that they can have multiple sets of borders. This would be useful for a room that was, say, a chasm, with a ledge on either side. You can't cross the chasm, so the two ledges are different entities. If you tried that in the current generator, it wouldn't guarantee reachability - sometimes, you'd have to cross the chasm to get to some rooms. But if you could specify multiple sets of borders for the room, you could specify that one ledge was one set of borders and the other ledge was another set - the room would get turned into two regions, and reachability would be done from that. Reachability guaranteed, ledge-room preserved. This shouldn't be too hard - the trickiest part is ensuring backwards compatibility in the representation of borders. I'll likely do that using an extra flag added to /jp_DungeonRoom, and rooms that use the multi-region stuff just set it to 1.

Can't think of any other features I'd really like to add to it right now. If any of you come up with one, pass it by me.

I can't announce what else I intend to do with the generator because of the Thought for the Day (Which appears to have vanished with the new site. Pity).
I might see if I can use this with TitanNet for random mission generation. I'll probably have it generate maps either in the background (with a delay inserted somewhere in the library) or have it generate maps while no-one's logged in. What would be the best place for such a delay?

It also seems that if you have short max path lengths, it dies while attempting to build paths - perhaps the rooms could be placed at most max path length tiles from each other? It won't guarantee connectivity, but it will probably help.
- Anyone got any ideas/links to website that describes how to do it?
I do
May be a bit sloppy. I tried to write a .txt to HTML program that doesn't generate HTML too well yet.
Hazman: Most of the time taken is spent placing paths between rooms. If you want a delay in the library, this code, in Generate(), is probably where you want it:
while(regions.len>1 || paths>0)
if(numits>maximumIterations)
if(regions.len>1) out_error = ERROR_MAX_ITERATIONS_CONNECTIVITY
else out_error = ERROR_MAX_ITERATIONS_EXTRAPATHS
break
numits++

Stick it after the numits++. You'll have one delay per attempt to draw a path.

If that isn't enough, you could also stick one in getPath(), here:
while(1)
var/turf/min
var/mincost = maxPathLength

Stick it just after the while. That will wait the delay for every square of every path, though, and there are a fair few pathfails in your average dungeon - that would probably take some time.

It also seems that if you have short max path lengths, it dies while attempting to build paths - perhaps the rooms could be placed at most max path length tiles from each other? It won't guarantee connectivity, but it will probably help.

Yeah, it currently doesn't try to place rooms 'close' to each other, so short max path lengths will kill the path-making. I'll have a look into ways of placing rooms near each other efficiently. It can always be an option, when all's said and done.