It's a Trap!

Traps are essential for 2D games. They present a challenge for a player that can only be defeated by timing and patience, rather than reliance on gunpower.

I decided to build 3 different types of traps for Platform Hack. Moving Blocks, Spinning Blades, and Flame Turrets. Each of these uses slightly different technology to work, but since they were similar enough I crammed all the functionality into a single class, called Trap.



The Moving Block is the simplest type. Its basically just a moving tile that hurts the player on collision. Some games have blocks that "crush" the player, and can also provide solid collision from the other directions (top, sides). I decided against this type of falling block, since it would require implement a "crushing" system of player damage. Instead, if you touch the block from any direction, the player will be damaged. Good level design (encasing the falling block inside Impassible tiles) can be used in conjunction with the trap type to good effect.

The Collision is pretty simple:



The Update function contains the only interesting piece of logic, using Linear Interpolation to smoothly move up and then slam down as a funtion of the entire TrapTimer



The Spinning Blade is the next type of trap.

This uses slightly more advanced collision and update logic. Given the same TrapTimer, we do a full rotation of both the texture, and the Rotation Matrix thats use for pixel-based collision detection:

Update:



Collision:





Draw:



One of the "gotchas" of Translation matrices in XNA (or I guess any graphics framework), is being sure to multiple by a translation of the negative origin. Matrix.CreateTranslation(new Vector3(-p.Origin, 0.0f)) This is needed whenever the texture is rendered using an origin. You need to adjust the Translation Matrix in the same way, so that the collision detection is "synched" with the drawn texture.

The collision detection with rotation is right out of the XNA tutorial found here

Lastly, the most complex type of trap is the Flame Turret.

The Flame Turret is using both Beam collision and the particle system for effect.

Beam Collision:

The benefit of using beam collision is if you have something like bullets that travel quickly. If the bullet moves 30 pixels in a single update, is has the chance to pass right through an enemy without causing collision. a Beam object can be used to represent a "line segment" in order to do collision. Of course, you can always Draw the single dot as the bullet, it just uses the Beam object to do the collision.

Here's my Beam struct:



There are two vectors, A and B. There is also a list of coordinates between the beams, which can be calculated with the following method. Note: this may not be an optimal method, comments welcome.



A beam can represent either a bullet moving quickly across the screen, or a burst of flame shooting out of a trap turret.

We can determine if the beam hits a player (or enemy) using the following collision detection method (again, possibly not optimal):



The last piece of the puzzle is a method to get a bounding rectangle around the beam. You *always* need to do bounding rectangle collision before pixel-based collision.



We can check for collision between the player and the beam in the following way:



Finally, we want our Flame Turret to look cool. This can be done using Particle Effects.

The particle engine I've used is heavily modified from the Particle Sample. The details are a topic for another post.

But briefly, we spawn fire particles along the length of the beam:



That's pretty much it for simple traps. With good art and creative level design, you can turn these three features into some pretty dastardly challenges for the player.

Web 2.0 Stuff

My game - Zombie Bash - is currently in Playtest for XBox Live Indie Games: http://forums.create.msdn.com/forums/t/78185.aspx

Also, I caved and created a twitter account.  I figure its really the only way to spread the news about the games I'm building outside the small group of people I know in RL who would care ;)

Follow me at @daydalus!

Our Hero!

We have the first test sprites of our hero in action!

Optimization!

I finally got around to purchasing the Creators Club Membership.

The main benefit is I can deploy the games I make to XBox 360, and after Peer Review, have them show up on the XBox Live Indie Games channel.

The set-up and deployment process was pretty painless, but once I loaded up Zombie Bash, I noticed something bad.

The game was incredibly slow! I'd be surprised if I was getting 1 frame per second, especially when the level first started and a bunch of enemies spawned.

The game ran fine on the computer, but the XBox has much weaker hardware. Also, the way XBox environment works under the hood (like disk IO) is different as well.

After doing some research and reading the forums, I came away with some suggestions to try:

1. Run the Xbox Remote Performance Monitor when the game is running on Xbox.
This is provided with the XNA Game Studio under Tools. I was able to get it up and running and look at some of the results in real-time. Unfortunately, the specifics that are profiled were a bit too low level to be of much help. I could tell that the Garbage Collection on the XBox wasn't keeping up with all the objects I was spawning, but why?

2. Run a .NET CLR profiler as you run the game on the computer.
I was able to download the Open Source tool SlimTune and configure it to profile my game. This turned out to be a lot of help. SlimTune actually attached to the CLR and uses Reflection to determine which methods are using the most processing time. This quickly points out the functions and calls that are slowing down the game. (Note: This program can often crash when testing XNA games, however it will still save the profiling to a file).

Which leads us to point number 3 -

