Spatial Awareness System

This is the first release of my Spatial Awareness System on March 13, 2008. (The download is small (200k) and includes a basic installer.)

A 'Spatial Awareness System' is a tool which keeps track of relationships between a large collection of objects represented by 3d co-ordinates (as floats).

The typical use for a spatial awareness system (SAS) is for AI and network traffic culling. In AI you may have a limited range that the entity is supposed to be aware of. Take for example a gun turret with a limited sight distance. The awarness system will automatically collect the set of objects which are within this range. The AI code can either iterate over this awareness list directly or respond to discrete events when objects come into and out of the awareness range.

For network traffic you may want to reduce bandwidth by only transmitting packets for objects that are within a certain distance relative to other objects in the world.

To use the spatial awareness system simply #include the file 'spatial_awareness_system.h'

Spin up an instance of a spatial awareness system by using the factory method.

Example: SPATIAL_AWARENESS_SYSTEM::SpatialAwarenessSystem *sas = SPATIAL_AWARENESS_SYSTEM::Factory::Create(strategy,this);

'strategy' is one of three possible spatial awareness system implementations to choose from. They are:

SAS_BRUTE_FORCE : Implements the brute force N-squared approach where every object is compared to every other object each frame. This is very slow and only used for testing purposes.

SAS_LAZY_KDTREE : Uses a KdTree to help maintain the awareness state. It is called 'lazy' because the KdTree is only updated every 16 frames. This can produce some infrequent false negatives but never false positives.

SAS_SAP_SYSTEM : Uses Pierre Terdiman's Sweep and Prune algorithm (www.codercorner.com) as the main engine for maintaining awareness.

The 'this' pointer refers to an implementation of the SpatialAwarenessObserver pure virtual class that will receive event notifications as objects enter and leave awareness.

The objects for which awareness is being maintained are referred to by a unique 64bit guid. If you wish, you can cast an object pointer to this GUID if necessary.

The test application is located in the directory 'SphereTest'. Simply load 'SphereTest.sln' into Visual Studio. (There is nothing windows specific about the code, other than the demo app, and the spatial awareness system itself should theoretically compile and run on any OS.)

After you build and run the application you can hit the 'R' key to toggle the visual display of the awareness data. Rendering is disabled by default since simulations with extremely large object counts can take a long time to display.

Pressing the 'M' key will write out a text file called 'sas_memory.txt' that shows all memory allocations performed by the current SAS

Press ESC to exit the application.

The command line argument passed in controls the number of objects to be simulated. A maximum of 65535 objects are allowed. For real-time visualization it is best to keep the count under 2,000 otherwise rendering is too slow and the number of connections fill the screen. Simulations on the order of tens of thousands of moving objects runs surprisingly fast. Objects with an awareness range of zero do not maintain awareness of other entities, yet, other entities are aware of it.

To experiment with the demo program you need to load the file 'ENTITY.CPP' and make some small code changes.

The first #define EVENT_BASED controls whether the objects are rendered by iterating the awareness, or by tracking create/delete events. Iteration is much faster but the option is there to debug that all of the create/delete events are being handled correctly.

The next #define ALLOW_DELETES controls whether objects are constantly created and deleted.

The next line defines which of the three SAS strategies to employ.

The #define LIFETIME controls the random lifespan given to objects which are being created/deleted.

I would consider this kind of alpha software at this point.

The brute force and lazy kdtree versions seem to be stable and work correctly in all test conditions.

The Lazy KdTree is fairly high performance and doesn't have performance or memory issues except in pathological cases where every object is nearly aware of every other object.

The sweep and prune implementation appears stable, high performance, and has a reasonable memory footprint. In this release, there appears to be a glitch or two when object deletions are enabled. I am still tracking this down.

The reason I am releasing this code is because, first it is built upon some other open source code and I felt it only fair to make it available. The second, and most important reason, is that I am looking for feedback, bug fixes, improvements, suggestions, and anything else I can learn from the rest of the development community on solving this particular problem.

For questions or feedback, please write to:

John W. Ratcliff
mailto: jratcliff@infiniplex.net