Member Discussions

I have a problem with an idea that I've been kicking around that no one seems to be able to answer. Essentially the problem boils down to sorting. What is the most efficient way to sort mobile objects by distance in a 3 dimensional environment? Here's the scenario:

There are several transmitters and a variable number of mobile recievers scattered about a 3 dimensional space. I need to determine whether or not each reciever is within range of a given transmitter to recieve a message. It would be too inefficient to go through a linked list or array of ALL the mobile recievers and calculate the distance of each from a given transmitter every time a message is sent. Most of the recievers will be out of range of all but one transmitter at any time. I need a system that can support hundreds of transmitters and recievers that are communicating frequently. I've been cranking my gears trying to determine an efficient abstract data type to use in this scenario. Currently I'm still theorizing linked list but linked lists are very slow at sorting and to compound the problem the data needs to be sorted frequently by dynamic distances. I know there must be a much better way to go about solving this problem, but I don't know what it is. I have come up with one small improvement:

Before performing an in-depth distance calculation between a given reciever and transmitter, check to see that the distance on any given axis is less the the maximum range. If so, then in-depth calculations are unneccesary. This serves as a sort of quick and dirty pre-check.

I hope this makes sense as I realize this is a rediculously abstract question and is only vaguely related to this forum topic. I've only brought it here as I assume some of you have tinkered with complex calculations in 3d environments. Right now this is only an idea, I haven't implemented it in code. If it would be more helpful to see code I can slap that together as well. If anyone can point me in a helpful direction I'll name my first born child after you.

Bob

(Comment added by orbitaldec on Tue Aug 22 13:53:00 2006)

I thought of another useful abstraction. This problem is essentially synonymous with the problem of calculating the range of visibility in a 3d environment, if that's at all helpful.

It sounds like maybe your problem isn't exactly "sort N receivers in distance order from this point" but is instead "find the subset of N receivers that are within distance D of this point".

If that's the case, there are good data structures for solving that problem efficiently. They tend to be memory-intensive because the structure ends up representing O(log N) or O(log N^2) or something copies of each receiver.

First you should read about the binary search tree (BST). I recommend the wiki page. That's useful in 1D for answering the range query "which points lie between x1 and x2?" Binary search trees have the problem that they can become unbalanced if you aren't careful when you build them / add stuff to them. If you are going to be dynamically adding, removing, and moving around sources, then you should consider some type of self-balancing BST like a red-black tree. Again, I recommend the wiki page.

That's 1D. You can handle more dimensions efficiently by nesting the 1D trees. You start out by building a 1D BST on the x coordinate and ignore the y and z coordinates. Then, for each node in that tree (including the interior nodes) you take the contents of its subtree and build a new 1D BST tree on the y coordinate of that set of transmitters. Then for each node in THAT tree you do it again on the z coordinate.

This can very quickly get you the set of transmitters in a 3D box. You can then just do distance calculations for that subset and see which ones are inside of your sphere. (There are also some other tricks for the sphere that will let you skip this step but make building the tree much more labor-intensive.)

So, that's how you do it efficiently. I believe if you have N transmitters and M are inside the range, it will find it in O(M+((log N)^3)) or so. Now you must consider if you really have to do this, because it's complex enough to implement that you might be better off just brute-forcing through all of your transmitters every time you need to do the check. Or, implement the brute-force approach first and when you start finding you're cpu-bound in these range checks, then implement the fancy stuff.

That's beautiful, thank you. Yeah I was considering exploring binary trees, I'm vaguely familiar with the concept though I haven't really ever implemented them. I've been thinking about this problem all day and I've come up with a few possible implementations that I think I'm going to play with. What's your first name again?

It's Jason, although I believe Kjartan is also a perfectly legitimate first name (in Scandinavia and Iceland, anyway).

Good luck with your project - post if you have any more questions (or if you open your game).

This question has come up at least once before on mud forums, so if you write a function that solves it, you might consider making it publically available in one of the many mud-snippet-hosting locations.

I do not think BST is the best choice here. You want something more like a quad-tree.

The concept is pretty simple. It's a tree and the top node represents all of space. It has four children each representing 1/4th of the space of the parent. Each of those has 4 children representing 1/4th of it, etc.

