There are several more in the set, so check it out! This is a beta build so things may change a bit before release, but this is what the game looks like as of right now.
Tuesday, December 8, 2009
Some Screenshots
I've posted some screenshots of the Replica Island beta build over at replicaisland.net.
There are several more in the set, so check it out! This is a beta build so things may change a bit before release, but this is what the game looks like as of right now.
There are several more in the set, so check it out! This is a beta build so things may change a bit before release, but this is what the game looks like as of right now.
Wednesday, November 11, 2009
It's Not the Size That Counts
One of the concerns that I occasionally run across when working with Android game developers is that Android handsets don't have enough storage space for applications. Some folks, such as John Biggs over at MobileCrunch, see this as an obstacle to "real" game development. In his article on the subject, Biggs notes that Myst for iPhone takes up 727 mb, making it too large for any of the existing Android handsets. His conclusion is that the lack of space on Android devices is preventing game developers from bringing "real" games to Android.
Actually, Android imposes no size limit on application space; each device maker may choose what kind of storage and how much they want to put in their devices, and there is already a bit of variation across the handsets currently on the market. The current partition space is the result of manufacturer preference, not some characteristic intrinsic to the Android OS.
While it's true that apps can't be installed on the SD card, and that the amount of available application space on existing Android handsets is smaller than some other devices, I think that this argument is based on the assumption that "better" games must take up more space. I'm here to tell you that there's no strong correlation between game quality, or even game length, and application size.
Level of Detail
If we take a look back at video games over the last thirty years, we can see that, with each new generation, games have required more space than before. Take the Super Mario series. Super Mario Bros. (1985) for the Nintendo Entertainment System shipped on cartridges that could only hold around 40k of data. Super Mario World (1990) for the Super Nintendo shipped on a 512k cart. Super Mario 64 (1996) for the Nintendo 64 ran in 8 mb, and Super Mario Sunshine (2002) for the GameCube came on a single 1.5 gb mini disc.
The reason that this increase in space is necessary is that the target resolution of the host device has increased over time. The original Super Mario Bros. was designed for a 256 x 240 pixel display, while Super Mario Sunshine was designed for 640 x 480, the standard SDTV resolution. This increase in resolution required that art assets also grow in size; extra pixel density isn't useful if you don't actually have content to fill it with.
This is true whether you're talking about 2D or 3D. In a modern 3D game, resolution is a function of texture detail and model complexity. Texture data includes normal maps, height maps, bump maps, reflection maps, and all kinds of other image data that has increased in resolution (or only recently become viable due to increases in storage space) since previous generations. If you are a gamer with a good memory, you might remember Hideo Kojima talking about how Solid Snake's mustache in Metal Gear Solid 4 contains the same number of polygons as an entire enemy character in Metal Gear Solid 3; presumably, the increase in complexity was necessitated by the move to HD televisions.
So there is a correlation between application size and target screen size. Just not one between application size and game quality.
Running the Numbers
To drive this point home, I took a look at the top games on three different digital distribution networks: Microsoft's Xbox Live Arcade, Apple's iTunes Store, and Android Market. Xbox Live Arcade games are written to be run on HD television sets with 1080p resolution. That's 1920 x 1080, or 2,073,600 pixels. iPhone apps and most existing Android apps are written to run at HVGA resolution, which is 320 x 480, or 153,600 individual pixels. So the XBLA games are running at a resolution roughly 13 times greater than that of the iPhone or Android devices like the T-Mobile G1 or myTouch 3G. So, if we assume that all things are equal and that cost of detail increases at a linear rate (neither of which are very true, but bear with me here), we can reasonably expect about a 13x difference in the physical size of the same content on an HD device compared to HVGA device.
Below is a graph comparing the average application size for these three networks. To calculate this average I used the sizes of the top 20 games (as of Nov. 3, 2009) from each network.
The average top Xbox Live Arcade game is 277 mb. Interestingly, paid games on both iTunes Store and Android Market tend to be a little larger than free games, perhaps because the cost of generating art assets requires the developer to sell the app rather than give it away. In any case, the average iPhone game is 21.5 mb, which is about 12.8x times smaller than the XBLA average--pretty dead on with our resolution-based expectation. The average Android game is even smaller--around 1 mb--though as on the iPhone, paid games tend to be larger than free games.
Though the Android games are smaller in aggregate, there certainly are a number of titles at or above the 10 mb mark on Android Market. This is within the same range as the top 20 iPhone games; Myst at 727 mb is clearly an outlier (and, as an aside, it's larger than all but two of the top XBLA games). You can fit a bunch of top-tier iPhone games in a G1, and even more in a myTouch or Droid.
It's interesting that the Android games are so much smaller. The most popular free apps are tiny--the average of the top 20 free games is only around 300k. This might have to do with how popular games are ranked, or the fact that paid apps have been available on Market for a much shorter amount of time than on Apple's platform. Or it might be something else; Labyrinth Lite, which is available on both platforms, is less than half the size on Android compared to its iPhone version. At any rate, even if the Android games were larger, the average user would still be able to fit a bunch of them on their phone.
So, Size Doesn't Matter?
I don't mean to suggest that size has absolutely nothing to do with game content. There are some types of games, like Myst, that are unusually data-heavy. But content quality isn't a function of size; Super Mario World's tiny 512k footprint is evidence of that. And Android should support installing apps to the SD card (though I suspect that some game developers would be uncomfortable with that option). In the mean time, apps are free to stream data over the network or cache resources to the SD card (as the Android Quake port does), though admittedly this isn't as elegant a solution as true SD card support. Still, it's an easy solution for big games like Myst.
While we're on the topic, 727 mb for Myst is a fairly surprising number. The original version of Myst targeted 640 x 480 displays at 256 colors and filled a single CD-ROM; even assuming that the iPhone version is using 24-bit color versions of the original graphics, the reduced screen resolution of the iPhone combined with advances in CPU speed and image compression technology should make it fairly easy to cram the game into less space than it originally required. After all, they fit Resident Evil 2, a 2-disc CD-ROM game for the Sony Playstation, into a single 64 mb N64 cartridge!
Plus, a game like Myst should be trivial to stream over the network; the spatial layout of each room is known and so room images close to the player's current location can be streamed in the background. Even if the developer elected not to cache those images to the SD card, 16 mb of application heap is a lot of room for 80k images, so it should be easy to stream far enough ahead into runtime memory that the player never experiences a loading pause.
The point I am trying to make is not that the Myst iPhone developers did something wrong, just that there are many ways to implement this sort of game and not all of them come with huge space requirements. I suspect that Myst on iPhone is as large as it is because that was the simplest way to port the game, not because the game itself cannot be made any smaller. And there's value in that--giving developers as many options as possible to make applications is the number #1 reason that Android should support installation of apps to the SD card. But the claim that this sort of game is impossible on Android platforms is, I think, wrong.
Wrap Up
Game quality has almost nothing to do with application size. For most games, physical size is most directly linked to the size of the screen and the resolution that the host device is running at. By looking at a selection of popular titles, we can see that on HVGA devices (such as the iPhone, or myTouch 3G) there is a fairly small range within which most games of significant scope reside. Looking at the top iPhone games, that range is well within the capabilities of existing Android devices. And while there are exceptions, they are few and far between; the existence of outliers, especially those that are large because of implementation decisions rather than necessity, is not sufficient to damn an entire platform.
Should Android support installing applications to the SD card? Yeah, sure, that'd be great. Is the lack of that functionality blocking games from working on existing Android devices? Not in the slightest.
And for the record, Replica Island is about 4.8 mb, which is a little heavier than I'd like, but not heavy enough that I'm going to spend time doing something about it. It has over 40 levels.
"The real culprit behind the lack of Android apps isn't lack of developer adoption or a difficult SDK – it's the ludicrous 256MB limit on app storage for most current Android phones and Android 2.0 itself. The OS also does not support the installation of apps on removable storage like SD cards, further ruining chances for more effusive and expansive titles. "
Actually, Android imposes no size limit on application space; each device maker may choose what kind of storage and how much they want to put in their devices, and there is already a bit of variation across the handsets currently on the market. The current partition space is the result of manufacturer preference, not some characteristic intrinsic to the Android OS.
While it's true that apps can't be installed on the SD card, and that the amount of available application space on existing Android handsets is smaller than some other devices, I think that this argument is based on the assumption that "better" games must take up more space. I'm here to tell you that there's no strong correlation between game quality, or even game length, and application size.
Level of Detail
If we take a look back at video games over the last thirty years, we can see that, with each new generation, games have required more space than before. Take the Super Mario series. Super Mario Bros. (1985) for the Nintendo Entertainment System shipped on cartridges that could only hold around 40k of data. Super Mario World (1990) for the Super Nintendo shipped on a 512k cart. Super Mario 64 (1996) for the Nintendo 64 ran in 8 mb, and Super Mario Sunshine (2002) for the GameCube came on a single 1.5 gb mini disc.
The reason that this increase in space is necessary is that the target resolution of the host device has increased over time. The original Super Mario Bros. was designed for a 256 x 240 pixel display, while Super Mario Sunshine was designed for 640 x 480, the standard SDTV resolution. This increase in resolution required that art assets also grow in size; extra pixel density isn't useful if you don't actually have content to fill it with.
This is true whether you're talking about 2D or 3D. In a modern 3D game, resolution is a function of texture detail and model complexity. Texture data includes normal maps, height maps, bump maps, reflection maps, and all kinds of other image data that has increased in resolution (or only recently become viable due to increases in storage space) since previous generations. If you are a gamer with a good memory, you might remember Hideo Kojima talking about how Solid Snake's mustache in Metal Gear Solid 4 contains the same number of polygons as an entire enemy character in Metal Gear Solid 3; presumably, the increase in complexity was necessitated by the move to HD televisions.
So there is a correlation between application size and target screen size. Just not one between application size and game quality.
Running the Numbers
To drive this point home, I took a look at the top games on three different digital distribution networks: Microsoft's Xbox Live Arcade, Apple's iTunes Store, and Android Market. Xbox Live Arcade games are written to be run on HD television sets with 1080p resolution. That's 1920 x 1080, or 2,073,600 pixels. iPhone apps and most existing Android apps are written to run at HVGA resolution, which is 320 x 480, or 153,600 individual pixels. So the XBLA games are running at a resolution roughly 13 times greater than that of the iPhone or Android devices like the T-Mobile G1 or myTouch 3G. So, if we assume that all things are equal and that cost of detail increases at a linear rate (neither of which are very true, but bear with me here), we can reasonably expect about a 13x difference in the physical size of the same content on an HD device compared to HVGA device.
Below is a graph comparing the average application size for these three networks. To calculate this average I used the sizes of the top 20 games (as of Nov. 3, 2009) from each network.
The average top Xbox Live Arcade game is 277 mb. Interestingly, paid games on both iTunes Store and Android Market tend to be a little larger than free games, perhaps because the cost of generating art assets requires the developer to sell the app rather than give it away. In any case, the average iPhone game is 21.5 mb, which is about 12.8x times smaller than the XBLA average--pretty dead on with our resolution-based expectation. The average Android game is even smaller--around 1 mb--though as on the iPhone, paid games tend to be larger than free games.
Though the Android games are smaller in aggregate, there certainly are a number of titles at or above the 10 mb mark on Android Market. This is within the same range as the top 20 iPhone games; Myst at 727 mb is clearly an outlier (and, as an aside, it's larger than all but two of the top XBLA games). You can fit a bunch of top-tier iPhone games in a G1, and even more in a myTouch or Droid.
It's interesting that the Android games are so much smaller. The most popular free apps are tiny--the average of the top 20 free games is only around 300k. This might have to do with how popular games are ranked, or the fact that paid apps have been available on Market for a much shorter amount of time than on Apple's platform. Or it might be something else; Labyrinth Lite, which is available on both platforms, is less than half the size on Android compared to its iPhone version. At any rate, even if the Android games were larger, the average user would still be able to fit a bunch of them on their phone.
So, Size Doesn't Matter?
I don't mean to suggest that size has absolutely nothing to do with game content. There are some types of games, like Myst, that are unusually data-heavy. But content quality isn't a function of size; Super Mario World's tiny 512k footprint is evidence of that. And Android should support installing apps to the SD card (though I suspect that some game developers would be uncomfortable with that option). In the mean time, apps are free to stream data over the network or cache resources to the SD card (as the Android Quake port does), though admittedly this isn't as elegant a solution as true SD card support. Still, it's an easy solution for big games like Myst.
While we're on the topic, 727 mb for Myst is a fairly surprising number. The original version of Myst targeted 640 x 480 displays at 256 colors and filled a single CD-ROM; even assuming that the iPhone version is using 24-bit color versions of the original graphics, the reduced screen resolution of the iPhone combined with advances in CPU speed and image compression technology should make it fairly easy to cram the game into less space than it originally required. After all, they fit Resident Evil 2, a 2-disc CD-ROM game for the Sony Playstation, into a single 64 mb N64 cartridge!
Plus, a game like Myst should be trivial to stream over the network; the spatial layout of each room is known and so room images close to the player's current location can be streamed in the background. Even if the developer elected not to cache those images to the SD card, 16 mb of application heap is a lot of room for 80k images, so it should be easy to stream far enough ahead into runtime memory that the player never experiences a loading pause.
The point I am trying to make is not that the Myst iPhone developers did something wrong, just that there are many ways to implement this sort of game and not all of them come with huge space requirements. I suspect that Myst on iPhone is as large as it is because that was the simplest way to port the game, not because the game itself cannot be made any smaller. And there's value in that--giving developers as many options as possible to make applications is the number #1 reason that Android should support installation of apps to the SD card. But the claim that this sort of game is impossible on Android platforms is, I think, wrong.
Wrap Up
Game quality has almost nothing to do with application size. For most games, physical size is most directly linked to the size of the screen and the resolution that the host device is running at. By looking at a selection of popular titles, we can see that on HVGA devices (such as the iPhone, or myTouch 3G) there is a fairly small range within which most games of significant scope reside. Looking at the top iPhone games, that range is well within the capabilities of existing Android devices. And while there are exceptions, they are few and far between; the existence of outliers, especially those that are large because of implementation decisions rather than necessity, is not sufficient to damn an entire platform.
Should Android support installing applications to the SD card? Yeah, sure, that'd be great. Is the lack of that functionality blocking games from working on existing Android devices? Not in the slightest.
And for the record, Replica Island is about 4.8 mb, which is a little heavier than I'd like, but not heavy enough that I'm going to spend time doing something about it. It has over 40 levels.
Sunday, November 8, 2009
Tuning Play With Automatic and Anonymous Player Metrics
As the developer of an "indy" game (meaning I don't have the backing of a big publisher, though Google is nice enough to give me 1 day per week of work time to spend on this), I have a problem that a lot of us indy developers share: play testing is hard. Play testing is the tried-and-true method of determining the quality of a given game design by watching users who are not experts play. When I worked in the game industry we'd bring kids in to the office, plunk them down in front of a TV that had a game machine and VCR hooked up, hand them a controller, and record their entire play session. This is hugely valuable information because problematic areas in the design are almost immediately identifiable. Nothing settles a design question faster than watching a real user fail to understand what you are trying to get them to do over and over again.
But as an indy developer, I don't have an office, I don't have a pool of play testers to draw from, and I can't easily connect my Android device to a VCR. My experience has been that play testing can vastly improve the quality of a game, so I really don't want to skimp on it. And the common refrain repeated by developers of universally loved, amazingly high-quality games is that they tested and iterated and tested and iterated and tested and iterated again until their game felt right.
For example, Naughty Dog, the rockstar developers behind the Crash Bandicoot series, the Jak and Daxter series, and most recently, Drake's Fortune, has been talking about the value of play testing for years. Back in the Playstation 1 days they pioneered methods for recording metrics about player style so that their levels could be tuned to increase in difficulty gradually. On top of that, their Crash Bandicoot series is a poster child for Dynamic Difficulty Adjustment (DDA), an automated system for dialing a game's difficulty up or down as the player plays to keep the level of challenge constant (full disclosure: I worked on a couple of Crash games for GBA at Vicarious Visions). Their goal is for the user to never see the game over screen; if the player dies repeatedly in the same spot, that indicates a failure of the design. With DDA and play testing, Naughty Dog has been extremely successful in smoothing out these "difficulty cliffs" and, as a result, their games get a lot of love.
So with these lessons in mind I released a build of Replica Island to Google employees about two weeks ago. Since I can't stand over every player's shoulder and watch them play, I asked for people to tell me about bugs that they encountered and provided a very short survey form at the end. Though a lot of people downloaded the game and tried it out, very few bothered to fill out the survey and even fewer wrote me directly about their thoughts. I learned a few things about my game but I did not collect not nearly the amount of information I need to tune my level design and game play decisions for a mass audience.
Fortunately, I also built some automated metric recording functionality into the game. Taking a page from Naughty Dog's book, I decided to focus on death locations: every time a player dies, I want to know about it. Looking at the aggregate results over a number of players should reveal hotspot areas where lots of people died; these areas are the first candidates for polish and tuning. So I added a very simple function to ping a web server every time the player dies and restarts the level. The ping carries no information about the user himself: just which level he is playing, where he died, and a session identifier so I can see if people died multiple times in the same place. After I released the game to Google employees the data began to roll in, and after a while I started to have enough information to be statistically relevant.
Once I had the data, I needed to decide how to use it. This is still a work in progress, but here's how I'm using it so far.
This is an image of an early level in Replica Island. The little colored dots represent death events from various users (each user is a unique color). As you can see, there's a couple of obvious spots where a lot of users died. (Actually, this is only part of the data I have received so far--the quality of the results increases as more players respond).
This spot is where the player encounters an enemy robot, one of the first in the game. This is a significant example because it takes place so early in the level; deaths in this location mean that the user got hit here at least three times, as there's nothing earlier in this level that can reduce the player's life. Also, now that the data has singled this location out, I can see why it's problematic; the low ceiling makes the Android's butt-stomp move (which is the only attack he has in the game) hard to pull off for novice players, and the slope likely causes people who are not used to the physics to roll down right into the enemy. This is a failure of the level design: I really don't want first-time players to die after playing a few seconds into the first or second level. Fortunately, the solution is simple: in this case I can just remove the enemy from that location.
Though this type of metric reporting and visualization is pretty rudimentary, it has already proven extremely valuable in identifying problematic level segments. It's also confirmed one of the conclusions that I drew from the survey feedback: nobody reads on-screen text, so in order to teach the player how to play I need to use big, visual indicators and design levels to require specific moves.
I am so happy with these results that I'm thinking of expanding the level and frequency of the events that I report; it would be great to know where players take the most damage, or which pits they fall down the most, or how long player spent traversing specific level segments. Now that the framework for event reporting and visualization is in place, it is pretty easy to add new types of events to it.
In fact, I could even release the game with this system turned on. It's probably a good idea to let the user opt-out if they want (even though I don't transmit anything personal), and I'd rather do my test and polish before the game is released, but leaving these metric reporting systems in place for the full release is very tempting. It would give me real, concrete data to tune and improve Replica Island even after it has been released.
But as an indy developer, I don't have an office, I don't have a pool of play testers to draw from, and I can't easily connect my Android device to a VCR. My experience has been that play testing can vastly improve the quality of a game, so I really don't want to skimp on it. And the common refrain repeated by developers of universally loved, amazingly high-quality games is that they tested and iterated and tested and iterated and tested and iterated again until their game felt right.
For example, Naughty Dog, the rockstar developers behind the Crash Bandicoot series, the Jak and Daxter series, and most recently, Drake's Fortune, has been talking about the value of play testing for years. Back in the Playstation 1 days they pioneered methods for recording metrics about player style so that their levels could be tuned to increase in difficulty gradually. On top of that, their Crash Bandicoot series is a poster child for Dynamic Difficulty Adjustment (DDA), an automated system for dialing a game's difficulty up or down as the player plays to keep the level of challenge constant (full disclosure: I worked on a couple of Crash games for GBA at Vicarious Visions). Their goal is for the user to never see the game over screen; if the player dies repeatedly in the same spot, that indicates a failure of the design. With DDA and play testing, Naughty Dog has been extremely successful in smoothing out these "difficulty cliffs" and, as a result, their games get a lot of love.
So with these lessons in mind I released a build of Replica Island to Google employees about two weeks ago. Since I can't stand over every player's shoulder and watch them play, I asked for people to tell me about bugs that they encountered and provided a very short survey form at the end. Though a lot of people downloaded the game and tried it out, very few bothered to fill out the survey and even fewer wrote me directly about their thoughts. I learned a few things about my game but I did not collect not nearly the amount of information I need to tune my level design and game play decisions for a mass audience.
Fortunately, I also built some automated metric recording functionality into the game. Taking a page from Naughty Dog's book, I decided to focus on death locations: every time a player dies, I want to know about it. Looking at the aggregate results over a number of players should reveal hotspot areas where lots of people died; these areas are the first candidates for polish and tuning. So I added a very simple function to ping a web server every time the player dies and restarts the level. The ping carries no information about the user himself: just which level he is playing, where he died, and a session identifier so I can see if people died multiple times in the same place. After I released the game to Google employees the data began to roll in, and after a while I started to have enough information to be statistically relevant.
Once I had the data, I needed to decide how to use it. This is still a work in progress, but here's how I'm using it so far.
This is an image of an early level in Replica Island. The little colored dots represent death events from various users (each user is a unique color). As you can see, there's a couple of obvious spots where a lot of users died. (Actually, this is only part of the data I have received so far--the quality of the results increases as more players respond).
This spot is where the player encounters an enemy robot, one of the first in the game. This is a significant example because it takes place so early in the level; deaths in this location mean that the user got hit here at least three times, as there's nothing earlier in this level that can reduce the player's life. Also, now that the data has singled this location out, I can see why it's problematic; the low ceiling makes the Android's butt-stomp move (which is the only attack he has in the game) hard to pull off for novice players, and the slope likely causes people who are not used to the physics to roll down right into the enemy. This is a failure of the level design: I really don't want first-time players to die after playing a few seconds into the first or second level. Fortunately, the solution is simple: in this case I can just remove the enemy from that location.
Though this type of metric reporting and visualization is pretty rudimentary, it has already proven extremely valuable in identifying problematic level segments. It's also confirmed one of the conclusions that I drew from the survey feedback: nobody reads on-screen text, so in order to teach the player how to play I need to use big, visual indicators and design levels to require specific moves.
I am so happy with these results that I'm thinking of expanding the level and frequency of the events that I report; it would be great to know where players take the most damage, or which pits they fall down the most, or how long player spent traversing specific level segments. Now that the framework for event reporting and visualization is in place, it is pretty easy to add new types of events to it.
In fact, I could even release the game with this system turned on. It's probably a good idea to let the user opt-out if they want (even though I don't transmit anything personal), and I'd rather do my test and polish before the game is released, but leaving these metric reporting systems in place for the full release is very tempting. It would give me real, concrete data to tune and improve Replica Island even after it has been released.
Android Game Development Resources
I get a lot of questions about when the Replica Island source will be released. Believe me, I'd like to see it finished more than anybody else in the world. If I had a date I could guarantee I'd give it, but I don't. It's close, though; I'm in final bug and optimization phase now. The laws of physics are simply not in my favor.
But in the mean time, there's a bunch of other code and resources that you can check out if you are looking for a way to get started on Android game development. Here's a few that I found:
- The Rokon game engine (blog and source).
- The Cloak open source game framework.
- An Android Quake port.
- Source to Alien Blood Bath, a side-scrolling action game.
- AGE engine source.
- SpriteMethodTest source, a sample which shows how to render sprites using Canvas and various OpenGL ES methods and profiles them.
With the exception of SpriteMethodTest (which I wrote), I don't have any connection to any of these projects, so your milage with them may vary. However, they all look promising and I think that there's plenty of information contained within them that is useful to the budding Android game developer.
If you have other links or resources that you've found useful, please post them here!
But in the mean time, there's a bunch of other code and resources that you can check out if you are looking for a way to get started on Android game development. Here's a few that I found:
- The Rokon game engine (blog and source).
- The Cloak open source game framework.
- An Android Quake port.
- Source to Alien Blood Bath, a side-scrolling action game.
- AGE engine source.
- SpriteMethodTest source, a sample which shows how to render sprites using Canvas and various OpenGL ES methods and profiles them.
With the exception of SpriteMethodTest (which I wrote), I don't have any connection to any of these projects, so your milage with them may vary. However, they all look promising and I think that there's plenty of information contained within them that is useful to the budding Android game developer.
If you have other links or resources that you've found useful, please post them here!
Tuesday, October 13, 2009
The Main Loop as a Graph Traversal
In an earlier post, I talked about treating game objects as a list of game components, with each component implementing a specific feature of the object. That way, I can call GameObject.update() and get a different result for each game object instance depending on which components have been inserted.
In fact, in Replica Island I apply that same idea to the entire game loop. The whole simulation step can be completed with a single call to MainLoop.update(). Though it's not a game object, the MainLoop object is similar to GameObject it that it simply contains a list of things to update. Those things might be GameObjects, or they might be some other kind of object that can be updated--the main loop doesn't have to know. Things that are inserted into that list will be polled every frame; that's all the MainLoop object does.
For example, there's a bit of code that needs to work out the current state of all the hardware inputs--touch screen, trackball, keyboard, d-pad, etc. That code needs to run every frame, but it's not a game object. As long as it has the right base class and implements update(), it just needs to be added to the MainLoop's list to be run every frame. Then there's the renderer; once all the game objects are finished this object needs to send the draw commands for the frame to the rendering thread (also described in a previous post), so it too can be inserted at the end of the MainLoop's list.
And in fact, systems that need to update every frame can themselves manage other systems that need to update every frame.
For example, game objects can be added directly to the MainLoop's list, but with one or two exceptions I never do that. Instead, a special system, called the GameObjectManager, is run by MainLoop every frame, and that object contains a list of GameObjects which it runs in its update() function. The reason that I have inserted this GameObjectManager class is that not all game objects should be updated every frame. Only a subset--the set that are within some radius from the camera--should be run. The rest should remain inactive to save CPU cycles. So the GameObjectManager, when updated by MainLoop, selects a subset of the GameObjects that it controls and updates them based on the position of the camera.
If you hadn't guessed already, the structure I am describing here is a tree. The MainLoop is the root node of this tree, and its children are things like the input system, render system, and GameObjectManager--bits of code that need to run every frame. The GameObjectManager has all of the game objects as its children, but it stipulates that not all of its children will be visited every traversal. The game objects themselves contain game components as their children; the game components are the leaf nodes of this kind of tree. So, to run the simulation step for the current frame, I just traverse the tree.
Actually, to be precise the structure that I am describing is a graph. The reason it must be a graph rather than a tree is that the structure allows for instancing of subgraphs and of cross-level traversals. For example, certain types of GameComponents that don't need to track state from frame to frame can be shared across multiple game objects; in that case, only one instance of the component exists but it is inserted into a number of different game object instances. In graph terms, shared GameComponents are nodes with multiple parents. However, for the general case the structure behaves like a tree, and so it's pretty safe to think about it that way.
I like using a graph to describe all the work that must be done in a frame because it's an extremely flexible way to set up a main loop. The MainLoop object hasn't changed since I originally wrote it; though the number of objects that it contains has increased, the management code itself has remained the same. For the next game, I can rip out the individual systems that I don't need any longer and insert new ones without altering any of the main program architecture.
This type of graph structure can also give you precise control over how your simulation step is run. Say you want to pause the game, but you need key systems (such as the renderer) to continue operating so that you can run the pause UI graphics. With a tree or graph system, you can insert "pausable" nodes into the tree and append to them children that should stop when the game is paused. At runtime these nodes will simply not traverse their children if the game is paused. This kind of control is hard to thread into a game that is already up and running using traditional hard-coded methods; it usually results in a lot of switches on the g_paused variable littered throughout the code base. With a graph, none of the actual simulation code needs to change--only the graph structure is modified to accommodate pausing.
Another advantage is that it's pretty easy to drive this sort of system with data. Though I haven't done this in Replica Island yet, on previous games I've worked with systems in which the entire runtime for the game is loaded from a file in the form of a main loop graph; you can see how such a structure would be pretty easy to describe in XML, and you could even use Java's reflective properties to automatically instantiate the various systems that live in the tree. Once the graph is described in data, you can change it easily from game to game, or even from level to level if necessary, all with general-purpose infrastructure code. I've not done that with Replica Island yet, but I will eventually--probably after the game ships.
Game graphs are not specific to Android, but I use them a lot and I find them a pretty powerful (and generally underrated) pattern for managing real-time update loops. Like the GameComponent system, they leave the door open to future revision by separating data structures from code. This kind of system is also pretty simple to write (my entire graph is based on two core classes, a node and a group node). Of course, for small projects they are probably overkill--it is likely faster and less error prone to just write a traditional main loop and update the code every time you need to change something. But for medium or large projects, or projects based on a codebase that is intended to be reusable across many different titles, game graphs are a pretty neat way to structure your frame.
In fact, in Replica Island I apply that same idea to the entire game loop. The whole simulation step can be completed with a single call to MainLoop.update(). Though it's not a game object, the MainLoop object is similar to GameObject it that it simply contains a list of things to update. Those things might be GameObjects, or they might be some other kind of object that can be updated--the main loop doesn't have to know. Things that are inserted into that list will be polled every frame; that's all the MainLoop object does.
For example, there's a bit of code that needs to work out the current state of all the hardware inputs--touch screen, trackball, keyboard, d-pad, etc. That code needs to run every frame, but it's not a game object. As long as it has the right base class and implements update(), it just needs to be added to the MainLoop's list to be run every frame. Then there's the renderer; once all the game objects are finished this object needs to send the draw commands for the frame to the rendering thread (also described in a previous post), so it too can be inserted at the end of the MainLoop's list.
And in fact, systems that need to update every frame can themselves manage other systems that need to update every frame.
For example, game objects can be added directly to the MainLoop's list, but with one or two exceptions I never do that. Instead, a special system, called the GameObjectManager, is run by MainLoop every frame, and that object contains a list of GameObjects which it runs in its update() function. The reason that I have inserted this GameObjectManager class is that not all game objects should be updated every frame. Only a subset--the set that are within some radius from the camera--should be run. The rest should remain inactive to save CPU cycles. So the GameObjectManager, when updated by MainLoop, selects a subset of the GameObjects that it controls and updates them based on the position of the camera.
If you hadn't guessed already, the structure I am describing here is a tree. The MainLoop is the root node of this tree, and its children are things like the input system, render system, and GameObjectManager--bits of code that need to run every frame. The GameObjectManager has all of the game objects as its children, but it stipulates that not all of its children will be visited every traversal. The game objects themselves contain game components as their children; the game components are the leaf nodes of this kind of tree. So, to run the simulation step for the current frame, I just traverse the tree.
Actually, to be precise the structure that I am describing is a graph. The reason it must be a graph rather than a tree is that the structure allows for instancing of subgraphs and of cross-level traversals. For example, certain types of GameComponents that don't need to track state from frame to frame can be shared across multiple game objects; in that case, only one instance of the component exists but it is inserted into a number of different game object instances. In graph terms, shared GameComponents are nodes with multiple parents. However, for the general case the structure behaves like a tree, and so it's pretty safe to think about it that way.
I like using a graph to describe all the work that must be done in a frame because it's an extremely flexible way to set up a main loop. The MainLoop object hasn't changed since I originally wrote it; though the number of objects that it contains has increased, the management code itself has remained the same. For the next game, I can rip out the individual systems that I don't need any longer and insert new ones without altering any of the main program architecture.
This type of graph structure can also give you precise control over how your simulation step is run. Say you want to pause the game, but you need key systems (such as the renderer) to continue operating so that you can run the pause UI graphics. With a tree or graph system, you can insert "pausable" nodes into the tree and append to them children that should stop when the game is paused. At runtime these nodes will simply not traverse their children if the game is paused. This kind of control is hard to thread into a game that is already up and running using traditional hard-coded methods; it usually results in a lot of switches on the g_paused variable littered throughout the code base. With a graph, none of the actual simulation code needs to change--only the graph structure is modified to accommodate pausing.
Another advantage is that it's pretty easy to drive this sort of system with data. Though I haven't done this in Replica Island yet, on previous games I've worked with systems in which the entire runtime for the game is loaded from a file in the form of a main loop graph; you can see how such a structure would be pretty easy to describe in XML, and you could even use Java's reflective properties to automatically instantiate the various systems that live in the tree. Once the graph is described in data, you can change it easily from game to game, or even from level to level if necessary, all with general-purpose infrastructure code. I've not done that with Replica Island yet, but I will eventually--probably after the game ships.
Game graphs are not specific to Android, but I use them a lot and I find them a pretty powerful (and generally underrated) pattern for managing real-time update loops. Like the GameComponent system, they leave the door open to future revision by separating data structures from code. This kind of system is also pretty simple to write (my entire graph is based on two core classes, a node and a group node). Of course, for small projects they are probably overkill--it is likely faster and less error prone to just write a traditional main loop and update the code every time you need to change something. But for medium or large projects, or projects based on a codebase that is intended to be reusable across many different titles, game graphs are a pretty neat way to structure your frame.
Friday, October 2, 2009
Rendering With Two Threads
The Replica Island renderer is based heavily on the GLSurfaceView class that ships with the Android SDK. I've made a couple of modifications but the code is pretty similar to the regular version: a derivation of GLSurfaceView.Renderer that draws the frame gets called every frame, followed by a call to eglSwapBuffers() to actually display the rendered frame.
GLSurfaceView provides a way to run user code in the same thread as the renderer. This makes writing games pretty easy; you can just implement a Runnable, implement a Renderer, stick them both into a GLSurfaceView and get stuff moving around on the screen. Indeed, it's more than sufficient for many applications; my SpriteMethodTest demo works this way just fine.
But for Replica Island I took a different approach. The problem with the single GLSurfaceView thread is that eglSwapBuffers() must block on the hardware until the previous frame finishes drawing. That means that even if you have nothing to draw, a call to eglSwapBuffers() takes 16.67ms to complete. (And of course, if you have a lot to draw, it could take a lot longer).
Now, just in case you are not used to thinking in terms of milliseconds, here's a quick primer. To achieve the magical "60 frames per second" that many games strive for, you need to have a new frame displayed to the user every 16.67 ms. If you go for 30 fps, you have ~32 ms to complete a frame. All your game code, plus all your OpenGL code, plus the actual time it takes to draw the frame must fit within 16.67 ms to achieve 60fps.
In Replica Island, the game code is fairly heavy-weight. I have all that collision to run, plus updates of all the active entities on the screen, plus sound playback and all that jazz. Turns out that it's usually more work to calculate a single simulation step than it is to actually draw the frame. Since this code takes time to execute, the 16 ms block that eglSwapBuffers() incurs makes it really hard to hit 60 fps. What I really want to be able to do is run game code while eglSwapBuffers() is blocking; that way I can pipeline the game updates while the hardware is busy drawing the frame.
So I split the game code off into a separate thread. This makes three threads, by the way: the main UI thread that all Activities have by default, the GLSurfaceView render thread, and this new game thread (actually, there are a few more that are generated by the system for things like orientation sensor updates, but they don't affect the equation much). Now my game code and my renderer can run asynchronously, and I win back some of that time spent in eglSwapBuffers().
Now comes the tricky part. I have two threads running in parallel that need to sync up once a frame so that the game thread can tell the render thread what to do. There's a lot of ways to go about synchronizing these two threads, but I went with a double buffer solution. The game thread fills up a buffer of commands to draw the next frame, and when it is ready it waits for the render thread to begin the next frame. At that point, the buffer is passed to to the render, which can then go off and draw the next frame asynchronously. The buffer that was used to draw the last frame is passed back to the game thread, which fills it up again the next frame. So drawing is the process of swapping these two buffers back and forth during a (hopefully short) choke point at which both threads stop and communicate.
This solution was attractive to me because it was simple, and so far it seems to be plenty fast. However, another solution might be to have a queue that is shared by both threads, with the game thread pushing commands in one end and the renderer executing commands out of the other. In theory such a solution wouldn't need both threads to ever perfectly align--blocking would only occur when one thread or the other was starved. But I haven't done this yet because it is going to be significantly more complex than the double buffer.
My render commands are objects that are allocated out of pools that the game thread owns, and must be returned to those pools when they have been drawn. In the double buffer system, the queue that is returned from the render thread contains commands that can be safely returned to their pools, but in the shared queue system there's no obvious way for the game thread to know how much has been drawn. I suppose there could be two shared queues, one in each direction, but that would still be a lot more complicated than what I have now. Right now almost no code outside of the buffer swap system knows about other threads; the pool objects and the objects they contain are not thread safe and, as it stands, don't need to be.
Is my solution the best for Android apps? I don't know. It seems to work pretty well and it is uncomplicated, which are two points in its favor. Still, I'd like to give this shared queue idea a shot at some point; my gut tells me that it will be slightly faster than the double buffer (less blocking in the average case) but a lot more complex, which might make it not worth the effort. Programmer guts are, however, extremely unreliable, so I will probably give this method a shot after Replica Island ships.
GLSurfaceView provides a way to run user code in the same thread as the renderer. This makes writing games pretty easy; you can just implement a Runnable, implement a Renderer, stick them both into a GLSurfaceView and get stuff moving around on the screen. Indeed, it's more than sufficient for many applications; my SpriteMethodTest demo works this way just fine.
But for Replica Island I took a different approach. The problem with the single GLSurfaceView thread is that eglSwapBuffers() must block on the hardware until the previous frame finishes drawing. That means that even if you have nothing to draw, a call to eglSwapBuffers() takes 16.67ms to complete. (And of course, if you have a lot to draw, it could take a lot longer).
Now, just in case you are not used to thinking in terms of milliseconds, here's a quick primer. To achieve the magical "60 frames per second" that many games strive for, you need to have a new frame displayed to the user every 16.67 ms. If you go for 30 fps, you have ~32 ms to complete a frame. All your game code, plus all your OpenGL code, plus the actual time it takes to draw the frame must fit within 16.67 ms to achieve 60fps.
In Replica Island, the game code is fairly heavy-weight. I have all that collision to run, plus updates of all the active entities on the screen, plus sound playback and all that jazz. Turns out that it's usually more work to calculate a single simulation step than it is to actually draw the frame. Since this code takes time to execute, the 16 ms block that eglSwapBuffers() incurs makes it really hard to hit 60 fps. What I really want to be able to do is run game code while eglSwapBuffers() is blocking; that way I can pipeline the game updates while the hardware is busy drawing the frame.
So I split the game code off into a separate thread. This makes three threads, by the way: the main UI thread that all Activities have by default, the GLSurfaceView render thread, and this new game thread (actually, there are a few more that are generated by the system for things like orientation sensor updates, but they don't affect the equation much). Now my game code and my renderer can run asynchronously, and I win back some of that time spent in eglSwapBuffers().
Now comes the tricky part. I have two threads running in parallel that need to sync up once a frame so that the game thread can tell the render thread what to do. There's a lot of ways to go about synchronizing these two threads, but I went with a double buffer solution. The game thread fills up a buffer of commands to draw the next frame, and when it is ready it waits for the render thread to begin the next frame. At that point, the buffer is passed to to the render, which can then go off and draw the next frame asynchronously. The buffer that was used to draw the last frame is passed back to the game thread, which fills it up again the next frame. So drawing is the process of swapping these two buffers back and forth during a (hopefully short) choke point at which both threads stop and communicate.
This solution was attractive to me because it was simple, and so far it seems to be plenty fast. However, another solution might be to have a queue that is shared by both threads, with the game thread pushing commands in one end and the renderer executing commands out of the other. In theory such a solution wouldn't need both threads to ever perfectly align--blocking would only occur when one thread or the other was starved. But I haven't done this yet because it is going to be significantly more complex than the double buffer.
My render commands are objects that are allocated out of pools that the game thread owns, and must be returned to those pools when they have been drawn. In the double buffer system, the queue that is returned from the render thread contains commands that can be safely returned to their pools, but in the shared queue system there's no obvious way for the game thread to know how much has been drawn. I suppose there could be two shared queues, one in each direction, but that would still be a lot more complicated than what I have now. Right now almost no code outside of the buffer swap system knows about other threads; the pool objects and the objects they contain are not thread safe and, as it stands, don't need to be.
Is my solution the best for Android apps? I don't know. It seems to work pretty well and it is uncomplicated, which are two points in its favor. Still, I'd like to give this shared queue idea a shot at some point; my gut tells me that it will be slightly faster than the double buffer (less blocking in the average case) but a lot more complex, which might make it not worth the effort. Programmer guts are, however, extremely unreliable, so I will probably give this method a shot after Replica Island ships.
Thursday, September 10, 2009
Why Android Flies
The main mode of movement in Replica Island is flying. The Android robot has thrusters in his feet, and while he can also slide upon the ground, most of the game is spent maneuvering through the air. Enemies are dispatched by dropping on them from above and the collision and physics systems make it easy to glide off of a ramp and into the air. I don't think this is a common approach for side scrolling platformers.
The reason that the Android flies is that many Android devices ship with a trackball. Some (like the Samsung Galaxy) have a d-pad, which works fine as well, but the devices from HTC (which include the G1, myTouch, and Hero) all sport a trackball. The great thing about a trackball is that it's an analog interface with a pretty high resolution. The bad thing about it is that you can't hold a single direction down like you can with a d-pad; to keep sending input events in a specific direction, you have to keep rolling in that direction.
When I started working on Replica Island, I knew that I'd have to do something different with the player controls to afford trackball use. Letting the Android robot fly seemed like a good solution: the player gets going in a certain direction and then only has to make minor adjustments in heading to steer rather than constantly depressing a button indicating the direction that they wish to travel. This sort control scheme is a bit like a car steering wheel--given velocity that you already have you just need to worry about turning left and right. Indeed, in early prototypes it was clear that the trackball would work very well for this sort of analog maneuvering, but I also quickly learned that it's hard to make precise movements with a trackball.
My initial implementation let the player move left, right, and up by rolling the ball, and while it worked and was playable, people had a really hard time moving in only one direction. It was too easy to accidentally roll up a little when trying to go left or right, which made the controls feel unwieldy and arbitrary. After experimenting with dead zones and other input filters, I finally reduced the trackball to horizontal movement and put a jump/fly button at the lower-left hand corner of the screen. This is a much better solution because it allows players to manage their horizontal and vertical velocity independently, much like they can with a d-pad or other traditional game input device. Furthermore, by ignoring vertical movement on the trackball the control scheme became a lot more forgiving to minor input mistakes.
Replica Island is playable with three inputs: the jump/fly button, left and right controls, and a drop/attack button. These three inputs were decided upon to allow the trackball to feel good, but they map well to other input systems (like a hardware keyboard or d-pad) too, so Replica Island is playable on a wide range of hardware.
Once I settled on the trackball-based steering approach for movement, many other aspects of the core game design fell out. I posted earlier about the collision detection system I wrote to support slopes and angles; this system was necessary to allow for ramp and bounce physics. The Android robot can slide across the ground but it's a lot more fun when he's in the air, so I needed to have a collision and physics system that allows him to take flight easily. Sliding down hills or going off ramps feels good and works well with the control scheme.
This approach also simplified animation: if the Android robot is going to fly with thrusters in his feet, he doesn't need a walk cycle, a run cycle, a turn animation, a skid to stop animation, a jump windup or a jump peak or a jump fall animation. His motion system is more complicated than most of the side scrollers I've made in the past but his animation system is extremely simple; the control scheme afforded this simplicity.
As awesome as Android is for games, the devices it runs on are not generally designed explicitly for gaming. To make a fun game, especially one that is part of an established console-oriented genre, you need to come up with a control scheme that works well for the hardware, even if there's not a lot of precedent for it. In the case of Replica Island, I started with the control scheme and the rest of the game design flowed out from there; as a result, I think that it's a quite playable platformer despite its rather unconventional controls.
When making games for this type of system, it's important to consider exactly how the available inputs are going to make the game fun; if you try to just glue controls from some other hardware paradigm onto a game running on a phone the results are almost guaranteed to suck. Getting the controls right is probably the single most important task you have as a game developer, and if you can nail them down early enough, a huge part of your game design will pretty much write itself.
The reason that the Android flies is that many Android devices ship with a trackball. Some (like the Samsung Galaxy) have a d-pad, which works fine as well, but the devices from HTC (which include the G1, myTouch, and Hero) all sport a trackball. The great thing about a trackball is that it's an analog interface with a pretty high resolution. The bad thing about it is that you can't hold a single direction down like you can with a d-pad; to keep sending input events in a specific direction, you have to keep rolling in that direction.
When I started working on Replica Island, I knew that I'd have to do something different with the player controls to afford trackball use. Letting the Android robot fly seemed like a good solution: the player gets going in a certain direction and then only has to make minor adjustments in heading to steer rather than constantly depressing a button indicating the direction that they wish to travel. This sort control scheme is a bit like a car steering wheel--given velocity that you already have you just need to worry about turning left and right. Indeed, in early prototypes it was clear that the trackball would work very well for this sort of analog maneuvering, but I also quickly learned that it's hard to make precise movements with a trackball.
My initial implementation let the player move left, right, and up by rolling the ball, and while it worked and was playable, people had a really hard time moving in only one direction. It was too easy to accidentally roll up a little when trying to go left or right, which made the controls feel unwieldy and arbitrary. After experimenting with dead zones and other input filters, I finally reduced the trackball to horizontal movement and put a jump/fly button at the lower-left hand corner of the screen. This is a much better solution because it allows players to manage their horizontal and vertical velocity independently, much like they can with a d-pad or other traditional game input device. Furthermore, by ignoring vertical movement on the trackball the control scheme became a lot more forgiving to minor input mistakes.
Replica Island is playable with three inputs: the jump/fly button, left and right controls, and a drop/attack button. These three inputs were decided upon to allow the trackball to feel good, but they map well to other input systems (like a hardware keyboard or d-pad) too, so Replica Island is playable on a wide range of hardware.
Once I settled on the trackball-based steering approach for movement, many other aspects of the core game design fell out. I posted earlier about the collision detection system I wrote to support slopes and angles; this system was necessary to allow for ramp and bounce physics. The Android robot can slide across the ground but it's a lot more fun when he's in the air, so I needed to have a collision and physics system that allows him to take flight easily. Sliding down hills or going off ramps feels good and works well with the control scheme.
This approach also simplified animation: if the Android robot is going to fly with thrusters in his feet, he doesn't need a walk cycle, a run cycle, a turn animation, a skid to stop animation, a jump windup or a jump peak or a jump fall animation. His motion system is more complicated than most of the side scrollers I've made in the past but his animation system is extremely simple; the control scheme afforded this simplicity.
As awesome as Android is for games, the devices it runs on are not generally designed explicitly for gaming. To make a fun game, especially one that is part of an established console-oriented genre, you need to come up with a control scheme that works well for the hardware, even if there's not a lot of precedent for it. In the case of Replica Island, I started with the control scheme and the rest of the game design flowed out from there; as a result, I think that it's a quite playable platformer despite its rather unconventional controls.
When making games for this type of system, it's important to consider exactly how the available inputs are going to make the game fun; if you try to just glue controls from some other hardware paradigm onto a game running on a phone the results are almost guaranteed to suck. Getting the controls right is probably the single most important task you have as a game developer, and if you can nail them down early enough, a huge part of your game design will pretty much write itself.
Tuesday, September 8, 2009
Aggregate Objects via Components
I used to make games like this:
This isn't a bad way to start making games, but it doesn't scale. Making a good game requires flexibility and the ability to iterate quickly, and this approach starts to break down when the game becomes medium-sized. What if we have more than one game mode? What if the behavior of a specific game object needs to change for a short period of time? What if Level 27's version of the player needs to be subtly different than Level 26's?
In a nutshell, the problem with this approach is that the structure of the code producing a single frame of the game is hard-coded into the program. What I want is something that can change its structure between levels, or between game modes, or even on the fly. I need something more dynamic than a hard-coded for loop.
Another Approach
Let's look at game objects as an example. Game objects are entities in the game world like coins, enemies, moving platforms, and the player. They often have similar functionality, so one way to go about implementing a set of similar objects is to use an inheritance tree. We can create a base GameObject class, and from that derive RenderableGameObject, and from that derive RenderableMovingGameObject, and from that derive RenderableMovingCollidableGameObject, etc, etc, etc. Each level of derivation can add some common functionality until the leafs of this tree are specific entities, like the player.
The real problem with inheritance trees is that features that don't need to be inter-related become dependent on each other because of the way the code itself is written. Given the example class structure above, it's not possible to make a GameObject that can move but doesn't need to render (short of littering the code with flags--don't do that). Because of inheritance, a dependency between movement and rendering has been created where none actually needs to exist. What if we could mix and match features on a per-instance basis rather than tying them all together in a class hierarchy? This is where object composition comes in.
Object composition (or "object aggregation" depending on which design patterns book you read) is the idea that an object "has a" feature instead of "is a" feature. Rather than using inheritance or some other code-side method of collecting functionality together in a single object, we make the object manage a list of separate feature objects; the contents of that list can be different per instance.
So for Replica Island, I have a GameObject class that contains a list of GameComponents. A game object with an empty list does nothing; it can't be drawn, or make noise, or hit things, or do anything else to affect the game. GameComponents implement all of those features, and they must be inserted into the GameObject for it to actually be able to act. Here's some psudeo-code of how GameObject and GameComponents work:
A GameObject just runs all the GameComponents it contains to produce its output each frame. GameComponents in Replica Island implement things like movement, physics, collision detection, sprite animation, rendering, animation selection, AI, player control, etc. Once a generic GameComponent is written it can be inserted in any number of objects; if a specific object requires special functionality, a new GameComponent can be written just for that object without disturbing anything else in the system.
The beauty of this approach is that individual components can be compartmentalized features, and brand new objects in the game world can be created just by sticking different pieces of pre-existing code together in new ways. The result is also dynamic: unlike an inheritance-based object, Replica Island game objects can change their structure at runtime. For example, one of the Android robot's powers is to possess other robots. When an enemy robot is possessed, his AI component is removed and a new component that lets the player control him is inserted. All of a sudden the robot is being driven by the player; all the rest of his code for animation selection, physics, and collision detection, continues to work without realizing that anything has changed. When the player releases the robot, the original component structure can be restored (actually, in this case the robot blows up, taking out anything else near it, but you get the idea).
I've made a couple of games now using components and I'm very happy with the result. In Replica Island I took a couple of shortcuts for speed that damage the goal of completely independent components, but I think it was worth it; the sacrifices I've made for frame rate haven't actually proved detrimental to the flexibility or extensibility of the system.
class RenderableMovingCollidableGameObject extends RenderableMovingGameObject {
public void update() {
super.update(); // Parent classes implement rendering and movement.
// implement collision detection here
}
}
class PlayerObject extends RenderableMovingCollidableGameObject {
public void update() {
super.update(); // Run rendering, movement, and collision.
// update the player
}
}
...
// Main loop!
while (true) {
InputSystem.update(); // poll for input.
for (gameObject : ListOGameObjects) {
gameObject.update();
gameObject.draw();
}
}
This isn't a bad way to start making games, but it doesn't scale. Making a good game requires flexibility and the ability to iterate quickly, and this approach starts to break down when the game becomes medium-sized. What if we have more than one game mode? What if the behavior of a specific game object needs to change for a short period of time? What if Level 27's version of the player needs to be subtly different than Level 26's?
In a nutshell, the problem with this approach is that the structure of the code producing a single frame of the game is hard-coded into the program. What I want is something that can change its structure between levels, or between game modes, or even on the fly. I need something more dynamic than a hard-coded for loop.
Another Approach
Let's look at game objects as an example. Game objects are entities in the game world like coins, enemies, moving platforms, and the player. They often have similar functionality, so one way to go about implementing a set of similar objects is to use an inheritance tree. We can create a base GameObject class, and from that derive RenderableGameObject, and from that derive RenderableMovingGameObject, and from that derive RenderableMovingCollidableGameObject, etc, etc, etc. Each level of derivation can add some common functionality until the leafs of this tree are specific entities, like the player.
The real problem with inheritance trees is that features that don't need to be inter-related become dependent on each other because of the way the code itself is written. Given the example class structure above, it's not possible to make a GameObject that can move but doesn't need to render (short of littering the code with flags--don't do that). Because of inheritance, a dependency between movement and rendering has been created where none actually needs to exist. What if we could mix and match features on a per-instance basis rather than tying them all together in a class hierarchy? This is where object composition comes in.
Object composition (or "object aggregation" depending on which design patterns book you read) is the idea that an object "has a" feature instead of "is a" feature. Rather than using inheritance or some other code-side method of collecting functionality together in a single object, we make the object manage a list of separate feature objects; the contents of that list can be different per instance.
So for Replica Island, I have a GameObject class that contains a list of GameComponents. A game object with an empty list does nothing; it can't be drawn, or make noise, or hit things, or do anything else to affect the game. GameComponents implement all of those features, and they must be inserted into the GameObject for it to actually be able to act. Here's some psudeo-code of how GameObject and GameComponents work:
class GameObject {
private Array<GameComponent> mComponents;
public void addComponent(GameComponent component) {
mComponents.push(component);
}
public void update(float time) {
for (component : mComponents) {
component.update(time, this);
}
}
}
class GameComponent {
public void update(float time, GameObject parent) {
// ... functionality goes here
}
}
A GameObject just runs all the GameComponents it contains to produce its output each frame. GameComponents in Replica Island implement things like movement, physics, collision detection, sprite animation, rendering, animation selection, AI, player control, etc. Once a generic GameComponent is written it can be inserted in any number of objects; if a specific object requires special functionality, a new GameComponent can be written just for that object without disturbing anything else in the system.
The beauty of this approach is that individual components can be compartmentalized features, and brand new objects in the game world can be created just by sticking different pieces of pre-existing code together in new ways. The result is also dynamic: unlike an inheritance-based object, Replica Island game objects can change their structure at runtime. For example, one of the Android robot's powers is to possess other robots. When an enemy robot is possessed, his AI component is removed and a new component that lets the player control him is inserted. All of a sudden the robot is being driven by the player; all the rest of his code for animation selection, physics, and collision detection, continues to work without realizing that anything has changed. When the player releases the robot, the original component structure can be restored (actually, in this case the robot blows up, taking out anything else near it, but you get the idea).
I've made a couple of games now using components and I'm very happy with the result. In Replica Island I took a couple of shortcuts for speed that damage the goal of completely independent components, but I think it was worth it; the sacrifices I've made for frame rate haven't actually proved detrimental to the flexibility or extensibility of the system.
Saturday, August 1, 2009
Detecting and responding to dynamic collisions.
In the last post I discussed how Replica Island uses line segments organized as a 2D regular grid of tiles as the basis for its background collision system. This time I will explain how dynamic collisions (collisions between moving objects) are detected and resolved.
In Replica Island I draw a distinction between collisions that occur with the background geometry (falling on the ground, sliding on a slope, hitting the Android's head on the ceiling) and collisions that occur between game objects (the Android depressing a button, or hitting an enemy, or collecting a coin). While both of those cases are forms of "collision detection," they represent very different types of tests and I have two (entirely separate--mostly) systems for dealing with them.
The solution is to "sweep" the space in between the character's position at the last frame and his current position, and snap the character back if an intersection is detected. I use rays to do this: rays are cast from a character's previous position to his current position, and the first intersection along the ray (that is, the intersection that is closest to the ray's start point) is considered to be the spot at which the character hit a wall. I also filter my ray test by the normals of the surfaces I am considering; surfaces that do not oppose the direction of the ray can be ignored (that is, I only care about surfaces whose dot product against the direction of the ray is less that 0). Characters are not well described by a single, thin ray, however, so I do two tests: one filtered against horizontal surfaces and one filtered against vertical surfaces (angled surfaces fall into one bucket or the other depending on their slope). This is a nice method because it allows me to tune exactly how I test a volume against collision; often I want to allow a small amount of intersection: when the character is standing on a sloped surface, for example, I want to allow his bounding box to intersect with the slope slightly so that it looks like his feet are on the ground. With a couple of simple ray tests this method covers the space between the previous frame and the current frame pretty well without too much processor overhead. I briefly experimented with a final volume test pass to make sure that collisions were not being missed by the ray tests, but in the end such a test wasn't necessary (and actually, despite being more technically correct, the results were a lot less fun).
Sometimes I want game objects that act like background collision but are not part of the collision tile map. For example, a moving platform might act in every way like a background element except that it can move. In these cases, I allow entities to submit temporary line segments to the background collision system which will then be used along with all the rest of the background collision line segment data. This way characters in the world can be made to act exactly like solid objects without remaining static, and other characters can come along and react to them without any special code.
Each animation frame in Replica Island can carry a list of "attack" volumes and "vulnerability" volumes. When detecting collisions, I stipulate that collisions can only occur between a single attack volume and a single vulnerability volume. Furthermore, volumes can be set to deal and receive specific types of hits, which allows me to filter the number of actual volume intersection tests I need to perform (for example, the coin is only vulnerable to a "collection" hit, so only collection-hit-dealing attack volumes will be tested against the coin.
Each time an animation frame changes a new set of attack and vulnerability volumes may become active. These volumes are unioned together into a sphere that is guaranteed to encompass them called the bounding sphere. The volumes, along with the bounding sphere, are then submitted to the runtime collision detection system. Each frame, the collision detection system sorts all of the bounding spheres that have been submitted and tests them for intersections. The sort is by the left-most point of the sphere, so objects end up sorted along the x-axis of the level. This is a type of sweep and prune algorithm, and it makes it easy to quickly find overlapping bounding spheres because potentially colliding sphere pairs are guaranteed to be grouped together in the sorted list. When a pair of bounding spheres that intersect is found, each of the related entities' attack and vulnerability volumes are tested for intersection. If an intersection between an attack volume and a vulnerability volume is found, we know that these two entities have hit each other and some other code needs to run in order to respond.
For a long time the Replica Island engine only supported sphere collision volumes for these kinds of dynamic tests. About half-way through development I added an axis-aligned box collision type as well, but otherwise no complicated collision volume tests have been necessary. I'm very happy with the way that this system turned out: it's reliable, fast, and easy to extend.
In Replica Island I draw a distinction between collisions that occur with the background geometry (falling on the ground, sliding on a slope, hitting the Android's head on the ceiling) and collisions that occur between game objects (the Android depressing a button, or hitting an enemy, or collecting a coin). While both of those cases are forms of "collision detection," they represent very different types of tests and I have two (entirely separate--mostly) systems for dealing with them.
Moving objects vs the background
Since I alluded to how background collision detection works in the last post, I'll start with that system. If Android is falling through space and passes into the ground, I need to detect that intersection and then fix it so that he doesn't actually fall through the floor. This is actually a pretty tricky problem because the frame rate of any Android game (and really, any modern game on any platform) can fluctuate as the game is played. The Android moves through space in game units / second, but the game is displayed in frames per second, and depending on the current speed of the game there's no good way to predict how far he'll move in a single frame. So I need a method that can cover a range of space between the last frame and this one so that even a dramatic movement won't allow the player to pass through walls.The solution is to "sweep" the space in between the character's position at the last frame and his current position, and snap the character back if an intersection is detected. I use rays to do this: rays are cast from a character's previous position to his current position, and the first intersection along the ray (that is, the intersection that is closest to the ray's start point) is considered to be the spot at which the character hit a wall. I also filter my ray test by the normals of the surfaces I am considering; surfaces that do not oppose the direction of the ray can be ignored (that is, I only care about surfaces whose dot product against the direction of the ray is less that 0). Characters are not well described by a single, thin ray, however, so I do two tests: one filtered against horizontal surfaces and one filtered against vertical surfaces (angled surfaces fall into one bucket or the other depending on their slope). This is a nice method because it allows me to tune exactly how I test a volume against collision; often I want to allow a small amount of intersection: when the character is standing on a sloped surface, for example, I want to allow his bounding box to intersect with the slope slightly so that it looks like his feet are on the ground. With a couple of simple ray tests this method covers the space between the previous frame and the current frame pretty well without too much processor overhead. I briefly experimented with a final volume test pass to make sure that collisions were not being missed by the ray tests, but in the end such a test wasn't necessary (and actually, despite being more technically correct, the results were a lot less fun).
Sometimes I want game objects that act like background collision but are not part of the collision tile map. For example, a moving platform might act in every way like a background element except that it can move. In these cases, I allow entities to submit temporary line segments to the background collision system which will then be used along with all the rest of the background collision line segment data. This way characters in the world can be made to act exactly like solid objects without remaining static, and other characters can come along and react to them without any special code.
Moving objects vs each other
However, the more common case is when two game objects--a bullet and the player, an enemy and some spikes, etc--that are moving and non-solid come into contact. In this case we need to detect the intersection and then let code specific to each entity decide what to do about it. Still, we can generalize the system a little bit more: usually in such collisions we can name one of the entities as the "offender" and the other entity as the "victim." When a bullet hits the player, the bullet is the offender and the player is the victim. When a robot runs into some spikes, the spikes are the offender and the robot the victim. In fact, if we consider an animating character, we might want to mark some parts of a given frame of animation as "offensive" and other parts "vulnerable." In a game where a character can punch, we probably want the character's fist to deal damage to other characters but at the same time we'd expect other parts of the character, say his back and head, to be vulnerable to hits. So in order to detect collisions between game entities, I decided to give my entities multiple collision volumes, some associated with offensive areas and others associated with areas that are vulnerable to hits.Each animation frame in Replica Island can carry a list of "attack" volumes and "vulnerability" volumes. When detecting collisions, I stipulate that collisions can only occur between a single attack volume and a single vulnerability volume. Furthermore, volumes can be set to deal and receive specific types of hits, which allows me to filter the number of actual volume intersection tests I need to perform (for example, the coin is only vulnerable to a "collection" hit, so only collection-hit-dealing attack volumes will be tested against the coin.
Each time an animation frame changes a new set of attack and vulnerability volumes may become active. These volumes are unioned together into a sphere that is guaranteed to encompass them called the bounding sphere. The volumes, along with the bounding sphere, are then submitted to the runtime collision detection system. Each frame, the collision detection system sorts all of the bounding spheres that have been submitted and tests them for intersections. The sort is by the left-most point of the sphere, so objects end up sorted along the x-axis of the level. This is a type of sweep and prune algorithm, and it makes it easy to quickly find overlapping bounding spheres because potentially colliding sphere pairs are guaranteed to be grouped together in the sorted list. When a pair of bounding spheres that intersect is found, each of the related entities' attack and vulnerability volumes are tested for intersection. If an intersection between an attack volume and a vulnerability volume is found, we know that these two entities have hit each other and some other code needs to run in order to respond.
For a long time the Replica Island engine only supported sphere collision volumes for these kinds of dynamic tests. About half-way through development I added an axis-aligned box collision type as well, but otherwise no complicated collision volume tests have been necessary. I'm very happy with the way that this system turned out: it's reliable, fast, and easy to extend.
Fast and accurate 2D collision detection with line segments.
Replica Island is a tile-based game, which means that the levels are laid out using small (32x32), reusable tiles. I chose this approach for two reasons: it's memory efficient and exceedingly common for this genre. With a tile-based game you define a set of tiles--in the case of Replica Island, a single texture representing each possible tile--and then draw the level by combining those tiles together. Even if you have a lot of levels you don't need to spend a lot of disk space (or runtime memory) on the actual art for the tiles, and the data describing the layout of each level is very small. So tiles are useful for games that have a lot of levels and wish keep the total size of their application down. Tiles are also the standard way to make side scrolling games. Pre-Sony Playstation 1 game hardware (and some post-PS1 hardware, like the Nintendo GameBoy Advance) was hardwired to deal with tiles because of these efficient properties, and as a result the vast majority of side-scrolling games are tile-based. So going with a tile-based game engine also made sense because it helps the game feel like a proper side scroller.
So when it came time to write a collision system to represent level geometry for Replica Island, tiles seemed like a natural choice. I already had a tool for editing tiles and tile maps, as well as runtime code for loading tile sets and maps, so using tiles for collision meant I could leverage a lot of existing infrastructure. Also, maintaining a 2D array of collision tiles in memory was appealing because it's very fast to query the contents of any particular tile; while many collision systems organize their data in trees, doing so requires that the tree be traversed for every collision test. A 2D array, on the other hand, can be indexed directly into, which is very fast (the down side is that these arrays are generally sparse, so there is a lot of runtime memory wasted; however, for the size of the levels I was considering and the available ram on Android devices, the memory required of an array to describe the level is trivially small).
The collision tile layout for an early test level.
Tile-Based Line Segment Collision? Huh?
The problem with using tiles for collision is that they are basically square. The simplest implementation is to simply consider the collision world a 2D grid of booleans, set to true in grid cells that are "solid" and false to cells that are "empty." Using this method you can calcuate the location of a collision cell in game space and then check to see if it is solid or not before deciding if, for example, your player can move forward. While that's a very simple approach (and I shipped a few games that worked that way back in the day), it's not really going to scale to the types of interesting level designs that modern players expect. At the very least you want to be able to support a sloped surface so you can make hills and valleys, and ideally you should be able to express bumps, spikes, curves, and other shapes that are much more complicated than a simple solid cube.
So, for Replica Island, I decided to implement a collision system based on arbitrary line segments, stored as shapes in tiles and laid out in the world as a tile map. The idea is pretty straightforward: within a 32x32 collision tile I can define any number of line segments, which can have arbitrary angles and normals. I can use my tile editor tools to lay the collision tiles out and at runtime I can leverage the speed of a 2D array (direct index into the current tile) to find a set of potentially-intersecting line segments. The nice thing about line segments is that they can contain both a slope and a normal, which allows for all kinds of interesting physics calculations without a lot of code (for example, to make a ball bounce convincingly off an angled surface you can simply reflect the ball's velocity about the normal of the surface). I've used similar systems (though never stored as tiles) on a lot of other games and, at least for 2D collision worlds, I'm quite happy with the approach.
The collision tileset used to build levels in Replica Island.
Did you know that you can actually script Photoshop with Javascript? I did not know this, but it's actually pretty easy to do (if neigh undebuggable). After a day of futzing around with Photoshop's Javascript API I had a tool that would walk Photoshop paths and generate a list of line segments with normals (calculated by requiring the path be closed and by assuming that all normals point away from the centroid of the path shape). Since I couldn't figure out a way to actually write out a text file from Photoshop, the script opens a new document, creates a text layer, and then dumps its output into that layer. Once the script was written I went over Genki's collision tileset with the path tool and generated unique paths for each tile. I also added a very simple tool to take the text output of my script and pack it as binary data for loading at runtime. It took a total of about three days to go from having no collision data to having a full tileset of data, ready for use at runtime.
So, given a collection of collision tiles, each containing a collision of line segments, and a map of those tiles laid out on a 2D grid, I was able to make a pretty expressive 2D collision system without a whole lot of effort. The next tricky bit, which I'll cover in a subsequent post, was what sort of tests, and what sort of response, are actually the best for game play. And this system only deals with intersections between entities and the background; in the future I'll write about the system I used to detect collisions between individual entities.
So when it came time to write a collision system to represent level geometry for Replica Island, tiles seemed like a natural choice. I already had a tool for editing tiles and tile maps, as well as runtime code for loading tile sets and maps, so using tiles for collision meant I could leverage a lot of existing infrastructure. Also, maintaining a 2D array of collision tiles in memory was appealing because it's very fast to query the contents of any particular tile; while many collision systems organize their data in trees, doing so requires that the tree be traversed for every collision test. A 2D array, on the other hand, can be indexed directly into, which is very fast (the down side is that these arrays are generally sparse, so there is a lot of runtime memory wasted; however, for the size of the levels I was considering and the available ram on Android devices, the memory required of an array to describe the level is trivially small).
The collision tile layout for an early test level.
Tile-Based Line Segment Collision? Huh?
The problem with using tiles for collision is that they are basically square. The simplest implementation is to simply consider the collision world a 2D grid of booleans, set to true in grid cells that are "solid" and false to cells that are "empty." Using this method you can calcuate the location of a collision cell in game space and then check to see if it is solid or not before deciding if, for example, your player can move forward. While that's a very simple approach (and I shipped a few games that worked that way back in the day), it's not really going to scale to the types of interesting level designs that modern players expect. At the very least you want to be able to support a sloped surface so you can make hills and valleys, and ideally you should be able to express bumps, spikes, curves, and other shapes that are much more complicated than a simple solid cube.So, for Replica Island, I decided to implement a collision system based on arbitrary line segments, stored as shapes in tiles and laid out in the world as a tile map. The idea is pretty straightforward: within a 32x32 collision tile I can define any number of line segments, which can have arbitrary angles and normals. I can use my tile editor tools to lay the collision tiles out and at runtime I can leverage the speed of a 2D array (direct index into the current tile) to find a set of potentially-intersecting line segments. The nice thing about line segments is that they can contain both a slope and a normal, which allows for all kinds of interesting physics calculations without a lot of code (for example, to make a ball bounce convincingly off an angled surface you can simply reflect the ball's velocity about the normal of the surface). I've used similar systems (though never stored as tiles) on a lot of other games and, at least for 2D collision worlds, I'm quite happy with the approach.
Data Generation
Once I had settled on the line-segments-in-tiles approach, the problem became actually generating the line segment data for each tile. Genki, the artist behind Replica Island, generated a set of collision tiles that would serve as the basic building blocks of our levels, but now I needed a way to represent that same data as line segments. I've had success with edge-tracing algorithms in the past but my experience with them also suggested that they require a bit of tuning to get right. And since collision detection and response is so closely tied into core game play, I wanted a way to hand-modify individual segments. When I worked in games development full time we would just sit down and write an editor tool for this kind of thing, but one of my goals with Replica Island is to see how simply (read: cheaply) I can get it finished, so writing a dedicated tool was a little out of scope. So I decided to piggyback on some existing tool to generate the data that I needed. After thinking about it for a bit, I settled on Photoshop.
The collision tileset used to build levels in Replica Island.
Did you know that you can actually script Photoshop with Javascript? I did not know this, but it's actually pretty easy to do (if neigh undebuggable). After a day of futzing around with Photoshop's Javascript API I had a tool that would walk Photoshop paths and generate a list of line segments with normals (calculated by requiring the path be closed and by assuming that all normals point away from the centroid of the path shape). Since I couldn't figure out a way to actually write out a text file from Photoshop, the script opens a new document, creates a text layer, and then dumps its output into that layer. Once the script was written I went over Genki's collision tileset with the path tool and generated unique paths for each tile. I also added a very simple tool to take the text output of my script and pack it as binary data for loading at runtime. It took a total of about three days to go from having no collision data to having a full tileset of data, ready for use at runtime.
Querying Collision at Runtime
So, now I have two different sets of data: I have a single collision tile set, which maps collision tile indicies to collections of line segments, and a bunch of collision tile maps (one for each level) that place individual collision tiles in space to describe level geometry. I can load the collision tile set once and keep it around; each level that I load brings with it its own collision tile map. At runtime, to check to see if a region of space in the game world is blocked or not, I can cast a ray through the tile map (using one of my favorite algorithms: the Bresenham line algorithm) and check it against the collision tiles that it touches. The actual line segment vs line segment test is pretty simple (here's a useful reference), and it produces an exact intersection point. As soon as an intersection is detected the ray test can be aborted and the results returned (note that it's necessary to test the ray against all segments in a particular tile, though; you always want the intersection point closest to the origin of the ray, so all segments within a given tile must be tested and only the closest intersection returned). It's also possible to test a collision volume against the world by simply visiting each cell that intersects the volume and doing a volume vs line test, but in Replica Island this sort of test did not end up being necessary. The game play is described using ray casts alone.So, given a collection of collision tiles, each containing a collision of line segments, and a map of those tiles laid out on a 2D grid, I was able to make a pretty expressive 2D collision system without a whole lot of effort. The next tricky bit, which I'll cover in a subsequent post, was what sort of tests, and what sort of response, are actually the best for game play. And this system only deals with intersections between entities and the background; in the future I'll write about the system I used to detect collisions between individual entities.
Replica Island Development Blog!
This is the first post for this new-fangled Replica Island development blog. I will use this space to talk about the development of Replica Island, both in terms of code and game design. Since this is the first post, here's the low-down on the game:
- Replica Island is a 2D side-scrolling platformer for Android devices.
- It stars the Android robot, who (it turns out) has a pretty devastating butt stomp move.
- The source for Replica Island will be released with the game. It's written in Java.
- Replica Island is currently in Alpha. I'm working hard on finishing it up.
- When it is released, Replica Island will be available for free on Android Market.
- The official Replica Island web site is http://www.replicaisland.net.
Subscribe to:
Posts (Atom)