Find_space

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.