Shape Query

[nsxdavid]

Is there any facility (perhaps buried under the API level) for doing a simple "does a given shape overlap any other shape" type query?

Essentially I want to be able to just test if a shape I'm about to place into the field would immediately be touching/embeded in some other shape. In my particular case, static ones. I have a playfield that has some line segments and circles that represent the static environment. The player can indicate where to drop a playing piece (and drag it around until satisfied). I want to check on the start and end of the drag if the shape can fit in that spot free of any collision. The line segment and box (AABB or otherwise) query won't cut it.

-- David
geoDefense / geoDefense Swarm

[slembcke]

Not directly, but there are other ways to get the same effect.

If you can live with a coarse approximation, you can do a bounding box query over the area that the shape will use when it's added. It's not going to be exact, but it will be pretty close.

If you want it to be exact, create your body and shape. Set the shape to be a sensor, and don't add the body to the space yet. Create collision handlers for the sensor that increments a counter in the begin() callback and decrements it in separate(). When the counter is 0, then there are no overlapping shapes. If you are spawning objects from a single spawning point, you can just keep the same sensor shape.

[slembcke]

As a side note, GeoDefense is awesome. I think it is one of my girlfriend's favorite iPhone games.

[nsxdavid]

Thanks! Glad you (or at least your GF) is enjoying it.

I'm working on geoDefense 2 actually. And I'm attempting to use Chipmunk to solve one of the sticky (pun intended) problems in the UI. Namely when you drag a tower near another tower or the path. Right now it gets stuck... I want it to sorta travel along it in a natural way, but if you pull past the obstacle it'll snap past it. I think the sensor approach will do the trick!

-- David
geoDefense / geoDefense Swarm

[slembcke]

Though I'm not sure how you will solve the overlap without running the Chipmunk solver and allow it to push the objects apart. Letting Chipmunk solve the overlap will work, though it might be easier and more efficient to use stiff constraints like you do with Jakobsen/vertlet style physics actually. http://www.teknikus.dk/tj/gdc2001.htm

Another thing to keep in mind is that you'll need to make sure it doesn't try to push the placement into the middle of a group of towers.

Don't get me wrong, it was one of my favorite games too, but I think she may have lost sleep over it a few times.

[nsxdavid]

Yeah, I've gotten the basics of this hacked up. It sorta of works, but not quite.

What I am doing is I have two bodies. One is slaved to the mouse position (by just moving it), and it's shape is a sensor. It tracks its contacts so it knows if the mouse position is clear or not.

The other body has a joint connecting it to the mouse body. So it follows along but doesn't move through other static things in the scene. This represents the tower being placed (and where the sprite shows). Pretty much what I'm after.

If the sensor at the mouse shows all clear, however, it'll warp the placing tower body to where the mouse body (aka sensor) is. So in this way as you "pull through" a path it'll snap to the other side when all clear. Which is, again, what I'm after.

The part that doesn't work, like you pointed out I think, is what happens if you have a group of placed towers and you just tap in the midst of them. The new tower sorta just plops right in the midst as it has no time to find its way out (or there may be no way out).

I was going to adjust the code to see if the placing tower shape was in the clear, but the collision tracking trick won't work here because it reporting a collision doesn't mean it's not in the clear. When you are pulling it against another tower or a path it is in the clear (due to collision keeping them apart) but reporting as colliding. So it's not really telling me what I want to know... which is... is it penetrating other shapes post-solve.

I think the easy solution is that I need to check if the mouse body had ever been in the clear during a touch/move/end cycle. If not, then the placing tower also never was in the clear. Going to try this next.

Of course the easier answer would be if I could just ask Chipmunk "does this shape overlap any other" sorta thing. Which, presumably ... somewhere... such an internal function may exist.

-- David

[slembcke]

Oh, I had to read that a couple of times, but I see what the issue is. You need to know if it's clear to add the following body on touch down. I think the easiest thing to do would be to delay adding the follower until you've ended a frame with the sensor shape being clear of collisions. On touch up, only place the tower if the follower was added. Even if you could do a shape query at touch down, you would still have to wait for the first moment that the sensor was clear to be able to add the tower anyway.

Shape Queries: The long answer
They aren't impossible, I just haven't thought a lot about what would be an ideal API. In our game Twilight Golf, we essentially did shape queries to give a simulated preview of the ball's path and collision point. (video) It's just a modified version of queryFunc() from cpSpace.c. I modified it just now to work with the 5.2.x, but didn't actually test it, buyer beware. I should look into this again probably as the 5.2.x changes actually simplified a bunch of the memory management requirements. Just beware that Twilight Golf code is probably cursed and will relegate anything that uses it to the same financial failure.

Code: Select all

static inline int
queryReject(cpShape *a, cpShape *b)
{
	return
		// BBoxes must overlap
		!cpBBintersects(a->bb, b->bb)
		// Don't collide shapes attached to the same body.
		|| a->body == b->body
		// Don't collide objects in the same non-zero group
		|| (a->group && b->group && a->group == b->group)
		// Don't collide objects that don't share at least on layer.
		|| !(a->layers & b->layers);
}

static void
queryFunc(cpShape *a, cpShape *b, bool *didCollide)
{
	// Reject any of the simple cases
	if(queryReject(a,b)) return;
	
	// Shape 'a' should have the lower shape type. (required by cpCollideShapes() )
	if(a->klass->type > b->klass->type){
		cpShape *temp = a;
		a = b;
		b = temp;
	}
	
	// Narrow-phase collision detection.
	cpContact contacts[CP_MAX_CONTACTS_PER_ARBITER];
	int numContacts = cpCollideShapes(a, b, &contacts);
	
	(*didCollide) = (numContacts > 0);
}

static bool
checkCollision(cpSpace *space, cpShape *shape)
{
	cpShapeCacheBB(shape);
	bool didCollide = FALSE;

	cpSpaceHashQuery(space->staticShapes, shape, shape->bb, (cpSpaceHashQueryFunc)queryFunc, &didCollide);
	if(didCollide) return TRUE;

	cpSpaceHashQuery(space->activeShapes, shape, shape->bb, (cpSpaceHashQueryFunc)queryFunc, &didCollide);
	return didCollide;
}

[slembcke]

Also, are you going to be at GDC?

[ShiftZ]

Ive found that cpSpacePointQuery returns sensor shapes, and i believe cpSpaceSegmentQuery too.
I think it should be considered as a bug.

[slembcke]

Hrm. I guess I could see why people would want them filtered, but I've actually used queries returning sensors on purpose before. If it's an issue with cpSpace*Query(), you can easily filter them out from the callback. For cpSpace*QueryFirst() you can still use layers to separate them. Is there a case where layers are insufficient?