Chris Johnson - Game Designer

Lessons Learned: Optimizing a Procedural Dungeon Generator in XNA


“Optimization” and “Accessibility” are two words that are, if nothing else, lingering in the depths of my mind when I’m writing code. I understand most of the basic steps that one must take to make sure their code is optimized, efficient, object-oriented, modular, and understandable by people other than myself and computers. But often times when rapidly making prototypes or proof-of-concept programs, I forsake such practices in order to save time. If I continue with the project, I’ll go back and fix the code later.

On my last assignment, however, I was required to revisit one of my earlier prototypes to do just that. It was interesting to sit down in front of a program and modify it for the sole purpose of cleaning it up. No addition of any new functionality, just a clean up to make the code more modular, more legible, and more efficient.

The program in question was a little thing that I wrote that procedurally generated a square tile-based dungeon map at runtime. In short, the program used an agent digger method that was left relatively stochastic in it’s behavior. The program could also load in maps that were stored externally as image files, and use the color info of individual pixels to determine asset placement. The reason I’m calling it a program and not a game is because all it did was generate a map, place the assets, build a minimap, and let you pan the camera around to look at it. There was no gameplay at this stage, more of just a study on procedural generation and tile-based maps. Still, it was very cool and I would like to use it for a game in the future. As such, I chose to clean it up for my assignment.

The switch from C++ to C# was a little rough for me in that on my first few projects, I didn’t break my code up into separate files or libraries. So that was the first problem to remedy. I decided to break the code into 2 files, one for the map generation, the other for the supporting UI/camera, which were nothing special. I threw the generation functions into a new class named DungeonGenerationManager, and went through the variables to make sure everything the program needed was either local or passed in via parameters. Next I needed to figure out exactly how one would implement it in a game. The information for each map was stored in a two-dimensional int array. I wanted to have the instance of DungeonGenerationManager itself store the map, instead of just returning it to the main program when created. However, while also trying to allow for reading in premade maps, this became very messy very fast. In the end, I chose to have four main functions in DungeonGenerationManager: loadMapFromTexture, generateBaseMap, generateAssetMap, and generateMiniMap (I hope those are self-explanatory). Each function would be called from main, would generate an int array containing the necessary info, and return the int array to main.

Another problem I encountered concerned itself with the order of execution of these functions. You see, generateBaseMap would be called first and return an int array. That same int array would be passed as a parameter to generateAssetMap which would use it to decide asset placement. But the generation of the base map is not instant. It’s fast enough to seem instant to the layman, but in computing terms it takes some time. So I encountered a problem where generateAssetMap would be called before generateBaseMap had returned it’s int array. As a result, generateAssetMap would be passed a null, empty int array, which it obviously did not like. I solved this by implementing an if statement to check if the needed int array was null, and only call generateAssetMap if the array was populated.

For easier readability, I did several basic steps. I read through my functions, and broke them up into more, smaller functions where necessary. For instance, the update function was split into updateMenu and updateGame functions, one for each game screen state. These functions each called other small functions to check input. The same was done to the draw function, and to several repetitive sections of the generation algorithm. I also improved much of my comments that explained how the program worked. I realized that there is a decent likelihood that I will share this with others, and I want them to be able to grasp how the procedural generation works.

Lastly, I turned to optimization. I’m unfamiliar to the techniques of advanced XNA or C# optimization, but I went through and did what I knew I could to to improve. I mentally walked through the logic of the code, and found ways to make unnecessary several variables, which is good. I changed any variable I could to a constant, knowing that they are handled differently and are generally better to use when a value will never be modified. What I couldn’t do that surprised me was declare inline functions. This was something available for use in C++ but largely absent from the programmer’s toolset in C#.

In the end, I think I improved the program pretty greatly from where it was beforehand. Not that it’s indicative of anything, but I started with 749 lines of code on one source file, and ended with 715 lines on two files, just to quantify my changes. More importantly, the code is understandable to others, and modular. My hope is that soon I can use my work here to implement the features of this program into one of my games.


Leave a Reply

Your email address will not be published. Required fields are marked *

Game Design Portfolio of Chris Johnson