3. Look for instances in the code where expensive operations are being done in real-time.
The number one difference between programming games and regular business apps - the same game code runs dozens (hopefully 60+) times a second. If there are any expensive operation in any of the loops, even if they occur once or twice (aka - loading assets), they can slow the entire thing down and lead to a bad gaming experience.

This was the culprit. Every time a new Enemy spawned, I was loading all its sprite textures from disk. This had been fine in the sample code, because the enemies were spawned once when the level was loaded. But Zombie Bash has Enemy Spawners, and dozens of enemies can pop out every few seconds. While the computer can easily handle that kind of disk IO, the XBox was choking.

There were a few other objects (weapons, particles) where the same thing was being done - realtime loading of texture assets into the newly instantiated object.

What I did was create a Loader class that is run once when the game first starts. This goes through and reads all the textures, and also calculates the required bounding boxes and Color arrays needed for collision. It then holds on to them in memory for whatever object needs them down the line (Enemies, Weapons, etc). It remains to be seen if this will lead to issues if the game gets sufficiently large (hundreds of enemies, etc)

Load them (textures and animations) once and save them for later!



A similar approach was taken for the particle system. Each individual particle was calculating its own Sin and Cos curves when initialized in order to follow curved paths. By moving those calculations to the parent class, and simply passing in a pre-initialized Curve object to each individual particle, the particle system was greatly improved!

This is incredibly expensive to do 50 times at once!



To sum up:

-The XBox is much weaker than a computer
-Make sure you don't load or calculate anything expensive during the game loop. Do it before!

For the Love Of...

Great write-up on the appeal of Rogue-likes: http://www.gearfuse.com/unevenly-distributed-how-i-learned-to-stop-worrying-and-love-the/

Mini-Maps

For games with complex level design, mini-maps are essential. Especially in games like Super Metroid where the focus of the gameplay is more on backtracking and using your new abilities than pure exploration, the many map is very important tool.

For Platform Hack, I'm planning on two different "mini" maps. One map will be accessible from the pause menu, and will show the entire level, along with special icons for the player, doors, chests, etc. The other map will be a true mini-map, in the upper-right corner of the HUD, showing only a tiny portion of the current level.



Originally I intended to draw a pixel directly on the screen to correspond with each tile in the level, but that turned out to be too slow.

Instead, what we can do it create a Texture2D object on the fly and display it on the screen. If we need to crop (for the small mini-map in the corner), we can calculate coordinates to center on the player, and then specify the sourceRectange parameter of SpriteBatch.Draw.

To build a Texture2D in XNA, we first have to set the size. Then we load in an Color array to specify the individual color of the pixels:



Drawing the full map is pretty straightforward:

spriteBatch.Draw(MapTexture,TopLeftPixel, null, Color.White,0,new Vector2(0,0),this.scale,SpriteEffects.None,0);

If we want to have a cropped version of the mini-map, we can use a function to determine the cropping rectangle, centered on the player position:



Then we can draw with these params in the Draw function:

spriteBatch.Draw(MapTexture, TopLeftPixel, getPlayerCenteredMapRec(this.scale), Color.White, 0, new Vector2(0, 0), this.scale,SpriteEffects.None, 0);

One important feature of mini-maps is the Fog of War. We don't want to reveal the entire map to the player from the beginning. Instead, we want to hide parts of it and reveal more as the player explores. Uncovering new sections of the map is one of the fun parts of games with complex level design.

To implement Fog of War, we store an extra 2D character array that determines which tiles in the map have been revealed. As shown above in the GetColorArray() function, sections that are not yet revealed (char '?') are drawn Gray.

The Fog of War char[,] array starts out completely filled with "unknown" tiles - '?'. Each time we draw, we make a call to update the Fog Of War, determine what tiles the player can see, and switch those tiles over to '.'.

I'm using an open source algorithm called MRPAS to determine what the player can see from his position. Full source available here: http://www.umbrarumregnum.net/downloads/mrpas

The code itself is somewhat complex, but essentially it draws lines out from the player until it hits an obstacle. One nice feature of the algorithm is you can specify to "light walls", which means the wall tiles themselves will be revealed in the Fog Of War, and therefore show up in the minimap.



I was a little worried that the whole thing would run slow, since we're doing a dozen nested loops on nxn mazes every Draw cycle, as well as running the MRPAS algorithm. However, it runs without hiccup. If performance started to become an issue (potentially on massive maps), you could simply keep track of which tiles the player has occupied. If we've already been to this tile, don't run the Fog of War / MRPAS algorithm. Similarly, only recalculate the Color[] for the actual mini-map tile if the player changes tiles.

Next time I'm going to look into everything related to enemies - path finding, line of sight, rudimentary AI, attacking, etc.

Building Mazes

Happy New Year!

