Finding a Better Path
Nothing deep here, I mean a path in the dungeon, not a way of life.
What we have …
A dungeon amounts to a connected collection of rooms. We have finessed the connection part by adding our squiggliest form of room to the mix until it winds up connected. Today we’ll start on a solution for paths between “suites” of rooms, where the paths are the kind of narrow long hallway deals one expects in places like this.
We have some pieces of a solution for this, and I think most of them will be helpful, at least as stepping stones on the way to a path forward. We’ll look at the code shortly but from memory: we have a nascent notion of “suite”, which today is just a simple set of rooms; we have a PathFinder object that can find a shortest simple path between two room cells; we have the ability to build a path map starting from any given cell (used in PathFinder). Probably there are other useful bits: we’ll try to notice them as we work.
What we want …
Rooms often are directly adjacent to other rooms, by intention or by accident. We call collections of adjacent rooms a “suite”, though there is no class Suite … yet. What we’re here to begin today is to find a closest pair of cells, one from each of two suites, and to draw a path between those two cells, thus connecting the two suites by what is likely to be a short path.
I say “likely”. Imagine that these two brackets are separate suites of rooms, separated by a third suite, the letter ‘g’.
[ g ]
There are two candidates for “closest pair” between the two brackets, the top inward bits and the bottom ones. Our algorithm—the one I plan to use—will only consider the manhattan distance between the two suites, so we might select the bottom pair, in which case the path will have to climb over the letter g. Because we like our dungeons to be “interesting”, I think this will be a feature, not a bug.
What we plan …
Our plan, as always, is tentative and incomplete. We discover good ways to do things, moving in the direction of what we want, changing both what we want and our moves toward it, as we learn things by our travels. I do have two steps pretty firmly in mind:
First, we’ll create a Suite class, so that our operations on a Suite will have somewhere to be. Right now a “suite” is just a set of rooms and has no useful behavior. I think we’ll want some useful suite-level behavior, including:
Second, we’ll provide code that, given two Suites, finds a pair of cells, one from each Suite, such that no other pair of cells is closer together than the pair we find. (There can be many pairs with the same distance.) We’ll use manhattan distance, because that’s the way we travel in the dungeon.
Third (I was mistaken about the “two”) we’ll probably look at and either reuse our existing pathing code, or adapt it to our needs.
Let’s get started …
We’ll review existing code as we work. I’m sure enough about the Suite idea to go ahead with it without a deeper look at the existing code. We have at least one test for suites:
def test_make_suite_lists(self):
space = CellSpace(10, 10)
dungeon = Dungeon()
o_0 = space.at(3,1)
r_0 = RoomMaker().cave(number_of_cells=1, origin=o_0, name='0')
dungeon.add_room(r_0)
o_1 = space.at(4,1)
r_1 = RoomMaker().cave(number_of_cells=1, origin=o_1, name='1')
dungeon.add_room(r_1)
o_2 = space.at(1,4)
r_2 = RoomMaker().cave(number_of_cells=1, origin=o_2, name='2')
dungeon.add_room(r_2)
o_3 = space.at(5,1)
r_3 = RoomMaker().cave(number_of_cells=1, origin=o_3, name='3')
dungeon.add_room(r_3)
o_4 = space.at(5,6)
r_4 = RoomMaker().cave(number_of_cells=1, origin=o_4, name='4')
dungeon.add_room(r_4)
o_5 = space.at(4,6)
r_5 = RoomMaker().cave(number_of_cells=1, origin=o_5, name='5')
dungeon.add_room(r_5)
suites = dungeon.define_suites()
assert len(suites) == 3
assert {r_0, r_1, r_3} in suites
assert {r_2} in suites
assert {r_4, r_5} in suites
That exercises this code:
def define_suites(self):
self.suites = []
unexplored = self.rooms.copy()
while unexplored:
suite = self.find_suite(unexplored[0])
self.suites.append(suite)
unexplored = [room for room in unexplored if room not in suite]
return self.suites
@staticmethod
def find_suite(room):
suite = set()
start = room.cells[0]
for cell in start.generate(lambda c: c.is_in_a_room):
suite.add(cell.room)
return suite
The find_suites method starts with a room cell, and generates the set of all the cells, starting there, that are in a room. That will essentially do a full search of the room, and all the adjacent rooms, but will not cross available space. Since it produces a set, the many duplicates are removed and we wind up with all the rooms accessible from the starting cell.
In define_suites, we start with all the rooms there are, take the first one, get all the rooms it attaches to, save those, and remove them from the list of unexplored rooms. Rinse, repeat, and we have some number of sets, each containing a number of rooms that are adjacent.
Our mission is to produce a Suite class to contain these sets, so that we can ask them suite-related questions. This is a speculative decision on my part: I think we’re gonna need it. Yes, I know that my advice on the topic is “you’re not gonna need it”, and that I generally don’t create a class until it’s really clear that we do need it.
It seems clear enough to me. By the end of this exercise, if not sooner, we’ll see if I’m mistaken1.
Let’s rename the define_suites method:
def define_suite_sets(self):
self.suite_sets = []
unexplored = self.rooms.copy()
while unexplored:
suite = self.find_suite(unexplored[0])
self.suite_sets.append(suite)
unexplored = [room for room in unexplored if room not in suite]
return self.suite_sets
I renamed the temp as well. Green. Commit: renaming as prep for Suite class.
Now let’s test-drive the Suite class into existence. Back to the test method, we’ll do a bit of renaming, and extend it:
Rename:
...
suite_sets = dungeon.define_suite_sets()
assert len(suite_sets) == 3
assert {r_0, r_1, r_3} in suite_sets
assert {r_2} in suite_sets
assert {r_4, r_5} in suite_sets
Commit. Extend:
suites = dungeon.define_suites()
assert len(suites) == 3
This is more than enough to fail. And enough to cause me to write this:
class Room:
def define_suites(self):
return [Suite(s) for s in self.define_suite_sets()]
class Suite:
def __init__(self, room_set):
self.room_set = room_set
We could extend the test to check the Suites for having the room sets but frankly I can see that they do, and if somehow that got broken, I’m sure that other tests would find it. We’ll commit, move the Suite to its own file, and commit again.
OK, breathe … settle … steady …
Right. Our next step was going to be finding closest pairs of cells between two suites. That still seems to make sense. I think we’d be wise to write at least one test for that. Let me sketch a picture:
Two suites, three tiny rooms each. Let’s write the test. First this much:
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
Now I’d like to ask for the closest cells between the two suites, and discover that we found ‘e’ and ‘a’, because, by design, they are the ones. Wishful thinking will get us there:
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
Now we need that find_closest_pair method. I think I can just code it, shall we try?
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]
We’ll just iterate all the cells against each other, a lovely little O(N2) operation, and return a pair with the shortest distance we find.
This would work if Suite understood cells as a generator for its cells.
I think I’ve got that but cells don’t know their room name so the test isn’t quite right. The correct test code is shown above but I actually had to fix it here. Here’s cells:
@property
def cells(self):
for room in self.room_set:
for cell in room.cells:
yield cell
The test is green. I almost don’t believe it myself, but along the way it failed in all the obvious ways. I’m pretty confident that we have what we wanted, so far.
I’m going to take a break: We’re only an hour and twenty minutes in, but this is a perfect point at which to commit and pause. Commit: Suite seems to be finding closest pairs correctly. I say “seems” because at this moment I’m not as confident as I might be. I’d bet $10 on it but not $10,000. We’ll see what to do about that next time.
Reflection
I freely grant that I had thought about how to do this yesterday and I had verified via the Internet that brute force is one of the accepted ways to solve the closest pair problem. Other solutions include partitioning the point sets into groups, and some exotic 3d tree structure thing that I stopped reading about after two sentences. Our rooms have around 100 cells, so our suites have less than a thousand, and what’s a million iterations among friends, right?
Even though Suite has only two methods so far, I think it is clearly bearing its weight, since the main entry method answers a rather difficult question: give me two points from yourself and this other suite such that there are no other two cells that are closer to each other.
Something to look at comes to mind: we have a nifty generator for the cells in a suite. I think we are just treating the cells of the room as a collection. Possibly we should have a generator for the cells in room? Note made.
Another thing, related: we can pass conditions to some of our iterators. That whole area might benefit from an injection of consistency. Note made.
And that brought to mind a design notion: A suite is a collection of rooms, which is a collection of cells. There is a pattern relating to this kind of thing: Composite. We might want to think about using that. It’s a pretty big hammer, so probably not, but it’s perhaps worth a look. Note made.
Perhaps later today, perhaps tomorrow, perhaps not until Monday, we’ll do the next thing, which I think will consist of setting up something in main so that we can look at it. Along the way we’ll probably add to PathFinder or perhaps just borrow some code from it to put it elsewhere.
But where? We surely want to draw a path between suites, while PathFinder draws between rooms (same thing nearly same thing?) There are some jaggy edges between the classes for our new purpose, so we’ll jostle things around and make them fit better.
All for next time. For now, a happy result. See you next time!
-
“I could be wrong, but I’m not.” – Eagles ↩