continuous3d.java

MASON代表多主体邻里或网络仿真(Multi-Agent Simulator of Neighborhoods or Networks)。它是乔治梅森大学用Java开发的离散事件多主体仿真核心库

package sim.field.continuous;
import sim.field.*;
import sim.util.*;
import java.util.*;

/**
   A storage facility for objects located in a continuous 3D environment.  This facility relates
   objects with 3D double tuples (in the form of Double3D).  The facility extends SparseField, and like
   other objects which extend SparseField (such as SparseGrid3D), the facility can only relate any given
   object with a single location at a time -- that is, an object cannot hold two locations at once in 
   the Continuous3D field.

   <p>Because hashtable lookups are more expensive than just storing the object, we suggest that you ALSO
   store the location of an object in the object itself, so you can read from the object rather than having
   to call getObjectLocation(object).  

   <p>The Continuous3D has been arranged to make neighborhood lookup information efficient.
   It discretizes the space into grid buckets.  The discretization size of the buckets is
   provided in the constructor and cannot be changed thereafter.  If the discretization was 0.7,
   for example, then one bucket would be (0,0,0) to (under 0.7, under 0.7, under 0.7), 
   another bucket would be (0,0,0.0,0.7) to (under 0.7, under 0.7, under 1.4), etc.

   <p>You can use Continuous3D to look up objects in a given region by asking for objects within the
   enclosing buckets, then rummaging through the buckets to find the individuals actually in the desired
   region.  The trick here is to come up with a good bucket size.  If the bucket size is much larger than
   the typical size of a neighborhood lookup, then a typical lookup will include large numbers of objects
   you don't care about; in the worst case, this is an O(n) lookup for something that could have been much
   smaller.  On the other hand, if the bucket size is much smaller than the typical size of a neighborhood
   lookup, then you have to do lots of bucket lookups to cover your range; many if not most of these buckets
   could be empty.  This can also be highly inefficient.

   <p>If your objects are point objects, you have no minimum bound on the discretization size.  But if
   the object are non-point location objects (that is, they have dimensions of width, height, etc.), and
   you care about this overlap when you do distance lookups, then you have a minimum bound on your
   discretization.  In this case, you want to make certain that your discretization is at LEAST larger than
   the LARGEST dimension of any object you plan on putting in the Continuous3D.  The idea here is that if an
   any part of an object fell within the bounding box for your distance lookup task 
   (see getObjectsWithinDistance(...)), you're guaranteed that the stored location of the object must be within
   a bounding box 1 discretization larger in each direction.

   <p>Okay, so that gives you the minimum discretization you should use.  What about the maximum discretization?
   It depends largely on the number of objects expected to occupy a given discretized bucket region, and on what
   kind of lookups you need to do for objects within a given distance.  Searching through one bucket is a hash
   table lookup.  A smaller discretization returns a more accurate sample of objects within the requested
   bounding box, but requires more hash table lookups.  If you have <b>point location</b> objects, and 
   your field is very dense (LOTS of objects in a bucket on average), then we recommend a
   discretization equal to the maximum range distance you are likely to look up; but if your field is very sparse,
   then we recommend a discretization equal to twice the maximum range distance.  You have to tune it.  If you
   have <b>non-point-location</b> objects, then you have two choices.  One approach is to assume a discretization 
   equal to the maximum range distance, but when doing lookups with getObjectsWithinDistance(...), you need to
   state that you're using non-point-location objects.  If you're fairly sparse and your objects aren't big, you
   can set the discretization to twice the maximum range distance, and you should be safe calling getObjectsWithinDistance()
   pretending that your objects are point-location; this saves you a lot of hash table lookups.

   <p>At any rate, do NOT go below the minimum discretization rules. 

   <p>But wait, you say, I have objects of widely varying sizes.  Or I have many different neighborhood lookup
   range needs.  Never fear.  Just use multiple Continuous3Ds of different discretizations.  Depending on your
   needs, you can put all the objects in all of the Continuous3Ds (making different range lookups efficient)
   or various-sized classes of objects in their own Continuous3Ds perhaps.  You have to think this through based
   on your needs.  If all the objects were in all of the Continuous3Ds, you'd think that'd be inefficient in
   moving objects around.  Not really: if the discretizations doubled (or more) each time, you're looking at 
   typically an O(ln n) number of Continuous3Ds, and a corresponding number of lookups.

   <p>Continuous3D objects have a width and a height, but this is <b>only used</b> in computing toroidal
   (wrap-around) situations.  If you don't care about toroidal features, then you can completely disregard
   the width and height.

   <p><b>Warning about getObjectsAtLocation() and numObjectsAtLocation()</b>  
   Because this class uses its superclass (the SparseField) to store the <i>discretized region</i>,
   getObjectsAtLocation(...) and numObjectsAtLocation(...) will not work as you might expect.  The Sparse
   Field is storing Int3Ds (the discretized grid locations), not Double3Ds.  While you could get all the
   objects in the same discretization cell as a given Double3D location with
   getObjectsAtLocation(discretize(theDouble3D)), almost certainly you're going to retain sanity better
   by using the neighborhood functions (getObjectsWithinDistance(...)).
   The same goes for getObjectsAtLocationOfObject() and numObjectsAtLocationOfObject().
*/

