The curious case of the LeetCode problem that was useful in the real world
Who knew all that coding interview prep would be useful?
Something very weird happened today with which I am only just starting to come to terms. A coding challenge question from LeetCode (which I have received in real interviews) turned out to be useful and in fact was just what I needed for the next step in my procedural content generation system. Who knew that all that time spent practicing dynamic programming and graph traversal would come in handy at some point?
If you recall, in the previous article we coded up a simple system, called the cellular automaton, for generating “organic-looking” maps, such as for a rocky cavern or an archipelago. We left off the discussion having produced output like this,
where the white space represents an open cave floor or, alternatively, the land mass of an island, and the black space represents solid rock or ocean.
To go from this to something useful in an actual rogue-like dungeon crawler, however, we need to apply additional constraints. In this article and the subsequent ones, we’ll look at algorithms for:
removing smaller rooms;
combining larger rooms; and,
tracing an outline of the resulting single connected space.
The dungeon map will “make sense” in that the player will be able to get from anywhere to anywhere else and we’ll know where to place the walls. Optionally, we’ll also implement the functionality to remove small enclosed areas of rock. I think they add interest to the map, but it’s nice to have the option.
⛵️ Navigating the islands
The challenging initial step to applying our constraints is to determine the connected components, or “islands”, in our map. But wait, I’ve seen this before as a LeetCode problem! One solution to calculate the connected components is as follow:
Initialize an array to store whether each cell has been visited by the algorithm.
Loop over map cells.
When we encounter a cell we haven’t visited, we start a breadth- (or depth-) first search for connected cells, that is, neighboring cells that have the same value.
After the algorithm has terminated, we have an array of “islands,” their cell locations and values.
Here is the gist of the algorithm in Python, using the same CellularAutomaton class as the previous article:
This code could use some tidying up and making object-oriented, but I’ll leave that for another day.
You can see a visualization in the video at the begining of the article.
→ What’s Next?
In the next article, we’ll use this information on the connected components to remove smaller components and join larger ones. Also, we’ll determine the boundary of the single large room so we know where to place wall (or coast) tiles in Unity.