From NetHack to Civilization to Diablo to MineCraft, lots of games have used procedural algorithms to generate semi-randomized levels. For a one man shop like myself, its a way to generate lots of gameplay without a ton of gruntwork.

So how to go you about building mazes?

One site that really helped me out was PCG.Wikidog.com - Procedural Content Generation. It contains algorithms for some of the classic roguelikes, including Angband.

A maze itself can be generated with a pretty simple iterative or recursive algorithm. The psuedocode is as follows:


1. Start out with a 2D array of size nxn.

2. Fill each cell in the grid with character '?' (undefined)

3. Carve out a random cell.
   a. Define function Carve: make the input cell empty '.'
   b. Make the surrounding four cells "maybe" ','.
   c. Add these surrounding cells to a coordinate list called Frontier

4. Iterate or Recurse through the Frontier list until it is empty.
   a. pick a random cell from Frontier. You can use weighted algorithms to pick near the front or back of the list, which lead to different styles of maze (tight and claustrophic vs long empty passages)
   b. Run function Check on the random cell. Define check (Note, this is the most complex part of the algorithm, so you may need to follow along the actual code below)
     i. get the EdgeState of the cell - sum up the cells surroundind the current cell. Empty to the north = 1, south = 2, west = 4, east = 8.
     ii. If we're not up against the side of the map, set the diagonal spaces adjacent to the input space as empty, and return false. Otherwise return true. This basically makes the maze have corners.
   c. If Check was true, Cave out the cell. Otherwise Harden the cell - turn it into a wall '#'
   d. Remove this cell from the Frontier list.

5. Once the Frontier list is emtpy, go through the entire map and change "maybe" cells ',' into empty cells '.' . Turn unknown '?' cells into walls '#'


Full Code:

private char[,] maze; //field
private List frontier;

private int height;
private int width;

