ObjectPlot

ObjectPlot

Java open source code for rapid, multi-threaded tracking of millions of 2D or 3D positions using an Octree.

  • Language: Java
  • Released: Apr 8, 2011
    Last Update: Jun 30, 2011

Developed originally to track terrain, unit markers, and other things on (or in) the map of a real-time game. While serving in part as a simple keyed set (like a TreeMap) containing everything on the map, ObjectPlot's primary purpose is to locate all the objects in a given region as quickly as possible. Location time depends on the number of objects in and around the given region rather than on the total number of stored objects.

Each entry has a location and a bounding radius (which can range from zero to a billion distance units—the maximum size of the map). A search region is usually a point and a radius (which can also be zero). Search regions that are line segments (to track the terrain being traversed, line-of-sight, etc.), and a few other types, are also supported. ObjectPlot handles adds, deletions, location changes, and queries from multiple threads with high efficiency.

ObjectPlot tracks locations with an Octree, adjusting its structure as necessary to handle adds, deletes, and movement while keeping complexity to a minimum.

ObjectPlot requires Java 1.6 due to its use of java.util.concurrent.ConcurrentSkipListMap. It is completely thread-safe and carefully designed to allow parallel updates and queries with little or no blocking. It is fully Javadoc'ed.

The source code includes a simple example program.

Hide

Usage Example

The following is a simplified version of the sample program included with the source code:

import java.util.*;
import rrc12.util.*;
import rrc12.util.map.*;

/** A simple example of the use of ObjectPlot. Note that this demo does
 * not show off ObjectPlot's ability to handle multi-threaded adds,
 * removes, and gets. */
public class Example  {

    /** A class for objects to be put in an ObjectPlot instance. */
    private static class MapObject  {
        /** A unique identifier.  Ought to have a good hash code--
         * particularly in the lower digits--because ObjectPlot uses
         * a primitive hash table in some cases.  Numbers 1-1000 are
         * good.  Multiples of 256 would be bad. */
        public Integer   key;
        /** The location. */
        public Location  objectLocation;
        /** The size of the object as a circle/sphere, which is kept
         * simple for this example.  A real-world object is apt to have
         * a more complicated size, and hence fancier calculations would
         * be necessary where this field is used. */
        public double    sizeRadius;
    }

    public static void main( String[] args )  {

        final ObjectPlot  masterPlot = new ObjectPlot();

        // Generate data.

        Random  diceRoll = new Random();
        for (int i = 0; i < 1000000; i++)  {
            MapObject  mo = new MapObject();
            mo.key = new Integer( i );
            // Use random location in z == 0 plane.
            double  x = (diceRoll.nextDouble() * 200000) - 100000;
            double  y = (diceRoll.nextDouble() * 200000) - 100000;
            mo.objectLocation = new Location( x, y, 0 );
            // Object is within a circle with a diameter of 200.
            mo.sizeRadius = 100;

            // Add object to masterPlot.
            masterPlot.addAndPlace( mo.key, mo, mo.objectLocation,
                        mo.sizeRadius );
        }

        // Locate objects close to a point.

        final int[]       opCount = new int[]  { 0 };
        final LinkedList  list = new LinkedList();
        final Location    point = new Location( 5000, 5000, 0 );

        masterPlot.getAreaContents( point, 250, new Selection()  {
            public void select( Object o )  {
                opCount[0]++;
                if ( !(o instanceof MapObject))
                    // Can't really happen here, but often there are
                    // entries we don't care about no matter where
                    // they are.
                    return;
                MapObject  retrieved = (MapObject) o;
                // Make sure object is really within desired distance.
                // Take into account the real location and the object's
                // real size.
                if (point.getDistance( retrieved.objectLocation ) >
                            250 + retrieved.sizeRadius )
                    // Failed the critical check.  ObjectPlot will return
                    // objects that could never pass this test simply
                    // because this test must be made here anyway, and why
                    // risk having it called twice?  Other objects are
                    // within the parameters we specified--ObjectPlot
                    // could not reject them, but we don't want them
                    // anyway.  Here, we're disposing of objects that are
                    // too far away.
                    return;
                // We got something we wanted.  Increment and save.
                list.addLast( o );
            }
        } );

        // Now have counts and list.  The difference between 1000000 and
        // opCount is the savings provided by ObjectPlot.
        System.out.println( "\nObjects in circle:" );
        System.out.println( "Original count: " + opCount[0] +
                    "   Actual count: " + list.size() );
    }
}
Hide

Javadoc

The javadoc for the ObjectPlot class, in plain text:

rrc12.util.map Class ObjectPlot

java.lang.Object
  rrc12.util.map.ObjectPlot

All Implemented Interfaces: java.io.Externalizable, java.io.Serializable

ObjectPlot

public class ObjectPlot extends java.lang.Object implements java.io.Externalizable

Tracks objects' locations in three (or two) dimensions, useful for maps. Intended for massively multi-threaded use, with objects being frequently added, moved, and removed.