To find the receivers you take the space that represents the range of a transmitter and, starting at the top of the tree, check which of it's children intersect with your transmission space, then check it's children for those that intersect recursively until you reach a transmitter.

This method typically only results in a handful of intersection checks each time (4-8) and you can play with the depth and width of your tree to optimize perfomance if need be.

Since you need to search through Three-Dimensional Space, you can use an Oct-Tree instead of a Quad-Tree.

A triply nested BST as I described will return the set of objects in an arbitrary box faster than an octree. (I think when Teelf said "quadtree" he meant "octree"). This is because in the octree, as you descend in detail in X you descend in Y and Z at the same time, and so you end up having to "find" the X boundary repeatedly in many different Y and Z cells. I think if there are N^3 lowest-level cells in your search volume then you would have to perform O(N^2) comparisons to identify the exact set. In the nested-BST approach, you only have to find the X boundary, Y boundary, and Z boundary once for each side, and the set of objects in your target box is all in one subtree.

There is a trick of adding a fourth dimension which even eliminates the test for being within the target sphere, replacing it with one more nested BST, but I don't remember exactly how it works now. I'll see if I can find it.

(Comment added by Kjartan on Wed Aug 23 9:20:50 2006)

I didn't mean to sound like I was putting down Teelf - what I meant was that Teelf is attacking the 2D problem whereas Raukodacil and I are attacking the 3D problem, because that was what we had assumed you were doing. However, Teelf's quadtrees can be generalized to 3D as octrees, and my nested X-Y-and-Z BSTs can be generalized to 2D as nested X-and-Y BSTs.

The oct-tree is an interesting approach as well, but I believe I've come up with an ideal answer for my specific problem. I wouldn't be able to use the oct-tree because the environment needs to be infinite (well, only limited by the data type used to store the coordinates). I'm planning on having all of this take place in space so there is no need for persistant rooms. Check this out.

1. Adopt a hybrid room system. Round all coordinates down for this part. If an object is moving, as it enters a new set of coordinates search to see if a room already exists at that set. If not, create it. If the room becomes empty again, destroy it.

2. Use one tree to organize the rooms instead of the objects. If there is more then one object in a room, this will save on overhead. Rooms will also be useful for local communication (e.g. I want to broadcast something to everyone else at my coordinates, all I have to do is check the list of contents on the room I am in)

But you ask, how could one tree be used to organize rooms by 3 dimensions? I've written a small demonstration, enough to outline my idea. The code only utilizes 2 dimensions but it's very clear that it could be easily modified to accomodate 3.


#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct listnode {
struct listnode *Next;
} tListNode;

typedef struct roomnode {
struct roomnode *Children[4];
signed short X, Y;
tListNode *Contents;
} tRoomNode;

tRoomNode *Search(tRoomNode *Root, signed short, signed short);

int main(int argc, char **argv)
{
tRoomNode *RootNode;
RootNode = (tRoomNode *)malloc(sizeof(struct roomnode));
memset((void *)RootNode, 0, sizeof(struct roomnode));
RootNode->X = 0;
RootNode->Y = 0;

// X, Y
Search(RootNode, -1, 1); // Quadrant I
Search(RootNode, 1, 1); // Quadrant II
Search(RootNode, 1, -1); // Quadrant III
Search(RootNode, -1, -1); // Quadrant IV
system("PAUSE");
}

tRoomNode *Search(tRoomNode *CurrentNode, signed short TargetX, signed short TargetY)
{
unsigned char Direction;

do {
Direction = (TargetX > CurrentNode->X) + ((TargetY > CurrentNode->Y) << 1);

/*
The direction index is the crux of my idea. It's fairly simple
and should be self-explainatory. You can see how this could
easily be modified to handle three dimensions. Here's how the
direction index will translate into quadrants in 2D.

Direction dX dY Cartesian Quadrant
--------------------------------------
0 - - IV
1 + - III
2 - + I
3 + + II
*/

printf("%d\n", Direction);

CurrentNode = CurrentNode->Children[Direction];
} while ((CurrentNode != NULL) && !((CurrentNode->X == TargetX) && (CurrentNode->Y == TargetY)));

return CurrentNode;
}




