World wrap around

[hungrybutterfly]

Oh ok I never thought about the idea of just averaging the bodies' positions. So what else do I need to average aside from position and velocity?

Also when you say 'complex contact' can you give an example?

And when I've exhausted that option I'll try looking into joints..... boo hoo hoo hoo. The pain.

[slembcke]

I would consider it complex when you have multiple objects resting on each other instead of just bumping and separating. Because of the way that the averaging is decreasing the collision impulse, stacked objects would act really mushy depending on how many or few of their copies are also touching.

[hungrybutterfly]

Ok i've been playing around with this for a bit now looking at making my own joint type. But I'm too stupid. However I did manage to get a version using built in joint types by doing the following....

* Create 2 identical bodies, one on the left (Object A) of the screen and one on the right (Object B).
* Create a body (Object C) with an infinite moment and no shapes.
* Create several pin joins (red and blue lines) to join the whole load together in a crazy way.

Image.png

The red lines keep A and B a set distance apart and the blue make sure they rotate together. And it actually worked. But it's really messy.

So instead I thought i'd make some special fudge and modify cpSpace.c for my purpose. So in cpSpaceStep, just after the collision, I go through all the shapes in the world that cross the screen edge, offset their position by the screen width, do the collision tests again for those shapes only and then un-offset the positions back to where they were originally. And it works too (or seems to so far). So if anybody needs a similar solution let me know and I can provide code snips.

Aside from not being able to easily integrate any future changes to Chipmunk does anyone forsee any problems with this approach (extreme collision etc.) ?

[hungrybutterfly]

I had a request for the code changes I made to Chipmunk to perform world wrap around so I thought I should post them here incase anyone else found them useful. I used this method successfully in quite a few situations but I'm sure there's something that it won't work with. I'm not sure what version I used then so my line numbers are probably wrong compared to the current version.This will only give you world wrap on the X axis but it should be really easy to extend it to Y. I've put little 'xxx' comments every time I made a change to Chipmunk so they're easy to spot.

Code: Select all

cpArbiter.cpp - Line 161

	for(int i=0; i<arb->numContacts; i++){
		cpContact *con = &arb->contacts[i];
		
		// Calculate the offsets.
		con->r1 = cpvsub(con->p, a->p);
		con->r2 = cpvsub(con->p, b->p);

		// xxx Step 4. Now adjust the collision point the body A only.
		con->r1.x -= arb->fOffset;
		
		// Calculate the mass normal.
		cpFloat mass_sum = a->m_inv + b->m_inv;

Code: Select all

cpArbiter.h - line 69

	// Time stamp of the arbiter. (from cpSpace)
	int stamp;

	// xxx storage for world wrap around
	cpFloat fOffset;
} cpArbiter;

Code: Select all

cpSpace.cpp - line 151

	cpCollPairFunc pairFunc = {0, 0, alwaysCollide, NULL};
	space->defaultPairFunc = pairFunc;
	space->collFuncSet = cpHashSetNew(0, collFuncSetEql, collFuncSetTrans);
	space->collFuncSet->default_value = &space->defaultPairFunc;
	
	// xxx Set up the wrap around stuff
	space->worldWrapWidth = 0;
	space->currentOffset = 0;
	space->wrappedShapes = cpArrayNew(0);

	return space;
}

Code: Select all

cpSpace.cpp - line 159

// xxx Set the wrap value. 0 will disable it.
void cpSpaceSetWorldWrapWidth(cpSpace *space, float fWidth)
{
	space->worldWrapWidth = fWidth;
}

Code: Select all

cpSpace.cpp - line 190

	if(space->collFuncSet)
		cpHashSetEach(space->collFuncSet, &freeWrap, NULL);
	cpHashSetFree(space->collFuncSet);

	// xxx shut down the wrap stuff
	cpArrayFree(space->wrappedShapes);
}

Code: Select all

cpSpace.cpp - line 431

		// Timestamp the arbiter.
		arb->stamp = space->stamp;
		arb->a = a; arb->b = b; // TODO: Investigate why this is still necessary?

		// xxx Step 3. Remember the offset for this collision so we can subtract it later in the arbiter
		arb->fOffset = space->currentOffset;

		// Inject the new contact points into the arbiter.
		cpArbiterInject(arb, contacts, numContacts);

Code: Select all

cpSpace.cpp - line 457

	cpShape *shape = (cpShape *)ptr;
	cpSpace *space = (cpSpace *)data;
	cpSpaceHashQuery(space->staticShapes, shape, shape->bb, &queryFunc, space);

	// xxx Step 1. This will add shapes to the wrap array if they cross over the world width.
	// It's just convenient and faster to build up the wrap array here rather than traverse the hash again.
	if (space->worldWrapWidth)
	{
		if (space->currentOffset == 0 && (shape->bb.l < 0 || shape->bb.r >= space->worldWrapWidth))
			cpArrayPush(space->wrappedShapes, shape);
	}

Code: Select all

