   |
|
This is the explanation of how I made a level generator styled after old school "chunk" based mazes. While there are many different ways to approach map generation the reasons I chose to go with a "chunk" or "tile" design are twofold. I wanted to go with something easy to visualize and possibly work with down the road in a modular fashion, and I needed to go with something feasible to create with a couple weeks' time after work and little programming knowledge at the onset. This turned into a fun little project as well as a good crash course on Unity C#.
Any of the tiles could be replaced by more dynamic terrain in the future; the only part that matters at this point is the entry and exit points of each tile (North, South, East, West).
Moving around the grid to place tiles follows a spiral pattern:
Up, Right, Down, Left, Up... At a rate of 1, 1, 2, 2, 3, 3, 4, 4, 5... The reason I chose a spiral pattern is once again to generate a more organic structure. This centers the maze and generates outwards in a circular (or square...) fashion rather than simply scanning from side to side or up and down. Another option would be to select a random location and place a random tile (compensating for any adjacent tiles already placed). I decided against this though as I thought it would create too many "islands", which is an issue I tackled later on. Upon further thought I'm not sure this would be truly be an issue, though you would need to create a non-repeating list of coordinates to pull from so that your generator doesn't waste effort "looking" at the same tiles more than once. 
Actually placing a tile is pretty simple. If it's the center tile a random tile ID (1-16) is selected and placed. For every other tile adjacent tiles are identified as either 1 (I must be able to go there), or 0 (I must not go there). For tiles that have not been generated yet (ID = 0) a random 1 or 0 is chosen. These variables together (1-1-1-1, 1-1-0-1, etc.) identify the particular tile (N,S,E,W, N,S,_,W, etc.) that is to be placed.
It was at this point that I was able to create some prototype maps out of buttons and text in Unity:
Screenshots are actually from a later version that I had added some colors to for debugging start and end points.
The above screenshots illustrate two problems I ran into at this point:
1) The need for a "buffer ring" around the whole map 2) Multiple islands being generated, which caused me a lot of grief to solve. The buffer ring is the response to an oversight I had about the interaction between my non-generated tiles (ID-0) solution and tile placement. Once the generator reached an edge of the array it treated every tile "off the map" as a non-generated tile and would randomly select whether or not the maze could fall off the edge of the map or not. I went with the simple solution of growing the array by two and setting the outermost ring to be empty tiles (ID=16). So to generate a 3x3 map you'd actually need a 5x5 2d array (as seen above).
The issue of multiple islands was much more involved and required creating a few different debugging tools before I found all of the little insidious issues this caused.
The main issue with multiple islands being generated is that the player start and end locations may not be on the same island. Even if both locations were on the same island they would be placed on a piddly little 2 tile island far more often than I liked. While the occasional simple maze could be seen as a breather between giant mazes, it occurred often enough that I felt map size was a poor indicator of what the explorable area to a player would be. Two solutions to this came to mind; either scan through the map and bridge all the islands together, or scan through the map and isolate the largest island. In the end I chose the second option. Although bridging all the islands together would reliably create mazes that filled the map it didn't feel organic enough to me. A 5x5 map by that method will have about 25 tiles, and it will be shaped roughly like a square. The isolation method would give me more interesting maze shapes and a wider breadth of sizes, but the trade-off was a loss of efficiency generating junk islands that would end up thrown away. Before getting into how I chose to isolate the islands, here are a couple of examples of mazes that the isolation method generated: 
So, the way that the islands are isolated is by scanning through the map until a tile is found. Once a tile is identified it is given an island ID number and marked in two 2d arrays; one representing the island ID numbers, the other representing the "active" island we're identifying. Based on that tiles ID number (1-16 from placing tiles originally) we know what directions we need to fill. After filling N, S, E, or W with the island ID number we move to the left and repeat for each line of the map. After scanning through the map we blank out the "active island" array and scan again looking for any islands that exist on our main map array but not on our island ID array. After all islands are identified we have an array that could be visualized as the map to the right with colors representing the island ID numbers. Once we have an array with all islands marked by different ID numbers we can easily calculate the size of each island and flag which one to isolate and retain. One of the reasons I went very "visual" with my solution as opposed to something more abstract is because of the debugging power this gives me. I could output any of these arrays at any stage of the process to troubleshoot if needed. This is what saved me when I hit one of those terrible intermittent bugs.
At this point I was able to reliably generate maps on these UI buttons. I even moved forward and built the system to place the actual geometry for the map. But then sometimes, about 1% of the time, no map would be generated! The solution was simple, but I never would have found it if I hadn't built the ID array in a way that was easy to visually debug. On occasion the empty tiles themselves would be identified as the largest island, and all of the actual islands would be removed in favor of the empty island of nothing. Simply removing it from the hierarchy of island sizes solved the frustrating intermittent bug. And these are the examples of the map with all the geometry placed. Each tile is set up with simple collision and the character (simple capsule shape) is set to move with WASD around the map. I also set up a finish point that wipes the map, generates a new one, and randomly places the player and the next endpoint.
This is the point where I felt satisfied with my personal project. I made a maze generator that had the game loop set up to finish the maze and get another one generated, brushed up on some programming knowledge, and generally had a lot of fun pushing myself to problem solve technical problems. Next steps that I could do if I come back to this excersize: Set up actual terrain tiles. Set size limits to the generator so you don't get levels that are too small. Do something more nuanced with the spawn/end location rather than two random points that might be pretty close to eachother. Increase maze sizes the more mazes you complete. |
