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 

Finished Red Dead Redemption

To be honest I never played the first game Red Dead Revolver. I was aware of it when it was released but for what ever reason it never made it to my gaming queue.

Since the game was developed by Rockstar it shares a lot of similarities with GTA but calling it GTA on a horse would be to a total disservice. Both games share similar game play elements but they are totally different games. I would almost say RDR  was a better game but it’s almost like comparing apples to oranges they are really different games. It would be completely possible to not like one game and like the other so if you didn’t like GTA I wouldn’t discount RDR. 

The plot is interesting and the ending is well... different. That’s about the best way to explain it. With out giving away any ending spoilers you basically play for another 1-2 hours after you would have expected it to end. The good thing about how the game ends it gives John Marston a truly “Western” ending and still allows you to play the game after you have finished it.

I don’t know if I enjoyed the game because there are so little “Wild West” games released and it was something different or it was truly a great game. I think its has more to do with the later.

Hopefully Rockstar will do another Red Dead game in the future. I would be up for a new story or even continuing where the game left off in the end.

Client Side Prediction with jME3 & Mina

Recently I have been researching various topics related to networking and games. I've always understood the basic fundamentals and have implemented lower level networking for non-game related applications but games are  different. You have to deal with latency and all the issues related to that. So I did some more detailed research into client side prediction and dead reckoning algorithms. Below is a test video of a server and 3 client instances. You may be thinking "but your running everything locally so there is no latency". It's true that local connections have almost no latency but the server is running at 8 FPS and the client is running at 60 FPS. Based off the clients last known information about the objects position, rotation, angular and linear velocity it makes a decent guess as to where the objects should be in the following frames before the sever sends another update.

The client and server are both using jME3 for the scenegraph and/or rendering and Mina for the low level NIO networking. If I ever have to write lower level code again to deal with selectors it will be too soon.

Secure Remote Password protocol

I was doing some research related to authentication and networked games and came across SRP. It seems to be the standard when developing a MMO for password authentication. Since Blizzard uses it for WoW (I would assume Battle.net as well) then that's got to say something. The user's password it sent to the server in the form of a one-way hash proof that is unique per session. This makes it useless for  hacker to try an play the packets back to replicate a session since it will be different every time. If both the client and server are in agreement you can also generate a unique session key to be used to encrypt/decrypt communications. There are several implementations out there if you are interested. I've written a simple implementation in Java that I'm going to use for my own projects. If there is enough interest I'll clean it up and release it.