From:	"Bikko" <bikko AT enteract DOT com>
Newsgroups:	alt.games.programming,comp.os.msdos.djgpp
Subject:	Re: Collision Detection
Date:	Thu, 9 Apr 1998 16:46:59 -0500
Organization:	EnterAct L.L.C. Turbo-Elite News Server
Lines:	39
Message-ID:	<6gjfgs$3il$1@eve.enteract.com>
References:	<6ghudj$krl$1 AT o DOT online DOT no>
NNTP-Posting-Host:	207.229.150.111
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

[iC] wrote in message <6ghudj$krl$1 AT o DOT online DOT no>...
>I'm writing a game ( 2d top down) which has a linked list of
>objects(structs), to check whetever objects collide I run a loop like this
:
>
>
>this works but is so damn slooooow....
>Has anyone else got a better idea on how to do this ?
>

It might help to optimize your check_bund function.

Probably the biggest speed improvement is if you partition the world into
128x128 or 256x256 (or any size) rectangles, so that you have an array of
"map zones".  Each map zone can have a linked list of objects in that map
zone.

This is a form of limiting the test-against set.
When  you get an entity that you want to check bounding boxes with all other
entities, you instead check only the entities in the zone(s) against your
first entity.

Note that by entity, I mean object....  You could consider an entity to be
in one zone, by it's origin point, or by it's top-left corner point
(depending on how the game works).  You could test the entity against all
the entities in the zone your test entity is in, and all adjacent zones (in
case the test entity is overlapping)....

Or if you use the top-left corner, you could just test against the zone the
test entity is in, and the zone to the right, right-bottom, and bottom.

It depends on how many entities you have... if you don't have many, this
probably won't help much...  but if you don't have many, and your method is
slow, your bounding-box checking function might be the bottleneck.


Bikko

- Raw text -