Designing Adventure (pt 1)
So we have this blog now, and it is “encouraged” for us to all to record our individual progress (or not, details are kinda hazy in that regard) during the sprint. So here I am.
My first assumption is some introductions are in order. My name is Mark Ian Baluyot Zablan. But people just call me Mark, it’s too much work otherwise. I was part of the original Microventures prototype team back at the beginning of Fall Quarter, 2011 when Microventures was just a glimmer in James’ eye along with Zach Lindblad (now leading “Hello, World!”) and Lok Kei Lui (We let “Puzzle Defense” have her. That’s my story and I’m sticking to it.). And now the team is all here making sure his baby comes out in good health. I’ve been programming since high school and have for the most part survived UC Santa Cruz’s Computer Science curricula without too many bad memories.
I am working on the level generation for the Microventures team. The most striking thing is that procedural level generation isn’t some super-unique thing that everyone will laud you for in the years to come. For the most part it’s simply a matter of making sure the generated level isn’t impossible to finish or worse, isn’t fun. No layperson is going to recognize your crafty implementation of a digging algorithm or Eller’s Algorithm that you modified for a dungeon. Yet if this isn’t executed correctly, if the level somehow isn’t good, it could break the game and ruin the player’s experience. Ironically this lead to only Fletcher and myself being assigned to the project.
Now the part where I actually talk about work (I know how much people love walls of text. I’ll throw in some images later when I’m up for it). The majority of this was defined waaay back when during the greenlight phase. Simply put, the two algorithms we’re focusing on dungeon generation for now are a “digging” algorithm and a Binary Search Partition (BSP) dungeon generation. Fletcher is focusing most of his efforts currently on the Digging algorithm he had already written during prototyping whereas I am primarily writing our algorithm. In a sentence, BSP dungeon generation involves taking your play field and dividing sections of it into subsections, hollowing out areas in those subsections, and then connecting the hollowed sections together using corridors. What you get as a result is several clearly hollowed-out areas and adjoining rooms.
So far, the largest amount of progress I’ve had is being able to divide the area into subsections. This is pretty straightforward given how we’ve designed the structures. There is a BSP node class that uses a binary tree structure. The algorithm examines the current node and determines it’s size depending on how large the current.
<DISCLAIMER: Potentially boring technical stuff incoming>
Right now my concern is how efficient this algorithm runs. Microventures is planning on deployment on mobile phone platforms, so memory will be at a higher premium than if we had deployed to PC or other systems. Recursion tends to add a bunch of method calls to the stack and depending on our level size this will quickly become unwieldy. I did some experimentation to try and develop a tail recursion function for the partitioning section of the algorithm, but it is difficult since node creation relies on two method calls, one for each child node making it difficult to do both at the same time. To this end I contemplated performing a iterative operation to create the tree, but so I haven’t done iterative binary tree traversal/creation since high school and I’m a tad rusty. I’m hoping to test it out sometime next sprint, but I would prefer to get something operational and then optimize it. I would rather have something work then make it structurally as efficient as possible while constantly crashing. Preferably I would like it to run and be efficient, but you have to start somewhere. Level gen code won’t run for long, only at the start of a level, but the game is intended to be executed quickly. So for now I have my sights aimed on both getting BSP working and as a long-term goal investigate more memory efficient options.
That’s all I have for now. Hopefully I can make these posts a little more interesting next time or come up with a better name.
-Mark
MicroVentures 