Project Good Robot 11: When Stuff Collides

By Shamus
on Sep 9, 2013
Filed under:
Good Robot

A running theme of this project is that 2D game development is like programming in Easy Mode. Everything takes less code, requires fewer steps, uses less CPU / memory, and has a larger margin for error. It’s amazing to be able to just make something without constantly getting snagged on annoying tech issues, performance trade-offs, and gameplay compromises.

Take collision detection, for example.

Early in the project I used rectangle-based collision. If I shot at a bad robot, the game would check for a collision between the bullet and the square region where it was drawing the enemy.

Okay, pixels don’t suffer zooming nearly as gracefully as polygons. Then again, you can fix this by just not letting the player zoom in too far. Good luck keeping the player from looking at the walls too closely in your FPS.
Okay, pixels don’t suffer zooming nearly as gracefully as polygons. Then again, you can fix this by just not letting the player zoom in too far. Good luck keeping the player from looking at the walls too closely in your FPS.

But this is a crappy solution. Basically every enemy is shaped like a box for the purposes of collision. That’s good enough when shots hit center-mass, but it’s really unsatisfying to have bullets score a hit when they pass through the (usually empty) corners of the rectangle. Unless I’m going to make all the foes square, this isn’t a viable technique.

So I change it to check using distance calculations:

Now I only score a hit if my shot enters the purple circle.
Now I only score a hit if my shot enters the purple circle.

This turns the robot hit zone into a circle. Now, this still isn’t perfect. Sometimes bits of the robot poke out from this circle, and bullets go through those points. But this is hard to notice and you can’t really see it happening unless you catch it in screenshot. This is basically good enough.

Well, until we get here:

You’re a big one, aren’t you? What have they been feeding you?

Neither of these collision systems is good enough in this case. This boss is very large and its shape is complex. Having bullets pass through parts of it is frustrating for the player. Having bullets strike empty air is unsatisfying. Neither case is acceptable. There’s no way around it. We need pixel-accurate hit detection.

This NeHe tutorial is the usual go-to approach for hobbyists. It’s pretty brute-force, but it gets the job done.

In the abstract, it works like this:

You zoom in with the rendering camera so that the bullet (or whatever point you’re checking for collision) would fill the entire screen. Then you tell OpenGL to go into “select” mode. Now start drawing stuff that you think this bullet might be crashing into. Give each one some sort of identifying number.

Okay, OpenGL, here is object #1. (Draw the first thing you think the bullet might crash into. It might be one polygon or ten thousand. OpenGL will treat all of them as “Object #1”.)

Then you give object#2, #3, and as many different objects as you’d like to check.

OpenGL won’t actually draw this stuff. Instead, it will keep a list of every object that lands inside the screen. (And remember the screen is super-zoomed in on the bullet, so anything that is within the screen is touching the bullet.) When you’re done, take OpenGL out of select mode and it will give you the list of stuff that would have been drawn. You then have a list of all the stuff the bullet is touching, and can respond accordingly.

Now, the most obvious objection to this approach is that it’s slow. You’re basically doing a little rendering loop for every single bullet in play. That sort of thing can get out of control fast. I also dislike it because it’s really cumbersome. It takes a lot of lines of code to make this happen. You need to do all the math to zoom the camera, you need to set up select mode, you need to gather up likely candidates for collision, you need to perform some sort of abbreviated render loop to draw those candidates, you need to extract the list from OpenGL and sort through it, then you need to clean everything up and put the camera back where it belongs.

In a 3D game, things are even worse. We’d have to take some other approach entirely. It would be time to bust out the trig textbooks and start intersecting lines (bullet paths) with planes (the polygons of all the stuff you’re shooting) to find out which dudes the player has shot. (Or whatever stuff is running into other stuff in this game.) This is also slow, complicated, and really annoying to debug.

But we’re working in 2D, and we’re drawing all of our robots from a single texture. Right now, that texture looks like this:

Sprites are 64×64 in the original. I dunno if I want to mess with that.  I’ll think more about art once the tech is working.
For the purposes of illustration, I’ve made the transparent areas magenta.

This gives me an idea. Normally I load this texture into memory, hand it off to OpenGL, and then throw it away after OpenGL makes a copy for itself. But instead of throwing it away, I’m going to hang onto it. And I’m going to switch back to using the old rectangle-based collision I started with. So let’s say the player shoots at a robot:

BZAP!