public /*strictfp*/ class Continuous3D extends SparseField
    {
    /** Where we store the Double3D values hashed by object */
    public HashMap doubleLocationHash = new HashMap();
    
    public double width;
    public double height;
    public double length;

    public final double discretization;
    
    /** Provide expected bounds on the SparseContinuous3D */
    public Continuous3D(double discretization, double width, double height, double length)
        {
        this.discretization = discretization;
        this.width = width; this.height = height; this.length = length;
        }

    public final Double3D getObjectLocation(Object obj)
        {
        return (Double3D) doubleLocationHash.get(obj);
        }
    
    public final Int3D discretize(final Double3D location)
        {
        final double discretization = this.discretization;  // gets us below 35 bytes so we can be inlined
        return new Int3D((int)(location.x / discretization), 
                         (int)(location.y / discretization), 
                         (int)(location.z / discretization));
        }
    
    public final boolean setObjectLocation(Object obj, final Double3D location)
        {
        boolean result = super.setObjectLocation(obj, discretize(location));
        if (result) doubleLocationHash.put(obj,location);
        return result;
        }
        
    public final Bag clear()
        {
        doubleLocationHash = new HashMap();
        return super.clear();
        }
        
    public final Object remove(final Object obj)
        {
        Object result = super.remove(obj);
        doubleLocationHash.remove(obj);
        return result;
        }
 

    /** Get the width */
    public double getWidth() { return width; }
    
    /** Get the height */
    public double getHeight() { return height; }
    
    /** Get the height */
    public double getLength() { return length; }

    /** Toroidal x */
    public final double tx(final double x) 
        { 
        final double width = this.width; 
        if (x >= 0) return (x % width); 
        final double width2 = (x % width) + width; 
        if (width2 < width) return width2;
        return 0;
        }
    
    /** Toroidal y */
    public final double ty(final double y) 
        { 
        final double height = this.height; 
        if (y >= 0) return (y % height); 
        final double height2 = (y % height) + height;
        if (height2 < height) return height2;
        return 0;
        }
        
    /** Toroidal z */
    public final double tz(final double z) 
        { 
        final double length = this.length; 
        if (z >= 0) return (z % length); 
        final double length2 = (z % length) + length;
        if (length2 < length) return length2;
        return 0;
        }

    /** Simple [and fast] toroidal x.  Use this if the values you'd pass in never stray
        beyond (-width ... width * 2) not inclusive.  It's a bit faster than the full
        toroidal computation as it uses if statements rather than two modulos.
        The following definition:<br>
        { double width = this.width; if (x >= 0) { if (x < width) return x; return x - width; } return x + width; } <br>
        ...produces the shortest code (24 bytes) and is inlined in Hotspot for 1.4.1.   However removing
        the double width = this.width; is likely to be a little faster if most objects are within the
        toroidal region. */
    public double stx(final double x) 
        { if (x >= 0) { if (x < width) return x; return x - width; } return x + width; }
    
    /** Simple [and fast] toroidal y.  Use this if the values you'd pass in never stray
        beyond (-height ... height * 2) not inclusive.  It's a bit faster than the full
        toroidal computation as it uses if statements rather than two modulos.
        The following definition:<br>
        { double height = this.height; if (y >= 0) { if (y < height) return y ; return y - height; } return y + height; } <br>
        ...produces the shortest code (24 bytes) and is inlined in Hotspot for 1.4.1.   However removing
        the double height = this.height; is likely to be a little faster if most objects are within the
        toroidal region. */
    public double sty(final double y) 
        { if (y >= 0) { if (y < height) return y ; return y - height; } return y + height; }

    /** Simple [and fast] toroidal z.  Use this if the values you'd pass in never stray
        beyond (-length ... length * 2) not inclusive.  It's a bit faster than the full
        toroidal computation as it uses if statements rather than two modulos.
        The following definition:<br>
        { double length = this.length; if (z >= 0) { if (z < length) return z ; return z - length; } return z + length; } <br>
        ...produces the shortest code (24 bytes) and is inlined in Hotspot for 1.4.1.   However removing
        the double length = this.length; is likely to be a little faster if most objects are within the
        toroidal region. */
    public double stz(final double z) 
        { if (z >= 0) { if (z < length) return z ; return z - length; } return z + length; }
        
    // some efficiency to avoid width lookups
    double _stx(final double x, final double width) 
        { if (x >= 0) { if (x < width) return x; return x - width; } return x + width; }

    /** Minimum toroidal distance between two values in the X dimension. */
    public double tdx(final double x1, final double x2)
        {
        double width = this.width;
        if (Math.abs(x1-x2) <= width / 2)
            return x1 - x2;  // no wraparounds  -- quick and dirty check
        
        double dx = _stx(x1,width) - _stx(x2,width);
        if (dx * 2 > width) return dx - width;
        if (dx * 2 < -width) return dx + width;
        return dx;
        }
    
    // some efficiency to avoid height lookups
    double _sty(final double y, final double height) 
        { if (y >= 0) { if (y < height) return y ; return y - height; } return y + height; }

    /** Minimum toroidal distance between two values in the Y dimension. */
    public double tdy(final double y1, final double y2)
        {
        double height = this.height;
        if (Math.abs(y1-y2) <= height / 2)
            return y1 - y2;  // no wraparounds  -- quick and dirty check

        double dy = _sty(y1,height) - _sty(y2,height);
        if (dy * 2 > height) return dy - height;
        if (dy * 2 < -height) return dy + height;
        return dy;
        }
    
    double _stz(final double z, final double length)