Precise collision for static sprites

0 favourites
From the Asset Store
A set of 10 pixel art animated magic effects with icons. 2 Fire, 2 Earth, 2 Wind, 2 Water, Portal, Explosion.
  • I was searching through the forums looking to see if there were any plans to implement precise collisions and was a little flustered to find that the primary concern here was performance. A lot of types of games though require a significant amount of different types of level geometry and to put it bluntly, polygonal collision is often inadequate for these purposes and computationally expensive to use for level geometry anyway (since you have to perform lots of additional checks as your level geometry expands). If you have large amounts of static solids, you can simplify collisions significantly by applying a collision mask and checking collisions at a single point (8 or so single point collision checks should be perfectly adequate for most platform game character movement systems for instance)

    Now, I understand that doing full collision meshes for sprites is a problem. It makes perfect sense why collision polygons would be preferable for that, but for level geometry such as for a platform game or an overhead adventure game, I would suggest that polygonal collision can actually be very expensive compared to doing collision against a mask... especially if you only need to check the collision at a single point. When you have large quantities of unmoving sprites that you can depend on staying in the same place all the time, you can simply throw every collidable pixel into a 2d boolean array with memory needs at one bit per pixel. That can actually add up rather quickly...

    So anyway, I have a feature I'd like to suggest and you all can feel free to use it or not, whatever floats your boat really. I won't be offended.

    Collision Mask Object - Can make a collision mask out of all sprites on a given layer

    has the following properties:

    int resolution

    somewhat complicated... but since even at one bit per pixel collision masks for modern high resolution games could be really expensive it would be useful to be able to skip around a bit. When converting geometry using a resolution value of 2 for instance, only every other row and column of a sprite would be read into the collision mask. Meanwhile collision checks would be divided by two on each dimension.

    Provides the following functions in the event editor:

    boolean checkCollision(int x, int y) //pretty self explanatory right?

    As for actually generating the collision mask... I'm not sure how it should work exactly. Assigning objects is a bit of an implementation decision, but I imagine the most convenient way to do it would be to have all of your collidable sprites on a single layer and have a tool for generating the collision mask from the sprites in the scene editor when the collision mask object is selecting. Then it could dump the collision mask into some manner of blob.

    It might be useful to also have the collision masks automatically be subdivided so that large clusters of empty space don't need a full set of collision data. All sorts of optimizations could be made on that end of course. Subdivisions could be full collision, full non-collision, or point to a blob mask to save memory at the expense of computation time.

    So implementation details aside, this really is a feature that I think is going to be somewhat necessary for a lot of people and I think C2 would really benefit from having something like it.

  • I don't think you're right about the performance aspect. A 256x256 object with 8 points on its collision poly requires 8 x 8 = 64 operations to check if it overlaps another similar touching object. (This could be optimised using a smarter algorithm, but I don't think it's a bottleneck for most games at this point.) If you resize both objects to 1024x1024, it requires only 8 operations per object to scale the polys, then another 64 operations.

    Using bitmasks a 256x256 object has 65536 pixels which need checking. Using a clever bitmask algorithm which checks 32 bits at a time it's possible to reduce this to about 2048 operations. However scaling up the object to 1024x1024 will require 32,768 operations (per object!) to re-fill a bigger bitmask, then up to another 32,768 operations to test the overlap. C++ is fast enough to muscle through this and can also use exotic machine-level features like SSE to optimise it. However this type of activity tends to exacerbate the weaknesses of Javascript.

    So I don't have actual performance measurements to back this up (but neither do you!) but based on the above I would think per-pixel collision testing would be significantly slower.

  • Checking against a mask for collision at just one pixel is just a single yes/no check against a value in an array (and yes, there are probably more clever algorithms out there involving collision masks). The reason it works is only because you have a limited number of pixels to check with.

    For doing something like platform movement, you only realistically need to check maybe 6 or 10 pixels for a single sprite to be able to reliably say if you have a collision going on against the collision mask and you'll generally know more about the collision than if you simply did a check against a collision polygon.

  • This sparked an interesting idea in my mind...

    ...Why not have a "Image point overlaps Sprite" action? :D

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • The per-pixel collision checker in Classic was one of the toughest bits of coding I've ever worked on. I don't want to take it on without an extremely compelling use case. And I don't think there's a good one here. The Platform behavior already works very well with polygon collisions.

  • I agree that this would be a significant investment of time. I don't think it's the collision itself that would be the problem here though. The hardest part would be figuring out how to generate those collision masks in the first place. I don't think it's something you should even begin to support the platform movement behavior with. It's clearly a feature that would be geared towards people rolling their own behaviors.

    Sometime this week I'll try to convince you why this is compelling with examples within Construct 2. It's mostly a factor in platform games that feature lots of irregularly curved and sloped terrain which requires complicated collision meshes to adequately suit the form of the visuals that it represents. For now though, think about a game like Worms where the terrain is just an absolute mess of elaborate geometry or Robot Unicorn Attack which is all kinds of curvy. It's not only computationally expensive to have elaborate collision geometry with polygons, it's also a serious drain on making art usable in game.

  • I just realised your name...

    Are you from SFGHQ forums? :D

    If you are, then it would make sense, your asking about platformer and collision related stuff, which would relate perhaps to a Sonic game. I've managed to make an unfinished but sort of working basic 360 Sonic movement using the built-in platform behaviour, but found that halfpipes and whatnot aren't particularly nice to travel up due to the polygon collision.

    Then again, if you're not the same person, then ignore all of this haha

  • Your inkling is correct. You could have just read my profile though <img src="smileys/smiley2.gif" border="0" align="middle" /> . I was involved in creating one of the more popular pivotal engines used by the community (not chiefly, but involved) back when I was in school and part of my interest in this topic is because this is a feature that I consider necessary for porting the engine from MMF2 to Construct 2. Well, strictly speaking we could work around it by creating tools externally to create the collision masks and then loading them from a text file into an array or something... but the intention is for anyone to be able to pick up the engine, throw some sprites in there for level geometry and then run it without having to muck about too much with collision and the closer to the core that functionality is, the better.

    That said, if it were only something needed for the purpose of one particular type of game which is itself a clone I wouldn't be suggesting this as that would be kind of selfish... so give me a little time and I'll throw together some nice examples.

  • I guess you're right about curved/complicated geometry - it would be useful to have automatic pixel-perfect collision masks for that. But I'm still not convinced Javascript is capable of managing all the processing. Perhaps if we compiled the collision engine with asm.js, but then it's even more complicated... are you sure you can't work around it by assembling lots of polygon sprites together? Hopefully a well-coded engine will still manage OK with curves made from lots of small straight lines. I think most physics engines more or less treat that as a curve if the error is small enough.

  • Forgive the intrusion, but for a looping, like in sonic, I would do it using events, and not collisions.

    Maybe this year I release one sample with it, but the behind scene of a looping is something like getting their diameters, and doing the trajectory manually, using events, and doing all the exceptions, like the player releasing keys too.

  • I guess you're right about curved/complicated geometry - it would be useful to have automatic pixel-perfect collision masks for that. But I'm still not convinced Javascript is capable of managing all the processing. Perhaps if we compiled the collision engine with asm.js, but then it's even more complicated... are you sure you can't work around it by assembling lots of polygon sprites together? Hopefully a well-coded engine will still manage OK with curves made from lots of small straight lines. I think most physics engines more or less treat that as a curve if the error is small enough.

    Well yes, to some extent all curves are just a series of straight lines, particularly when you are dealing with pixel art. There are a couple problems with using lots of smaller polygonal sprites though. For a platform game along the lines of what I'm thinking (and we are talking small resolutions for the visible frame right now... 320x240), level sizes routinely end up being somewhere in the neighborhood of 14000x4000 pixels and can come in much larger sizes. In order to achieve the kind of curve density that is appropriate with simple approximations, we would probably have to divide them into much smaller chunks (somewhere between 8x8 and 32x32, and those are a pain in the butt to work with in levels of that scale). It's a huge sprite explosion anyway and I have some concerns about the performance in that case. The worst thing about it though is how much additional strain it puts on getting art into the game. Generally we prefer for people to be able to work with 128x128 terrain pieces, but for something of that size you can expect to have somewhat complicated geometry that has a few notable problems:

    1. The automatic collision mesh generator fails to create something resembling what it should be.

    2. The amount of points needed to map the whole terrain piece vastly exceeds the recommended limits given by C2 (probably not as significant of a problem since these recommendations are more likely intended for small standalone and numerous sprites).

    It's also common to have over a hundred different set types of 128x128 blocks each needing to be set up separately for collision... so for this type of game the problem is really compounded.

    To sum it up bluntly, no, I don't think that approach would work.

    Collision masks are really the most proper way I can think of to do this. I think you are misunderstanding something about the problem though. The real-time processing component of this is very small. The simplest (IE extremely expensive as far as memory is concerned) variation of this is a boolean array of x by y where x is the x and y are those dimensions for the scene. Figuring out whether you have a collision at a single pixel is just a check against one element in the array (array[x][y] where x and y are where you are checking) to see if it's true or false. I don't think it's actually possible for any kind of collision to be computationally cheaper. It only gets expensive if you need to check a large number of pixels (which I think is why you are assuming it's so expensive). Most behaviors only need to check a handful of points. And consider how this is done with polygons... if you want to know significant details about how an object has collided with another, such as whether it was a front collision, a top collision, etc. you have to use numerous objects anyway, so the additional checks still have to be done just like they would if you were checking pixel collision at numerous positions. So for people who need advanced knowledge of the collisions there really aren't any perceivable savings using polygonal collision solving... at least assuming polygonal collision is more expensive than checking a single value in a boolean array for truth.

    Forgive the intrusion, but for a looping, like in sonic, I would do it using events, and not collisions.

    Maybe this year I release one sample with it, but the behind scene of a looping is something like getting their diameters, and doing the trajectory manually, using events, and doing all the exceptions, like the player releasing keys too.

    Loop-de-loops are a very small piece of the puzzle. It's also one we've hit from several different angles over the years.

    The problem with trying for individual math-based approaches to solving it is how varied the loops are in the first place. They aren't all perfect circles. Some are ellipsoids rather than circular. Some taper off in places. Others are just plain irregular curves that can't be solved with simple trigonometry. Even if this weren't the case though, you still have to consider that there are ways to hit them that don't involve moving through them smoothly. You still have to have the collision in place for them even constrain yourself to just loops that could be solved with simple math. What you are suggesting has been tried before back with old Click n Create engines and the results have always been unsatisfactory and hard to apply with any versatility.

    It's much simpler and you'll achieve better results in the long run to just have the loops as normal geometry. Things look better when the movement always follows the same basic set of rules anyway.

  • I have tried here, for the first few types of looping and math is working well, but sonic have several types and exceptions, as I said, needing treat each one individually.

    As a lover of challenges, maybe finish this sample and share it with you will be amazing.

    Also, I didn't said your idea is bad, my post was just a point of how I would make it, because we don't have curved surfaces.

    scirra.com/forum/request-curves-in-collission-polygons_topic49138.html

    Think, any line have a math, simple or not, everything is possible using events..

    Flash have the same issue about the collisions, and you need to code your game using AS3, but I saw Sonic remakes everywhere, and looking inside the .swf, everything look being made with code, so, it's possible.

    <img src="http://www.renderhjs.net/bbs/flashkit/sonic_loops_diagram.jpg" border="0">

    http://board.flashkit.com/board/showthread.php?758308-MX-Rotation-sonic-style-on-slopes

    [tube]http://www.youtube.com/watch?v=rFSVpVCCzMI[/tube]

    This is just a matter of elipse nonlinear.

  • You can do this with my canvas plugin, here's an example:

    https://dl.dropboxusercontent.com/u/5426011/examples17/perpixel_pointcollision.capx

    More advanced per pixel collision detection can be done with it as well. There are a few capx i made that are scattered around the forum.

  • Wow...Is there anything your Canvas plugin CAN'T do? It's helped me so much in the past :D

  • Gave it a look. Conceptually, it's very similar to what I'm thinking with this. The only problem is the canvas assigns (I'm guessing here) 32 bits per pixel and it probably has a full buffer for the entire canvas all the time. I can't just copy an entire 20000 x 4000 level into the canvas and call it a day. The memory needs are pretty large. I might be able to get around that by creating lots of smaller canvases as needed. I'm not sure how workable that is.

    I think we just need a more targeted solution for this. Ideally we could have something like an array of 64x64 (or whatever resolution. Maybe even make it user-specifiable) patches which could be all empty, all full, or point to a 64x64 mask so that when you are checking for collision at a spot, you would do the following:

    *pardon my silly pseudocode*

    a 64x64 mask has the following values:

    collision_type - enumerated from ALL_EMPTY, ALL_FULL, MIXED

    collision_mask - NULL if ALL_EMPTY or ALL_FULL, a pointer to a 64x64 binary array if MIXED

    int collision_at_point(int x, int y)

    this_64x64mask = all_64x64masks[x / 64, y / 64];

    if (this_64x64mask == ALL_EMPTY)

        return 0;

    elif (this_64x64mask == ALL_FULL)

        return 1;

    else

        return this_64x64mask->collision_mask[x % 64, y % 64];

    That way areas with no collision to worry about and areas with big spaces all contained within collision wouldn't be a significant memory burden.

    Pretty impressive little plugin though. It'll be a good start for some of the experiments I'm working on right now.

    EDIT: Performance testing using the canvas is less than promising. Using the same method as the Mario mask against a 1280x720 canvas, I was able to test about 10 points per frame and still maintain a 60 frame rate with webGL off. Meanwhile using the same conditions with sprite collision, I was able to keep full frames while checking over 1000 triangles each frame against 7 identical objects with a 30 point collision mesh with concavity. I don't think canvas is going to work for these needs. Also for some reason WebGL just kills the performance of all my tests... not sure why and doesn't really have anything to do with this topic.

    link to test capx

    filedropper.com/testcollisionvscanvaspoint

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)