For the purposes of what we’re doing here, our bullets are single pixel in size, even if they’re visually massive and giving off a little cloud of glowing particle effects to make them seem even larger. If we detect our bullet has landed inside of the rectangle of a robot, then we ask the robot where it’s drawing from on the sprite sheet:

Not very impressive looking outside the normal in-game context, is it?

How far is the bullet from the upper-left corner of the hit box? 25% of the way across and 74% of the way down? That would mean the bullet is touching this single pixel of the robot’s texture:

64×64 pixels of glorious detail. Eat your heart out, Crysis!

I look at that pixel in the texture data I saved earlier and check to see if it’s opaque. It is? Then the player just shot this robot.

Now we have pixel-perfect collision for basically free, in just a couple of lines of code.

The only problem is this:

Bzzzzzzzzz.

This is some sort of spinning… sawblade… cutty-thing. I’m going to re-do the art for this one. Someone pointed out it looks kind of swastika-ish, and not like “shuriken made of scythes”, which is what I was kind of going for. Of course, I might re-do the art for everything. The robots are basically just the point where my prototypes looked acceptable enough that I could ignore them and go back to coding.

At any rate, this reveals a slight problem with collision. The blades are spinning very fast. The bullets are moving very fast. The robot is moving fast. And outside of that circle in the center, the robot’s texture is about 80% empty space. Which means if bullets pass through the area where the blades are, they only have a 20% chance of landing on a solid pixel each frame. If the bullet spends 5 frames travelling through the robot’s space, that means it still has a ~33% chance of passing all the way through without hitting it at all.

You could excuse this by saying it’s like shooting through helicopter blades: Some rounds are bound to slip by. But it doesn’t feel right. It feels like collision detection is broken.

There are a bunch of ways I could fix this. The most obvious would be to have it trace all the points along the bullet’s path if it finds itself in the hit-box of a robot. That would help, but I think there would still be a chance for the bullet to pass through when the blades are moving fast. A more lazy way would be to make some of that empty dead space between the blades semi-opaque. An opacity of 1 (out of 256) would be invisible to the player but would cause bullets to collide the way your eye expects.

A well. When in doubt, put it off. I can make this call later after I’m sure I’m done messing with the art.

Enjoyed this post? Please share!


A Hundred!1101 comments. Quick! Add another to see if this message changes!

