GeePaw Hill is undertaking a dungeon sort of thing, in Kotlin, using a very interesting room allocation scheme. So I was thinking, what if …

Hill wants lots of rooms with interesting shapes, and very few long narrow hallways. He’s planning to set up some polyominos in interesting room shapes, and to til the entire dungeon area with those shapes. (We know that this is not always possible in the general case, but if you toss in a 1-omino it surely is. Anyway burn that bridge when we come to it.)

It is possible that I have been nerd-sniped by this idea, and I’ve been thinking about it, half-asleep, for an hour or so and I have a very vague idea for an alternate way to get interesting rooms with few long hallways, tiling the entire dungeon area, and it goes like this:

What if we pick an open cell, give it the next room number, and then add side-adjacent cells to it, randomly, for a while, and then declare that room done and start another? We will ultimately fill the space with rooms of various shapes.

Then, with a lot of hand-waving right now, we connect the rooms by selecting a wall that abuts a different room and put a door there. We can (somehow) find rooms that are not yet connected and connect them. We can (using some as yet uninvented scheme) detect separate “islands” and, since they must be adjacent to some other rooms, find places for doors to connect the islands.

I hope I haven’t done too much design above. Pretty sure that I haven’t. I can imagine several ways this could fail to work. They’ll all be interesting, which is all I ask.

My plan, such as it is, is to do this in Python, which fits my hand well, using pygame, which I have used before and can probably relearn. So my first few tasks include:, not in any particular order.

  1. Set up a new PyCharm project;
  2. Include source and test folders;
  3. Write a test using pytest to drag it in;
  4. Write some code, perhaps a tiny main program, to get pygame dragged in and working;
  5. Get around to allocating rooms.

As I wrote those lines I realized that I don’t really have to do the pygame bit early on. I’ll want it fairly early, because looking at the rooms will tell me things that writing tests will not. But I could, in principle, work a while without pygame. That said, bringing in a new library is a big enough deal that we might want to do it early on. Or I might be rationalizing.

And, item 6 might be to review my existing projects to see if there’s anything there worth studying or borrowing. Not that it’s last. The tasks could have names instead of numbers, which suggest priority or order or something. But let’s not invent a new software management scheme here. Let’s do the work.

I’ll record my PyCharm setup work here, because I always get it wrong and I’d like to have a record of what I’ve done. It might work, in which case I’d like to copy the scheme, and if it doesn’t work, I can look back and see what might have been better.

New Project
File / New Project. Pick Pure Python, include a git repo and a main program. The main program runs, printing “Hi, PyCharm” as advertised.
Project Structure
In Settings, Project Structure, we can define the project’s folders. I set up ‘src’ and ‘tst’ as source and test root, and mark the venv and idea folders as excluded. Now I think I should move the main.py to the src folder.

