Sign in to follow this  

Point based physics engine

This topic is 1171 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, first post here. I hope it's the right section.

 

I'm developing a small game for learning, and I was wondering if you knew a free/open source game engine that would fit it well, or else some tutorials to avoid common pitfalls so I could brew my own.

 

These are the main characteristics of the game world, from the physical point of view:

  • the world is a 3D cartesian space
  • objects only occupy a single point, that is they all have 3 coordinates (x, y, z)
  • gravity pushes objects down on the z axis, other forces may act on the other axes (if an object is thrown horizontally, it must fall both down and horizontally)
  • different objects can have the same coordinate in space
  • certain points in the space can be blocked, for example if I block the point (0, 0, 0), an object initially on (0, 0, 10) will fall (because of the gravity) for 9 points down and stop at (0, 0, 1).
  • For now, impact is not considered between objects or when they fall on the "blocked points", however I should be able to query the physics engine to implement the right game logic (to know, for example, if an object is still falling down or has reached the "floor", in which direction it's moving, with which speed/acceleration..)
  • objects can "die" and be removed, and new objects can be spawned

I'm using Java, so I'd need either a pure java library or one with bindings (like Box2D).

 

I'm sure I could tweak a 2D or 3D engine to achieve this (arguably very simple) simulation, or write my own as I had started doing, but for the former, I fear it would be like using a Ferrari as a catering van, for the latter I'd like to focus more on the game logic and learn the physics as I go.

 

Also, there is a certain focus on speed, as the number of objects can grow quite a lot and they do have a good amount of game logic - so I'd like to spend the least possible amount of time on the physics step.

 

Any advice welcome. Thanks!

Edited by koteko

Share this post


Link to post
Share on other sites

I've forgotten to add that I don't need rendering. I "just" need a library to handle the most important parts of the simulation.

 

I've been searching a lot to no avail - my physics knowledge is little and rusty. Can anyone provide any pointers or better terms than the naive ones I've given, so that my search can be more focused?

 

My guess is what I need is a "dynamic physics engine" implementing Newtonian physics and collision detections on (also) points. But most of the stuff I've found is for rigid body dynamics and soft body dynamics.

Edited by koteko

Share this post


Link to post
Share on other sites

It's not likely that you'll find an engine that deals with points, as classical physics deals with objects that have extent, shape and mass. In addition, it's not clear from your description whether your intent is to use real numbers (a number with a fractional part) or integers, as you mention an object dropping 9 "points" and stopping** at (0,0,1) if blocked at (0,0,0). I think you will find that available physics/collision engines, in addition to using finite objects (vs infinitesimally small points), use real numbers (floating point).

 

** as opposed, for instance, to stopping at (0,0,+particle-radius).

Edited by Buckeye

Share this post


Link to post
Share on other sites

Yep, I feared that. However I do remember lectures of physics dealing with dimensionless points with cartesian coordinates. It's been too long though. Possibly it was Kinematics rathern than Dynamics. Mass can be present - just the size of the point should be transcurable. The usual formulas to change acceleration through a force, than changing velocity due to acceleration and in turn changing position due to velocity, they all apply. It would just take me ages to put the equation in, as I'm very, very rusty on this stuff.

 

Regarding the numbers, it's not a big deal if the engine/library uses real numbers. In the game logic I can approximate the position to the closest integers in all 3 dimensions and put the object onto the discrete grid I guess.

 

Actually thinking about it, I could use an object with "extent and shape" as you say. If my objects were spheres with radius of half the "unit" (say, 0.5 meter radius), and in the game logic I approximated the position of the center of the sphere to the closest integer (in all 3 dimensions), I might get what I want.

 

Can you advise on a decent library usable from Java that does have bounding spheres?

Share this post


Link to post
Share on other sites

I'm not a Java programmer. However, googling for "java physics engine sphere" yields ~17 million hits, including JBox2D (apparently a Box2D port) and several youtube videos that should get you heading in the right direction.

 


It's been too long though ...  I'm very, very rusty on this stuff.

 

Been there! wink.png Before trying to integrate a particular library, you may want to spend some time brushing up on Newtonian physics, as that will likely ease the pain.

Share this post


Link to post
Share on other sites

Were you perhaps thinking of simulating it more like fluid physics, where the points interact with each other through forces based on distance? Like atoms and other realistic thingys.

 

Since that would give them such an 'extent' (although blurry) of sorts.

 

If all the points had a limited radius of influence, you could use a hash map or a grid to do the physics in O(N) (since for each point, you only have a fixed number of surrounding grid cells to check, and only a very limited number of other points can fit in those cells) I think... :|

 

It would be almost equal to having integer coords and only interacting with points in adjacent coords. Just a bit more detail.

Edited by Waterlimon

Share this post


Link to post
Share on other sites

Uhm no I wasn't thinking about fluids, and I don't know enough about them to tell if they are applicable to what I need :)

 

