A Boy and His Dog Development Info
After reading Gregg Tavarez and Dan Chang's excellent article Programming M.C. Kids, I was inspired to try to create my own game in a similar style. I set to work on what would become A Boy and His Dog in Fall 2005. Originally, the game was programmed for Windows using OpenGL, as that was the only experience I'd had with graphics. Around that time, the PSP homebrew scene was gaining speed, and I saw a good opportunity to learn something new, and maybe introduce my work to an already established community. I shifted gears and learned how to write C for the PSP.
The biggest stumbling block for me was how weak the PSP is compared to my previous platform, the desktop computer. In order to maintain a framerate of 60 FPS, you need to perform all of the work for each frame in less than one sixtieth of a second. While desktop computers with processors running at 3GHz and above have no problem doing many, many complex operations in such a short amount of time, moving to work on the PSP's 222MHz processor is quite a change. Because I wasn't properly prepared for this change when I began the project, my lack of optimization caught up with me late in development, and eventually forced me to either restart the project or discontinue work on it. Below, I'll describe how I created the game, what I think I did well, and how I should have improved the code to prevent running into the problems that made me stop work.
When I began the project, I didn't know where it would end up. This was my first effort at a 2D side-scrolling game, and I didn't really know what to do with it. I finalised most of the hit detection and game mechanics before I thought of adding the dog. The dog opened many possibilities: he is smaller, so he can reach places the kid can't; he could be used to hold switches down for the player, which is why I added the seemingly useless sitting option; the player would have to be careful to prevent the dog from recieving damage, while trying to figure out how to solve the level. It was also an original concept. I don't know of any games that used the idea of a partner in a side scroller like I did.
As I mentioned earlier, I modeled this game after Virgin Interactive's M.C. Kids. Many of the basic building blocks used in ABAHD are borrowed from M.C. Kids. I built each level as a grid, with each cell in the grid being a 16x16 block, as you can see in the picture below.
ABAHD's Grid System
The background is simply a static image which the tiles are drawn on top of. Using a grid system like this has many advantages. For example, I always know that every tile is 16 pixels wide and 16 pixels tall. It also makes hit detection simpler because you simply need to look at object is at what position in the grid. For example, if the player's feet are at point (232, 95), you simply need to divide each number by 16 resulting in (14.5, 5.9), truncate the decimal, and look that cell up in the grid. In this case, we look up cell (14, 5) and see that his feet are at the top of a log, as in the picture above. To make drawing the sprites simple and consistent, the dog and boy are both created out of 16x16 tiles.
Drawing the sprites' images was one of my favorite parts of creating this game. It's a challenge to create convincing images with just 256 pixels. Taking some cues from M.C. Kids (the tree trunks are nearly carbon copies), I created what I think are fun, colorful images that really add to the levels. The conveyor belts were especially challenging because they needed to be animated.
Some sprites I'm particularly proud of
I created a simple level editor to make level creation easier. Instead of loading the texture files for the sprites, the editor would just color the tiles differently. The editor would let me define the textures used by each tile, the types of the object, and place each tile. It would then format and save the code automatically, which I could then use in the actual game. While crude, it was a tremendous time saver, and I think it was pretty clever.
The ABAHD level editor, complete with early name
(Click to enlarge)
The most difficult part of any game, hit detection, was no exception in ABAHD. I believe the HD algorithm went through 5 major revisions before I finally settled on one that worked fairly well. The final algorithm is, thankfully, fairly simple. I managed to keep myself from fudging numbers for the most part, which really increases the integrity of the method. I used a simplified version of kinetic physics, and based some of the code off of the M.C. Kids programming article.
The kid moves by having momentum. When the player holds right on the D-pad, the kid gains momentum in the positive X direction. Holding left yields momentum in the negative X direction. Jumping adds a certain amount of momentum to the kid's Y momentum. The kid's position changes by however much momentum he has in each direction. Friction and gravity are simulated by subtracting (or adding, if the kid is moving to the left) a certain value from the kid's momentum each frame.
In order to efficiently detect when the kid hits an object, I set up some important points in the kid's sprite (the kid is actually made of two 16x16 sprites stacked on top of each other, but to keep this simple, I'll just refer to them as one single sprite):
Points used for hit detection
Each set of colored points are used for different parts of the HD algorithm. The light-blue point checks to see if the player hit his head while jumping. The orange points check if the player hit an object while jumping and moving horizontally. The blue points, for moving horizontally. The red point checks to see if the player is on a solid surface. If the red point is not on a solid surface, the green points are to check if the player is on a ledge. To speed up the HD code, the orange and light-blue points are only used when the kid is jumping and the green and red points are only used when the kid is falling or moving horizantally. These shortcuts did result in some glitches. For example, if you're moving fast enough and jump at just the right time, the HD algorithm won't check the green points (because you are jumping), and can cause you to find yourself inside of a hill's slope. Because of some poor planning early in development, these shortcuts are essential to keep the game running at full speed.
Each tile has two types associated with it. The first type, type1, is the most specific. Some examples of values used for type1 are TILE_TYPE_BUTTON, TILE_TYPE_GOAL, and TILE_TYPE_UPHILL. The second type is more general. The values for type2 are TILE_BTYPE_IGNORE, TILE_BTYPE_NORMAL, TILE_BTYPE_UPHILL, and TILE_BTYPE_DOWNHILL. type2 helps speed up the HD algorithm and make it easier to read. Instead of writing
we can simply write
and be done with it. Preserving type1 lets us handle more specific cases such as 1ups, Goal tiles, and coins.
The level select screen never gets much attention, despite being integral to many games. Thankfully, the level select screen was pretty easy to program. The screen is made up of tiles, just like the rest of the game. Each tile has a type, but instead of using the types I described above, I used the type variable to describe where the player could move, and any actions that should be taken on that tile. It's very basic and doesn't really need more attention. In the Preview of ABAHD, the level select uses the dog as a placeholder image. I was going to create a smaller version of the kid, facing the bottom of the screen (think Mario 3).
ABAHD's Level Select Screen
On to the actual HD. Each of the kid's points checks against the grid to see if it is intersecting with a tile. If there is a tile in the same spot, it will handle the collision. Usually, this means changing the kid's momentum, moving his position, or picking up an item. type2 dictates which HD method should be taken (stop the player if he hits a wall, stop the player from falling further, start moving up or downhill, etc.) while type1 dictates any special interaction that the tile performs (coins, 1ups, goals, conveyor belts, moving platforms, switches, etc.). For more information on how ground hit detection is performed, read the Programming M.C. Kids Article linked above.
Hit Detection Problems
Or at least, that's how the hit detection should have worked. Instead of using the grid system outlined earlier, I used a linked list. Since there is no random access into a linked list, in order for each of the kid's HD points to find an intersecting tile, the program would have to scroll through the entire list of tiles, comparing the point with the location of each and every tile. This is a terribly inefficient way to look up tiles. Unfortunately, this method worked well enough for all 6 of the levels included in the Preview, that I didn't give it a second thought until I started expanding the size of the levels in World 2. Suddenly, the frames were taking much more than 1/60th of a second, since there were so many tiles to scroll through for each HD point.
The levels in the Preview were created small intenionally. They're designed to give the player an area to run around and get used to the game mechanics before moving into the more challenging areas. In World 2, which is designed to be larger and more challenging than World 1, the tile count quickly rose to over 1500. For comparison, the largest level in World1 had only about 800 tiles. With so many tiles in the list, the framerate plummetted. I tried several shortcuts and optimizations, but they had little effect and would only put the problem off until later. I had three options: keep the levels small, convert the game to a grid system, or cancel the project.
The first option was out from the start. This game is an effort to make a game on the scale of M.C. Kids, and there's no way I'm going to limit myself to tiny levels. If I'm going to do it, I'm going to do it right. The second option involved a tremendous amount of work; in effect, it meant I would have to restart the game from scratch. I did try patching in a grid system on top of what I had, but it was way too unstable. There was no way to convert my current HD and tile lookup functions to fit a grid system without tearing everything out and starting again. This left the third option. I decided I should cut my losses and move on to a new project.
I would like to go back and finish ABAHD some day. I think the dog was a novel idea, certainly one I hadn't seen before, and had a lot of potential. Unfortunately, I have neither the time nor the will to restart the project. Maybe I'll be able to revisit ABAHD in the future when I am better at programming.