Collision Detection & Response

Ah yes the area of game development that usually has a game programmer pulling his or her hair out at 3am. These days collision detection is usually handled by a 3rd party library like the ever popular Havoc or Bullet  physics. I was working on an XNA based project and needed some basic collision detection to move around a world of oriented bounding boxes where the player is a sphere. A few days of research and comming to a good understanding of the Separating Axis Theorem and I came up with a working demo shown at the bottom of the post.  

In my research I found the following links that I think may be useful to others
Separating Axis Theorem (SAT) Explanation
Simple Intersection Tests For Games
N Tutorial A - Collision Detection and Response
http://www.gamedev.net/community/forums/topic.asp?topic_id=346956
General Collision Detection for Games Using Ellipsoids  (Includes sliding algorithm)

Source from other projects
Bullet Physics
Oops! Framework
XNA Physics API (not in active development but worth a look)
JigLibX

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