Slick Forums

This topic is about building a simple, slick-based, non-component, library to solve collisions between object into our games

let's start!

_________________
Blog | Last game Gravity Duck tribute | In progress Gravity Duck tribute

I'll pitch my interest into this.
So I'll start with what i have been thinking.

As I understand it the primary goal is to make a library where simple things are easy to implement. The developer shouldn't have to concern themselves with more information than is applicable to the problem they are trying to solve.
Extrapolating from that when a developer is extending the library they shouldn't have to inherit any unnecessary baggage.
While the library (IMHO) isn't intended to be as sophisticated as phys2d it should be possible for a developer to extend the systems provided to obtain that functionality if needed.
In short it should be designed to make common/repeated tasks as simple as possible.

*yeah I know that is not really useful but maybe it will get things started.

_________________
If at first quads don't succeed tri tri again.

Can we define what this functionality is? Here are some thoughts:

* Let's start with just detecting intersection, we likely need position and dimensions to handle this
* But how do you resolve an intersection? Well, now we might need velocity
* And what if we have a big entity and a small one? Likely you want mass to distinguish heavy things from light things
* What about acceleration or friction? How are these managed? By the user, are they important for collision resolution?

So, now we have position, dimensions, velocity, mass. Assuming two dimensions for each vector that's seven properties or fourteen get/set methods! Now, I don't think a good library makes you implement fourteen throw away methods; on the other hand I'm not happy with a library that makes you use your one shot at inheritance on some base class...

Not to mention that at this point we've nearly duplicated all of the state on an object in Phys2d, so we're back to square one and in that case we already have libraries that do what we want and more. (Will you want support for bouncing balls? Joints? Sprints?)

Let's try again. How about we think about some scenarios:

* The library handles intersection, we're making asteroids and only need boolean collision detection
* The library handles intersection and client handles resolution but needs more than a boolean result from the intersection, we're making a simple platformer and need the side of the collision for example
* The library handles intersection and resolution, the physics are too involved for the client, such as resolving intersection between irregular shapes, we're making a platformer with simple physics and complex shapes

In my mind a "simple" library is one that scales to address these different scenarios without forcing the client who needs boolean hit detection to follow the same patterns as the client who needs the full blown collision resolution system.

Now, in my mind this might be accomplished by allowing the user to define what physical properties his POJO has and then configure the collision detection/resolution object to operate on the definition. At the same time performance is important so we don't want to rely on reflection for all of this. And we still haven't solved the problem of having to implement a dozen properties...

Anyone care to respond?

_________________
My website about game development http://anotherearlymorning.com

API design is definitely not something I claim to be good at, but I don't want to see this thing die so I will try to respond anyway. It's not as though bad ideas have never sparked good ideas before so who knows.

For starters I'm just going to look at the issue of not wanting to have dozens of properties to implement. The way I see it, when you handle the collisions, regardless of the physics you want to do with it later; you only need information about the shape. And all the shape information you need is:

1. A list of the paths that make up the "edges" of the shape.
2. The translational displacement of the shape (start and end position)
3. The rotational displacement of the shape (start and end angle)

*There could be more, but things like mass and elasticity would not be required.

So the minimum for a shape interface would be 5 get/set methods. Now if you want to resolve the collision you need a lot more information. Chances are good the client will need a lot of domain specific information at this point. But lets just assume physics for now. A body that has physics information can implement the Shape interface, wrap a Shape object and proxy all the calls to the shape object. So that half is dealt with.
As for the physics information that could just be stored in an an object map. Admittedly not the most elegant solution, but it could work. If a resolution object has access to the result of the collision between to shapes and the physics properties for each shape; mass, elasticity friction etc, then it should be able to resolve the collision.

The big problem is that the CollisionHandler, CollisionResolver, and CollisionResult objects would be rather coupled. The collisionResolver is going to require a CollisionResult of a certain type. Which means the collisionHandler used needs to produce a CollisionResult of the type required. In short the resolver used is going to dictate what handler you use.

Admittedly this doesn't really solve any problems so much as create new ones. But I'd rather propose bad ideas than none at all and let this die.

_________________
If at first quads don't succeed tri tri again.

Interesting discussion :)



While this is a good goal on paper, the end result could be a library that isn't as simple as it could be for basic needs and isn't as robust as it could be for complicated needs. It might be better to limit the scope a bit. Phys2d and jbox2d are already good at realistic physics, how about aiming for something a step (or more) below that?

One of my perpetually-in-development personal projects sort of fills that role. I'm a little busy with school right now but I think I'll have some free time in about 2 weeks - I will clean the code up and host it somewhere.

Quite right; but it least it got the ball rolling

I also agree that this library should be a aimed at providing services a notch or two bellow phy2d. To look at manunderground's scenarios (really like those by the way), I think the second scenario would make an ideal primary target. Even at that level it seems that it would be quite possible for a client to extend the system to incorporate at least most of the common physics functionality. Even if it does require more cognitive friction then is generally desirable.

_________________
If at first quads don't succeed tri tri again.

So perhaps what you want is a library which handles:

1. Broad phase collision detection using AABBs or similar
2. Narrow phase collision detection for arbitrary shapes
3. A hook which can be used to by a custom responder to handle the intersection

That sounds reasonable to me. The only problem is that handling collision resolution is one of the hardest parts and not completely separate from what goes on in step 2.

Maybe this means that we can't make a library which meets our demands. Instead it might be wise to focus our efforts on creating a facade for Box2D. Perhaps what we really want isn't a library to handle 2D physics but something else...

Personally, I would like a library which allows clients to issue physical queries. This is something that Box2d isn't so good at, though in practice it might require using both libraries. For example, we might have the following requirements:

