I’m only making a very basic game, and with a program that provides the base engine for you. But even so, that means hand-coding some pretty fundamental stuff, and it’s taught me that you can’t use the word ‘basic’ to describe anything you haven’t tried to code yet. I like to do stuff like The Hardest Logic Puzzle Ever in my spare time with a Google Docs spreadsheet (and xkcd’s The Hardest Logic Puzzle In The World in a text doc), but implimenting the most basic laws of game worlds is on a whole other level of complexity.

This bit of game logic, for instance:

When you hit something, stop.

Is impossible. I don’t mean hard, it’s just not the way algorithms work. You have to pretend it is, though, and the intricacies of that are what’s taken up most of my time.

The issue is that time progresses in discrete chunks in games, so just the word ‘when’ is problematic. Real life doesn’t really care if it’s not at exactly 1 second or 2 seconds that a man walks into a door, he just stops when he hits it. Code isn’t smooth, it has to re-examine and re-create the whole world sixty times a second, and there’s nothing in between these frames. Unless you want everything to move very slowly, some things are going to have to move more than one pixel at a time. That permits a nasty possibility: after 1 frame you haven’t hit anything, and after 2 you’ve already gone through it.

So collision logic fudges it one of two ways: the game either waits until you’ve already gone through something and pops you back out, or it looks ahead to see if you’re going to hit something and pretends you already have. The effect can be seemingly perfect, since these precautions are computed before the result is drawn on-screen, but it makes the underlying logic fiddlier than it ought to be.

Generally, though, it’s all fine so long as your character is a solid unchanging block.

platformers-smallOld-school platformer protagonists versus actual human proportions. Chick proportions not pictured.

That’s why a lot of 2D games have very compact, boxy characters: the game can treat them as a simple rectangle regardless of what animation they’re playing. Real people change shape much more dramatically when they run, jump and hit things. If you want a human-like character to dive headfirst into a wall – and I do! – you have to solve this insoluable problem for a thing that keeps instantaneously and dramatically changing size and shape.


I won’t get into why this is even more complicated, difficult and annoying than it sounds, but suffice it to say that the next time I fall through the ground in the latest FPS and plummet into the infinite grey limbo below, I won’t be thinking “Why can’t these idiots fix shit like this?”

I will be thinking “Why don’t these idiots account for shit like this?” though, because it only took me a few days of tinkering to realise a fundamental law of coding.

If there’s something you don’t want to happen, code it never to happen.
Then code what to do when it happens.

So early on, when I had so many collision bugs to fix that it seemed daunting, I spent some time on an “Oh fuck, I’m stuck” subroutine. It’s a little spiralling algorithm that searches with increasing desperation for a nearby space to teleport you to, should you somehow get stuck in solid matter. I know I’ll never solve all the minor or rare collision glitches that could happen, so I feel I should at least try to make sure they don’t break the game when they do.

Getting collision logic stable and robust was the hardest thing I’ve had to do so far, and the most intricate stuff I have planned for the game now seems trivial by comparison. I’m looking forward to the point when I’ve done enough of the coding that the question becomes “Is this fun?” rather than “Why doesn’t this fucking, fucking, fucking work?”