Tada! and it still accomodates the ability to travel in any one direction infinitely, or at least as far as the data type permits. What do you think?

(Comment added by orbitaldec on Wed Aug 23 11:00:58 2006)

As an afterthought, I suppose this idea could accurately be described as a quaternary search tree in a two dimensional environment. In a 3D environment, ummm well you get the idea. I believe that this would be more efficient then nestled BST trees but would retain the flexibility.

(Comment added by orbitaldec on Wed Aug 23 14:05:04 2006)

As another afterthought, this definitely retains certain properties of the quad-tree but from what I understand for a structure to qualify as a quad-tree the boundries have to be established. Am I correct in this assumption?

(Comment added by orbitaldec on Wed Aug 23 14:08:02 2006)

Alright I swear this is my last edit. I believe that the other difference with this system would be the ability to change the root node to improve optimization. It seems to be that an oct-tree would be impossible to balance if the origin were static.

Technically speaking, any tree that always splits into four children along two dimensions is a quadtree. Similarly, any tree that splits into eight children along three dimensions in an octree.

I'm not 100% I'm following what you're presenting, but it looks like a form of quadtree to me.

Just two toss in my own two cents - whenever you're talking about points in space as opposed to solids in space, I tend to think about a kd-tree. Read up on 'em.

Your code does sort of resemble binary search tree code, in that each point is itself a boundary in both x and y. You have made a pretty efficient data structure for the query "return the node at (x,y), if any, else return null". For that particular question, it's as efficient in time and more efficient in memory than the nested BSTs I had suggested.

However, I'm not sure that there is an easy way to answer range queries in that structure. I thought what you had wanted was to quickly answer "return all nodes within radius R of (x,y)". Do you see some way of answering that quickly with this structure?

And I'd like to reiterate that this may all be overkill unless you either have a whole lot of sources or a whole lot of queries. If you have say 100 sources and a handful of sensors in a given arena (e.g. solar system) then there is no need for any of this fancy stuff, you'd be fine with brute-force checks of everybody, especially if you used some bounding boxes to avoid unnecessary algebra.

kd-trees are also good for the "what points are in this box" query. They are allegedly hard to keep balanced, but I have never actually tried it. The nested-BSTs approach is as efficient as a kd-tree speed-wise and can be kept balanced by any of the usual approaches for keeping a BST balanced (e.g. red-black).

Yes I'm still working on the "search within a particular range" problem, but I believe that I can still accomodate fairly well with this system. I still need to sit down and pick at it a little bit but if my initial thoughts are correct then this system still fundamentally retains the attributes of the nested bsts only the algorithms will be slightly more complex. Here's the updated code if anyone is interested. Next comes the balancing algorithm *uggghhh* Anyway, thanks for your help everybody!

Bob

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct listnode {
struct listnode *Next;
} tListNode;

typedef struct octnode {
struct octnode *Parent;
struct octnode *Child[8];
signed short X, Y, Z;
tListNode *Contents;
} tOctNode;

typedef signed short s_short;

tOctNode *SearchOctNode(tOctNode *, s_short, s_short, s_short, unsigned char *OctantPtr = NULL);
tOctNode *CreateOctNode(s_short X, s_short Y, s_short Z);
int InsertOctNode(tOctNode *, tOctNode *);

int main(int argc, char **argv)
{
unsigned char Octant;
tOctNode *RootNode, *RetNode;

RootNode = CreateOctNode(0,0,0);
RetNode = CreateOctNode(-1, 1, -1);
InsertOctNode(RootNode, RetNode);
SearchOctNode(RootNode, -2, 1, -2);

/* X Y Z Octant if root is 0,0,0
SearchOctNode(RootNode, 1, 1, 1); // 0
SearchOctNode(RootNode,-1, 1, 1); // 1
SearchOctNode(RootNode, 1, -1, 1); // 2
SearchOctNode(RootNode,-1, -1, 1); // 3
SearchOctNode(RootNode, 1, 1, -1); // 4
SearchOctNode(RootNode,-1, 1, -1); // 5
SearchOctNode(RootNode, 1, -1, -1); // 6
SearchOctNode(RootNode,-1, -1, -1); // 7
*/

system("PAUSE");
}

