Page 1 of 3

Moving a static and rehashing

Posted: Sun Sep 20, 2009 10:59 pm
by mobilebros
I was wondering if there was a better/faster way, when moving a static object, to tell space's static hash about it. Right now I move a static shape every dt and call cpSpaceRehashStatic, this works but probably would be slow with a lot of static objects in the space since that function seems to iterate all of them. It seems like there might be another way... I've thought about removing the shape and then adding it back in, but wasn't sure if that would be more expensive. Any ideas?

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 2:03 am
by dieterweb
why do you not add the shape to the normal non-static hash? You can do this even when you do not add the body and hance control the position by yourself.

thomas

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 9:16 am
by slembcke
If you are moving a static object and then rehashing every step, your shape isn't really static. ;)

The only difference between static and active shapes is that static ones aren't rehashed every frame, and they can be hashed with different parameters.

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 9:59 am
by mobilebros
Oh ok, I'm getting a clearer picture now. I should have been more clear before; Its only sometimes that I'll move the object for a period of time, and then when I'm not I want it to just sit still. Now I could do what dieterweb said and just make it active without adding the body, however I'm trying to optimize (its on the iphone) so I'm not sure it'd be the best. So I take it there's no easy way to "update" just one static object within the hash? Thanks.

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 12:38 pm
by slembcke
Well, in that case I guess it works out to treat it as a static object if it's not moving all the time.

The long answer is that you can rehash a single object in the spatial hash, but there isn't an accompanying function to let you update a single shape at the level of the space.

cpSpaceHashRehashObject(cpSpaceHash *hash, void *obj, cpHashValue id) is the function that you are looking for, and you would use it something like this:

Code: Select all

cpShapeCacheBB(shape);
cpSpaceHashRehashObject(space->staticShapes, shape, shape->id);
There is a downside to doing this though, it only adds references and doesn't remove them. Collisions won't get missed at the new position, but you will also get false positives at the old position. For an objects that only move in a small area this is fine, but don't do it for many objects that move all around the screen without doing an occasional full rehash.

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 1:19 pm
by mobilebros
Thanks Scott! Of course that downside is a pretty big one, I would not want false positives especially if they start to accumulate. Do you think I might be able to remove it from the hash first, and then add it back in. Something like:

Code: Select all

cpSpaceHashRemove(space->staticShapes, shape, shape->id);

cpShapeCacheBB(shape);
cpSpaceHashRehashObject(space->staticShapes, shape, shape->id);
I suppose the question would be if this is more optimal than rehashing everything, I suppose it would if it works.... By the way I'm doing all this for this project here:http://code.google.com/p/chipmunk-spacemanager/ I'm basically trying to get the cocos2d part (What they call actions, moving, rotating, etc) to also update their chipmunk counterparts with correct values.

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 2:20 pm
by slembcke
Well, I don't mean that you would get false positives on the collisions themselves, but that the spatial hash would return potentially colliding pairs for an object near were the object was before it was rehashed. This just means that Chipmunk has to perform more expensive collision checks to determine if the objects really are colliding. The spatial hash already returns quite a few false positives given that it only works on a low resolution grid, and only works with AABBs. The problem is only going to be when you've smeared your objects all around the static hash because you will get a large number of false positives that need to be checked using more expensive checks.

Also, in the code you posted. You would be removing the object you wanted to rehash, then told the hash to rehash the removed object. CRASH. Removing the object also doesn't remove all of it's references. It only blanks them out until the next time the hash is rebuilt. That wouldn't solve the problem either.

I would just try using the code I posted alone. If you notice slowdowns as time goes on, have it rehash the static hash every few seconds or so.

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 4:11 pm
by mobilebros
Ok thanks again, that makes sense of course; the hash is only used for the initial discovery of potentials. I suppose I meant an "insert" not a "rehash" in the code I posted before. I'll try it a few ways now that I have a better understanding, thanks!

Re: Moving a static and rehashing

Posted: Mon Sep 21, 2009 9:08 pm
by mobilebros
For those of you interested I went with this method:

Code: Select all

	
cpSpaceHashRemove(_space->staticShapes, shape, shape->id);
cpShapeCacheBB(shape);
cpSpaceHashInsert(_space->staticShapes, shape, shape->id, shape->bb);
It essentially like removing a shape from the space and adding it back in except I left out the shapeRemovalArbiterReject() call because I wasn't sure it was necessary. This does work, still not sure if its the "right" or fastest way, but it's what i'll stick with for now.

Re: Moving a static and rehashing

Posted: Thu Sep 23, 2010 4:03 am
by dieterweb
One question:

I use

cpShapeCacheBB(shape);
cpSpaceHashRehashObject(space->activeShapes, shape, shape->id);

to update the hash for an active shape I move in my code, when chipmunk is "paused" so no spaceStep is called. When running chipmunk again, active shapes are always rehashed every spaceStep, right. So no need to worry about false positives in the hash.

How about the code of mobilebros:

cpSpaceHashRemove(_space->staticShapes, shape, shape->id);
cpShapeCacheBB(shape);
cpSpaceHashInsert(_space->staticShapes, shape, shape->id, shape->bb);

Will this make a complete rehasing obsolete? Especially when we are talking about static shapes?