22 Replies to “Collision”

  1. Oh lordie. Can’t wait to playtest the next build and make you weep bitter tears.

    “I have to code this bit again? Ffff-“

  2. I’m looking forward to the point when I’ve done enough of the coding that the question becomes “Is this fun?” rather than “Why doesn’t this fucking, fucking, fucking work?”

    Please believe me when I tell you this is exactly backwards. Your top priority needs to be making the gameplay fun. That way you can make huge sweeping changes to the design without it being a big deal. When your collision detection is awesome but you realize it would be more fun if he could pass through walls like they were jelly, just the thought of ripping all that code out is going to kill your enthusiasm. If collisions are really, truly vital to your gameplay, stick with the easiest square bounding box you can for now.

    I know the bugs stick out like a sore thumb, but it will be so much easier to fix them the right way once you’ve actually decided on the design. Full disclosure: I haven’t finished any of the games I’ve started, because I don’t listen to my own advice.

  3. As a student Game Development/Computer science, I’m all too familiar with the Issues you are describing. The article was nice to read and that law is very useful. It perfectly describes what you end up doing a lot (this value should not be null, but what if it is!? What if the value I am dividing over is 0?).

    The funny thing is that you end up being proud of a system, a few lines of code, that no one ever knew was needed. And it can be easy to forget you have to test if it is actually fun.

    I recommend breaking all coding challenges into tiny pieces, especially when you think you already know all the steps to take, so you can quickly iterate and easily spot problems that could be impossible to find in a big program. It also allows you to test for fun more often.

    Have fun!

  4. As someone who is just learning to code, I can sympathize with your problems, albeit in a much, MUCH smaller scale than your own.

    I know I will take those fundamental laws to heart from now on. I guess it’s good to get input from others, because as well developed and thought-out your point of view is, there still might be something hiding that someone standing a few feet (Or yards, meters, miles, etc) to your side will see as a glaringly obvious thing.

  5. Also as to your changing-shape problem, what if you broke him down into several little boxes? I know this would require an assload of additional coding (Rather than say, one box as you provided an example of), but for something that changes shape, boxes on maybe hands, arms, head, upper and lower torso, legs and feet might make collision work a bit better.

    Again, I’m still a very green coder, and have yet to even start work on anything more complicated than a simple text adventure, but I like to think that my input might still be valuable.

  6. Chynes, this post isn’t about getting it perfect, it’s about getting it working. Until it’s working, you can’t know whether it’s going to be fun. I was looking forward to the point where I had it working, and could decide if it was fun.

    I did the simple box thing as soon as I’d figured out basic collision, and it was good. But it was abstract, and I needed to know if this made sense and felt right for a human. I didn’t wanna start making levels for this movement system before I knew it worked.

  7. Well done, man. Keep going! Really cheered me up to see you were persevering despite all of that stuff.

    You reckon this’ll change the way you review regular games?

  8. i used GM8 for a while, and made a few games, and had the problems you described, my stickman changed sprite every time he moved. However, i believe (don’t take my word, it was years ago) that you can change the mask of an object depending on what state its in (ie, is there a solid obj below it) and then do the collision detection on it. that way to can still use sprite that looks like a nicely shaped dude, but let the program think its actually a rectange

  9. Heh I’m actually working with a larger group on a game with Unity right now where one of the recent bugs was exactly due to that delay in checking for collision. Basically there are instances where the player moves so fast, the avatar has gone through the outer walls of the level before it has time to check if it’ll be hitting the wall within the next tick.

    Our solution… make the walls thicker. *Cough*

  10. i’ll be looking forward to it!
    Good luck on the game and Don’t rush it!
    wait doesnt Yahtzee also make indie games?

  11. Yahtzee used to make games. He made three really good ones, and a fourth one which basicly tried to ruin everything else but was still semi decent. They were all adventure games that did huge dick moves he is not found of.

    Incidently, despite them being VERY good, in both plot, art style, and programing, he’s disowned them, saying that as far as he cares he’s never made them.

  12. Yeah, basically Yahtzee was a game developer and writer who suddenly transformed into a fountain of loathing, shedding his previous identities like so many dried up skin layers. I loved his site, and his games were pretty cool, but I started to get tired of the pandering and game-bashing in the Zero Punctuation series about a year ago.

    I do still watch them occassionally, and they are still good for a chuckle, and it’s not that he’s terrible at judging games either, but I can only stomach so much of the snark.

  13. Here’s a trick I learned from the Quake engine to simplify collision handling considerably: if you enlarge the building blocks the world is built from by the radius of the player, you can treat the player as a point. Then you can check for collision between frames with a line segment test, which isn’t so tricky, and if there is a collision, you can move the player to the point of intersection.

  14. Wow, that’s smart. How does it deal with the player’s bounding box extending by a different amount in different directions? Presumably he’s taller than he is wide, for example, which dimension should the world expand by?

  15. If your building blocks are axis-aligned rectangles, you can move the top and bottom of the rectangle outwards by half the height of the player, and you can move the left and right sides of the rectangle outwards by half the width of the player.

    It gets trickier if your building blocks are arbitrarily shaped, like Quake’s are. If I recall correctly, Quake has three hard-coded collision hulls to support three sizes of moving object, all perfect cubes. A testament to how much you can simplify without anyone noticing.

  16. “Why don’t these idiots account for shit like this?”

    The thing is they do. When many games notice you’re outside the map they warp you back in. And it’s these “Oh shit get the player back in the game” hacks that are the source of many glitches.

    Just think of HL2, if an NPC gets stuck under/in/on/whatever an object they warp to the next bit of the story. The speedrunners noticed this and abused it to get through the in-game cutscenes.

  17. “Wow, that’s smart. How does it deal with the player’s bounding box extending by a different amount in different directions? Presumably he’s taller than he is wide, for example, which dimension should the world expand by?”

    Assuming a 2D world, break it into two separate scaling operations. Scale the world’s x axis by the character’s width, and then the world’s y axis by the character’s height.

    Note that this trick only worlds with convex geometry. So a concave shape needs to be broken into convex parts. This is one of the reasons why Quake and its kind force level designers to use convex brushes when making maps.

    But it does allow you to easily calculate when the character hits the wall during collision updates as a line verses plane intersection test. No more fast moving players getting outside the world between collision updates.

Comments are closed.