Collision Detection
There are two kinds of collisions that can happen in a game of Contra: object vs. object collisions, and object vs. level collisions. Each is handled by completely different code and detected using completely different data, so they are basically two separate systems.
Object vs. Object Collision
In the first post of this series, I mentioned that the game keeps track of three different kinds of objects: players, bullets from players, and enemies. Collision detection is one of the areas where this separation comes into play. Instead of checking for collisions between any and all of these objects, the game only checks collisions between the groups that will react to each other. Players never interact with other players or their bullets, and enemies never interact with other enemies, so the only collisions that matter are those between players and enemies, and those between player bullets and enemies.
Given that enemies are always involved in the object/object collisions that matter, collision detection between objects is done as part of updating all of the enemies. Each frame, the game loops over each active enemy and runs its particular update logic. After an enemy updates, the collision system kicks in and checks that enemy for collisions with players, and then collisions with player bullets. Each enemy has a pair of flags that can be used to indicate to the collision system whether either or both of these kinds of collisions are enabled for that enemy. This is how some enemies, like the bodies of turrets, are able to be shot by the player (by allowing collisions with player bullets) but not able kill you if you walk into them (by not allowing collisions with players.) Beyond these flags, no special logic is used to narrow down the list of potential collisions for an enemy. Every enemy is simply checked against every player and every bullet.
Checking for a collision between a given enemy and a given player is based on a point vs. rectangle test. The point that represents the player’s current position is checked against the rectangle that represents the current hit box that the enemy is using. If the point is inside the rectangle at the moment the check is performed then a collision has occurred. At first glance this seems a little strange. You need the player to be able to be shot in the head as well as the feet, but only the point that represents the player’s current position (which is usually fairly close the the center of the player sprite) is checked for collision with the enemy hit box. The key to making the system work is that the enemy hit boxes are not just tight bounds around the enemy sprites themselves, but rather representations of the area where collisions would occur if we were doing a more traditional rectangle vs. rectangle test. Put another way, the hit boxes that enemies use represent the space where the player position would have to be to make the player sprite overlap the enemy sprite.
You can see this process in action in the image above. In each of the three sections, the player’s position is indicated by a single green pixel in the center of a green circle. The pink rectangle represents the hit box that the white enemy bullet is using to check for collisions against the player’s position. Notice how the enemy bullet uses a different hit box depending on what the player is doing. This is how the game effectively changes where the player is vulnerable without actually having a hit box around the player to work with. Each enemy has a version of their hit box to use against a player in the water, a jumping player, a player on the ground, a standing/running player, and a player bullet. The particular type of player bullet is not taken into account when picking a hit box to test against so there is no difference between the different guns you can get from a bullet collision perspective.
Object vs. Level Collision
Collisions between objects and the level itself are not handled by a system in the way that collisions among objects are. Instead, level collisions are tested for directly wherever they are needed. If a player needs to know if he has run off the end of a platform then the code that updates a running player will query for a collision at the player’s feet every frame until it finds that there is nothing there. Most enemies don’t need to know about collisions with the level at all, but those that do will similarly check for them at specific times as needed. The only kind of query that is supported is checking a point against the level collision map that we’ve talked about before. The collision query returns the collision code for tile under the point that was checked (empty, solid, water or platform) and then the caller will do whatever it needs to in response to the different results.
3D Collision
Collisions in the pseudo-3D base levels work almost exactly the same as in the 2D levels but with certain constraints to make the effect hold up in fake 3D. Enemies are not allowed to collide with the player if their screen space Y position is too small (i.e. too far toward the top of the screen which means too far back “into” the screen.) This works because players are known to always be at the bottom of the screen during these levels. Player bullets are timed and only allowed to collide with most enemies once they have been on screen long enough to have reached the “back” of the room. For enemies that can be shot at any Z position within the room (like the rolling grenades that you have to blow up before they roll down and kill you) the timer on your bullets is not used. Instead, a flag is checked to see if your bullet was fired while you were lying on the ground, and if so, normal 2D collision detection is allowed to continue as usual. This works only because you are detecting a collision between two objects that are both known to be on the ground where Y position maps directly to Z position (i.e. if two things look like they are colliding in 2D, then you know they are colliding in 3D as well, but only along the ground.) With these constraints in place, the normal, flat 2D collision detection system can be used to detect collisions between objects even in a pseudo-3D environment.
(Prev – This is part 5 of a 7 part series – Next)
Tags: Allan Blomquist, Retro Game, Retro Game Internals, Tomorrow Corporation
Now THIS is plain cool. I can see how point-rectangle collision would be a lot simpler and faster than rectangle-rectangle collision, and changing the collision rectangles of the bullets themselves is a pretty awesome workaround. Only thing I don’t understand is that third collision rectangle image on the right. Is the bullet supposed to be at the bottom of that? It looks to me like the center of the player object is about in the center of the visible sprite, at least in this illustration. That’s also cool how the individual objects themselves had to manually test for level geometry. Reminds me a bit of Aquaria with the Lua callback functions that are called when two objects collide, which lets the objects themselves determine what happens. Good stuff!
That third hit box does seem a little wonky but it is indeed what the game uses. I wouldn’t be surprised if the developers never had a nice real time visualization of what the hit boxes actually looked like like you would do in a modern game. It’s conceivable that they just tuned the numbers in the code by hand based on what felt good while playing. That could explain why the jumping hit box is a little off because you’ll always be in motion while testing it so it would be harder to tell if it’s right. Another possible explanation is the fact that there are only 15 hard coded hit box settings that all of the enemies in the game have to pick from. Maybe that hit box is a little funny because it needed to work for a few different enemies and that was kind of the average best shape?
That does make a lot of sense. I never thought about older games not having visual debug functionality and that sort of thing like most modern game engines do. I reckon old consoles were crazy hard to debug on as it was.
Very interesting article!
I’m wondering though: when you write “Players never interact with other players or their bullets, and enemies never interact with other enemies, so the only collisions that matter are those between players and enemies, and those between player bullets and enemies.”
How do you handle collisions between enemy bullets and players: it seems to be missing from this schema. Is a third group needed ?
the group of objects that i’m calling “enemies” actually includes things like the bullets that are shot by enemies. from the game engine’s point of view, those enemy bullets are just another kind of enemy that the turrets and soldiers spawn and send flying toward the player. it doesn’t treat enemy bullets and the enemies that shoot them as two distinct sets of objects like it does player bullets and players.
I see, thank you for the comment. And I guess there is some flag that says we should not test player bullets against enemy bullets unless there are some bullets that can be “cancelled” by your own bullets (haven’t played enough with contract to remember that :)) ?
Hi,
I believe in modern physics engines this collision shape is referred to as the “Minkowski Sum”. GJK etc use it too.
That fake-3D collision stuff is VERY sneaky! I mean, a timer? That’s a stroke of genius!
This stuff is highly fascinating for me, especially because it concerns deeply clandestine mechanisms in a game that I hold in unparalleled esteem. I’d like to know how you’ve learned these things, but I’m afraid I wouldn’t understand an explanation.
I do have a question, though. If the bullets and enemies change their hitbox range in response to player activity, how do they handle the changes between two players in co-op? I don’t see how this method could possibly work when, for example, player 1 is ducking, while player 2 is running. How would an enemy bullet choose which hitbox to use?
Since collisions are checked for by specialized code, each enemy can feed different hit boxes into collision checks with different players. So when an enemy goes to check for collisions with players, it says for each player, check what state that player is in (running, jumping, etc.) and then check for a collision between that player’s position and the hit box that I want given that player’s current state. If there are 2 players it just does the same check again based on that other player’s state and position.
That’s crazy! It sounds so over-complicated and clumsy, but apparently it works very well. Thanks for the answer.