The main still runs inside PyCharm, so I haven’t broken anything too awful. Let’s commit: initial file structure. That offers me a lot of files that I don’t want to commit, in the idea folder. I thought we were excluding that. I try putting .idea/* into Exclude Files in the Project Structure. That has no effect. I think I do not know what Exclude does and will look that up later.

Leaving that for now, just committing the main. Let’s get a test file up in here.

Initial Test
Create file ‘test_dungeon’ under ‘tst’. import pytest at the top, which asks to install pytest. We allow it and then add a standard hookup test:
import pytest

class TestDungeon:
    def test_hookup(self):
        assert 2 + 1 == 4
Run Test
Right click ‘tst’ folder and it offers to run all the tests. Test fails, as expected:
FAILED                         [100%]
test_dungeon.py:4 (TestDungeon.test_hookup)
3 != 4

Expected :4
Actual   :3
<Click to see difference>

self = <test_dungeon.TestDungeon object at 0x104985a00>

    def test_hookup(self):
>       assert 2 + 1 == 4
E       assert (2 + 1) == 4

test_dungeon.py:5: AssertionError

By golly, that’s right. It’s two plus two that makes four!

Fix, Green, Commit
Commit: initial test in place

OK, I think we have a somewhat viable project structure, modulo all these files that I want to ignore but am not sure quite how to do it.

Adding /.idea/ to gitignore doesn’t seem to stop PyCharm showing those files. This is irritating me and surely you. Sorry.

Let’s do some damn work here, OK?

First Real Test

What object or objects should we start with? Good question. I suppose there will be a Dungeon class, containing Rooms, made up of Cells, which will be square areas of some standard size, arranged in rows and columns, making up a rectangular grid. (We might do a hex-based dungeon, more common for outdoor campaigns, but let’s not worry about that now. Probably won’t make much difference.) Cells, for now, will have x and y integer coordinates, from zero and up to whatever limit we assign. This should be more than enough to give us a place to stand and do something real.

I think we should consider the base structure of the dungeon, the rows and columns of cells, as somehow separate from the rooms. No, too much thinking. Let’s do a room as a list of cells, with the requirement that when we add a cell it must be adjacent to an existing cell, just to see if we can do it. We’ll work toward that:

    def test_dungeon_exists(self):
        dungeon = Dungeon()

class Dungeon:
    pass

Test. Green. Commit: very simple dungeon.

A Dungeon contains Rooms. Let’s have a Room class.

    def test_room_exists(self):
        room = Room()

class Room:
    pass

Test. Green. Commit. very simple room.

Add a room to a dungeon, find out how many rooms there are? Maybe that’s useful.

    def test_adding_rooms(self):
        dungeon = Dungeon()
        assert dungeon.number_of_rooms == 0
        room = Room()
        dungeon.add_room(room)
        assert dungeon.number_of_rooms == 1

This seems nearly useless, but I’m just trying to get enough code in place to give me a place to stand to do something useful.

PyCharm wants to help with these methods. Via a joint effort:

class Dungeon:
    def __init__(self):
        self.rooms = []

    @property
    def number_of_rooms(self):
        return len(self.rooms)

    def add_room(self, room):
        self.rooms.append(room)

I expect green. I get it. Commit: can add a room.

OK, swell. What now? Let’s give rooms the ability to grow. We’ll have some kind of a structure, basically a list of cells, and if the room is empty, it’ll pick a random cell and remove it from the structure. If it’s not empty, it will go through its existing cells, checking their neighbors in the structure, and if it finds one there, it will add that cell to itself, removing it from the structure.

We need a cell bank. We’ll just call it that for now until a better name comes to mind.

It needs to be convenient to use to find cells at (x,y). Let’s do a few tests for that thing.

    def test_cell_bank(self):
        bank = CellBank(10,10)
        assert bank.cell(3,4) is not None
        bank.take(3,4)
        assert bank.cell(3,4) is None

So if you ask for a cell and it is present, you get it (and it stays in the bank, at least for now). You can take it and after that it is not in the bank. I think inspect might be a better word than cell but it’ll do for now.

In the course of coding up CellBank, I change the test:

    def test_cell_bank(self):
        bank = CellBank(10, 10)
        assert bank.has_cell(3, 4) is True
        bank.take(3,4)
        assert bank.has_cell(3, 4) is False

And the class:

class CellBank:
    def __init__(self, max_x, max_y):
        self.cells = set()
        for x in range(max_x):
            for y in range(max_y):
                self.cells.add((x,y))

    def has_cell(self, x, y):
        return True if (x, y) in self.cells else False

    def take(self, x, y):
        self.cells.remove((x, y))

Green. Commit: initial CellBank.

I could use a break, and need to study up on what files should be ignored and how to do it, but we’re so close to being able to do something interesting.

The real code will be probabilistic in nature, I suspect. Some function will decide, randomly, that a room is not large enough and the room will decide, probably randomly, which of its cells to use as an expansion base, and so on. But we’ll code and test methods that unconditionally do the things, and then have other methods that call those randomly. That should help us avoid tests that may or may not do things. Maybe.

I think I’ll start in the middle of things. The initial cell selection for a room isn’t clear to me. So let’s assign a room its initial cell and then ask it to expand. We’ll set up various CellBank situations as tests. Something like this:

    def test_room_adds_cell(self):
        bank = CellBank(10, 10)
        room = Room()
        bank.take(5,5)
        room.add_cell(5,5)
        room.grow()
        assert room.has_cell(5,5)
        assert room.has_cell(4,5)
        assert bank.has_cell(4, 5) is False

I’m assuming that the room will somehow discover that it has 5,5 and will ask about the neighbors, starting with the one to its left. Make it so. That turns out to be doable:

class Room:
    def __init__(self):
        self.cells:list[tuple[int, int]] = []

    def add_cell(self, x, y):
        self.cells.append((x,y))

    def grow(self, bank):
        sx,sy = self.cells[0]
        for nx, ny in [(-1,0), (0,1), (1,0), (0,-1)]:
            check = (sx + nx, sy + ny)
            if bank.has_cell(*check):
                bank.take(*check)
                self.add_cell(*check)

    def has_cell(self, x, y):
        return (x,y) in self.cells

This has a bit too much assembly and disassembly of tuples, but that aside, we are green. It seems clear to me that, while this needs work to be really useful, our grow method will find all the cells that are available and adjacent to the initial cell we give it. It will not, however, add any cells to those, because we only search starting from our first cell element.

We can commit: initial grow capability.

I need a break and an iced chai. Let’s sum up.

Summary

I clearly need to better understand project setup in PyCharm. My excuse for not knowing such a simple thing is that I really only write small programs so that I can write about incremental development, refactoring, and the like, and I have no need to work with a team or even share the files with anyone else (although I do often put them up on GitHub.)

We now have three nearly trivial classes, CellBank, Dungeon, and Room. They mostly work with lists or sets of tuples. There’s every reason to believe that we should have classes of our own in there, covering or replacing those system classes. That will come: the code will start telling us that the base classes aren’t helping and we’ll do something about it.

What we have here, but have not actually tested fully, is a Room that can grow from


  X

To

  X  
 XXX 
  X

We’ll test that and do more next time. Now I need to go read up on best practices for setting up PyCharm projects. If you know the answer, feel free to let me know.