Designing Adventure (pt. 2)
Hey guys it’s Mark again.
We’re nearing the end of sprint 2 now, so that entails yet another blog post.
Good news, the BSP algorithm is finally operational. There were definitely quite a few rough spots but we powered through them well enough with assistance. Part of the algorithm needed tweaking as the rooms generated at first tended to the side of extreme proportions. Rooms would look like corridors or almost appear non-existant.
Michael Mateas here at UCSC is teaching a Game AI course that everyone on the team is taking, including myself. Part of the class involves us taking up a final project involving artificial intelligence in games. For our level generation team we’ve decided to do an extension of our current workload with a bit of help from some of the other guys. Chris, our engine guy, and Clement, an upstanding resident of the game lab are with us on this.
Long story short our group is planning on incorporating a third algorithm and doing work towards having multiple algorithms used within the same level. Rather than having a level purely generated using digging or BSP, we can instead have two or potentially three different algorithms operating in the same area. So an outdoor clearing could be a made with the digging algorithm connected to an indoor section made with the conventional BSP algorithm. We have plans on refactoring BSP code to operate in this context, seeing as it does a good job of dividing an area into reasonable chunks.
The third algorithm we haven’t really ironed out yet. My suggestion was using a pre-established maze generation algorithm then simply filling in dead ends to make it appear less sparse. Maze generation algorithms are easy to come by, the logic for filling in gaps is a little less defined. Alternatively Chris suggested we do something with particle systems that connected particles together to form a level. It bears similarity to a cellular automata building algorithm, but it sounds interesting nevertheless. I’m excited to see where it all goes.
-Mark “I really can’t find time for pictures” Zablan
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 