Here's an example of the functionality I had in mind:

 

- Point A is at (0, 0, 0) moving 1 meter per second on the positive x direction ("east" in common language)

- After 1 second, A is a (1, 0, 0), where point B is in a static position (velocity = 0). The collision is not acted upon at this level.

 

The physics engine would be moving around objects using just three things:

 

- acceleration

- velocity

- position

 

And changing the acceleration only when told to do so externally, by the game logic. Friction for now could be ignored.

 

The game logic would usually call World.getCollisions(point) on point A and get back a list of points having exactly the same coordinate, and also in a different context call World.getPointsInRadius(point, radius) to efficiently get all points in the spherical area around the point determined by the radius.

 

I was thinking on implementing it manually, as it shouldn't be too much of a big deal, but I'm especially worried about collision detection - looking up neighbouring cells with an hashmap sounds like a killer.

Share this post


Link to post
Share on other sites

Ok I see, so you want basically a grid based (3D) game with physics?

 

What I was thinking is that give each 'point' a float position to make the physics smooth.

 

However, you could still have the physics rely on the grid cells - a point may only interact with neighboring grid cells.

 

 

I did something similar for a 2D grid game, because I wanted the player to be able to stand anywhere, not just at the center of a grid cell. But the collision detection still worked based on grid cells (the player was 1 grid cell sized square)

 

 

What I did was to have a normal grid for the world (you know, grass in this cell, stone here etc.)

And each moving entity had:

-Float position, velocity

-Integer position (grid position)

And the physics applied velocity to the float position, which was rounded to get the grid position (so it can find neighbor cells to do collision detection, like if in a cell above ground, limit the float position from going too low into the ground).

Share this post


Link to post
Share on other sites

I think that's a good idea. I wasn't taking into consideration the fact that using integers for the position means I'd have to make my unit length definitely less than 1 meter. Silly me.

 

I'm brushing up on my physics, and implementing the system using floats now. It's good stuff to learn anyway. Thanks for the pointers!

Share this post


Link to post
Share on other sites

If anybody stumbles upon this and has a similar problem/need, here's some solutions I've gathered. All pure Java.

 

  • Traer Physics: created for use in Processing, is, in fact, pure Java. Easy to understand and extend. Implements Euler, Modified Euler and Runge-Kutta 4 integrators. I've written a Verlet Velocity integrator class, that's almost as fast as Euler but more precise (will put on github). A good middle way between Euler and RK4.
  • Toxilibs: a more advanced collection of utilities for physics, collision detection etc. Will probably end up using this if I stop writing my own. It uses Verlet Integration.
  • And of course, last and (for now) least, my own dirty little physics engine. I'm trying to write the simplest and fastest version without caring too much about readability/code reuse. If you are trying to learn these things like, it might be useful to study my code. Or not.

Share this post


Link to post
Share on other sites

You can do this yourself pretty easily. I imagine your simulation of forces can be very simple and straightforward. To me it sounds like the collision detection would be the hardest part, but luckily for just points you can do this very easily.

 

You can use for a broadphase a hashed grid. The idea is extremely simple to implement and very fast. You can look up source code on how to construct a hashed grid in Ericson's Orange Book on Real Time Collision Detection.

The idea is to take the floating point components (x, y, z) of a point and then hash them into an integer index. The grid isn't stored in memory. Here's an example of finding out which grid cell an arbitrary point is in:

#define GRID_CELL_SIZE = 5.0
Vec3 particlePosition = particle.position;

int x = particlePosition.x / GRID_CELL_SIZE;
int y = particlePosition.y / GRID_CELL_SIZE;
int z = particlePosition.z / GRID_CELL_SIZE;

int hash = CoordinateHash( x, y, z );

// Example of hashing a coordinate
int CoordinateHash( int x, int y, int z )
{
    const int someLargePrimeNumber0;
    const int someLargePrimeNumber1;
    const int someLargePrimeNumber2;

    return x * someLargePrimeNumber0 + y * someLargePrimeNumber1 + z * someLargePrimeNumber2;
}

This is used to place the point into a hash table bucket. The hash collisions can be resolved through chaining.

 

To check for collision in the broadphase, hash a point and check it's chain for near-proximity with any other points in the chain (or check collision for a pair of points in any way you desire). Please note it doesn't matter if two different grid cells map to the same bucket, since you'd be doing a proximity check on a collision chain anyways.

Edited by Randy Gaul

Share this post


Link to post
Share on other sites

Yep, in fact I've implemented a small Verlet Velocity integration in a few hours (mostly spent reading around and refreshing my physics).

 

For collisions, I was actually thinking on using (or implementing) a KD-Tree allowing range searches. As far as I understand, for points that's about the best. I haven't yet looked into it though: is the approach you mention comparable or totally unrelated?

Share this post


Link to post
Share on other sites

This topic is 1171 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this