#collision detection

No. Once upon a time I was going to do a video about this, I don't know if it's the right time for a video about Earthworm Jim.

Earthworm Jim is a victim of a lot of things. A lot of Shiny was born out of Virgin Games, right. Guys who worked on Disney games like Aladdin for the Genesis.

Some of those Virgin Games guys have been very forthcoming about the culture back then -- about the rental market being this big scary boogeyman. So developers would deliberately insert difficulty spikes in to their games. Things that were arbitrarily SUPER difficult, just to stump players who were on a rental, to make sure they couldn't finish the game in a weekend.

Because that's how you added length to a game back then. You just made it harder. The harder the game, the longer it took to finish. Once you realize this, it unlocks a lot about why older games were "Nintendo hard." (Sakurai very recently touched on this!)

Earthworm Jim has the unfortunate position of being one of those games. There's a very specific level -- the "Tube Race" segment -- that feels like it was added as one of those rental-blocking difficulty spikes. The idea is that you've been in this underwater facility for a while and there's a glass submarine you can pilot. Since its glass, bumping in to walls cracks it, and too much damage will cause it to implode and kill you. You also have an oxygen meter you have to refill too.

You play a pretty normal level that's a mixture of fighting enemies in the base with a couple of simple submarine segments. Where the level would normally just end, you get this Tube Race segment, which is one very, very, very long submarine maze where you have a minute and a half to make it to the end without running out of oxygen or damaging the submarine so badly that you die. It is ten times harder than everything to come before it, and one of the hardest parts overall.

But that's not enough to spoil the game, no. Earthworm Jim in general is also just... one of those games that is so in love with its own artwork that it kind of hurts the experience. It's one of those games where the animation and the jokes and the character comes before everything else, even at the cost of gameplay.

Video games have something called a "hitbox." Basically, what you see is not what the game actually understands as being your character. When you see this:

What the game is seeing is this:

These are the hitboxes around characters in video games. If blue touches green, that's a floor. If blue touches red, take damage. If blue touches purple, instantly kill the player. If blue touches yellow from below, grant item. That's how the game logic works.

And you may notice that a lot of early games have characters that very easily fit in to a square for this very reason.

From a technical standpoint and a player standpoint, it is extremely easy to read when and how things collide with each other.

Earthworm Jim (and to a lesser extent, Aladdin) is a game that says "Screw that! We've got REAL CARTOON ANIMATION!" And that's the priority: showing off the animation. Not playing well.

What are the hitboxes here?

In practice, it shakes out to something like this. There's no clear line to denote what you can stand on, because the background is drawn like a cartoon show, where characters are placed in a kind of slightly angled view, inside of the floor.

There are margins of empty air on everything -- Earthworm Jim can overlap objects and not actually touch them, and the same happens in reverse. That rigid, readable collision detection from games like Mega Man and Mario don't apply here. There's a little bit of guesswork in every action Jim takes.

Now, of course, with the advent of polygons, a lot of games have more vague hitboxes. It's harder to judge what is touching what, and we've developed a better sense for it, so maybe it's not that important, right?

