Precise collision for static sprites

Discussion and feedback on Construct 2

Post » Mon May 13, 2013 10:01 am

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.
B
4
Posts: 17
Reputation: 484

Post » Mon May 13, 2013 2:13 pm

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.
Scirra Founder
B
359
S
214
G
72
Posts: 22,952
Reputation: 178,600

Post » Mon May 13, 2013 3:20 pm

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.
B
4
Posts: 17
Reputation: 484

Post » Mon May 13, 2013 7:32 pm

This sparked an interesting idea in my mind...
...Why not have a "Image point overlaps Sprite" action? :DJase002013-05-13 19:32:58
B
45
S
19
G
10
Posts: 562
Reputation: 9,543

Post » Mon May 13, 2013 8:25 pm

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.
Scirra Founder
B
359
S
214
G
72
Posts: 22,952
Reputation: 178,600

Post » Mon May 13, 2013 9:52 pm

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.
B
4
Posts: 17
Reputation: 484

Post » Mon May 13, 2013 11:03 pm

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 hahaJase002013-05-13 23:10:30
B
45
S
19
G
10
Posts: 562
Reputation: 9,543

Post » Tue May 14, 2013 12:33 am

Your inkling is correct. You could have just read my profile though . 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.
B
4
Posts: 17
Reputation: 484

Post » Tue May 14, 2013 12:37 pm

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.
Scirra Founder
B
359
S
214
G
72
Posts: 22,952
Reputation: 178,600

Post » Tue May 14, 2013 12:55 pm

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.
ImageImageImageImageImageImage
B
93
S
20
G
12
Posts: 1,214
Reputation: 18,486

Next

Return to Construct 2 General

Who is online

Users browsing this forum: spacedoubt, Unconnected and 0 guests