[MUD-Dev] Finding Space
yospe at hawaii.edu
Sun Aug 17 21:48:05 New Zealand Standard Time 1997
On Fri, 15 Aug 1997, Michael Hohensee wrote:
:I've been working up a system in which objects take up space in a
:co-ordinate based world, and I seem to have hit a stumbling block. I
:know that others have probably solved this problem (Physmud++ *must*
:have had to solve this ;), so maybe someone can help me.
Yes and no. Same as collision detection... exactly the same, in fact, as
this is a big part of what I consider collision detection. I use spheres
around the center of volume (not to be confused with the center of mass)
of a group of objects, single composite object, individual components...
and then I assume that the particulate (smallest tracked) components are
spherical. This reduces any "will I fit?" problem to a series of fast
comparisons that only get ugly when a collision is immenent (and since I
track in four dimensions, the fourth being a minute projection forward in
time, I have a chance to prepare for collisions.)
:Here's how it works:
:We are representing a three dimensional space, but in this example we'll
:restrict it to two dimensions.
: 0 2 4 6 8 1012
: 1 3 5 7 9 11
:'-' = empty space, '*' = space taken up by an object.
:For simplicity, all objects take up a cubical volume of space (square,
:in this case). Objects are held in a tree or linked list of structs
:which contain the origin point of the object, and the dimensions of the
:object. For example, the big square in the picture above would be
:Location=6,1 -- Dimensions=6,3.
First off, spheres are simpler in 3D than cubes. Little bit of advice from
a graphical engine hand. MUCH simpler.
:I can store anything to any location I want, but I want to avoid
:overlapping objects onto each other (it's bad), so I need to be able to
:find empty space between objects. I can't just try to place an object
:in every location, since there isn't any granularity to this space (I
:use floats instead of ints).
And thus the reason for spheres. Use a transform and a single calculation
gives you the shortest distance between two points. Then just check to
make sure that's more than the radius of both spheres summed.
:A friend of mine glanced at this problem and said, "Oh, that's a
:bin-stuffing problem." Of course, he didn't remember anything else
:about the problem, so here I am. :)
Um. Bin stuffing would have been ints and a grid of locations.
:Does anyone have the answer? :)
Well, if mine made any sense...
"You? We can't take you," said the Dean, glaring at the Librarian.
"You don't know a thing about guerilla warfare." - Reaper Man,
Nathan F. Yospe Registered Looney by Terry Pratchett
yospe at hawaii.edu http://www2.hawaii.edu/~yospe Meow
More information about the MUD-Dev