tOctNode *CreateOctNode(s_short X, s_short Y, s_short Z)
{
tOctNode *NewNode;

NewNode = (tOctNode *)malloc(sizeof(struct octnode));
memset((void *)NewNode, 0, sizeof(struct octnode));
NewNode->X = X;
NewNode->Y = Y;
NewNode->Z = Z;
return NewNode;
}

tOctNode *SearchOctNode(tOctNode *nNode, s_short X, s_short Y, s_short Z, unsigned char *OctantPtr)
{
/*
If the coordinates of the node pointed to by the return value of
this function do not match the parameter coordinates then:

1. The node pointed to by the return value of this function can
be the parent node of a node which contains the parameter
coordinates.

2. OctantPtr will be assigned the value of the proper child
index of the potential parent node.

Otherwise this function will return a pointer to the node which
contains the specified coordinates.
*/

unsigned char Octant;

Octant = (X < nNode->X) + ((Y < nNode->Y) << 1) + ((Z < nNode->Z) << 2);
while ((nNode->Child[Octant] != NULL) && !((X == nNode->X) && (Y == nNode->Y) && (Z == nNode->Z)))
{
nNode = nNode->Child[Octant];
Octant = (X < nNode->X) + ((Y < nNode->Y) << 1) + ((Z < nNode->Z) << 2);
}
if (OctantPtr != NULL)
{
*OctantPtr = Octant;
}

return nNode;
}

int InsertOctNode(tOctNode *Root, tOctNode *Child)
{
/*
Always make sure that a node doesn't already exist with the same
coordinates before inserting it!!!
*/

tOctNode *Parent;
unsigned char Octant;
Parent = SearchOctNode(Root, Child->X, Child->Y, Child->Z, &Octant);
Parent->Child[Octant] = Child;
return 0;
}

(Comment added by orbitaldec on Wed Aug 23 19:58:27 2006)

You are right about a big problem being "find all objects with a particular range of another object" but I was also particularly worried about how to efficiently and dynamically index all of the items so that a query of a particular set of coordinates could return anything located at those coordinates quickly. I think that solving that problem is where this really shines.

I've never really looked into the idea of having multiple nested binary search trees before - that's interesting and seems like a simple solution.

What I personally use is an Oct-Tree with a fixed depth to store terrain information. The lowest child node allowed represents a particular cube of terrain. However, if each of the children at the lowest depth are the same, they are deleted to save space and the terrain type/info of the parent represents the space of each of those children put together. Simple and easy to visualize, at least in my mind! Similar to a quad tree used to store information about a picture on a computer, except in 3D.

I then use a R*-Tree to store more abstract world information (spacial data), and also object information(point data). For example, any tree type terrain within the bounding box of whatever node might be part of the "Dark Forest" and any river terrain type within another bounding box might be the "Quick River." More like R-Trees and unlike normal R*-Treees, I let the nodes overlap and do not split them. (To make it easier for me, and so that a river can run through a forest easily, for example.)
As the point information is also part of the R*-Tree it is easy to see, for instance, how many players are in "The Dark Forest."
The OctTree is used so that the terrain can be changed by players or in world events easily and only affecting a small plot of terrain. For example, a player can dig a tunnel into the side of a mountain. (Changing that terrain spot from mountain rock to mountain tunnel or whatever.) Then in the R*-Tree the node representing that Mountain can also define mountain tunnel locations to "A tunnel under mount whatever." Also, a major event can change a large plot of terrain by affecting a higher level node. I think it works pretty well for me.
However, as your game takes place in space, you wouldn't have to resolve specific points down to terrain plots so an OctTree like I use it wouldn't be necessary.

Sorry if this doesn't make any sense!
Teelf knows more about RTrees than I do, I think he's been using them a while longer - so maybe he can clarify.
You can define bounding boxes in an R*-Tree for the transmission distance of a transmitter (the spacial data) and any receivers (the point data) and then do a pretty easy check for what points are within that space.