I believe that the answer of Sin is the more
realistic ; have you seen that in DAOC the PNJ all have "areas" of
I fact those area can be a small
"sector" of the total geometry of the world , this allow PNJ to
collision detection , ie to stay on the
floor: a test with an Axis Aligned Bounding box Vs the faces
list of this small area (cluster). Also for PNJ against PNJ as
far as they are in the same sector (let say "cluster")
it is much faster... The other optimisation is a simplified collision mesh used instead of the
mesh of the world .
Is is a bit like ZOI (Zone of
Influence) in lightening 3D scene ; they are predefined sectors set in
order to reduce the geometry "reached" by a dynamic light (look in NeverWinter Night how the
shadows "disappear" sometimes .., in order to limit shadow castings to
3 or 4 on the PJ )
----- Original Message -----
From: "Sin Chian" <<EMAIL:
To: "Wong Kong Yew" <<EMAIL:
Sent: Thursday, August
29, 2002 5:01 PM
Subject: Re: [Algorithms] Collision Detection on a MMORPG
> Just a small suggestion: why don't you divide your game world into
> small areas and only check for collision between game objects that
> within the same area?
> One method that come to my
mind immediately is the BSP (binary space
> partitioning) tree approach.
You can organize your world and static
> in the world into a
hierarchical BSP tree, this way you can quickly filter
> through the
static objects that might be colliding with your moving
entities. Another similar method is the Portal-based method.
be you would like to check out the article by Nick Bobic.