[Library] Splash.lua - bump.lua with more shapes.

[bakpakin]

I needed collisions for ongoing Doom-style FPS, without full physics but with the convenience of bump.lua. Specifically, I needed walls and circles to represent the player and things in the world. Splash.lua is my ongoing generalized implementation of that. If you don't know what bump.lua is, check it out.

The above demo is in the github repository, so If you want to run it, just download the repo and follow the instructions on github.

Code: (Github Repo)

So, claiming that has everything that bump has and more is a bit misleading, but it is similar in several ways. Right now, It doesn't do everything that bump does, but it has static collision detection and ray-casting, as well as the ability to query parts of the world. It's also fast and memory efficient. Full support for swept collisions like bump is something I will try to add, but the situation is more complicated with different types of shapes.

In regards to bump.lua:
Still incomplete at this point, but Splash.lua has most of bump's functionality. The only thing missing that I can think of is a bounce collision response and custom responses, but there is probably more. Also, bump is better tested and simpler to use at this point. But I'm working on it! I have not intended to replace bump.lua, but to generalize it a bit.

Biggest TODOs:

• Implement more sweep functions, like sweeping a circle against a line segment. This would be very useful for games like top-down shooters, where a player could be a circle and walls would be line segments. Seeing as this was one of the reasons for Splash.lua, the current lack of this is annoying.
• Add a bounce collision response and custom responses. This shouldn't be too hard, (knock on wood).
• Add real tests to the specs. Right now it's just some simple tests that will pretty much always pass.

I had a lot of fun making this and figuring out all the math involved. At this point however, there is still a lot to do. Debugging and typos are stilling lurking in the source, waiting to be found. Feedback is appreciated, help even more so.

[kikito]

Full support for swept collisions like bump is something I will try to add, but the situation is more complicated with different types of shapes.

Swept collision is definively a step up vs static collision, but the real challenge (and what took me the longest to figure out) is collision resolution. Do you plan to include that in Splash, too?

[bakpakin]

I already have some ideas about how to go about that as well, by moving each object one at a time and ordering collisions by normalized time (I'm assuming that's how bump does it). That will also be a challenge, definitely. Originally, I was going to add verlet physics, but I realized that perfect collision detection was more feasible with with a move-objects-one-at-a-time approach.

I'm also not sure if I want do resolution the way bump does, but we'll see.

Also, I have to write the collision resolution code once, and 6 different methods for swept collisions (circle vs. circle, circle vs. aabb, etc.), just like I have 6 different methods for static collision.

[kikito]

Good luck then. I certainly can't help you on that - not for lack of willingness, but lack of math capacity.

I can offer some pointers though:

The implementation of bump's algorithm is based on this article by wildbunny (don't let the title fool you, it is quite good). The article describes the Minkowsky Difference as a way to calculate the swept collision between arbitrary polygons. I didn't want to have to handle vector math in my library, that that's why it is restricted to boxes. That allows me to "cheat"; the MD of two AABBs is another AABB, so I can transform the problem of "intersecting two moving boxes" into "intersecting a segment vs a box". I can solve that without vectors with the liang-barsky algorithm, a good description of which can be found here.

You can not cheat like I did if you want to implement swept collisions in general (not limited to AABBs). You will have to use some vector math. I know two options: a) implement the Minkowsky Difference as wildbunny does on its article, using polygons and vector math and b) Use the separating axis theorem instead. Wildbunny finds it less "intuitive" than the Minkowsky Difference, but that's what the guys who implemented N used. It is also the route taken by vrld in HardOnCollider (you should definitively give it a look). I haven't tried it myself.

I also seem to remember that Vrld was thinking about making HardonCollider move things one-at-a-time on its next version, like bump does. But I don't know what's the latest on that. Maybe you can join forces somehow there.

Again, good luck. What you are trying to achieve is beyond my capabilities.

[bakpakin]

