Precise collision for static sprites

Discussion and feedback on Construct 2

Post » Tue May 14, 2013 4:56 pm

[QUOTE=Ashley] 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.[/QUOTE]

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.

[QUOTE=TELLES0808] 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.[/QUOTE]

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.
Posts: 17
Reputation: 509

Post » Tue May 14, 2013 5:34 pm

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.

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.


This is just a matter of elipse nonlinear.TELLES08082013-05-14 18:32:25
Posts: 1,374
Reputation: 22,826

Post » Tue May 14, 2013 7:17 pm

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

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.
Posts: 5,360
Reputation: 73,781

Post » Tue May 14, 2013 8:33 pm

Wow...Is there anything your Canvas plugin CAN'T do? It's helped me so much in the past :D
Posts: 571
Reputation: 9,819

Post » Wed May 15, 2013 1:06 am

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;
    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 05:58:48
Posts: 17
Reputation: 509

Post » Fri May 17, 2013 2:56 am

Alright, update time. Here is an example of some simple collision mask collision using C2's built in array object. This is the simplest type of mask collision which is really just a straight array of layout x by layout y and it's pretty suboptimal as far as performance expectations go, especially since everything is buried under C2's function calls which are kind of slow compared to what you could expect out of something specifically coded for the task.

Actually the news is pretty good. In this manner, up to 450 pixels per frame could be tested on my machine before framerates dropped below 60. This might not seem like a huge amount, but when you consider that you can usually get by testing 8 or so pixels for the primary character collision against terrain and usually less than that for other entities, it's not half bad. Performance would probably go up significantly if something were written to handle this more properly in javascript too. And it's much faster than what I was seeing when using a canvas of the same size and checking rgba even when it wasn't obscured behind as many layers of events.

Sorry for the simplistic geometry in this example. I didn't want to spend all day coming up with a method for converting sprites to pixel mask points. I have an idea of how to do it by using a temporary canvas, but it shouldn't take away from the purpose of the demonstration regardless of that.DimensionWarped2013-05-17 02:57:54
Posts: 17
Reputation: 509

Post » Fri Nov 20, 2015 4:16 pm

Now I know this form is old, but I couldn't find anything else to fit.

If your looking for a compelling case (to the creator of scirra) I have one.

I am re-creating a limbo-type level, and the terrain is compiled in a single image (1920*8000pi). This was the best method to design limbo terrain after much research. Originally attempting 2D in Blender3D BGE it just didn't work out so I turned to my long-time used engine of Construct 2. I looked for an option for HD Collisions but I couldn't find it, so I looked up and I found this.

Sure, I understand performance issues, but with High Resolution terrain that your only rendering a certain portion at a time, this sort of thing is NEEDED. It would take me a very long time to do each point by hand, and especially since that covers an entire level. So correct collisions are needed, and in the past your engine has done them better than me.

I just ask that maybe there be an option for "HD Collisions" with a Warning so users know what they're getting into.
Posts: 62
Reputation: 627

Post » Fri Nov 20, 2015 8:01 pm

I agree per pixel collision would be welcome. Ability to draw collision masks on layout would be also welcome. @Ashley I absolutely understand why you are not convinced to do those things, but those are modern days standards in game development. In c2 we do can make walk-arounds for simple things, but in more complex situations everything tends to get super complicated and fall apart. And I personally would expect engine to take care of those things, as I was mentioning multi-level collisions, push out of solids etc. Those all would be extremely welcome for everyone. Our gamedev would become much shorter and more good games could come out.
My professional Royalty Free Music at Scirra Assets Store
Specs: i5 2500, 16gb of ram, gtx 770, win 7, Focusrite Scarlett 8i6, Mackie mr8mk2, Alesis 320, browsing the net on chrome.
Posts: 1,987
Reputation: 20,178

Post » Sat Nov 21, 2015 3:25 am

The simplest way to do it would be to fill a tilemap with a duplicate of your collision mask.

To do this you'll need a tilemap with a 1x1 tilesize that covers the area of your collision mask image. It's only for collision detection so it can be invisible.
Next you'll need a canvas object with the collision mask as its image.

Then at the start of layout use two for loops to loop over every pixel. Use a system compare with canvas.alphaAt(X,y) to read the alpha of the pixel. If it's say >128 then set a tile on the tilemap at the same position.

At the end of it the tilemap will be ready for collisions and all behaviors can interact with it. It can take a while to do, so as a speed up you could save the tilemap as json and use that in your actual game.
Posts: 5,360
Reputation: 73,781

Post » Sat Nov 21, 2015 12:29 pm

dilk wrote:I am re-creating a limbo-type level, and the terrain is compiled in a single image (1920*8000pi).

We strongly recommend against designing games like this. See remember not to waste your memory. The memory use will be very high, and an image that large will not even load on systems with a maximum texture size of 2048x2048 or 4096x4096.

You don't need to design the collision mask point-by-point for an entire level like that. Just create some collider objects which are invisible sprites with a simple shape (e.g. triangle, rectangle, etc) with a matching collision mask. Then you can design the collisions for your level in the layout view by arranging those objects. The collision cells optimisation keeps this fast regardless of how many collision objects you have scattered across the level.

Given the high complexity of the per-pixel collisions feature, I really don't want to have to support that. As I said earlier in the thread the implementation complexity is very difficult, it has high performance and memory overheads in some cases, it was an ongoing source of bugs and crashes in Classic, it would be even more difficult in C2 (since there is a new poly-to-pixel-mask case), and every new collision feature exponentially increases the types of collision interaction that must be supported, effectively ruling out ever adding any other new collision features. I really think it's best to stick to polygons. AFIAK, that's how all 3D games work anyway - I don't think many games use voxel collision masks (which would be the 3D equivalent) - and if polygons are good enough for 3D...
Scirra Founder
Posts: 24,550
Reputation: 195,537


Return to Construct 2 General

Who is online

Users browsing this forum: No registered users and 9 guests