There are several approaches to allocating space for rooms for dungeon generation - Angband and variants use a cell based approach where the dungeon is divided up into 11x11 cells and then cells are marked as being filled when a room is placed which intersects the cell. The most common room size is 33x11 grids, or 3x1 cells, which was chosen because the space available in the Angband main screen was 66x22 grids on the majority of platforms it was ported to. The room sizes ensure that most rooms can be cleanly fit within the display.
A naive approach to placing the rooms is to pick a random top left-hand corner from 0 to dungeon_width - room width in cells, for the x-axis, and 0 to dungeon height - room height, again in cells, for the y axis. This approach is used in Angband and persists for the more sophisticated implementation used in Sangband (and I suspect Oangband and variants) in the find_space routine.
I've discovered several issues with find_space. The first is that space is never freed (cells marked as empty) if the room fails to be placed subsequent to find_space being called - easy enough to fix. But the one I want to talk about here is that the random approach fails significantly often - often enough for room placement to fail even when multiple attempts are made (25 per room in find_space).
My initial attempt to rectify this was to slide the room into an available space 'nearby' by moving it either horizontally or vertically a short distance and checking if it fit again. But this routine just highlighted how expensive multiple iterations within find_space was: making it 5 times more expensive (4 directions to test, plust the initial placement) resulted in a significant slow down in dungeon generation even on my Core Duo notebook.
I realised that there is one fact we know from attempting to place a room and failing that I could exploit: that the location we had tried was full. Sliding 'nearby' was counter-productive because nearby full was probably also full. So I should instead be looking as far away as possible, on the assumption that that would be empty.
The quickest way of doing far away as possible was to try reflection in either the x or y axis and try again. For checking grids near the midpoint, instead of reflecting, the code chooses either edge on that axis; basically a transformation from inner to outer. And to avoid checking the same far away multiple times, the code keeps choosing a random value for the axis that we don't transform - just like the original naive implementation.
To minimise calls to random, we just modulo the loop counter to determine which tactic to use, ensuring that the first time through the loop, as well as frequently enough in later iterations, we keep trying the naive approach.
This approach noticeably improved the success at placing rooms using find_room. It works well even if you don't randomly pick the position of the untransformed axis - because Sangband and Unangband attempt to place rooms from largest to smallest, I ended up with clusters of smaller rooms together, which had collided with a larger room in the originally attempted position, but could be placed near each other in the transformed position. I'm still undecided if I'll keep this artefact - it improves the dungeon aesthetic at a cost of requiring increased iterations to place rooms successfully.
As for moving to another placement method I've seen other coders use, such as binary subdivision, or even simulating playing Tetris, I want to keep compatibility with the original Angband code as much as possible, to keep this portable between variants.
A common variation is to allow collisions, so that it is possible for rooms to be placed on top of other rooms.
ReplyDeleteThis definitely results in a different dungeon design, so you can try to place it with the random approach, and if after say 5 iterations it has not been placed, just allow it to collide.
Of course, depending on how you're handling halls and how you're storing rooms, this may not be an option ;)
Nolithius: This only works if your room generation code only removes walls, and never adds them. Unfortunately, the Angband tunnel code requires walls drawn around every room, so it isn't feasible.
ReplyDeleteWhat if 2 collided rooms were merged into a single larger room? You could then draw walls around the enlarged outer perimeter.
ReplyDelete@Pikalek This is essentially what I was getting to, where the initial state of the level is all stone, and the rooms are carved, so that walls don't have to be explicitly drawn.
ReplyDeleteThis way, a room can be drawn entirely inside another room, or adjacent to it, essentially "expanding" the initial room.
I think you're right about O (and FA) dungeon generation - although it is one area I've left almost untouched. Which means I can't make any more intelligent comment...
ReplyDeleteIf my assumptions on the angband tile types are correct (never played), Cant you drop rooms over each other, drilling out space, and then line the appropriate dirt edges with walls when only when thats complete?
ReplyDeleteTo everyone who's suggest the overlapping rooms trick: the 'base' room type for Unangband is already two overlapping rectangles. And I explicitly describe positions of objects in the room as I place them using the room description code. So the suggestion won't work in this specific instance.
ReplyDeleteI can see where you're coming from though...