next »

[vinheim3]

SuperV, I really think you shouldn't code based "on a particular situation" or only resolve the collision from one tile based on which one has more coverage. What if a spike came fast from your left and another spike came slow from the bottom? If you resolved the collision based on which one has more coverage, you'd be pushed left fast without the small jump increase and if you went fast enough, you would miss the bottom spikes entirely.

As for not winding up in walls, it's as simple as pushing the character in the opposite direction that he last moved in until free. Your collision event shouldn't be handled by the other object (in this case, the wall). I think it's messy, more so when you add more objects. It'll feel kinda weird to have it in the other object too, the usual OO practice means you should be able to reuse the code from your walls and it would be weird if they came with collision events.

[ThemsAllTook]

What if a spike came fast from your left and another spike came slow from the bottom? If you resolved the collision based on which one has more coverage, you'd be pushed left fast without the small jump increase and if you went fast enough, you would miss the bottom spikes entirely.

Both collisions in your example would get processed. When a collision is "discarded", it's really only deferred. Discarded collisions will be detected again and processed on a subsequent timeslice iteration, unless an earlier collision has altered the course of events such that the discarded collision is no longer valid. I'm writing the tutorial as we speak, so hopefully it'll clear things up in a bit...

[vinheim3]

I dunno, seems kinda messy having to withhold the other collision for some time when it could all just be done at once, seems especially messy having to withhold multiple other collisions if, say, 3 more spike were impaling you in such a direction that you'd still be able to move. But if it works, go ahead, I just don't think it's that flexible?

[ThemsAllTook]

They're done all at once in the sense that all potential collisions (within reason) are resolved in a single framestep. It's not the sort of thing where the player can move around freely while collisions are still in the process of being resolved; that would most certainly be problematic!

[vinheim3]

I know they're resolved in the same framestep, I was talking about being withheld in the code. The whole "withholding for later" seems like it can be compacted to a single block of code for collision, it would be less messy. But like I said, whatever works. I'm guilty of using the easy way out, ages ago, and even now.

[vittorioromeo]

ThemsAllTook, how does your collision detection/resolution method compares with the traditional "smallest axis" method in terms of performance?

[ThemsAllTook]

I know they're resolved in the same framestep, I was talking about being withheld in the code. The whole "withholding for later" seems like it can be compacted to a single block of code for collision, it would be less messy. But like I said, whatever works. I'm guilty of using the easy way out, ages ago, and even now.

Absolutely, I understand what you're saying. Intuitively it seems simpler and more efficient not to defer collisions, but consider the following example: In a single framestep, object a is on a path of travel that will cause it to collide with both object b and object c. Colliding with either b or c will alter a's path such that it doesn't collide with the other one. In this case, the result changes depending on the order in which you process collisions.

To do the correct thing in an order-independent way, you need to determine which collision happens earlier within the framestep and process it first. Since processing that collision alters the line of travel of one or more objects, any collisions you've found that occur later in the framestep are now invalid. You might as well have discarded them, since you now have to redo all of your intersection tests for the rest of the framestep based on the changes to the simulation caused by the first collision.

ThemsAllTook, how does your collision detection/resolution method compares with the traditional "smallest axis" method in terms of performance?

Not sure which one you mean, are you talking about the Separating Axis Theorem?

I haven't had a chance to profile the entire system with a large number of objects yet, but performance will most heavily depend on how you do your space partitioning. If you know a given object can safely ignore a large portion of the simulation, you save yourself a lot of time. The core technique of processing one collision at a time and subdividing the timeslice is unlikely to have a negative effect on performance in practice, unless your simulation has a large number of very fast-moving objects colliding with each other in a single framestep.

The tutorial is halfway finished. I'll be working hard tonight to try and get it done.

[st33d]

Smallest axis means shove it out of the side that it overlaps the least.

It's how you do collision when you start making games. There's nothing wrong with it...

Until you need moving platforms or crates (or move faster than the width of a tile).

The spikes in SuperV's game are a moving platform. The smallest axis method will simply not work on its own.

In order to sit on a moving platform, you have to be aware of the platform you are sitting on. That's an extra bit of code that says, "I'm on this platform, where is it going? I should be moved along with the platform when it moves. That will make things look natural."

Give the player a "platform" property. When he's on a moving platform, that's becomes the player's "platform". You can now move when it moves by monitoring it.

SuperV should not tackle stackable crates till he has moving platforms figured out. Crates are hardcore and will require a collision engine that is built from the ground up with crates in mind (everything is technically a crate and cascades collisions).

[vittorioromeo]

SuperV should not tackle stackable crates till he has moving platforms figured out. Crates are hardcore and will require a collision engine that is built from the ground up with crates in mind (everything is technically a crate and cascades collisions).

But I can stack crates just fine :D

[vinheim3]

What if your stackable crates are on a moving platform? O.o

[vittorioromeo]

What if your stackable crates are on a moving platform? O.o

Same problems with the player apply. Anyway I forgot to mention that I can stack crates with the "smallest axis" method, not with the "resolve X first" method.

[Triplefox]

As it happens I implemented some platformer collision over the last ~2-3 days, and the result(after a few rounds of being rusty and getting it wrong in various ways) follows this fairly elaborate velocity-based structure:

0. Create velocity values for the frame.
1. Broadphase detector(in my current detector, tiles within the swept AABB of shape+velocity; later I may add other shapes)
2. Eliminate stuff that never hits after velocity is applied, it is irrelevant for the next part:
3. Get adjustment vectors(SAT/AABB) along both axes for everything left in 2; split into single-axis versions as well so that I can preserve sliding movement after adjustment.
4. Eliminate any adjustment vectors that don't work when retested; I reuse the entire broadphase for this for more accuracy. If there are any adjustments to begin with, also include a failsafe "doesn't move at all" for the case of inside corners, where collisions are found but none of the generated vectors will work.
5. Use the smallest manhattan-distance adjustment, of the ones that work.

Only implemented for square tiles against a AABB player, but I think I can extend it to moving plats or crates if needed.

To generalize, the main thing I'm doing is mapping the "OMG, geometry!11" problem into a sorting/ordering problem - of the adjustment vectors generated, look at all of them to find a "best one," and guarantee that it works before you use it; then the result will be sane and predictable. It depends a lot on having a "good" initial state(not already overlapping, velocity vectors available) but once that's in place, things can work very smoothly with few hacks, and basic entity-on-entity solid interaction becomes straightforward(add priority, order collision updates by highest priority first, higher priority objects ignore lower priority ones in broadphase; done). And if things get stuck, they can always be popped out following the main algorithm.

I'm pretty sure that I can improve my strategy more so that instead of searching for a single dual-axis vector, it combines the existing velocity and the suggested adjustments into a "valid range" rectangle, and turns that into the vector which preserves the most velocity. This will help if I want to support non-AABB shapes for slope movement or such, and still get sliding behavior without a player-state hack.