Well, yes and no. Earthworm Jim was trying to show off, you see. It was one of the first games of its type. It's not doing this because it's a better way of handling collision detection (it isn't), it's doing it because it's trying to look flashy. It's trying to impress you. And that's all its using it for. It is deliberately and intentionally putting itself at a disadvantage in order to say "this is an interactive cartoon."

That thinking sabotages the entire game. I can guarantee almost every idea in Earthworm Jim started with pitching the characters and how they animate with the gameplay being left as the final afterthought. To Earthworm Jim's credit, it's not a total disaster, it's just very loose and unbalanced.

Do you remember The Order: 1886 for the Playstation 4? It was lauded for having beautiful graphics, but in practice there wasn't a whole lot else. It was more like a 5 hour QTE. A lot of great tech and incredible visuals, but not a lot of deep or engaging gameplay.

That is exactly what Earthworm Jim was in 1994. Except in Earthworm Jim was beloved, because nothing really looked or sounded like it did. Aladdin was a big deal for Sega, but Earthworm Jim was a clear and definitive next step, and it was on everything.

Made some refinements to collision this week. I had screwed up nearest-point-on-triangle and voronoi region detection on triangles. Remember: epsilon has it’s place, don’t just blindly use it everywhere just because you’re doing collision work. The voronoi detection was clamping between [e..1] instead of [0..1] giving all sorts of weird ghost hits and empty edges but now it’s all correct.

Also added a continuous capsule-v-capsule test so actors can collide with each other. Finding an example of a continuous cap-v-cap test online was pretty tough and Ericson’s Collision Detection doesn’t go over it. With knowledge of the fundamentals though I got something I’m pretty happy with:

So… it all stems from the fact that, in reality, we’re made of physical matter - muscle, bone, fat, skin, blood, etc. - that stops other matter from interpenetrating it. In computer games, there is no sense of that. A 3D model in a game is completely hollow and has no inherent behavior that stops things from going through it as if it weren’t there.

Instead, we have to write simulation code to handle [collision detection], which scales in complexity with how detailed the shapes involved are. With things like clothing, that gets incredibly complex super quickly. Cloth molds to the shape of the thing that it touches, so all of that has to be simulated via a ton of math calculations, which is really hard to do in real time. When you see it in a CG movie, you’re seeing the results of hundreds of hours of workstations calculating what each frame should look like. Because it’s so complicated, most of the time we actually make the clothing directly part of the entire model, and we only animate the independently movable parts (sleeves, dangly bits, cape, etc.).

The other way to do this is to bypass the simulation altogether and have a human animate the whole thing. That becomes super time-intensive, because every fold, detail, bit, and piece of the clothing must be adjusted and moved by a human. A single sequence could take weeks for an animator to do, and it isn’t something that you can break out across multiple animators at the same time. 

Overall, showing somebody getting dressed doesn’t really gain us much. Most of the time we can get the same effect by cutting away or showing a character model only from the neck up while making motions like they are getting dressed. Then we just swap one model out for another. It’s a similar reason why we rarely directly show characters transforming into other models, and instead obscure it with a puff of smoke or a flash of light or something. Instead of having to do the incredibly labor-intensive transformation with a lot of extra animation bones and time spent, we just hide it behind smoke and mirrors.

[Join us on Discord]

The FANTa Project is currently on hiatus while I am crunching at work too busy.

[What is the FANTa project?] [Git the FANTa Project]

Got a burning question you want answered?

Short questions: Ask a Game Dev on Twitter

Long questions: Ask a Game Dev on Tumblr

It makes the math easier. 

Computers can’t actually see and have no inherent concept of things colliding with each other, so the only way for them to tell whether two objects collide is through math. We know information like an object’s position, orientation, and shape. We need to do the math to figure out whether that shape interpenetrates another shape.

The simpler the shape, the easier it is to do math on them. The easiest shape is actually spheres - since all points on a sphere are the same distance from the center, I just need to check the distance from the centers of the spheres to each other. The orientation isn’t important. Like so:

If the distance between the centers is less than the sum of the radii of the spheres, they have collided. 

Boxes are also super simple, because they have a bunch of properties that make the math easier. For example, all boxes have four sides. All boxes have their sides at right angles to each other. Thus, all boxes have sides that are also parallel to each other. As long as the boxes are all oriented in the same direction, we can assume that all box sides of the same orientation are parallel to each other for all boxes. Thus, we only need to know the position, the length, and the width to represent a box. Like so:

We can actually use math to represent these boxes. We know the position of the lower left corner of box A (x, y) and height and width, so we know the horizontal and vertical values for each of its edges:

Left edge: horizontal position = x, vertical position = all points from y to y + height

Right edge: horizontal position = x + width, vertical position = all points from y to y + height

Bottom edge: horizontal position = all points from x to x + width, vertical position = y

Top edge: horizontal position = all points from x to x + width, vertical position = y + height

We can use this to represent every rectangle, because all rectangles abide by the same mathematical rules.

Now let’s actually get into the detection of the overlap. When dealing with rectangles, it’s actually easier to tell if there isn’t a collision than if there is. I can isolate all of the situations where a collision is impossible, check for those, and then say if any of these conditions comes back true, there’s cannot have been a collision. If all of these conditions come back false, there must have been a collision. 

A collision is impossible if…

… the leftmost edge of box B is to the right of the rightmost edge of box A

… the rightmost edge of box B is to the left of the leftmost edge of box A

… the topmost edge of box B is below the bottommost edge of box A

… the bottommost edge of box B is above the topmost edge of box A

If any of these requirements are met, there can be no collision. But logic dictates that if none of these requirements are met, then there must have been a collision, because these combined conditions are the only criteria where a collision is impossible. That’s [contrapositive] logic for you!

Remember, this is only in 2 dimensions. In three dimensions, we’re not just talking about edges anymore, but sides - topmost side, bottommost side, leftmost side, rightmost side, frontmost side, backmost side. There’s more conditions to consider.

Now… let’s say that the boxes aren’t all oriented in the same direction, but we keep all the other factors the same. 

Do you see how this small change suddenly makes the previously “simple” math a lot more complicated? Now we need to start taking the angle of rotation of box B relative to box A into account before we can tell whether the boxes collide, and all of math needs to be updated for this. We can’t make the assumption that the edges are guaranteed to be parallel anymore, and our calculations need to reflect this. Now consider using other geometric shapes instead. That also affects the math, and it affects it in very complex ways.

Then remember that we have to do these collision calculations for each collideable shape against each other collideable shape in the scene. We have to do a lot of these calculations every frame all the time. This is why simple shapes are the best - because it simplifies the math involved.

So… why do we use boxes and not silhouettes? Because it makes the math easier.

Got a burning question you want answered?

Short questions: Ask a Game Dev on Twitter

Long questions: Ask a Game Dev on Tumblr