Paths , Really!
OK, we made the change easier. Now can we do the change? Yes! Slow is smooth: smooth is fast.
Here’s PathFinder:
class PathFinder:
def __init__(self, bank):
self.bank = bank
self.queue: list[Cell] = []
self.reached: dict[Cell, Cell] = dict()
def find_path(self, source: Cell, target: Cell) -> list[Cell]:
self.put(source, None)
self.flood()
path = []
start = target
while start is not None:
path.append(start)
start = self.reached.get(start)
return path
def flood(self):
while len(self.queue) > 0:
self.expand()
def expand(self):
reached = self.reached
next_cell = self.queue.pop(0)
for neighbor in next_cell.neighbors:
if neighbor not in reached and neighbor in self.bank:
self.put(neighbor, next_cell)
def put(self, cell: Cell, former=None):
if not isinstance(cell, Cell):
raise TypeError
if former and not isinstance(former, Cell):
raise TypeError
self.queue.append(cell)
self.reached[cell] = former
Basically, flood starts from the source location, and floods the whole available space, recording for each cell, which cell was being expanded when the cell was reached. We could probably optimize things quite a bit by stopping the flood when we find the target. But no need for that yet.
If we were to start in a room with the code as it is, the neighboring cells would not be available and we would get an empty path. At least that’s what I think would happen. Let’s write a test that will run when we have this right.
def test_path_with_rooms(self):
bank = CellBank(100, 100)
size = 20
source = Cell(10,10)
target = Cell(90, 90)
source_room = Room(bank, size, source)
target_room = Room(bank, size, target)
finder = PathFinder(bank)
path = finder.find_path_between_rooms(source_room, target_room)
assert len(path) == 1 + source.manhattan_distance(target)
I think this should be approximately what we want. There is no such method … yet. Run the test to get the failure.
def find_path_between_rooms(self, source_room: Room, target_room: Room):
self.room_list = [source_room, target_room]
return self.find_path(source_room.origin, target_room.origin)
My thinking here is that we’ll have a list of rooms through which we are allowed to travel. Test should still fail, this time with a length of one:
> assert len(path) == 1 + source.manhattan_distance(target)
E assert 1 == (1 + 160)
So far so good. Now let’s see where we can check the candidate cells for being in one or the rooms or available.
def expand(self):
reached = self.reached
next_cell = self.queue.pop(0)
for neighbor in next_cell.neighbors:
if neighbor not in reached and neighbor in self.bank:
self.put(neighbor, next_cell)
Let’s extract that check for in to a new method and then expand the method:
First the extract gives us this:
def expand(self):
reached = self.reached
next_cell = self.queue.pop(0)
for neighbor in next_cell.neighbors:
if neighbor not in reached and self.can_use(neighbor):
self.put(neighbor, next_cell)
def can_use(self, neighbor) -> bool:
return neighbor in self.bank
Should still be failing the same way … and it is. Now …
def can_use(self, neighbor) -> bool:
if neighbor in self.bank:
return True
for room in self.room_list:
if neighbor in room:
return True
return False
I don’t know that Room understands in but if not we’ll make it do so. Test.
> if neighbor in room:
^^^^^^^^^^^^^^^^
E TypeError: argument of type 'Room' is not iterable
As I suspected. Easily fixed:
class Room:
def __init__(self, bank, size, origin):
self.origin = None
self.cells:list[Cell] = []
r = random.randint(0, 255)
g = random.randint(0, 255)
b = random.randint(0, 255)
self.color = pygame.Color(r, g, b)
print(self.color)
self._build(bank, size, origin)
def __iter__(self):
return iter(self.cells)
The good news is that the test runs. The bad news is that it seems quite slow. The tests are taking about four seconds to run. Of course our test is flooding 10,000 cells, but still that seems like a lot. However, we’re green. I’m rather sure this worked but let’s extend the test a bit:
assert len(path) == 1 + source.manhattan_distance(target)
assert path[0] == target
assert path[-1] == source
Green. Let’s change the test a bit to make it faster.
def test_path_with_rooms(self):
bank = CellBank(30, 30)
size = 5
source = Cell(10,10)
target = Cell(25, 25)
source_room = Room(bank, size, source)
target_room = Room(bank, size, target)
finder = PathFinder(bank)
path = finder.find_path_between_rooms(source_room, target_room)
assert len(path) == 1 + source.manhattan_distance(target)
assert path[0] == target
assert path[-1] == source
Green. Commit: PathFinder method with two acceptable rooms. Could be extended to more.
I feel the need to make a picture of this. Let’s change main. That requires a bit more than I’d like but not too much:
def main():
bank = CellBank(64, 56)
# random.seed(234)
dungeon = Dungeon()
number_of_rooms = random.randint(12, 12)
for _ in range(number_of_rooms):
size = random.randint(90, 90)
x, y = random_available_cell(bank)
origin = Cell(x, y)
room = Room(bank, size, origin)
dungeon.add_room(room)
for room_1, room_2 in zip(dungeon.rooms, dungeon.rooms[1:]):
dungeon.find_path_between_rooms(bank, room_1, room_2)
view = DungeonView(dungeon)
view.main_loop()
The new loop draws a path between consecutive pairs of rooms. Dungeon and DungeonView are changed slightly so that Dungeon saves a list of paths and DungeonView draws them:
class Dungeon:
def __init__(self):
self.rooms = []
self.paths = []
def find_path_between_rooms(self, bank, room_1, room_2):
finder = PathFinder(bank)
path = finder.find_path_between_rooms(room_1, room_2)
self.paths.append(path)
class DungeonView:
def main_loop(self):
running = True
moving = False
background = "gray33"
color = "darkblue"
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
self.screen.fill(background)
self.draw_grid(color)
self.draw_rooms()
self.draw_paths() # <===
self.clock.tick(60)
pygame.display.flip()
pygame.quit()
def draw_paths(self):
for path in self.dungeon.paths:
self.draw_path(path)
def draw_path(self, path):
for cell in path:
cx = cell.x*cell_size
cy = cell.y*cell_size
pygame.draw.rect(self.screen, 'black', [cx, cy, cell_size, cell_size])
And we get this result:
Summary
It’s clear that all the rooms are connected. Presumably we’d not display the paths inside the rooms, and we’d have doors or portals or openings where a path hits a room. But it is surely doing what I expected.
It is also very slow. It takes about six seconds to lay out and connect those dozen rooms, and most of that time is probably in the path-finding. It takes about 2 or 3 seconds to lay out the rooms with the paths turned off. So we could do some work on performance.
At a guess, we are probably filling four times more cells than we need to, on each find, because we don’t short-terminate upon finding the target. And we’re doing it twelve times. Unfortunately, since source and target are different for each find, there is probably no useful way to do it in one pass. Or, at least I do not know of a good way to do it. Deserves some research.
Allocating the rooms can probably be sped up by keeping track of cells interior to the room, since we select a random cell to grow from and most of the cells are interior and we search for another.
Both those seem to be reasonable things to work on. But for now, we have what we set out to have, paths between the rooms.
The process has gone rather smoothly, and I attribute most of that smoothness to having taken the time to make the code better before adding capability. This morning’s changes were particularly nice, moving in tiny steps mostly aided by the machine refactoring, with very little opportunity for mistakes, because I didn’t have to type much code.
Slow is smooth: smooth is fast.
See you next time!