Good luck then. I certainly can't help you on that - not for lack of willingness, but lack of math capacity.

I can offer some pointers though:

The implementation of bump's algorithm is based on this article by wildbunny (don't let the title fool you, it is quite good). The article describes the Minkowsky Difference as a way to calculate the swept collision between arbitrary polygons. I didn't want to have to handle vector math in my library, that that's why it is restricted to boxes. That allows me to "cheat"; the MD of two AABBs is another AABB, so I can transform the problem of "intersecting two moving boxes" into "intersecting a segment vs a box". I can solve that without vectors with the liang-barsky algorithm, a good description of which can be found here.

Thanks for the pointers. I think I will go with using the Minkowski difference as I already have a segment-aabb sweep and segment-circle sweep, essentially already solving part of the problem. I didn't use the liang-barsky algorithm, but something similarly fast that I derived myself. It doesn't have all of the early exists of the liang-barsky algorithm, but I could substitute one for the other easily enough.

As for the vector math, I've been unrolling it by hand so I don't need a vector class, but it's the easiest way to do this.

[Jasoco]

Collision resolution and ease of use is why I use Bump. I'd love to have shape collisions and slopes but I don't want to have to write my own resolution or screw around with Box2D.

[vrld]

You can not cheat like I did if you want to implement swept collisions in general (not limited to AABBs). You will have to use some vector math. I know two options: a) implement the Minkowsky Difference as wildbunny does on its article, using polygons and vector math and b) Use the separating axis theorem instead. Wildbunny finds it less "intuitive" than the Minkowsky Difference, but that's what the guys who implemented N used. It is also the route taken by vrld in HardOnCollider (you should definitively give it a look). I haven't tried it myself.

Just to clarify: HC uses the GJK and EPA algorithms that in turn are based on the Minkowski difference. HC used to detect collisions by the separating axis theorem (SAT, which I find more intuitive than GJK), but it turns out that GJK+EPA is much faster than SAT.

[bakpakin]

As i'm not doing polygon collisions yet, I think GJK is a bit overkill.

[bakpakin]

Just wondering, how should I best go about resolving corner collisions? I know this is a common problem in collision engines, so I want to make sure I get it right. My plan is to solve collisions that happen first, and prioritize edge collisions over corner collisions. I'm not sure if that's the best way to do this.

collisionProblemDiagram.png (5.5 KiB) Viewed 5206 times

In the above picture, a red box moving along the blue arrow collides with two other boxes at the same time, one on an edge, and one on a corner. How does bump make sure the edge collision is resolved first, and is that scalable to more shapes? Also, I have a feeling that if I use a sliding response to the first collision (A) so that the red box moves along the purple arrow, It will still collide with block B.

[kikito]

The way it's done in bump has two parts:

• Make sure that the collision with A always happens before the collision with B
• Make sure that once the collision with A is resolved, the collision with B does not happen.

For the first part, the sweeping algorithm gives me an "idea" of what happens first (for each collision it gives me a "t" between 0 and 1 - the one with the smallest t happens first - remember that the red block is collapsed into a segment while I resolve the collision). The reality is a bit more complex because there are several edge cases: what happens if the red block starts partially inside A? What happens if the red block isn't moving (and yet you want to resolve its collision with A)?

The second part was a matter of tweaking the <, >, <= and >= of my algorithms, trying lots of combinations until it felt right. It was quite a hassle to implement. It seems to work well now, but I am never 100% sure that it works correctly.

And on top of that, there are floating-point considerations to take into account. Those were a huge hassle too.

Other people do it differently: They don't use "solid blocks" for the tiles; Instead, they are made of "4 segments". The segment at the top only collidable from the top. The segments on the sides are only collidable on the sides. And the same for the bottom. When a tile is next to another (as A and B are in your example) their "touching segments" are deactivated.

This has several drawbacks: tiles have to "know their surroundings" to work properly. But it is probably easier to program than what I did.