The fastest way ...

Starting the game seems too slow. How much? Why? Measure. Measure better. Think. Realize something. Plus: help from a new friend.

While you were away, I did a bit of experimentation. I added a check to PathFinder to see if it has encountered the target, and if it has to stop searching. The changes were few. Here are the changed parts of PathFinder now:

class PathFinder:
    def find_path(self, source: Cell, target: Cell) -> list[Cell]:
        self.put(source, None)
        self.flood(target) # new parameter
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = self.reached.get(start)
        return path

    def flood(self, target): # new parameter
        while len(self.queue) > 0:
            self.expand(target)

    def expand(self, target): # new parameter
        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)
            # new code to stop the search
            if neighbor == target:
                print(f'flushing {len(self.queue)} cells')
                self.queue = []
                return

The tests are all happy, so let’s commit that: pathfinder stops upon finding target.

Help from new friend @blackoverflow

I received a very kind email from @blackoverflow, covering a number of topics which I still need to absorb. They described some of the “AI” capabilities that are built into PyCharm, some of which run locally and are automatically enabled. That may possibly be contributing to the “intelligence” of some of its suggestions. I think I may have no objection to a small LLM or similar capability that runs on my own machine using my local files as source of information. I’m a bit concerned that this was turned on without my selecting the option.

Another area @blackoverflow mentioned was automatic testing, which was useful because I had entirely forgotten that PyCharm lets me click a button and have the tests run automatically, after any save and after any change followed by a delay. It pops up a little message saying whether tests passed or failed. I’m grateful for the reminder and have turned the feature on.

@blackoverflow also gave me some hints for setting up my gitignore properly, for which I’m also grateful. I’ll be reviewing all the letter’s ideas and will report here such things as I find worth mentioning.

And … this may be the first personal email I’ve ever received with comprehensive footnotes containing links to supporting articles. Well done @blackoverflow, thanks!

So now we are proceeding with tests auto-running. I can’t believe I forgot that feature. Something about having to program with Sublime for a month or so, where the tests run only when I ask them to.

Let’s do some rough timing. I’d like to have three numbers, the time to build a dungeon without paths, the time with a complete flood, and the time with my check for target. I can do that by turning on a test that starts main, and a bit of commenting in and out and arithmetic. The rough results are:

Hm. So it’s taking PyGame about 1.7 seconds to open the window and clear it, including drawing the grid. Adding rooms takes another 1.7 seconds, which is about 0.15 seconds per room. Optimized paths takes 1.4, saving 2.5 compared to the full flood. That’s about 0.12 seconds per path.

From that very rough set of figures, an improvement to a path generation or a room creation would have about the same impact on time.

Note

I had no intention of profiling. I wasn’t even sure what profiling PyCharm might have. But getting those simple figures has induced me to see if we can readily get a bit more detail. Turns out we can!

Profiling

PyCharm does have profiling built in. I decide to run profiling. I modified main so that it terminates before doing any drawing, that is, right after building all the rooms and paths.

This is honestly the first time I’ve ever looked at PyCharm profiling, so if you notice any mistakes of interpretation or have suggestions, do let me know.

The “Flame Graph” looks like this:

Hovering around in there tells me that about half the total setup time is in expand in PathFinder, 53% of total, with most of that time in can_use (44%).

The call tree shows that another 22ish percent is spent in building the rooms, most of it being consumed in find_adjacent_cell, with a whopping 8.8 percent of total time being spent in Cell equality comparisons.

There’s nothing too surprising there, although the time in __eq__ suggests to me that we may be able to improve things by using a set instead of a list for the cells in the room. We’d have to review the code for that. And certainly it will be helpful to remove all the non-peripheral cells from the search for a location that can be added to the room. That would essentially eliminate those cells from consideration at all, which is a larger savings than speeding up the comparison.

Still, one would suspect that there’s more improvement to be found in the path-finding code, if only because more total time is spent there, and we know that it’s doing repeated path creations.

Idea!?!?

One “interesting” idea comes to mind: what we really need is for all the rooms to be connected. Instead of drawing a connection between all pairs, as we do now, we could perhaps find a simpler approach that would take advantage of proximity and adjacency, if we permit it.

Often when code is too slow, the best solution isn’t to optimize it but to replace the algorithm with one that is better. And sometimes that can come down to finding a completely different approach that solves the problem differently.

Bad Idea!?!?

Let’s consider a bad idea, just to start the idea flow. Suppose we drew some paths first, basically random lines in the space, all criss-crossing so as to be fully connected. Then suppose we always select a cell on some path to build a room around. And, suppose we allow rooms to contain path cells (which they’d have to if we start with one). We’d wind up with fully connected rooms, and a lot of paths that lead nowhere. And path creation would be essentially free.

Hm. Maybe it’s not such a bad idea after all … don’t improve the path-finding code: eliminate it.

The fastest way to do something is not to do it at all.

Summary

I had thought that we might work on A* searching today or soon. Getting some facts, which I started doing just to give a basis for discussion, has led me to suspect that instead of optimizing the code, we could eliminate it and get the effect we need some other way.

Very interesting. Must consider this a bit.

See you next time!