A Bug!
Hello, loves!
No, a DEFECT, and a serious one. All hands on deck! Red Alert! OWOOGAH OWOOGAH!
We were going to do some design this morning, but because I wanted to show some random dungeon layouts, I turned on the code that places Dot as far from center as possible, and this is the result:
There is no outlet from that patch of dungeon. The dungeon is supposed to be fully connected. If we were ever to put Dot where she is now, she’d be unable to continue the game.
We will chase this down. It’s an important fatal flaw, and even though the game is not released and not playable, we need to fix this ASAP. Before I close this dungeon, I want to think a bit about what to do. I don’t think we can do much right now, but if there’s anything, I want to know.
-
Is there any displayed output in the console? There is not. We should probably add some printed diagnostics as we try to reproduce and fix this.
-
Reproduction will be difficult: this dungeon was created randomly. We can try setting the random seed and testing until we recreate the situation. That could take a long time, but we might be lucky, or this might be happening a lot.
-
PyCharm offers a stop button in the console. If I hit it, do I get a breakpoint, or does the program just stop. I’ll wait to find out until I’m sure I’m out of ideas. When I try it, it just stops.
-
We should create a keystroke command and put a breakpoint in the code for occasions like this.
-
Review the connection code before starting to debug.
-
Try to remember to debug with more than stepping. Tests can be very helpful.
-
Turn on full illumination to see everything.
-
Possibly create a mini-map, or rescale things to display the whole dungeon for easier inspection.
That’s all I’ve got right now.
First thing, I’m going to just run again and see if we get trapped again. It appears not.
Comment out the lines that make the dungeon invisible. Easily done. Let’s try making a breakpoint command.
def on_key_press(self, symbol: int, modifiers: int) -> bool | None:
if self.key_lock is not None:
return
self.key_lock = symbol
if symbol == arcade.key.RIGHT:
self.dungeon.move_player(Direction.EAST)
...
elif symbol == arcade.key.B:
pass
elif symbol == arcade.key.H:
self.make_initial_announcement()
...
I’ve set a breakpoint on the pass statement and it works. From there I can see the dungeon and layout so can at least check some forms of the state.
In the course of doing this, I’ve started the program half a dozen times and while I didn’t wander all the way to the center, things looked OK. That could be misleading, I suppose.
I really wish I could see the whole dungeon. I think that if we were cell_size smaller, we just get a smaller window with the same limits but maybe …
Yes, I can hack that.
That’s useful, but visually tracing all the paths to be sure there are passages isn’t really on.
I’m sure we have some ensure_connected method somewhere. Remember when I said we should review how it works? It’s time.
Yes, in main:
main.py
...
for _ in range(number_of_rooms):
make_a_cave_room(layout, maker)
make_experimental_room(layout, maker)
layout.ensure_connected()
layout.make_passages()
layout.make_borders()
# connectivity
def is_fully_connected(self):
suites = self.define_suites()
return len(suites) == 1
def ensure_connected(self):
count = 0
while not self.is_fully_connected() and count < 10:
count += 1
self._make_path_rooms()
Well, would you look at that? I remember, vaguely, that this used to loop forever once in a while. Let’s add a message, and we can also set a breakpoint there.
- Note to Self
- If we drop out of that loop, we can drop all but one suite and the remainder is fully connected. Bit of a hack but would probably work.
However … now that we’re here, how can a disjoint dungeon happen? Maybe we can create a test if we figure it out. Let’s read on:
def _make_path_rooms(self):
suites = self.define_suites()
# self.check_intersection(suites) # debug method
for s1, s2 in zip(suites, suites[1:]):
cells = s1.find_path_cells(s2)
if cells:
room = Room(cells, 'path')
self.add_room(room)
# cells can be empty if no path is possible
# because we only accept source room,
# target room, or available cells.
# SuiteMaker class?
def define_suites(self):
suites: list[Suite] = []
unexplored = self.rooms.copy()
while unexplored:
suite: Suite = self.find_suite(unexplored[0])
suites.append(suite)
unexplored = [room for room in unexplored if room not in suite.room_set]
return suites
def find_suite(self, room) -> Suite:
suite_rooms: set[Room] = set()
start = room.cells[0]
for cell, _ in Flooder(layout=self, origin=start).in_any_room().flood():
suite_rooms.add(self.get_room(cell))
return Suite(self, suite_rooms)
def find_path(self, source, target, room_list):
def can_use(cell):
return self.is_available(cell) or self.get_room(cell) in room_list
reached = self.path_map(source, can_use, 1.0)
path = []
start = target
while start is not None:
path.append(start)
start = reached.get(start)
return path
class Suite:
def find_path_cells(self, suite) -> list[Cell]:
source, target = self.find_closest_pair(suite)
rooms = [self.layout.get_room(source), self.layout.get_room(target)]
cells = self.layout.find_path(source, target, rooms)
on_path = cells[1:-1]
return on_path
def find_closest_pair(self, suite) -> list[Cell]:
my_best = None
his_best = None
distance = 1_000_000
for mine in self.cells:
for his in suite.cells:
dist = mine.manhattan_distance(his)
if dist < distance:
my_best = mine
his_best = his
distance = dist
return [my_best, his_best]
This is a lot to take in but here’s what’s going on.
A Suite is a collection of rooms that have adjacent cells. That’s what ‘connected’ means. If we start from some room and find all the connected rooms, and we get all the rooms, the dungeon is fully connected. If we don’t get all the rooms, we make another Suite. We connect two Suites by finding the cells that are closest to each other, and connecting them with a path.
I think we can be comfortable with the assumptions that if we get all the rooms in one suite, counting the various paths we’ve created, our partition logic will open passages between all the combinations and we’ll be OK. (This assumption could be false, but we’ll assume it’s true until we see evidence otherwise.)
The most likely assumption is that the loop ensuring connection dropped out. So let’s instrument that and see if we can make the problem happen.
I have set up main to loop its creation code until the Dungeon is NOT connected and then to run, which should show us a picture of what happens. I tried running under debug but it’s too slow.
What I should have done is iterate the seed, so that I’d have a reproducible situation. I’ll stop it and do that.
So far it has run about 800 times without failing. I’m not surprised, though I have no real reason to think the case is rare, since I don’t explore the map every time I run the game.
I’ve restarted it. It’ll stop with a print and with the map up … and it does!
We can see a small disconnected area at top right and the whole leftmost section is disconnected from the central section.
Here’s the print:
915 915
could not connect
Suite (13)
Room(cave: 4456545840),Room(unknown: 4456545360),Room(unknown: 4363362928),Room(cave: 4456545408),Room(diamond: 4425492112),Room(unknown: 4456545456),Room(round: 4456545984),Room(path: 4456542960),Room(cave: 4429201136),Room(diamond: 4429599504),Room(path: 4456543008),Room(unknown: 4456545216),Room(round: 4456546272)
Suite (1)
Room(cave: 4429373584)
Suite (2)
Room(unknown: 4456545696),Room(unknown: 4456545744)
Suite (7)
Room(cave: 4363370176),Room(cave: 4456545504),Room(cave: 4456545552),Room(cave: 4456545600),Room(path: 4456543056),Room(unknown: 4456545648),Room(unknown: 4456545264)
Hm it reports four suites. Ah, yes, lower left there is a lone room.
Note that the two central suites span the full height of the space.
We try to connect Suite 0 to 1, 1 to 2, 2 to 3 with this code:
def _make_path_rooms(self):
suites = self.define_suites()
# self.check_intersection(suites) # debug method
for s1, s2 in zip(suites, suites[1:]):
cells = s1.find_path_cells(s2)
if cells:
room = Room(cells, 'path')
self.add_room(room)
Let’s verify that:
def test_zip(self):
things = [ 0, 1, 2, 3]
pairs = []
for f,t in zip(things, things[1:]):
pairs.append((f,t))
assert pairs == [(0,1), (1,2), (2,3)]
And from the size of the Suite, we can see that they are numbered, from left to right, 1->3->0->2. Like this:
And sure enough, with that layout, 0 can’t reach 1, 1 can’t reach 2, 2 can’t reach 3, and the dungeon cannot be connected with the code we have.
I think that if we had gone ahead and tried 3->0, we would have connected. We’ll defer that until later, as we have isolated the defect, understand what is happening, and need a break. So let’s sum up.
Summary
The morning was disrupted by a critical all-hands defect. We thought a bit, worked out how to get a breakpoint if we need one.
Then we checked the code that was responsible for ensuring connection, and observed that it could conceivably not work. Added a few prints … and then modified our main program to loop until it created a disconnected dungeon.
Having found that, a couple more print improvements showed us just what is going on. We even have a theory about a fix.
The best part of this is that while now we have a built-in command to cause a breakpoint (if we’re running in debug, but that could become a habit), we never really did any debugging with the debugger. Too often, working in the debugger leads to stepping the code, saying DAMMIT WENT TOO FAR, starting over, stepping … and not thinking enough. No? Only me? OK.
Anyway, the good moves were to
- hack the display to show the whole dungeon,
- loop creating dungeons on known seeds until one failed, and
- printing useful information from the failure.
That let us see exactly what situation can cause the problem. From there to a fix should be straightforward. I suspect that adding 3->0 into the mix will resolve it. We’ll find out.
Next time. This time is now chai time. Cancel red alert. See you next time!