Essentially, answers the question: which objects fall within a certain distance of a given point at this time? Because the true position of an object may be somewhat complicated, this class tries to only exclude as many objects as possible. It will often return objects that do not meet the criterion, sometimes because it lacks sufficient information and often because it would take too much time to exclude them.

This class can drastically reduce search times when the area or volume to be searched is small relative to the area or volume over which entered objects are scattered and when most of the entries have small radii relative to this area or volume.

Each entry has a point location and a bounding radius. The area to be searched is likewise a sphere or circle. Objects are guaranteed to be returned if if their sphere intersects the search sphere. Note that radii of zero can make sense for both the search sphere (to determine if that location is within an entry) and the objects' bounding spheres. (But if all the entries have a radii of zero, the search radius must be larger or nothing will be found.)

The tracked objects require key values, or identification objects. Typically these are Long instances, though just about anything that implements Comparable and Serializable will do. Whatever is used as an ID should have a hashCode method that returns a wide selection in the last bits of its hash code (ObjectPlot uses a simple hash table for some purposes).

In fact, it is really the key that ObjectPlot tracks, rather than the object itself. It is quite possible that the thing to be tracked might be represented by different objects at different times. Its key, or identity, must always keep the same value (whether or not two keys are the "same" is determined by the keys' Object.equals method.)

An ObjectPlot instance handles distances of up to 1 billion units in each of the three dimensions. Object densities greater than two per cubic unit will degrade performance. It would be best to keep it well below one per cubic unit.

Distances are stored and manipulated as doubles, but the organizing structure goes no smaller than cubes two units on a side. For working on a normal sized map, one unit being one meter should be fine, allowing the earth and the moon to be included and efficiently allowing up to two objects per square or cubic meter. For much larger or much smaller scales, a unit should be much larger or much smaller.

Note: several methods require that a value not be changed until the method returns. This means primarily that the passed object should not be accessible from another thread, but also that changes should not be made to it from within the callback method in the passed Selection instance.

Constructor Detail

public ObjectPlot()

Creates a new ObjectPlot instance.

Method Detail

public java.lang.Object putAndPlace(java.lang.Object id,
                                java.lang.Object o,
                                Location point,
                                double radius)

Adds an Object instance to this ObjectPlot at a particular location. If an object was already there with the specified id, it is replaced (and returned). The location maintained by this ObjectPlot is only approximate and is used to limit the size of the list when getAreaContents is called.

Parameters:

  • id - the object's identifying number. May be null, in which case nothing is done and false returned.
  • o - the object to be added.
  • point - the point that, roughly, is where the object will be placed. If null, it will not have a location but remain in this ObjectPlot.
  • radius - the radius of the bounding circle centered on point.

Returns: The previous object with this id number. Null if there was none. This object if it was already there.

See Also: addAndPlace, place, remove, get

addAndPlace()

public java.lang.Object addAndPlace(java.lang.Object id,
                                java.lang.Object o,
                                Location point,
                                double radius)

Adds an Object instance to this ObjectPlot at a particular location. If an object is already there with the specified ID, the add fails and the original remains untouched at its old location. The location maintained by this ObjectPlot is only approximate and is used to limit the size of the list when getAreaContents is called. This method is marginally faster than putAndPlace for ordinary adds.

Parameters:

  • id - the object's identifying number. May be null, in which case nothing is done and null returned.
  • o - the object to be added.
  • point - the point that, roughly, is where the object will be placed. If null, it will not have a location but will remain in this ObjectPlot.
  • radius - the radius of the bounding circle centered on point.

Returns: null if the add was successful. If there was already an object using that key, that object is returned.

See Also: place, remove, get

remove()

public java.lang.Object remove(java.lang.Object id)

Removes an Object instance from this ObjectPlot.

Parameters:

  • id - the identifying number of the object to be removed. May be null, in which case nothing is done and a null returned.

Returns: the object removed. Will be null if nothing was done.

See Also: get

clear()

public void clear()

Removes all content and location information from this ObjectPlot.

isEmpty()

public boolean isEmpty()

Returns true if this ObjectPlot is empty and false if it has at least one element. A return of false does not mean that any of the contents have actual locations.

getMaxDistance()

public int getMaxDistance()

Returns the maximum distance between any two points in this ObjectPlot space. Never more than half the maximum value of an integer, so the returned value may safely be doubled.

size()

public int size()

Returns the number of objects stored in this ObjectPlot. None of the objects need have locations to be counted. This method is not efficient: it has to manually count each entry.

containsKey()

public boolean containsKey(java.lang.Object id)

Returns true if this ObjectPlot contains an item with the specified identification and false if it does not.

Parameters:

  • id - The identification object of the stored object to be checked. May be null, in which case the method returns false.

get()

public java.lang.Object get(java.lang.Object id)

Returns the Object instance identified by the specified id object. Returns null if there is no such object.

Parameters:

  • id - The identification object of the stored object to be retrieved. May be null, in which case a null is returned.

place()

public void place(java.lang.Object id,
              Location point,
              double radius)

Places an object already in this ObjectPlot at a specified location. The maintained location is only approximate, and is used to limit the size of the list when getAreaContents is called.

Parameters:

  • id - the identifier used when this object was added to this ObjectPlot (via addAndPlace or putAndPlace). May be null, in which case nothing is done.
  • point - the point that, roughly, is where the object will be placed. If null, it will not have a location and be removed from the visible map, but remain in this ObjectPlot.
  • radius - the radius of the bounding circle centered on point.

getAreaContents()

public void getAreaContents(Location point,
                            double radius,
                            Selection s)

Passes all the possibly-relevant objects surrounding the specified location to the passed Selection instance's select method. This method should not make duplicate calls with the same object, but the calling program should not become unstable if it does.

Parameters:

  • point - the location whose surrounding objects should be passed. Do not change this value until the method returns!
  • radius - the maximum range desired. Objects beyond this range may be returned, but everything within this range will be returned.
  • s - a Selection instance whose select method is called at least once with each Object instance.

getAreaContents()

 public void getAreaContents(java.awt.geom.Rectangle2D rectangle,
                        Selection s)

Passes all the possibly-relevant objects within the specified rectangle to the passed Selection instance's select method. This would be all objects whose x and y coordinates fall within it, with the z coordinate being ignored. This method should not make duplicate calls with the same object, but the calling program should not become unstable if it does.

This method can be used to locate everything visible in a display if the display is looking straight down on the x/y plane. Basically good for 2D graphics drawn in immediate mode. Not so good for 3D or retained mode graphics.

Parameters:

  • rectangle - the area whose objects should be passed. Do not change this value until the method returns!
  • s - a Selection instance whose select method is called at least once with each Object instance.

getAreaContents()

 public void getAreaContents(java.util.Collection mc,
                        Selection s)

Passes all the possibly-relevant objects that might be within the specified MapCircle objects to the passed Selection instance's select method. This method should not make duplicate calls with the same object, but the calling program should not become unstable if it does.

Parameters:

  • mc - a Collection of map circles containing the objects that should be passed. Do not change these values until the method returns!
  • s - a Selection instance whose select method is called at least once with each Object instance.

getPositionsContents()

public void getPositionContents(Position position,
                            Selection s)

Passes all objects that might possibly intersect the specified position to the passed Selection instance's select method. Note that this method is likely to return only objects with a radius, or area, of their own. (New Position implementations that have an area in the z = 0 plane or that have a volume might be able to capture points. This method was originally intended to locate the terrain over which a path traveled.)

Parameters:

  • position - the position. Do not change this value until the method returns!
  • s - the Selection instance for receiving data.

getAll()

public void getAll(Selection s)

Calls the select method of the passed Selection instance once for every object in this ObjectPlot that has a location. Differs from getEverything in not passing location-less objects. No object will be passed twice in one call to getAll. Much faster than calling one of the get...Contents methods and passing large areas.

getEverything()

public void getEverything(Selection s)

Calls the select method of the passed Selection instance once for every object in this ObjectPlot. Differs from getAll in that it passes location-less objects also, and it will be marginally faster if there are no or very few location-less objects. No object will be passed twice in one call to this method. No object will not be passed.

read()

public void read(java.io.ObjectInput in)
      throws java.io.IOException,
             java.lang.ClassNotFoundException

Reads data into this ObjectPlot. Note that location data is not read in. Each object read will be nowhere until the place method is called on it!

Throws: java.io.IOException java.lang.ClassNotFoundException

write()

public void write(java.io.ObjectOutput out)
       throws java.io.IOException

Writes the contents of this ObjectPlot to the specified output. Note that this data does not include locations! Each object must have another way to recover its position if it has one.

Throws: java.io.IOException

readExternal()

public final void readExternal(java.io.ObjectInput in)
                    throws java.io.IOException,
                           java.lang.ClassNotFoundException

Specified by: readExternal in interface java.io.Externalizable

Throws: java.io.IOException java.lang.ClassNotFoundException

writeExternal()

public final void writeExternal(java.io.ObjectOutput out)
                     throws java.io.IOException

Specified by: writeExternal in interface java.io.Externalizable

Throws: java.io.IOException

You need to log-in or create an account
  • Create an account
  • Log-in

Please use your real name.

Activation link will be sent to this address.

Minimum 8 characters

Enter your password again

Clicking this button confirms you read and agreed to the terms of use and privacy policy.

X

Save your watchlist

Fill your details below to receive project updates from your watch list - including new versions, price changes and discounts.

I agree to the terms of use and privacy policy.

2 licenses, starting from From » FREE View Licenses 14 day money-back guarantee
Post a comment

Or enter your name and Email
No comments have been posted yet.