One of the more interesting suggestions I got as feedback on my Ludum Dare 23 entry was to randomly generate the maze that the player must navigate. When I say “interesting” in this context, I really mean “wow that sounds pretty tricky to do but man that would be awesome.” This was one of the earlier comments that came in during the judging period, and I could see how it would definitely add a lot of replayability value to the game, so I went straight to work on attempting to add it.
The first thing I did was look at the entry for maze generation algorithms on wikipedia. The key takeaway I got from this was that this is a bit different than the roguelike dungeon generation I had been toying with earlier, and is really quite a bit simpler, is it there is no differentiation between rooms and corridors. It's just all corridors in a pure maze generator. The different algorithms that can be used basically boil down to some variation of depth-first search. I eventually decided on Prim's Algorithm, as it uses a standard iterative loop rather than recursion – less messy.
The hard part, of course, is making it work on a cube-wrapped 2D map in such a way that the sides all connect together seamlessly. To do this, I'm having to build a system to work with spatial coordinates of the form (face, x, y), where face is an index in the range [0,6] and x and y are within the range [0, size], size being the length of each edge of the cube. These face coordinates get mapped into a 2D array, where each (row, cell) combo maps to a specific location on the surface of the cube. To prevent the annoying situation of having an edge space on one side be open while the corresponding edge space on the next adjacent face of the cube be closed, all such edge spaces share the same (row, cell) location with each other. The corners of the cube are always occupied, as having to work with open corner spaces would be needlessly complicated and would not add much value to the mazes.
With the corner spaces not represented at all and the edges being special case rows in the array, we're left with the the inner (size-2)x(size-2) area of each face. Since the parts of the edges that are not corners are also (size-2) units long, this means that everything can be mapped to a 2D array that is (size-2) units wide. Since each face is (size-2) units high, and we always have 12 edges, we get 12+6*(size-2) rows in the array.
The mapping code to go from (row,cell) to (face,x,y) and back is a bit complicated. I created a suite of test cases using PICT-generated inputs, hand-calculated expected results from those inputs, and a small data-driven test harness class to check just this mapping, as it really comes down to a lot of if/else code that can be highly error-prone otherwise. Using the PICT-generated test cases snuffed out like 95% of the issues I had with this code directly through the test cases themselves, and got me close enough to the other 5% that they were easily visible as I was fixing the other errors in the code. This experience has led me to take a more TDD-esque approach wherever possible, particularly with this mapping code. I'm in the process of creating a distance function to find the surface distance between two points on the surface of the cube, and have created a similar set of test cases using PICT and manually-calculating the results on paper (and Excel).
The actual maze generation code got a bit messy at first. My initial implementation produced these odd-looking mazes that hardly ever would be completely navigable and were thus not very fun to move around, which was disappointing. I took another crack at this yesterday, refactoring the maze generation code using the 15 line rule and the Single Layer of Abstraction Principle (SLAP) into several short, concise functions, and made a little tiny change in what turned out to be the middle layer of abstraction in this former spaghetti mess, and was amazed to find the algorithm generating mazes similar to the ones pictured in the wikipedia article, only wrapped around the surface of the cube.
There's still a bit of work to be done before I can call it a game and release the thing. I'm still debating whether to go the simple find-the-end maze route where I pick an end point and have the player navigate there, or open up parts of the maze, populate with dots, and add enemies that chase the player around, or both. Either way would definitely involve the distance function I'm working on now as a key element.
No comments:
Post a Comment