cpSpace.cpp - line 508

	// Collide!
	cpSpaceHashEach(space->activeShapes, &active2staticIter, space);
	cpSpaceHashQueryRehash(space->activeShapes, &queryFunc, space);

	// xxx Step 2. This chunk will go through all the shapes added to the wrap around list and perform more collision
	// tests but offset by the world width
	if (space->worldWrapWidth)
	{
		// go through all the shapes we found touching the edge of the world
		cpArray *wrappedShapes = space->wrappedShapes;
		for (int i = wrappedShapes->num-1;i >= 0;i--)
		{
			cpShape *shape = (cpShape*) wrappedShapes->arr[i];

			// offset it by the world width
			if (shape->bb.l < 0)
				 space->currentOffset = space->worldWrapWidth;
			else
				 space->currentOffset = -space->worldWrapWidth;
			shape->body->p.x += space->currentOffset;
			updateBBCache(shape, NULL);

			// test collision for just this shape
			cpSpaceHashQuery(space->staticShapes, shape, shape->bb, &queryFunc, space);
			cpSpaceHashObject(space->activeShapes, shape, &queryFunc, space, shape->id);

			// now undo the offset back to where it really is
			shape->body->p.x -= space->currentOffset;
			space->currentOffset = 0;
			updateBBCache(shape, NULL);

			cpArrayDeleteIndex(space->wrappedShapes, i);
		}
	}

	// Prestep the arbiters.
	for(int i=0; i<arbiters->num; i++)
		cpArbiterPreStep((cpArbiter *)arbiters->arr[i], dt_inv);

Code: Select all

cpSpace.h - line 69

	// Set of collisionpair functions.
	cpHashSet *collFuncSet;
	// Default collision pair function.
	cpCollPairFunc defaultPairFunc;

	// xxx world wrap around stuff
	cpFloat worldWrapWidth;
	cpFloat currentOffset;
	cpArray *wrappedShapes;
} cpSpace;

Code: Select all

cpSpace.h - line 120

// Update the space.
void cpSpaceStep(cpSpace *space, cpFloat dt);

// xxx Set the wrap value. Only wrapping in X is supported. 0 will disable it.
void cpSpaceSetWorldWrapWidth(cpSpace *space, float fWidth);

Hope this helps someone.

Aaron

[mohnjahoney]

Aaron,
Thanks for posting this wrapping code. Have others tried this with any success?

I wonder what the current consensus is on how this should be done.

A - using joints
B - using wrapping code as above
other?

Any chance this will become part of Chipmunk in the near future?
-john

[mohnjahoney]

world wrapping = toroidal world or periodic boundary conditions

I have been interested in world-wrapping for the purposes of doing physics/material science research.

I have implemented some additions to chipmunk which seem to provide this feature.

@slembke
First of all, is there any chance you would want to incorporate this into chipmunk? This seems like a relatively important feature to include for people who want to gaming, or for people like me who are interested in bulk material simulations.

Second, is there anyone else interested in playing with this code? I am happy to share.
I tried using the code changes suggested by hugrybutterfly,
http://www.slembcke.net/forums/viewtopi ... wrap#p1884
but without success, thus the effort to do it myself.

Feel free to contact me at j r m a h o n e y <at> u c d a v i s . e d u
-john

[slembcke]

I'm not sure I guess. The problem is that it makes pretty much everything more complicated? It would basically have to be coded into not only the collision detection code, but also the collision solver and all of the joints as well. That is a lot of effort involved for a feature that only a small fraction of people want to use. I think this has only come up maybe a half a dozen times, and half of those just wanted to make an asteroids clone. It's come up about as often as people wanting Chipmunk to include features that make it trivial to implement a 2D Portal clone.

I've been thinking that I should start a directory of community contributed code that I distribute with Chipmunk. Then projects like this would be visible and people would be able to use them if they wish. It also means that I wouldn't have to spend my limited time supporting and testing them if only a handful of people use each one.

[mohnjahoney]

More complicated = yes.
But in a pretty modular way.

I was hoping to tidy things up and send you a demo - both for sharing with whomever, and also to hopefully get some feedback on the method.

There are only a couple of minor changes I made to the existing code.

The rest hinges around:
- a pair of new constraint classes
- 4 sensors that form a boundary around your world
- callbacks that handle collisions between your world objects and these sensors
create/delete the appropriate mirror objects
link mirror objects with new constraints

Given a space with some objects in it, I would like to make the world wrapping as clean as possible

makeSpaceToroidal(my_space, parameters)

This adds the appropriate sensors and sets up the callbacks (which are based on collision_type).

Regarding the 2D Portal clone, looking around at existing demos, it seems that all of them implement this as a "teleportation". That is, when a certain criterion is satisfied, the object is removed and replaced somewhere else. This is different that what I am doing. When the object "peeks" through the first portal, I want that part to "peek" out of the other portal.

Advantages:
- objects are not teleported on top of something
- dense systems (or ones that have larger objects) are better simulated as bulk
- looks nice

Here is a screenshot of this wrapping in action for 10 balls.
red = normal
green = paired horizontally
blue = paired vertically
gray = both horizontal and vertical
brown = non interacting - about to be deleted

And 1000 balls is more fun...

Picture 45.png

Picture 39.png

[asinglepixel]

For an easier way to do this, particularly for a Thrust-style game, simply give your map some blank space on either side. The ship flies into this area and has no physics in view besides your ship.

Implement your wraparound as "if ship.x < 0 then ship.x = WAY_RIGHT" and similarly if the ship goes off to the right, reset its position back to x=0. The player won't notice anything happened.

Self-promo: For a Thrust-style game that implements this kind of wrap-around, have a look at Rocket Gold.

[mohnjahoney]

asinglepixel,

You are absolutely right that this is the simplest way to implement a wrapped world. And for many situations this will work just great.

Unfortunately, I must admit how many hours I have worked to obtain a type of wrapping that often looks *almost* the same.
However, in the systems I am studying, there are noticeable differences.

The first problem is that if you "teleport" objects around, you run the risk of landing on top of something.
Also, extended objects in a wrapped world should be able to "peek" around to the other side - interacting with things on both sides of the screen at the same time.

If you are a physicist/engineer/material scientist doing simulations of bulk materials, you will notice that simulations with the "teleport" wrapping lead to edge effects. Periodic boundary condition simulations always come with some degree of interpretation, but when wrapping is implemented in the simpler way, the statistics can be significantly different.