Todo List

[SolarLune]

• [x] Reverse how collision resolution happens.

• [x] Add Lines as a Shape.

• [x] Implement position data (X, Y, W, H) as floats instead of ints to allow for more fine-tuning / using the positions directly when applying speeds that are fractional (floats). I've thought more about this, and currently, this would probably best be done by reworking the entire resolve process. Instead of moving Shapes incrementally by 1, the Shape should be moved in increments of its size or the delta, whichever is smaller. If a collision is detected, the Shape should then be aligned to the edge of the colliding shape. The hardest part of this is definitely going to be the calculation for the Line, which needs to take into account the slope of the line at the leading point of the collision.

• [x] Add Line-Circle collision to complete the current set of collision types.

• [x] Re-do the examples to have a more consistent design. I could combine a couple of examples (WorldPlatformer and WorldZones, as an example). I should clean up the current design, as well; a few things are shared amongst Worlds, when they should be wholly independent and not depend on anything else except for WorldInterface, really.

• [ ] Add a Point shape. I waffle back and forth on this. On the one hand, how the heck would a Point "collide" with a Point or Line? It's so thin, the collisions would barely ever happen, so it's not that useful. On the other, checking to see if a Point is within a Circle or Rectangle sounds fairly useful. On the other other hand, you can do this already with a tiny Rectangle or Circle, so adding a whole new struct for this sounds like a waste. On the other other other hand, a Point creation function could just return a Circle of radius 1, minimizing additional cruft while providing the same functional behavior (at least for now), so ??? on this for now. If I do end up adding a Point struct, then I should probably replace any X, Y pairs in the API with Points for maximum utility.

• [x] Replace SDL with raylib; SDL2 behaves threateningly with my windowing manager. Perhaps better yet, have two sets of examples, one with each framework.

• [x] Fix up the API function names a bit - I believe "correct Go" Getters shouldn't have "get" in the name, and I should use a type switch instead of casting to the various types for each collision shape type check.

• [ ] Fix a missing edge case check where lines lie on the same line (and so, should be thought of as colliding), but don't return as true.

• [x] Add polygons - this would be tough, but shouldn't be too difficult. Upside is that this would be probably the most powerful Shape if it got added. EDIT: This can now be kind of done just by adding Lines to a Space (except for checking if a Shape is inside a Polygon).

• [ ] While working on adding the step above, a function to create a Space containing multiple lines (i.e. something like a "polygon" creation function) would be nice.

• [ ] Add a function to get the intersecting Rectangle between two Rectangles.

• [x] Add a test for collision checks and resolutions for Lines.

• [x] Improve collision resolution to return more information about collisions. The ending X and Y position of the collision might be nice, alongside references to the two Shapes that are colliding. I'm trying to keep this simple, rather than implementing a full physics library, so it won't be exact, but hopefully will be enough.

• [x] Add multi-shapes, which could be composed of children Shapes. This would allow you to test for collision with a group of Shapes, allowing you to compose a more complex Shape out of simpler Shapes. EDIT: This is now in as of v0.3 in the form of just adding the ability to re-use Spaces as Shapes. The readme has a simple example of this.

• [ ] Add the ability to resolve against all Shapes in a loop. Currently, the Resolve() function stops at one Collision, when it should either return all Collisions for all resolutions, or return the Collision that moves the Shape the furthest distance. Either one (or both) might be good additions to resolv.

• [x] Add soft collisions. A soft collision is basically resolv not forcing a resolution for a collision directly against the collided object on the main axis if the colliding shapes are very close to not colliding. Basically, a collision system that is not a "hard" collision system, but that has some margin.

In the above example image, the yellow square is attempting to resolve a movement upwards into the white square; that would place it where the red square would be. Currently, this is just implemented as a simple collision, and so resolv returns a Collision that butts the yellow square against the white one.

However, it might be good to implement the capability to try alternative resolutions within a certain "wiggle-room range" first to attempt to move to the target location. If that was implemented, then resolv could allow the yellow square to move into an alternative location, where the blue square is in the second example. If that doesn't work, then it can proceed with the resolution process as it currently stands.

Ishisoft's Leilani's Island has an implementation of this, and it looks fantastic. I'd like to add something that would be able to reproduce this.

See this Leilani's Island post for a more in-depth explanation of this.

• [ ] Optimize - partitioning. In addition to optimizing the core code running collision testing and resolution, another means of optimizing would be to run the code less often. That would mean doing fewer collision tests. I have two ideas for this. To do collision resolution, each Shape that tests must check against all other Shapes in the Space. In reality, this is inefficient, as almost all other Shapes are not even close to the checking Shape (assuming each Shape takes up only its own space, and doesn't infringe on other Shapes' spaces). If this is the case, then we could simplify the collision checking / resolution process by only checking a Shape against the other Shapes in the same partition / general area. We could store those Shapes in a partition, and provide functions to move the Shapes. These functions would also handle adding / removing them from the partitions as necessary. The end result should be that in a Space of 1000000 objects, checking a Shape against all other Shapes could only need to check against a few hundred, which is doable. See KD-Trees for more info.

