solarlune/resolv

A Simple 2D Golang collision detection and resolution library for games

resolv's Issues

Optimized Tags

In relation to PR #20, HasTags has ended up being one of the heaviest function calls in resolv. In terms of optimizing this, would it be possible to introduce using either:

• A tag field like TagIDs with corresponding HasTagIDs and related funcs
• Use generics to allow overriding the tag type
• Some other smarter idea

I have no problems implementing either one myself. Generics would be more performant, but would introduce some complexity and potential API changes (might be able to "wrap" the second problem, but not certain yet).

Use Ebiten game engine as your example.

You should include an example for Ebiten, and maybe even use that as your default example. Ebiten is a game engine developed entirely in Go with good follower base and very active development by the lead developer. When I try to download your package using "go get", it shows all kinda of messages/errors relating to external dependencies in your examples for raylib and sdl2.

# pkg-config --cflags  -- sdl2
Package sdl2 was not found in the pkg-config search path.
Perhaps you should add the directory containing `sdl2.pc'
to the PKG_CONFIG_PATH environment variable
No package 'sdl2' found
pkg-config: exit status 1

# github.com/gen2brain/raylib-go/raylib
In file included from raudio.c:208:
../../gen2brain/raylib-go/raylib/external/jar_xm.h:620:9: warning: 'ALIGN' macro redefined [-Wmacro-redefined]
/usr/include/i386/param.h:83:9: note: previous definition is here

Todo List

• Reverse how collision resolution happens.

• Add Lines as a Shape.

• 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.

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

• 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.

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

• 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.

• 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.

• Add a test for collision checks and resolutions for Lines.

• 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.

• 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.

• 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.

• 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.

Get coordinate for intersection?

object bound calculate error

resolv/object.go

Line 153 in 4f47f68

ex, ey := obj.Space.WorldToSpace(obj.X+obj.W+dx-1, obj.Y+obj.H+dy-1)

position (5.5, 7.5) convert into grid index (4, 6), it should be (5,7)

// WorldToSpace converts from a world position (x, y) to a position in the Space (a grid-based position).
func (sp *Space) WorldToSpace(x, y float64) (int, int) {
	fx := int(math.Floor(x / float64(sp.CellWidth)))
	fy := int(math.Floor(y / float64(sp.CellHeight)))
	return fx, fy
}

i think it should be math.Ceil rather than math.Floor

Maybe remove the Game binary from the repo?

You probably intended to gitignore this file: https://github.com/SolarLune/resolv/blob/master/Game

Example rendered by Ebiten, and compiled to WebAssembly

I wrote a version of the resolv example using Ebiten: https://gist.github.com/peterhellberg/c8b61e9efc73c2c9eeae26c7cef207e8

And then I compiled it to WebAssembly using wasmgo (which also deploys to jsgo.io): https://jsgo.io/9e575f464c9bdc76db833f4160b646dc007d25f6

Feel free to copy my code if you like it.

Image dump

Point line intersection

Hi!

I discovered this package yesterday and like it a lot.

Would it be possible to get the point of intersection between lines? I've been working on ray casting to cast shadows, and currently use github.com/paulmach/go.geo, but it would be great if resolv could support it.

Example here: https://jsgo.io/kyeett/2d-vision

How is the performance?

You said your using "fmt" and "math" packages. The "fmt" package is notoriously slow, what are you using it for?

Maybe you can run some performance metrics to show how many rectangles you can a make and have collision testing and resolution for at 60 fps? ... to being with.