2D Game Dynamics Engine Requirements

[rje]

I'm currently working on a 2D Game Dynamics Engine and was wondering what people here would find useful. I've avoided the term Physics engine because, well it isn't really. My current requirements are:

• 2D Collision detection between oriented rectangles, circles (swept SAT tests) and geometrically defined tiles.
• Simple collision response
• Ray casting (line of sight)
• Tile based world management

These features call all be found else where, however the main design goal of this engine is CPU and memory efficiency. It wont have, for example, any rendering capabilities, that will all need to be handled by the end user. So, any thoughts/ideas/requirements that would make it useful to you?

[rachil0]

I'd say if you're going out of the way to make a reusable package, I would make sure to include robust spatial partitioning to reduce the number of entity-to-entity collision tests. Either spatially bucketing objects into different partitions, or something more advanced like quadtrees. This can also accelerate raycasting/line of sight, by letting you bypass large collections of entities with one test.

You're probably already be planning this, but didn't see it expressed in the requirement list so I thought I'd pipe up.

[rje]

Thanks - I forgot that one. I'm considering a few options at the moment, quad trees and this.

The type of algorithm depends on the number of objects you want to test. I'm using simple AABB's for under 5 objects at the moment because they are very cheap to calculate.

[Flashkit]

definitely quad tree... and high speed collision detection between fast moving objects

[rachil0]

Interesting reference, but I personally wouldn't do it that way. I can't see the rationale for obfuscating the hashing procedure with an intermediate function (especially f = (p1*x) ^ (p2*y) ^ (p3*z)... that has zero intuition to me).

I totally dig on the idea of putting things into seperate containers like they describe (hashing/bucketing) but for 2D geometrically based data I think it's more sensible bucket things into a 2D array, where each index is based on one of your spatial axis. IE, bucket[g(x)][g(y)].push(object). (Where g is some function that rounds to the nearest 100, or nearest 1000, then rescales into a 0..N-1 range, or something).

In particular, what happens when your object extends a little bit past the bounds of its containing bucket or hashtable region? With simple 2D bucketing you can still deduce the a maximal set of buckets it interacts with. Look at the radius r, and then your neighborhood of interactable objects are inside buckets[x-r .. x+r][y-r .. y+r]. (I'd typically design the size of the buckets so that you're just looking 1 neighboring bucket at most).

If you're using that hashing approach, of course you check for collision against all objects that are in the same hash container, but it is not at all clear what other buckets should be included for consideration when the object is starting to poke out past the boundary of the hash container. I for one can't even fathom what geometrical shape would hash to the same key - so I don't even know how to detect this case is occuring.

Even if I did know that my object extended significantly outside the hash container (some oracle told me), I still have no idea of how to compute which neighboring container(s) I am encroaching upon.

The only solution I see generate a bunch of new points at the extents of my object, and then push these whiskers through the hash function and see where they get mapped to. (And then check collisions against objects in those hash containers, if any). Seems wonky to me, unless there is something very clever about that approach that I am missing.

[rje]

and high speed collision detection between fast moving objects

Thats one of the main requirements, I'm using swept SAT for this at the moment. For many reasons I'm limiting the world objects (but not the tiles) to either rectangles (can be rotated) and circles. I'm currently assuming that most game objects could be reduced to one of these - I dont see many games using triangles, pentagons etc as the collisions shapes, or is that too limiting?

[rachil0]

If you're going to push for rotated rectangles, I'd make the code work for any convex polygon (it won't be that much more complicated, and that's a pretty flexible modeling primitive).

On the other hand, I think circles and non-rotated rectangles can get the job done most of the time. You can always make build up aggregations of these shapes if you need to collision-detect something unusual. On my own 2D projects, my policy is to support just circles, and just say to hell with it.

[EvilKris]

How about a good tutorial on how to use it instead of doing what everyone else does by just throwing it on FlashKit for people to download, scratch their heads over for 5 minutes, and then dispose of. There's no point in designing an open-source engine without tutorials to go with it- you're reducing your target audience to about a half-dozen peeps who will spend all day long trying to figure out how it works.
Strangely enough though, most people don't consider this when they design their own 2d engines for the Flash public, they expect people will understand by themselves too much.

[rje]

I thought I'd dig up this old thread - I released the first part of this engine today - just the physics at the moment. There is a thread in the Math & Physics forum with links to the project, source and demos.