private void BuildMaze()
{
 maze = new char[height, width];

 //traverse the maze and fill in unknown blocks
 for (int i = 0; i < height; i++)
 {
  for (int j = 0; j < width; j++)
  {
   maze[i, j] = '?';
  }
 }
 //carve out a random spot
 Carve(r.Next(width-1),r.Next(height-1));

 while (frontier.Count > 0)
 {
  double pos = Math.Pow(r.NextDouble(), Math.Pow(Math.E, branchrate));
  int index = (int)(pos * frontier.Count);
  Coord c = frontier[index];
  if (Check(c.x, c.y))
   Carve(c.x, c.y);
  else
   Harden(c.x, c.y);
  frontier.Remove(c);
    
 }

 for (int i = 0; i < height; i++)
 {
  for (int j = 0; j  0)
 {
  if (maze[y - 1,x ] == '?')
  {
   maze[ y - 1,x] = ',';
   frontier.Add(new Coord(x, y - 1));
  }   
 }
 if (y < height - 1)
 {
  if (maze[y + 1,x] == '?')
  {
   maze[y+ 1,x ] = ',';
   frontier.Add(new Coord(x, y + 1));
  }
 }
 if (x > 0)
 {
  if (maze[y,x - 1] == '?')
  {
   maze[y,x - 1] = ',';
   frontier.Add(new Coord(x - 1, y));
  }
 }
 if (x < width - 1)
 {
  if (maze[y,x + 1] == '?')
  {
   maze[y,x + 1] = ',';
   frontier.Add(new Coord(x + 1, y));
  }
 }
 //shuffle frontier?
 
}

private void Harden(int x, int y)
{
 maze[y,x] = '#';

}

private bool Check(int x, int y)
{
 int edgestate = 0;
 if (y > 0)
 {
  if (maze[y - 1,x ] == '.')
   edgestate += 1;
 }
 if (y < height - 1)
 {
  if (maze[ y + 1,x] == '.')
   edgestate += 2;
 }
 if (x > 0)
 {
  if (maze[y,x - 1] == '.')
   edgestate += 4;
 }
 if (x < width - 1)
 {
  if (maze[y,x + 1] == '.')
   edgestate += 8;
 }

 if (this.noDiagonals)
 {
  if (edgestate == 1)
  {
   if (y < height - 1)
   {
    if (x > 0)
    {
     if (maze[ y + 1,x - 1] == '.')
      return false;
    }
    if (x < width - 1)
    {
     if (maze[y + 1,x + 1 ] == '.')
      return false;
    }

   }
   return true;
  }
  else if (edgestate == 2)
  {
   if (y > 0)
   {
    if (x > 0)
    {
     if (maze[y - 1,x - 1 ] == '.')
      return false;
    }
    if (x < width - 1)
    {
     if (maze[ y - 1,x + 1] == '.')
      return false;
    }
   }
   return true;
  }
  else if (edgestate == 4)
  {
   if (x < width - 1)
   {
    if (y > 0)
    {
     if (maze[y - 1,x + 1 ] == '.')
      return false;
    }
    if (y < height - 1)
    {
     if (maze[ y + 1,x + 1] == '.')
      return false;
    }
   }
   return true;
  }
  else if (edgestate == 8)
  {
   if (x > 0)
   {
    if (y > 0)
    {
     if (maze[y - 1,x - 1 ] == '.')
      return false;
    }
    if (y < height - 1)
    {
     if (maze[y + 1,x - 1 ] == '.')
      return false;
    }
   }
   return true;

  }
  return false;
 }
 else
 {
  if (edgestate == 1 || edgestate == 2 || edgestate == 4 || edgestate == 8)
   return true;
  else
   return false;
 }

}

And that's it. You end up with something like this:

.#.##.#.#.#....#.#.#
....#.#.#.#.##.#....
###.#...#...####.###
#...###...#..#.#.#..
..#.#.##.#####.....#
###.#.#........###..
.#..#.##.#####...###
.#.##..#.....#.####.
....#.##.#######..#.
#.###.#...#...###...

The trouble is that the passageways are only a single tile wide or tall, which would make it very hard for our hero to navigate the game world, since he's two tiles tall! So we can scale the maze, simply by take a tile and copying it to 3 tiles to the east, south and south east. This doubles the size of the board. We can continue to double until the maze feels right - for my game it's a factor of 2, which is 4 times the size. You end up with something like this:

....########....####........####....####........########....####....########....
....########....####........####....####........########....####....########....
....########....####........####....####........########....####....########....
....########....####........####....####........########....####....########....
........................########....########........####....####........####....
........................########....########........####....####........####....
........................########....########........####....####........####....
........................########....########........####....####........####....
####################....................########............########....####....
####################....................########............########....####....
####################....................########............########....####....
####################....................########............########....####....
........................################################....########............
........................################################....########............
........................################################....########............
........................################################....########............
################....########....####....####....####............####....########
################....########....####....####....####............####....########
################....########....####....####....####............####....########
################....########....####....####....####............####....########

The world is still pretty boring, so one thing we can do is generate "rooms". These are large areas of empty space that we can later populate with platforms, elevators, traps and enemies. Generating rooms is pretty easy. Prior to building the map, select a few cells and expand them by random dimensions, changing them to type the "maybe" type ',' We don't want to completely empty them out, so the maze algorithm will still work. So now we have something like this. Better, but still not a game world:

....................########............########....####....####....####....####
########....####................############........................####........
########....####................############........................####........
########....####................############........................####........
########....####................############........................####........
....####....####....####....########............################............####
....####....####....####....########............################............####
....####....####....####....########............################............####
....####....####....####....########............################............####
....####################....################................####....####........
....####################....################................####....####........
....####################....################................####....####........
....####################....################................####....####........
....########............................####....................................
....########............................####....................................
....########............................####....................................
....########............................####....................................
........########....########....############....................................
........########....########....############....................................
........########....########....############....................................
........########....########....############....................................

The next step is to place special characters. These are tiles that will represent platforms, traps, enemies, elevators, items, powerups, etc. Once we have our fully scaled map, we can traverse through and check for certain patterns in which to place our special tile. For example, to place a platform '-', we want to be in a large empty room. So before we place a platform, check to see that the 5 spaces above and below are empty:

........................####............
........................####............
........................####............
........................####.......A....
....####................####....########
....####..............-.####....########
....####................####....########
....####................####....########
############............####............
############........-...####............
############...-........####............
############............####............
......................-.........####....
................................####..-.
................................####....
..A......A...-..................####....
############....-...........########....
############................########....
############................########....
############................########....

Lastly, we want to add some challenge and progression to our maps. We can do this with locked doors and keys. The easiest way is to generate lots of smaller maps, place a random key 'K' inside, enclose the entire thing with a wall and a single locked door as the exit 'D'. Connect all the smaller maps together, and we have a maze that requires some thinking to complete!

############################################################
#..................#............####...#............####...#
#....K.............#.....K......####...#.....K......####...#
#.A........A.......#..A.........####...#..A.........####...#
################...#########...........#########...........#
################.-.#########...........#########...........#
################...#########.-.........#########.-.........#
################...#########...........#########...........#
#..................D............####...D............####...#
#..................#............####...#............####...#
#..................#............####...#............####...#
#.A.............A..#...A........####...#...A........####...#
########....################....################....########
########....################....################....########
########....################.-..################.-..########
########....################....################....########
#..................#...................#...................#
#..................#...................#...................#
#..................#...................#...................#
############################################################

The fun thing about maze generation is that the possibilities are endless. You can instantly generate a new world to explore and jump around in.



Next time I'm going to look into minimaps, and "fog of war". We don't want to be able to spoil the entire maze in one glance!