• [ ] Optimize - favorite collision pairs. This is kind of the other side of the same idea from above - almost all other Shapes usually come into contact with the same sets of Shapes regularly over a given set of frames. As an example, let's take a usual sidescroller game, like a Mario-like. Over a set of frames, say, frame 1201 - 1261, if the player was grounded, he'd probably be touching the same Shape over those frames. If that's the case, then it doesn't make sense why we'd have to loop through possibly every Shape in the map until we get to the same one we touched on the last frame, just to end up touching it again on this frame. In other words, it could be more efficient to check for the Shapes that were collided with previously first when checking for collisions repeatedly over several frames. This would boost memory usage by a lot, but might simplify the collision checks considerably, and be relatively cheap to implement, but it would only benefit the most when we know the Shape is actually touching other Shapes. Otherwise, it'd still have to loop through every Shape to confirm that it's not actually touching any. Another side to this would be to sort the Shapes by distance to the calling Shape before attempting to see if it's touching any of them.

• [ ] Avoid tunnelling - add sub-resolutions / maximum distance for resolve() checks. This would be useful for situations where you want an object of small size to resolve with a large delta; it could either attempt to resolve multiple times when the delta arguments exceed the size of the checking Shape, or it could default to a maximum value that you can tweak in the Resolv package itself. Either way, it might be nice to add some ability to avoid tunnelling, and I don't think I want to keep adding on options to the Resolv() function (unless I make an Options struct you can tweak, or something like that).

• [ ] Add rotatable shapes. For simplicity, it might be best to make the most powerful shape, the Polygon, the rotatable one (or just redesign this entire API at this stage to allow any shape to be rotatable).

• [ ] Add a DistanceBetween() function. This function would return the distance between the two shapes such that at a value of 0, they are touching (so it would be a function that would return a distance between the two closest points of two given Shapes).

• [ ] Add 3D collision testing and resolution. To be honest, this is the realm of a completely separate repository with similar core concepts, but I think having an easy 3D collision testing and resolution library could also be really nice.

• [x] Add collision ignore lists so shapes can ignore other shapes if they're in the list. Alternatively (or in addition?), add bitmasks for collision checking so you can easily make certain objects not collide with others as necessary. EDIT: I'm trying to minimize the heavy stuff of Resolv to optimize; this is now kind of implemented with a simple function on Space to filter out Shapes, thereby making it a bit easier to ignore specific Shapes. For now, we'll call this implemented and revisit later if necessary.

[einthusan]

Are you working full-time on this? Is there any way to incentive you though donations to complete these pending issues in your work?

[SolarLune]

Hello!

Nope, I'm not working on this full-time. This library was created for gamedev awhile ago, and I've been working on it until about a year and a half ago.

I do appreciate the idea of donations, but I'm uncertain if there's enough demand to warrant working on this full-time / for a bounty. As it currently stands, I have a technically improved version sitting on my hard drive that runs faster and is more efficient by using an overall grid for collision-checking, but that also only has basic rectangle intersection checking.

[einthusan]

I see, i managed to wire up box2d ... i did give your engine a try, but had a bit of trouble and not enough clear documentation. Anyhow, best of luck with this project!

[sergey-koba-mobidev]

Hey, nice lib, but really should migrate int32 to float64, wanted to use it, but this is a blocker for my game :(

[SolarLune]

Yo, thanks! And yeah, I agree; I've already made the adjustments on my local copy, but I'd like to fix up the examples and fix up the SAT intersection testing before releasing an official update to master, as I'm still kind of figuring out . If you want to use it in its pre-release stage, you can check out the Revamp3 branch. It's still subject to change, but the fundamentals are there.

[sergey-koba-mobidev]

Wow! I hoped you did not abandoned the project! Nice job developing it further! ps: thx for quick response I will definitely check out the Revamp3 branch cause it should save me a lot of time

[sergey-koba-mobidev]

Revamp3 looks promising :) A circle is critical for me, so will be waiting for it

[sardap]

The float64 update is very exciting! I'm switching to the Revamp3 branch as well!

[SolarLune]

Okay, so it's been a couple of weeks, but I've finally gotten this to a point where I feel relatively comfortable, I think, with putting it out there. master has been updated to bear the fruits of this labor, and resolv is now sitting at v0.5.0. This effort resolves a variety of issues that are brought up in this post, and so the todo list will be removed, as I've basically been able to implement a ton of the things from this list, including:

• Floats instead of ints for positions.
• A faster method of collision checking through grid-based position checking.
• ConvexPolygon shapes.
• Circle-Line intersection testing (as part of Circle-ConvexPolygon intersection testing).
• General API improvements.
• Soft collisions are now possible and are now seen in the WorldPlatformer example, etc.

Thanks for holding out hope that I'd come back to this, haha. Your encouragement has been very helpful~