From the Archives:

  1. Yerushalmi says:

    What’s wrong with the “more lazy way” that you’re still “in doubt” about it? It looks like a good solution.

    • Chefsslaad says:

      I guess a problem would be that you could get a collision if a fast moving robot moves into the path of a bullet after it has passed.

      • kdansky says:

        That problem is completely unaddressed anyway. There will be annoying problems when bullets or robots become fast enough to move more than their own length in one frame, because they can literally pass through each other: Imagine an X, and the four end points are start / end of the two objects. If you only detect collisions at the end of a frame, all four spots are fine, but they moved through each other in the middle.

        What you need to do is a sweep-sphere algorithm. It’s actually fairly easy to implement, and very good. The downside is that your characters will have to be either boxes or ellipses for it to be somewhat easy. The next step for big enemies is to have more than one hit-box, layered over each other. I could post some code, but it’s Scala, and has at least one bug. ;)

    • MALfunction84 says:

      You could add some radial motion blur between the blades. Then you have semi-transparent pixels for hit detection that double as art.

      • rofltehcat says:

        I think that would be a good solution for those roto-thingies and would also maybe change its look ;)
        After all, maybe the robot was hit but you just didn’t see it in time? A little impact explosion could make it even more feasible (though you probably already have those).

    • ET says:

      Yeah, Shamus, I think the “lazy” way with the not-quite 100% transparent alpha would be the best.

      Why?
      Let’s take the more accurate collision detection to its logical extreme:

      So, you’ve detected a hit inside of the rough hitbox, and it’s an enemy that has rotating bits, and thin sections.
      If you trace all the pixels along the bullet’s path and find one where it hits, that gives you (after some quick algebra) the time between this frame and last frame, where the bullet hit the robot.

      But wait!
      You’re only checking one frame of animation to get this time when it hits.
      The correct solution is to check both frames, and also all the in-between-ed frames for whatever sub-frame timeslice you’re using.
      You did write the code for in-betweening 2D animation frames, right?
      And it is both non-buggy and feels right, yes?

  2. Abnaxis says:

    Would it still be cheating to put a little motion-blur effect behind the blades on the sprite sheet? Then you get the best of both worlds–the sprite looks better, and hit detection is cleaner. It’s like not cheating at all!

    EDIT: Suggetion number 2: Instead of doing all the poinst along the trajectory, why not just do all the points the bullet moved through during the last frame? The way it is, it seems like you’re going to wind up with the bullet inconsistently phasing through thin sections even if it isn’t a sawblade otherwise.

    Why not take the pixel from last frame, the pixel from the current frame, draw a line segment between them, and check that? Is there an OpenGL call to return the points that make up a line segment as a vector of pixels? If so, that’s like 5 extra lines (Tracking points takes a couple assignments, draw line is one line, grab pixels is one line, iterating is enclosing your existing code in a loop for the last extra line) on top of what you’ve already got.

    EDIT 2: Ugly scaled-up boss eyeball is ugly.

    • Bropocalypse says:

      Do your textures support different levels of alpha? If so you could stick a circle behind the robot at 1% opacity. Virtually invisible and should satisfy the detection, yes?

    • Deoxy says:

      Instead of doing all the poinst along the trajectory, why not just do all the points the bullet moved through during the last frame? The way it is, it seems like you’re going to wind up with the bullet inconsistently phasing through thin sections even if it isn’t a sawblade otherwise.

      Something very much like this is what I was going to suggest, as well, though I would add that you should check for hits if it was in the hit square this frame OR last frame – only exceedingly fast shots that clipped a rectangle would really have a chance of not being checked.

  3. Corpital says:

    Just like Half Life 2. You managed to escape your persecuters and solved the hitbox problem on the seesaw and everything will be just fine? Nope, have some manhacks to mess everything up.

  4. You could create an arc starting from the point of the bullet with the center of the bad robot as the origin. Make the arc as big as however fast the robot is rotating * the time between frames. If any of the pixels on the arc would have hit the robot, it’s a hit.

  5. Hal says:

    Huh, there are boss robots now. Interesting.

    Out of curiosity, I think in the first post you mentioned trying to add destructible terrain into a game (although that was before you went 2D.) I haven’t heard that mentioned at all since then. Is that still a thing? Or did that go out the window with the shift to 2D?

    • Volfram says:

      That went out the window with the shift to 2D. Not Project Good Robot(the 3D one with destructible terrain) and Project Good Robot(the 2D one with the cute little evil robots) are two entirely different projects.

    • Piflik says:

      The Marching Squares Algorithm would make for pretty easy destructible terrain. It relies on a 2D-array of boolean values (or 0/1) to determine which tile to draw where. If you can change the entries in the array when you shoot it, you can make terrain disappear. You could even give each tile a ‘health’ value, just use bigger numbers. Everything bigger than 0 is still there (it is also possible to use different graphics to represent the damage done to the tile), once it reaches 0, the tile disappears. (and I think there already is hit detection with the terrain…at least I remember seeing some rocks fall from the ceiling in one screenshot…)

      When I think about it, I guess Red Faction’s Geo-Mod Engine did something similar with Marching Cubes (but I haven’t read anything on that subject, it just seems like that from my memories). And the base for Red Faction was Descent 4, which is a nice circle to this project XD.

      • Volfram says:

        Think I’d read that Red Faction actually used subtract brushes for the Geo-Mod tech. Actually, that’s another potential option for this.

        You are correct, however, that Marching Cubes should lend itself nicely to destructible terrain.

      • Piflik says:

        Addendum: Rocks fall, everyone dies.

        Falling rocks from destroyed terrain tiles damage the player and the enemies. The player can use this to his advantage, but he has to be careful and not wildly shoot everywhere.

  6. Matthias says:

    What about adding a kind of motion blur between the blades? That should fill it with something not completely transparent, and might look good in motion.

    Edit: Ninja’d! I should really refresh the article after reading and before commenting :-)

  7. Volfram says:

    Since you’re already using texture-based collisions, what’s to stop you from making a new texture specially for collision detection? In this case, you could replace the collision texture for the Spinny-Bot with something that covers everything you actually want to check?

    And hey, it’s not like you’re using a lot of texture memory yet, anyway.

    Also, I personally would probably use 50% as my alpha collision threshold. Though if you’re using a special collision map, there’s no reason not to use binary.

    Personally, I would have used a collection of collision areas for the big ol’ Boss Robot. I’m seeing 3 circles and perhaps a series of lines for the gear cogs.(My lines have thickness, it’d be pretty easy to make it work)

  8. Abnaxis says:

    I just thought of something while making my suggestion earlier: isn’t your collision code dependent on your frame-rate now? I mean, I know this 2D stuff is light-weight, but if someone is stressing their machine with other programs (say, running fraps and streaming on livestream and recording on Vent Josh) enough to slow down the FPS, isn’t that going to completely bork-up your collision detection as it’s coded now?

    I mean, I guess it’s the same problem as you’re talking about with the buzzsaw bot, but I think the real problem is deeper and more serious than that

  9. WILL says:

    Just use circle collision for this enemy and not others? If it’s spinning very fast, it might as well be a circle.

    • evilmrhenry says:

      More generally, using multiple collision-detection methods; circles, rectangles, and pixel-perfect. Make it so that a enemy can be built out of multiple areas.

    • Piflik says:

      It is quite bothersome to create collision detection that functions differently for different objects. You would first have to determine what object you hit, before you can calculate if you hit it…of course you can first use a very easy collision detection, like a bounding-circle or oriented-bounding-rectangle, and then test against recursively smaller bounding-areas that fit the actual shape of the object better, which is called a Bounding-Volume-Hierarchy (in 3D ;)), but Shamus’ test with the texture is really clever and as he said practically free. But he could use a separate ‘collision’-texture, so he can tweak the hitboxes of the objects separately from their visual representation. (would, of course, be more work for him, especially if he wants to change the design of an object or move objects to a different spot on the texture)

      • Svick says:

        It is quite bothersome to create collision detection that functions differently for different objects.

        Isn’t that what object-oriented programming (specifically, virtual functions) was invented for?

        Though assumes you always do collision between a pixel-bullet and some object, not between two arbitrary objects.

        • Piflik says:

          Sure, but if you have two different robots, each with its own type of collision-detection (say one with a oriented box, i.e. testing the distance in X and Y directions separately, one with a sphere, i.e. actual distance) one might be hit and the other not, with the same robot-position/projectile-position constellation. So you would first have to hit the object, and then determine how you you would detect a hit. Just like in the first screenshots. The one with the box is hit, the one with the circle not. You have to know the type of collision geometry before evaluating a hit.

          (Of course it can be done, it is not really too difficult, but it is more code, and roughly twice the collision checks, in this case. If you create a complete BVH, one more check doesn’t make much of a difference)

          • Cerapa says:

            The entire point of using a virtual function is that you don’t need to manually determine the how.

            Currently it seems to have a bounding box as the initial check and then the indepth check, so the code might just be as simple as:

            if(robot.checkboxcollision(bullet.x, bullet.y) {
            if(robot.checkcollision(bullet.x, bullet.y)) {
            //blablabla
            }
            }

            with checkcollision() being overridden by the particular robot. If you don’t do anything stupid, then you will only have to write 1 collision per non-standard collision type, which tends to be the universal minimum with these things.

          • Zukhramm says:

            No, that’s the thing you can avoid. It doesn’t matter what type of check the individual robots do if they’re all done through the same method.

        • Volfram says:

          Having a single unique case in the entire game will give most experienced programmers a conniption. It’s anathema to good program design. If the only thing you can think of to fix a problem is to break consistency, it typically means there’s a much better way to do it that you’re not thinking of.

          Having a unified combined collision engine(one capable of doing per-pixel and procedural-space detection) is an OK idea, but it usually comes off as a bit sloppy.

  10. DGM says:

    You’ve got the whole article on the front page. It’s a bit much.

  11. MrGuy says:

    Curious – given the projectiles all LOOK like they’re longer than a single pixel, would it be hard to treat the projectiles as such for collision detecting purposes? If the projectile was a short line segment (say 5 pixels long, which seems totally supported on screen), you could check if ANY of the “projectile pixels” collide.

    This would greatly reduce the “through the spinning blades” problem without really making the idea that much more complicated.

    I guess this is five times as many pixels to check when we do a check, but this looks like it ought to be fast…

    • Tizzy says:

      Along the same line of thought, since the concern here is to make sure that the collision looks right, I was wondering if reducing the bullet to a single pixel (when it is depicted some sort of halo) was going to make it look wrong.

      At the same time, the gameplay looks rather frantic, so I’m not sure that I would notice any of it, except maybe if Shamus used a single square hit-box on a really big robot…

  12. Matt K says:

    Perhaps adding a few more arms to the thing would alleviate the problem. Less shuriken and more buzz saw. Then at least the odds of passing through would be pretty small.

    • Lovecrafter says:

      I second this. You could post screenshots of it so we can act as a pseudo test group to make sure, but one extra arm should probably stop the swastika comparisons and help reduce the missed shots. Personally, I’d go for an extra 5 arms (for a total of nine), to make it even more wicked-looking.

      Also, I actually like the current robot look and I hope you’ll keep it for the final product.

      • I think nine would be pretty busy. Five might be OK. But I don’t think this approach is needed for collision detection (and it doesn’t generalize). I think there have been some cool suggestions presented anyway, including Shamus’ original notion about very slight opacity.

  13. Neko says:

    I can’t help but notice the large A B X Y on your sprite sheet, Shamus. Please tell me you’re adding some obnoxious quick time events!

    • ET says:

      Make sure that the game always shows the exact same A B X Y for the button prompt, regardless of controller mapping, or whether or not they’re using mouse + keyboard!
      Also, make sure it’s super tiny and off to the side of the screen too, and not centered around your robo-guy.
      Also, make sure it replays all of the cut-scenes from this level.
      You’re adding unskippable cut-scenes, right?

    • Lovecrafter says:

      One of the breather levels will have you go into a robot bar and ask people where you can find some robot sailors.

  14. Tizzy says:

    Shamus: I think you forgot to put a cut in the post for the blog’s front page.

    (I mean, a “read the rest of this stuff” link)

  15. Alan says:

    It’s not a large difference, but I would have just gone with a second bitmap for the collision area. As a side effect, it would allow for sections that are colored, but not something you can actually shoot. For example, you might bake lightning shooting off the top of the robot into the texture, but not want the lightning to be a target.

    On the other hand, this requires maintaining the second bitmap in sync with the original and dealing with two bitmaps in memory.

    • Rick says:

      I’m not a graphics developer but that occurred to me too. Let each robot optionally specify a second sprite on the texture to set as its collision area instead of its rendered sprite.

  16. Daniel says:

    If I have learned anything from playing lots of games, the proper way to handle this issue is as follows:

    1. Release the game with hit detection as is.
    2. If there are enough consumer complaints, continue to number 3, otherwise move onto next game.
    3. Release DLC which corrects the issue (along with 1 new enemy type and 3 new skins for your avatar!)

  17. defaultex says:

    A solution I liked was to build quad-trees for each object and test agaimst those. Using position before and after motion to form a line, project that lime onto quad-tree nodes in it’s path. Similar to SAT collision but the tree cuts back on points to test.

  18. Felblood says:

    I’ve played with a couple of solutions to this particular problem, before.

    You might want to create two separate sprite sheets, one to give to OpenGL and one to save for collision detection. That way, you can tweak collision mechanics without messing with the visuals, even by 1%. This is probably easiest to do code-wise, but might be a pain to maintain down the road, especially if you do decide to re-design the robots.

    –OR! you could just create a special case for collisions involving spinning robots, and have them use distance collision on any bullets that fall within their box. This is more work to code, and less versatile, but you don’t have to worry about keeping the sprite-sheet and the collision mask in sync.

    • Volfram says:

      You’re now the 3rd person I can see to suggest a collision sprite sheet. I hope he notices one of us.

      I feel better that it wasn’t just me.

      • Shamus says:

        Heh. I read every comment, so yes I noticed. I was just thinking, “Man, I hope these people notice each other.”

        • Rick says:

          Not only that, but they noticed you noticing them noticing eachother and putting them on notice.

        • felblood says:

          Okay, I should have noticed the older of the other two, but I think the other one ninja’d me. That’s the trouble with posting and eating; it takes too long from page load to comment submission.

          That said, I don’t think that a sprite mask is the right choice for this particular project. The stated goal is to see how he can use his coding mojo to minimize the art assets needed. So using distance collision for the sawblades instead of maintaining a whole new suite of sprite sheets, just feels right.

          Plus, he already wrote and tested a distance collision function.

          • Zorn says:

            I’m (re-)reading this way way too late, but whatever, as if that stops anyone on the internet. This way I get to prove my awesome intellect/foolishness for future generations of late readers…

            Couldn’t the collision detection sprite sheet be auto-generated on startup by merging (say) 359 copies of the original sprite rotated by 0-359 degrees for the rotatable sprites, and a direct copy of the non-rotatable ones?

  19. Alfie275 says:

    Perhaps define a color in your sprite sheet just for collisions. At the moment magenta is transparent, maybe turquoise could mean transparent but solid?

    • Kian says:

      Magenta isn’t transparent, that’s just for us to see the transparent areas. He’s using the alpha channel for transparency. If he showed the actual sheet he has, however, the browser would not render the transparent areas (since they are transparent) and we’d just see the sprites against the background. It’s just convention to show the transparent areas in a striking color you are unlikely to use. The actual areas are generally colored white, which is the default color when you create a new image in most image editing software. Setting alpha to 1% would do the same thing as defining a transparent but hittable area, since 1% alpha is essentially invisible, but the computer would register it.

  20. thark says:

    Not-too-ancient shmups generally have simple hitboxes where the player’s hitbox errs on the side of being smaller than the sprite (or is deliberately just a teeny part of it, in bullet hell cases) and enemy hitboxes err on the side of being larger than the sprite. Dirty, but avoids any player frustration from “unfair” hits/misses (as the case may be).

    • Robyrt says:

      In that same vein, 2D fighting games usually have hit boxes made up of a handful of rectangles for super fast checking, and then reposition the boxes away from the sprite to get the correct feel. For example, a low sweep kick will have a hitbox ending at your ankle, so the hit animation will always line up with your foot around the back of their leg, and extending downwards past your leg to the floor, so that two characters with different animations won’t miss each other.

      This isn’t as intensive as having a collision texture, but it does require way more hand-crafting, which is a bit much to ask of a side project.

  21. Steven Cannavan says:

    Just a quick suggestion, when it comes to collision detection your always going to leave yourself open to unintentional misses if your just detecting after discrete steps, the more accurate way is to test where your going / have been and as your dealing with pixel collision your best option might be to draw a line.

    If you detect a bullet has or did in the last frame enter the collision box just ‘draw on top’ the line between the current and last position of the bullet (a ray) and if you detect a solid pixel you know you hit the object.

    This won’t completely solve the problem but its a start.

    • Zak McKracken says:

      Was going to suggest something similar:

      My first idea was analytically calculating the trajectory of the bullet through the robot’s hit box. If the robot is rotating that would be in the rotating inertial system and look something like:
      xr(t) = (x0 + Vx*t) * cos (omega*t)
      yr(t) = (y0 + Vy*t) * cos (omega*t)
      (y0 and x0 being the coordinates where the bullet entered the hit box, t the time, Vx and Vy the velocity components in “regular” space and omega the rotational speed).
      You draw the curve in robot-coordinates on the robot sprit and if it intersects with the robot, you have a hit, if not the bullet will just squeeze through the rotating arms.
      … then I though this might be more complicated than needed:

      just plot a short line from the last frame’s position of the bullet (on the sprite) to the current one, and if that intersects with the bot, you have a hit. fewer computations per frame, no trigonometry functions to evaluate, and it should give a realistic result. This regards the robot as non-rotating during the frame, so it might not be ideal, though.

      And THEN this occurred to me: Treat the bullet not as a point but as a line whose length corresponds to the distance travelled in 1/60th of a second. Then the above method becomes much more accurate, and collision detection will be certain to never miss a hit, even if you’re shooting at a 1-pixel-thick wall. The only thing still missing then is the movement of the robot. Because (as with single-pixel checks) the assumption is that nothing of significance happens between frames.

      Maybe that’s still not ideal, but I’d say that making the bullet bigger should be better than making the robot collision area bigger than its visible size.

      • Zak McKracken says:

        Oh, how I love thinking about these things rather than doing what I should!

        I think the watertight way would be to define a polygon for each robot, then extrude that along the z direction (i.e. normal to the screen), but skew the resulting shape so that the new polygon is where the robot was in the last frame.
        Then make a line (you don’t have to actually draw it, but imagining will be enough, I think) from the current position of the bullet to where it was be in the last frame, plus the same z-offset as the next-frame robot has. This means: You are now in 3D space, with the z coordinate representing time.
        A simple collision check or visibility check (or whatever, just set the perspective to the bullet position, view along the bullet flightpath and hav OpenGL render the center pixel), and you know if robot and bullet trajectory intersect. And exactly where (and when!).

        This is probably more complicated (and possibly slower) than needed, but it would be impervious to problems like very thin geometry and fast movement:
        Let’s say a robot arm is 6 pixels wide, and moves at about 8 pixels per frame (which means it still needs 4 seconds to get across an HD monitor!). Your bullet makes the same distance in two seconds, so it covers 16 pixels per frame in opposite direction — so there’s a 1 in 4 chance that in no single frame the bullet will be where the arm is! Thus simple static position analysis with single-pixel bullets will probably fail more often than is acceptable, and some way of looking at what happens between frames is necessary

  22. MelTorefas says:

    I actually REALLY like the current art style on pretty much everything. It has a sort of old-school MegaMan feel to it that I think is great. I hope if you do change the art you keep the same style, with those big shifty glowy eyes and silhouettes. XD

  23. krellen says:

    The most important question is yet unasked: when do I get to play?

  24. Ravens Cry says:

    I love the sheer elegance of your collision system. I am neither an engineer nor a programmer, but even I am not blind to its beauty.
    This might be one of your few projects, if you release it, my computer could run well, and it sounds fun.

  25. Lord ZYRK says:

    You could always keep the spinning scythiken of death and just claim you are fighting space Nazis.

  26. Chris Davies says:

    For your animated enemies, you can take advantage of the fact your collision masks are essentially 1 bit per pixel, while probably being stored as 32 bits per pixel. You can pack your whole animation cycle in to a single mask.

    Then, to do collisions, you take the frame number, do a some modulo arithmetic, shift 1 << by the number you get and & it with the appropriate pixel. Pixel perfect collision detection for animated figures in only a couple more clocks than for statics.

  27. Rosseloh says:

    Am I the only one who doesn’t have a problem with those robots looking like swastikas?

    Anyway, I bet adding a single extra arm to the little guy would fix that problem right up.

    • Ravens Cry says:

      Some countries have actual laws against displaying swastika, so it’s not just an ‘Ooh, somebody might be offended’ issue.

      • DoctorSatan says:

        The swastika is actually a Hindu symbol. But whatever.

        • Ravens Cry says:

          It’s also a Buddhist symbol, a Jainist symbol, a Navajo symbol . . . etcetera, etcetera. That doesn’t change German (among other countries) law, though, at least in Germany, they make an exception for Jainism, being on their holy symbol and all that.

        • Zak McKracken says:

          It surely is that, and more.
          The problem is that if you’re showing one in Germany, that will not be the context in which it will be regarded.
          It is very problematic to disallow the showing of certain symbols or flags, but there was a very very serious thing that happened a few decades ago, and that demanded very serious consequences that would be enforced, too. It would have looked a bit funny if politicians had claimed to have moved on from the Nazi era while some more extreme groups still ran about waving Nazi flags and stuff… still, there is a valid argument that Germany has not done enough after the war to get rid of that ideology, or too much, or the wrong kinds of things … but this is not the place to discuss that.
          Let me just say that the most significant form of terrorism in Germany in the last few years was from a Nazi group, and it is a touchy subject.

          That said, Shamus has probably already updated the robot. Simply changing the number of arms or replacing the straight outside edges by spirals (scythes usually have spirally-curved edges) should do the trick.

          • Kian says:

            Curious about the law; is it actually swastikas that are illegal, or is every swastika-like shape or symbol that is illegal? Because the shape seems easy to come across. Meaning, do you have to be intending it to be a swastika, or can anyone see a swastika in a squiggle and have it removed?

            • Ravens Cry says:

              I am no lawyer, but reading the quotes in Wikipedia’s article on the law in question, “Symbols which are so similar as to be mistaken for those named in sentence 1 shall be deemed to be equivalent thereto.” that sounds to me like, yes, accidental swastika are still prohibited.

  28. DoctorSatan says:

    I use 2D arrays for collision detection. There is a screen height by screen width array which has integer values for everything. Say, 1 for background, 4 for missiles and 7 for enemies.

    Then depending on how many things are on a pixel, that value is added to that pixel. So if on that pixel, there is background (which is on every pixel) and a part of a missile, then the value of that pixel is 5.

    Then we check if the value of a pixel is 11, then there is a missile and an enemy, so both are then destroyed.

    You can even send this to the draw function which will draw the thing based on this and another array which tells the function which type of missile it is.

    Probably not as efficient as those fancy vectors, but hey, works for me.

    • Kian says:

      Don’t you have to do a fair bit of upkeep on that matrix? Or do you recreate it each frame? On an HD screen (1920×1080 px) that’s over 2 million pixels. Aside of the 2 MB you need to allocate (assuming you’re using 8-bit chars, it’d be 8 MB if you’re using 32-bit ints), it seems like a fair bit of work to check it. Also, you need to be careful about the values you use. How do you differentiate between, say, 1 + 5 and 1 + 2 + 3? Although if you’re using masks instead of values…. But then what about many similar items intersecting?

    • Cerapa says:

      The OCD and efficiency-loving part of my brain crashed after reading this.

      Then again, I’ve seen weirder things that are faster than some other less crazy systems despite the protests of my brain.

      Do you have it running at a reasonable speed?

  29. Jarenth says:

    Is that an experience bar I spy?

  30. bigben1985 says:

    You know, I see the screenshots and all I can think of is “Man, I want to give this game a try =/”

    Good job writing, as usual :)

  31. Kaeltik says:

    Do you think there could ever be a Kickstarter for this?

    • Volfram says:

      I don’t think that would be necessary. I’m pretty sure the moment Shamus posts something that says “Here, give me some money and you can play my game,” he’s going to get ALL OF THE MONEY. For the purposes of selling a game like that, Kickstarter is vastly overshadowed by things like PayPal, the Amazon marketplace, the Humble Bundle(through which Bleed and…something else I recently bought but can’t remember are sold), and Steam Greenlight(where all things begin and all things end).

      That, and I have a vendetta against Kickstarter.

      • What follows is speculation:

        From what I have seen of Shamus talking about his projects, he doesn’t want to get tied to what is essentially him messing about with code. To produce an actual ‘thing’, would require being tied to that thing.

        In any case, Kickstarting a project is often required when expenses are needed to be covered. Since this is a one man job, expenses are near zero. Since he seems to be bringing enough cash in from other sources to pay for living I agree with Volfram; if this does go to market as a final product, the income from doing it with fewer third parties would be much better.

        Maybe something like GOG for people who aren’t readers of the blog to go for a wider audience.

      • Blanko2 says:

        Steam greenlight is the worst thing, Fyi

    • Felblood says:

      He already has a Paypal. Look in the right sidebar.

  32. SlothfulCobra says:

    Many of the 2D shooters that I’ve played just use the simple trick of placing the hitbox within the enemy sprite as a kind of weak spot, as opposed to just chipping the enemy to death with hits all over their sprite.

    All of your little robot enemies already have a big glowing robot eye that’s just begging to be aimed for, it would make a great weak point.

  33. Jake says:

    Maybe set the fast spinning one up with super low health and leave the hard to hit option in as a single boss monster.

    Its not a bug, its a Feature! /snark

  34. Blanko2 says:

    Maybe this is silly, but can’t you just check in a line? the blades occupy most of the given space so you could just extrapolate the bullet as a line and check if it intersects the non-opaque pixels.
    I’m not sure how that would respond to the rest of the enemies, since I’m not 100% on how the hit mechanics look, but i can’t really see it causing a problem from the sprite sheet unless bullets are really slow.

  35. Something spinning very fast would appear to have a spherical collision box.
    My suggestion is to do just that. But add a random factor to the hit collision.
    So if you feel that the player shout “hit” the spinning blades 90% of the time then just ensure the random factor remain s within that.
    I assume you have a random number generator initialized and seeded in the program,
    So a Random(100) number if it’s from 1 to 90 would mean a hit, 91 to 100 a miss.
    I’m also assuming that you already have a hit difficulty modifier on the enemies.

    And that big boss enemy, can’t you use the same/similar code to how you project the visibility/radar field? Only just the outline instead? (edge detect + edge collision?)

  36. Neil Roy says:

    In my own game I use a circle collision. Each object had a radius for collision. To check for collision you simply take the sum of the two radius’, and if that is equal or less than the distance between the two objects (measured from their center of course) than you have a collision. You can adjust the radius so that it is just a pixel or two less than the size of the object, after all, when you shoot something, your shot actually has to penetrate that object before it explodes. Also, these things happen so fast while playing nobody really notices or cares. You can also have different types of collision for different objects. I see no need to stick to just one type for the entire game.

    • Neil Roy says:

      Oh, one more comment. I personally found pixel perfect collision to be more trouble than it is worth. There’s more to checking those pixels on modern 3D hardware than there used to be. For what you’re doing, I found circle or box, slightly smaller than the object to be adequate. It’s a case of fretting over something that most people simply won’t care about (so long as you’re not hitting air, or getting hit, which a smaller circle/box solves).

  37. Neil Harding says:

    I had almost pixel perfect collision on the Atari ST in Hyperbowl, the sprites were 32×32 pixels and were irregular in shape (the shots were circular, and so was the puck, so I did a circular detection for that, and also as a first pass on the ship collision). I built a mask that was 16×16 for each ship for each rotation angle, then I could use shift in 32 bit value by up to 16 and would and the 2 masks together, and if there was any overlap I would get non zero and could mark it as collided.

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>