Passages
Hello, loves!
I have a somewhat complex idea about passages, but a simpler scheme might work. Let’s find out. Anticlimax: I stop just before the thrilling conclusion.
Last night, in between time-wasting activities, I did a little thinking about passages. The main concern is to randomly choose, on each border between rooms, one passage. However, we’d like it to tend to choose areas in the border that are relatively complex, rather than in the straight bits.
So that got me thinking about weighted random choice, for which Python has support, so I sketched out a series of data structures that I thought I could get, leading to this scheme:
- Make a list of all the cells on both sides of the border. When a cell is found to have a neighbor in the other room, add both to the list. This will result in some cells occurring 1, 2, or 3 times.
- Using Python’s Counter, make a dictionary from cell to the count of times it occurs.
- Associate the desired weight with each possible count, perhaps 1:1, 2:10, 3:15.
- Use those weights in a weighted random choice, which Python also has, to select one cell.
- From that cell’s neighbors in the other room, select one.
- Make a passage between those two cells.
I’m sure that scheme could be improved by taking a bit of care with what the code remembered. Maybe the original structure would be a dictionary from cell to adjacent-room neighbors, for example.
But that’s a lot of mechanism to do in one go, and while it is certainly capable of being tuned, which is nice and could be useful, we might be able to get a satisfactory result more simply.
So this is this morning’s idea: Make that initial list and select randomly from it to get the cell on one side, and randomly select one of its neighbors in the other room.
Well, it was this morning’s idea. Thinking of making the initial structure be a dictionary from cell to neighbors … wouldn’t that give us a shorter scheme than the one above?
- Make a dictionary of all the cells on either side of the border, to a list of that cell’s neighbors in the other room.
- The lengths of those lists, possibly adjusted, are the weights we want. Choose based on those.
- From the list pointed to by that cell, choose the partner.
- Profit!
I think we’ll try that. It’d be nice to test-drive it somehow. And, if memory serves, which assumes facts not in evidence, we have a couple of border-related methods from the past few sessions, which we might scavenge from. There is also the very complicated Borders code, used to select the tiles for the dungeon floor. We’ll have to work on that a bit, but I don’t think we’ll try to find bits of it to use here.
What are those recent border things?
There’s this test, which builds two rooms [a][bc] and determines which cells are border:
def test_is_room_border(self):
layout = DungeonLayout(10, 10)
c_a = layout.at(3, 3)
c_b = layout.at(4, 3)
c_c = layout.at(5, 3)
room_a = Room([c_a], 'room_a')
layout.add_room(room_a)
room_bc = Room([c_b, c_c], 'room_bc')
layout.add_room(room_bc)
assert layout.is_room_border(c_a)
assert layout.is_room_border(c_b)
assert layout.is_room_border(c_c) is False
The operative code is:
class DungeonLayout:
def is_room_border(self, cell) -> bool:
room = self.get_room(cell)
return any((self.get_room(n, room)!=room for n in self.neighbors(cell)))
Find the room the cell is in, return True of any of its neighbors are in a different room. Note that the second, optional parameter to get_room is returned if the neighboring cell is not in a room. That addition made the predicate in the any simpler. Otherwise it would have to check for None as well as not equal to the original room.
The code to produce the dictionary we want would be similar to this. I would not try to write it as a comprehension, though after it’s done I might convert it. I do that because I can, and because I enjoy doing it, and because I think that facility with comprehensions has value. But I digress.
Reviewing commits, I find the commit message “new border_with method”. Let’s find that.
class Room:
def border_with(self, room):
result = set()
for my_cell in self:
for other_cell in room:
if my_cell.manhattan_distance(other_cell) == 1:
result.add(my_cell)
return result
There is a test for that:
def test_find_border_cells(self):
layout = DungeonLayout(64, 56)
maker = RoomMaker(layout)
origin = layout.at(20, 20)
diamond = maker.diamond(number_of_cells=13, origin=origin, name='diamond')
round = maker.round(radius=5, origin=origin, name='round')
layout.add_room(diamond)
layout.add_room(round)
border_cells = diamond.border_with(round)
assert len(border_cells) == 8
It’s interesting that these two methods use a different way of determining neighbors. I think I know why. The older one, border_with, assumes that a test for whether a cell is in a given room is slow, which it used to be, and the code using neighbors assumes that the test is fast, which it now is.
Neither of these methods is in use in the actual game. It might be nice to have them, but they have no reason to exist. We will face the difficult choice of whether to remove them soon. But for now, let’s TDD up the method we really want, if we can figure that out.
The Layout does not know which rooms are adjacent. Even when developing the suites during the phase where we make sure the dungeon is connected, we don’t really know which room leads to which. So, to get all the passages we need, we’re going to have to check each room against each other room, see if we get any border cells, and if we do, create a passage.
It occurs to me that this may not be entirely desirable from a game-play viewpoint, especially the way our path rooms work, wandering around until they find the room they’re looking for. Such a path might brush past several other rooms. We might not want to add all those possible passages. I think we’ll ignore this issue for now. Forget that I mentioned it.
OK. What do we want? We want, given two Rooms, a dictionary whose keys are every cell on the border between the two rooms, and whose values are a list of that cell’s neighbors on the other side. And we want a test for it.
I’ll resort to drawing a picture on one of my quad-ruled cards.
And this test:
def test_passage_dictionary(self):
layout = DungeonLayout(6,6)
r1 = [(1,1), (2,1), (3,1), (4,1),
(1,2), (2,2), (3,2), (4,2),
(3,3),]
r2 = [(1,3), (2,3), (4,3),
(1,4), (2, 4), (3,4), (4,4)]
r1_cells = [layout.at(*r) for r in r1]
r2_cells = [layout.at(*r) for r in r2]
room_1 = Room(r1_cells, 'room_1')
room_2 = Room(r2_cells, 'room_2')
layout.add_room(room_1)
layout.add_room(room_2)
b_d = layout.border_dictionary(room_1, room_2)
assert len(b_d) == 8
There are 8 border cells, some of them used more than once. We’ll extend the test, but this is enough to get us started:
def border_dictionary(self, room_1, room_2):
result = dict()
for cell_1 in room_1:
for cell_2 in room_2:
if cell_1.manhattan_distance(cell_2) == 1:
self.add_borders(cell_1, cell_2, result)
return result
def add_borders(self, cell_1, cell_2, result):
self.add_border(cell_1, cell_2, result)
self.add_border(cell_2, cell_1, result)
def add_border(self, cell_1, cell_2, result):
try:
cells = result[cell_1]
except KeyError:
cells = []
result[cell_1] = cells
cells.append(cell_2)
I swear I just typed that in and it worked … as soon as I remembered to add the new list to the result, in the penultimate line.
The test passes. I’ll print the result to see how to test it further.
Cell(1, 2): [Cell(1, 3)],
Cell(1, 3): [Cell(1, 2)],
Cell(4, 2): [Cell(4, 3)],
Cell(4, 3): [Cell(4, 2), Cell(3, 3)],
Cell(3, 3): [Cell(3, 4), Cell(4, 3), Cell(2, 3)],
Cell(3, 4): [Cell(3, 3)],
Cell(2, 3): [Cell(3, 3), Cell(2, 2)],
Cell(2, 2): [Cell(2, 3)]
By inspection, I can see that that’s correct. Let’s check at least one, the tricky one at 3,3:
def test_passage_dictionary(self):
layout = DungeonLayout(6,6)
r1 = [(1,1), (2,1), (3,1), (4,1),
(1,2), (2,2), (3,2), (4,2),
(3,3),]
r2 = [(1,3), (2,3), (4,3),
(1,4), (2, 4), (3,4), (4,4)]
r1_cells = [layout.at(*r) for r in r1]
r2_cells = [layout.at(*r) for r in r2]
room_1 = Room(r1_cells, 'room_1')
room_2 = Room(r2_cells, 'room_2')
layout.add_room(room_1)
layout.add_room(room_2)
b_d = layout.border_dictionary(room_1, room_2)
assert len(b_d) == 8
print(b_d)
entry_3_3 = b_d[layout.at(3,3)]
assert len(entry_3_3) == 3
assert layout.at(2,3) in entry_3_3
assert layout.at(3,4) in entry_3_3
assert layout.at(4,3) in entry_3_3
I think that’s a go. Commit: Layout has border_dictionary.
I want another test. When the rooms do not share a border, we’d like an empty result. I’m sure we’ll get that but let’s test it.
def test_border_dictionary_disjoint(self):
layout = DungeonLayout(6, 6)
r1 = Room([layout.at(2,2)])
r2 = Room([layout.at(3,3)])
b_d = layout.border_dictionary(r1, r2)
assert len(b_d) == 0
assert not b_d
Passes. Commit: testing disjoint rooms. We should rename that first test to test_border_dictionary.
Done. Commit.
What now? Well, we have yet to create a passage. We intend do do that randomly. As I look at the little map in the initial test, over time, I’d like to see more passages from C than from b or e, and more of those than from a.
Let’s generate some pairs and see what we get. I’ll extend that test … no, I’ll duplicate its setup and write a new test.
I think we’d like to flatten the dictionary and select from the result. Like this, perhaps:
flat = []
for k, v in b_d.items():
for k2 in v:
flat.append((k, k2))
counts = dict()
for cycle in range(10000):
k, v = random.choice(flat)
counts[k] = counts.get(k, 0) + 1
for k, v in counts.items():
print(k, v, v/10000*100)
assert False
Here’s the resulting report:
Cell(3, 4) 792 7.920000000000001
Cell(1, 3) 815 8.15
Cell(2, 3) 1619 16.189999999999998
Cell(3, 3) 2534 25.34
Cell(2, 2) 813 8.129999999999999
Cell(4, 3) 1692 16.919999999999998
Cell(1, 2) 874 8.74
Cell(4, 2) 861 8.61
So Cell(3,3), the hallway that juts up into the upper room, got 25% of the goodies, 3 times the share of the cells with just one partner, and 2x that of those with two partners. Just about as one would expect. I delete that test: I just wanted the visual verification.
I think we have two steps yet to take. One is to have the Layout create a random passage between every two adjacent rooms. The other is to have the passages visible enough in the dungeon view so that we can see what it’s really like in play.
Let’s do the display thing. We have a passage hand-crafted into the layout already:
main.py
...
dungeon.add_passage(Cell(32,30), Cell(33,30))
...
class Dungeon:
def add_passage(self, cell_1, cell_2):
self.passages[(cell_1, cell_2)] = True
self.passages[(cell_2, cell_1)] = True
I’m not at all convinced that passages belong in the dungeon rather than the layout, but we’ll not worry about that for now: they’ll surely have to be accessible anyway.
I think for an initial cut, we’ll just put a marker in each cell that is part of a passage. By way of a hack, Let’s see if we can make a kind of content and add that to the relevant cells. We create the content sprite list like this:
def setup(self):
self.setup_scroller()
self.setup_cameras()
self.room_sprite_list = arcade.SpriteList()
self.create_rooms(self.room_sprite_list)
self.create_content_lists()
def create_content_lists(self):
self.content_views = dict()
self.content_sprite_list = arcade.SpriteList()
for cell, content in self.dungeon.contents.items():
for item in content:
resources = item.resources
scale = item.scale
view = ContentView(item, resources, scale)
view.sprite.position = cell.center_position(cell_size)
self.content_views[item] = view
self.content_sprite_list.append(view.sprite)
No, that’s too much to mess with. How about explicitly drawing something in on_draw?
I bash this in:
class DungeonView:
def on_draw(self):
self.clear()
self.scroll_dungeon_camera()
with self.dungeon_camera.activate():
self.room_sprite_list.draw()
self.draw_contents()
self.draw_passages()
with self.scroller_camera.activate():
self.scroller.draw()
def draw_passages(self):
for c1, c2 in self.dungeon.passages:
cx, cy = c1.center_position(cell_size)
arcade.draw_circle_filled(cx, cy, cell_size //8, arcade.color.YELLOW)
So the plan is a small yellow circle in each passage origin. Recall that there are two passages, one in each direction. Anyway that gives us just what we wanted:
Anticlimax
Yes, I know, all that remains now is to use code like in the preceding test to create passages all over the dungeon, and yes, I know it’ll be simple. But the fact is, I’m tired and I don’t like to work tired. So I’ll have a little break. I’ll do the final bit, perhaps this afternoon, perhaps tomorrow, in a follow-up article.
Summary
We have a data structure that provides a reasonable-seeming distribution of passage locations. It was test driven and looks decent. If we want to change the weights, we’ll know where to look.
And we have a hacked-in indication of where passages are. We’ll see about some other ways of doing that as a separate bit of design and coding.
We have about 20 lines of nearly-production-ready code, and have identified a place where we might display passage hints, but probably won’t. But we could.
Less than 30 lines of code from a morning’s effort. Is that good, or is it bad? I don’t know, it just is. Doubtless I’d go faster had I not also written 350 lines of text. But I’m not here to go faster. I’m here to do what I do, at the pace I do it. If I had different needs, I’d go differently.
But hey: we have passage generation well in hand, and we can display them when we get them. That’s progress. I am satisfied with the morning.
See you next time!