Following the Path
Let’s finish up the path between suites and see what it looks like. I suspect we’ll want to try to tune it.
Yesterday this test ran green:
def test_find_closest(self):
space = CellSpace(10, 10)
dungeon = Dungeon()
maker = RoomMaker()
a = maker.cave(number_of_cells=1, origin=space.at(1,1), name='a')
b = maker.cave(number_of_cells=1, origin=space.at(1,0), name='b')
c = maker.cave(number_of_cells=1, origin=space.at(0,1), name='c')
d = maker.cave(number_of_cells=1, origin=space.at(5,4), name='d')
e = maker.cave(number_of_cells=1, origin=space.at(4,3), name='e')
f = maker.cave(number_of_cells=1, origin=space.at(5,3), name='f')
dungeon.add_room(a)
dungeon.add_room(b)
dungeon.add_room(c)
dungeon.add_room(d)
dungeon.add_room(e)
dungeon.add_room(f)
suites = dungeon.define_suites()
assert len(suites) == 2
cell_pair = suites[0].find_closest_pair(suites[1])
names = [cell.room.name for cell in cell_pair]
assert 'a' in names
assert 'e' in names
This assures us that our find_closest_pair method finds a pair of cells, one from each suite, such that no other pair is closer together than the one found. (There could be other equally close pairs.)
We already have a PathFinder object, including this method:
class PathFinder:
def find_path(self, source: Cell, target: Cell, room_list) -> list[Cell]:
def can_use(cell):
return cell.is_available or cell.room in room_list
reached = source.path_map(can_use)
path = []
start = target
while start is not None:
path.append(start)
start = reached.get(start)
return path
I think that what we’ll work toward is to use that code to find paths between suites. Presently Suite:
class Suite:
def __init__(self, room_set):
self.room_set = room_set
def find_closest_pair(self, suite):
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]
@property
def cells(self):
for room in self.room_set:
for cell in room.cells:
yield cell
Let’s decide, at least for now, that a path is just another kind of Room, since a Room is just a moderately clever collection of cells. And let’s just extend the find_closest test a bit. You could make a case that we should write another test but I think this will be OK.
No. I’ll copy the setup, at least for now, and proceed from there. Seems more nearly right. I’m glad you were watching: keeps me from cheating.
def test_path_between_suites(self):
space = CellSpace(10, 10)
dungeon = Dungeon()
maker = RoomMaker()
a_cell = space.at(1, 1)
a = maker.cave(number_of_cells=1, origin=a_cell, name='a')
b = maker.cave(number_of_cells=1, origin=space.at(1,0), name='b')
c = maker.cave(number_of_cells=1, origin=space.at(0,1), name='c')
d = maker.cave(number_of_cells=1, origin=space.at(5,4), name='d')
e_cell = space.at(4, 3)
e = maker.cave(number_of_cells=1, origin=e_cell, name='e')
f = maker.cave(number_of_cells=1, origin=space.at(5,3), name='f')
dungeon.add_room(a)
dungeon.add_room(b)
dungeon.add_room(c)
dungeon.add_room(d)
dungeon.add_room(e)
dungeon.add_room(f)
suites = dungeon.define_suites()
path = suites[0].find_path(suites[1])
assert len(path.cells) == a_cell.manhattan_distance(e_cell) - 1
The path will include the cells between the two closest cells. Those belong to the suites. So we’ll have one less cell than the distance between them. At least that’s the way I figure it.
We need find_path on Suite. I get it nearly right. Originally the test above was checking the distance between a_cell and a_cell: PyCharm filled that in and I accepted it. Imagine how much trouble I’d be in if I was allowing the “AI” to run. And I initially got the slice wrong in this code:
class Suite:
def find_path(self, suite):
source, target = self.find_closest_pair(suite)
finder = PathFinder()
cells = finder.find_path(source, target, [source.room, target.room])
on_path = cells[1:-1]
room = Room(on_path, on_path[0], 'path')
return room
I think this is good. Commit: Suite.find_path Now let’s use it in main for the visual test.
def main():
space = CellSpace(64, 56)
# random.seed(234)
dungeon = Dungeon()
maker = RoomMaker()
make_diamond_in_round_room(dungeon, maker, space)
number_of_rooms = random.randint(2,2)
for _ in range(number_of_rooms):
make_a_diamond_room(dungeon, maker, space)
make_a_round_room(dungeon, maker, space)
suites = dungeon.define_suites()
for s1, s2 in zip(suites, suites[1:]):
path = s1.find_path(s2)
dungeon.add_room(path)
view = DungeonView(dungeon)
view.main_loop()
We just draw a few rooms and then connect 1 to 2, 2 to 3, etc. And it works, though there is an oddity and an artistic objection to be had. I’m not sure if the oddity is an error or not:
The artistic objection is that the paths are very straight, and I would prefer more turns where possible, such as in the path from top left to the center, which could have a few bends in it without being any longer. I think we may be able to improve that by randomizing the order of checking neighbors in the pathfinding.
The oddity though, is the path from the top center round room to the bottom center round room. It travels inside the room, which the code does allow but which I do not like. If the center round/diamond room were not there, I think the path would not have done that but instead would heave headed right down. But when I look at the points chosen, they don’t look to me to be the closest pair between those two round rooms.
I look at some more examples and when I see this one, I twig to the issue:
What is happening is that the paths are drawn sequentially. We choose “closest” points to be closest manhattan distance, not the shortest possible path given the existing rooms and paths. So between those two rooms, heading straight up seemed like the best thing to do, but then when it came time to find an actual path, we had to go way around.
I remain a bit concerned, but I can’t see offhand how that “closest pair” code could be wrong. (That means I can’t see it, not that it isn’t wrong: it could be. I don’t think it is, but it could be.)
We could allow paths to cross with a bit of fiddling on the acceptance conditions. Let me try something quick and dirty.
I hammered this into main:
suites = dungeon.define_suites()
allowed = []
for s1, s2 in zip(suites, suites[1:]):
path = s1.find_path(s2, allowed)
allowed.append(path)
dungeon.add_room(path)
When we get a path room back we add it to the list allowed. And in Suite:
class Suite:
def find_path(self, suite, allowed=None):
source, target = self.find_closest_pair(suite)
finder = PathFinder()
accept = [source.room, target.room]
accept.extend(allowed or [])
cells = finder.find_path(source, target, accept)
on_path = cells[1:-1]
room = Room(on_path, on_path[0], 'path')
return room
We add those rooms to the acceptance list. This won’t really work, I’m pretty sure, because a cell can only belong to one room, so the crossings will break the other paths. We could fix that in a number of ways, including making the paths all one big disconnected room. I think I’ll back that code out for now.
Here’s an interesting map that came out as a final check to be sure I had removed the hack. It looks to me like if we started the adventurers in the lower left, they’d have a long linear slog until they meet the boss in the central diamond. I like it.
I think we’ll commit what we have here, since I’m confident that it’s working as intended and we’ll look next time to see what refactoring or other improvements are needed. I’m sure there will be some, especially if we want to allow paths to cross each other.
Summary
All went well. PyCharm prompted me with a proposed line and I accepted it mistakenly. I made my own mistake with a slice on the path cells, and I think that slice is pretty iffy anyway. We would do better to move the removal of the room cells over to the path creation code, I suspect.
We’ll see in due time. For this morning, good progress. See you next time!