Friday, October 1, 2010

Procedural Content Generation

Usually when I'm doing any sort research related to game programming I have a tenancy to end up in a totally different area than what I started because something else sparks my interest. This happened while I was researching Android development. I found out that Unity 3D was going to support Android in the next 3.0 release.  This was a few weeks ago, Unity 3.0 was released this week but thats a different post entirely. Anyway, I've always played around with Unity in the past and it's a really good tool. If you don't want to mess with all the low level stuff like collision detection, rendering, and platform differences and want to focus on your game and not the technology then it's the tool for you. It got me thinking about all the work it takes to create content for an average game and procedural content generation game to mind. So, I stated think how cool it would be procedurally generate a dungeon for a player to navigate. I know it's been done before like many roguelikes that have been created before to more modern versions like Daggerfall, Diablo, and to an extent X-Com. The point is that I've never attempted to do it before.

There are a lot of dungeon generators on the internet that are mainly used for D&D or other P&P RPGs. The bad part is there is no source code for any of them. I did find a link describing the process used in roguelikes to generate dungeons and was able to get a copy of the source for Angband so that was a good start. I ended up deciding try and implement a cell based algorithm that's used in roguelikes   

It basically works like this
  1. Pick a cell size like 8x8 or 2x4
  2. Pick a map width and height and multiply each by the cell size and that will give you the total map size
  3. For each cell randomly decide to add a room that has a random width and height less than the size of the cell but greater than 1
  4. Loop through all the cells that have a room and find the closest cell with a room thats not already connected and add a corridor between  the rooms.
  5. Mark the room as connected 
  6. Repeat steps 4-5 until all the rooms are connected
 I currently store the map in a 2-dimensional enum array that marks a block as None, Wall, Room, or Corridor. This helps with adding doors in a later pass. 

Remember when I said Unity was a good tool to focus on the game and not the technology? This also makes it a VERY good prototyping tool. Here is a link to what I implemented in Unity. If you want to see a different dungeon just hit the refresh button to reload the plugin. 

Unity isn't actually generating the dungeons. It's hitting a servlet on the Google app server it's hosted on that returns generated dungeon data. The generator servlet outputs both binary and html that I used to visually debug the code.   

I may or may not continue working on generator but it was fun figuring out how to make it all work 

No comments:

Post a Comment