* We have a scrolling camera and need to know what's in the viewport
* We want to implement a steering algorithm and need neighboring bodies
* We want to fire a missile and need line of sight information

I'm sure you can come up with some more use cases. In the past I've added methods to Crash to address these cases, but it would be a big step forward to have a pluggable system. That way when the client needs some crazy new question answered we don't need to muck with the API. But how do you expose an API which handles ray casting and simple hit testing without exposing everything?

_________________
My website about game development http://anotherearlymorning.com

That gave me an interesting thought.

What if you present the virtual world where all the bodies reside as an analogy of a database?
Adding bodies to the world via "insert" removing bodies vie "delete" and making queries with "select".

With that in mind, the queries suggested might look like:
* We have a scrolling camera and need to know what's in the viewport


* We want to implement a steering algorithm and need neighboring bodies
Dont entirely understand this one so I may have gotten it wrong.

* We want to fire a missile and need line of sight information


So any body can be interpreted as a table where its contents are any other body that is inside either partly or entirely the original body.
The cool thing is you could add new tables that add additional information about the bodies used in collisions and just do a join ala.



You could also do interesting queries like finding only the objects that intersect two other objects.


Of course this is all very fanciful, just thought it was a neat idea.

_________________
If at first quads don't succeed tri tri again.

I think creating a domain specific language to handle these cases would be awesome -- though maybe not based on SQL . It's also nice to see how you've broken things down into common operations. Great job!

Now, how would one go about creating such a library in Java...

_________________
My website about game development http://anotherearlymorning.com

I'm glad you think it would be cool too (SQL was just convenient since most people are familiar with it). Of course I also can't think about how to implement something like that either.

Anyway I think the following constraints are pretty good.


Myself I don't find the resolution to be that hard, assuming I have all the information about the collision that I need. That's the part I really dislike, deriving information about the collision because it's a lot of fiddly math. Now this is where it becomes domain specific and where step 2 and 3 are not as different as we would like, because the way we want to resolve the collision will dictate what information we need and thus what information the narrow phase detection must provide.
The way I see it the only way around this is to have more than one narrow phase detection strategy. With different strategies providing more or less information, and I'm not sure how reasonable that is. Is the set of all information one could want about a collision finite? If not is the set of all information used in most (80%) scenarios finite? The one really attractive thing about this is that it kind of lets you dial a nob for the trade off between speed and level of information. This has been the main reason I don't use any existing library; they are all over encumbered with functionality I don't need and would run too slow for what I want.

Side note: started thinking about a how one might implement a domain specific querying language for collisions while I was writing, will post thoughts later.

_________________
If at first quads don't succeed tri tri again.

check this great article:
http://www.javaworld.com/javaworld/jw-1 ... tml?page=1

i think this is exactly what you talked about

_________________
Srsly, DaRealSheep

- There will never be a problem that could defeat sunrise or hope. -

i like this topic

I think that for users (programmers ) library must help to "scale" from physics simulation to simple-collision-response.

I like the idea of an api to help this library, less the idea of a query language: too many heads to keep this on a simple way, IMHO.

Why not simply add an interface to all "objects" that can be "Colllidable"?
A sort of "getCollisionInfo" that return a CollisionInfo with all property that we need to calculate collisions: x,y, mass, etc..
when CollisionManager.collide(CollisionStrategy) starts, check every "objects" with "Collidable" Interface and apply given strategy to "objects": if we want full-phisycs collision, we need to specify all information on CollisionInfo of an "object", and so on?

note: CollisionStrategy can be pluggable (an interface?), so everyone can do whatever he/she wants? An so we can test in a common enviroment different strategies?

*: name are just an example

_________________
Blog | Last game Gravity Duck tribute | In progress Gravity Duck tribute

That's very similar to what I was thinking except applied to resolution instead of just detection. As a result some of the same problems apply.
First what happens when your collidable object doesn't have a mass property but the resolver you are using requires it to resolve the collision? True this the clients own fault, but it is still unpleasant.
Second what strategies are provided as part of the library? Are these going to cover the most common scenarios? How hard is it going to be to extend existing strategies when I need to add just a little more detail?

I do think that collision handling (just the geometry) and collision resolution (the physical properties) should be separate using a communication pattern for resolution to hook into handling; but otherwise I tend to agree. I like the idea of using strategies and just storing the properties in a collection for strategies to use as necessary. As it happens I don't mind the answers to the questions I posted, but I think they are worth mentioning as they also apply to my own idea.

_________________
If at first quads don't succeed tri tri again.

so.. anyone have some ideas?

_________________
Blog | Last game Gravity Duck tribute | In progress Gravity Duck tribute

Here's that code I mentioned. http://github.com/psalaets/spash
edit: jar and javadoc at http://github.com/psalaets/spash/downloads

If nothing else this could be a decent starting point towards what is being discussed in this thread.

Some notes:
-Shapes supported out of the box are rectangle, circle and line. You should be able to add your own by implementing Shape but I don't know how well it will work
-No shape rotations
-Does no collision resolution or response, only overlap detection
-Eliminating narrow phase checks with bounding boxes can be done by implementing org.spash.PairFilter
-Nothing is done to stop "tunneling". If your bodies are small enough and/or fast enough the overlap will be missed.
-I was trying out some different ideas for testing so naming could be a little weird

Usage:
1. extend org.spash.DefaultBody or implement org.spash.Body
2. create a Space with a BroadPhase and a BodyOverlapper
3. (optional) add OverlapListeners to Space
4. (optional) add PairFilters to Space
5. add Bodies to Space
6. call Space#processOverlaps
7. clear Space
8. repeat 5-7

Broadphase implementations:
-Brute force
-Sweep and prune style
-Spatial hash

I have 2D grid based ray casting code done but haven't found a good way to integrate it. I'm still thinking about how to do this.

Any thoughts/comments?