Print

Print


Okay, I see the issue.  You're doing toroidal lookups.  The toroidal code presently runs from max to min, doing toroidal wrap-around, without considering if a grid cell was looked up twice.  For example, if you have a 10x10 grid and are in location <5,5>, and do a 5-element range lookup, cell <5,0> will be in that collection, along with cell <5,10>, which is the exact same cell.

If you switch to NON-toroidal, you won't get duplicates any more.

So lemme think about this for bit.

Sean

On Aug 10, 2012, at 5:42 PM, Chris Hollander wrote:

> Hi Sean,
> 
> This is the code that I'm using to add objects to the SparseGrid2D.
> The reason that I shuffle the bag is because at each time step we
> search through its contents, and we don't want to always be pulling
> the same object if the neighbors are unchanged from t to t+1.
> 
> 
> 
>        IFirmAgent a = null;
>        this.agentSchedulePosition = this.currentSchedulePosition;
> 
>        for (int i = 0; i < numAgents; i++) {
>            a = new SimpleFirmAgent(
>                    this.random,
>                    this,
>                    this.nextAgentId,
>                    upkeepCost,
>                    initialFirmWealth,
>                    priceAdjustmentRate,
>                    priceAdjustmentThreshold,
>                    visionRadius,
>                    interactionRadius,
>                    movementRange);
> 
>            this.incrementNextAgentId();
> 
>            // Uniformly distribute the agents in the environment.
>            int x, y;
>            do {
>                x = random.nextInt(width);
>                y = random.nextInt(height);
>            } while (this.agentscape.getObjectsAtLocation(x, y) != null);
>            this.agentscape.setObjectLocation(a, x, y);
>            a.setLocation(x, y);
>        }
> 
> 
> For however many agents we need, we create a firm agent, pick a random
> x and y location, make sure that that space on the grid is empty, and
> then put the agent there.
> 
> 
> 
> 
> 
> On Fri, Aug 10, 2012 at 3:47 AM, Sean Luke <[log in to unmask]> wrote:
>> Chris, can you give me the code you used to *add* objects to the field prior to doing this?  No biggie, but it'd be nice to see.
>> 
>> Also, why are you shuffling the bag at the end?
>> 
>> Sean
>> 
>> 
>> On Aug 10, 2012, at 2:39 AM, Chris Hollander wrote:
>> 
>>> Hi Sean, I realized after I left work that I should have attached the
>>> file, but here is a slightly older version that does exactly the same
>>> thing (but doesn't filter to remove duplicates) with some prints to
>>> show the results... and yes, SparseGrid2D is being used.
>>> 
>>> 
>>>   protected void determineNeighbors(int range) {
>>>       neighbors.clear();
>>> 
>>>       // Preallocate bag sizes to try and speed up performance...
>>>       Bag neighborBag = new Bag( (int) Math.pow(2 * (range + 1), 2) );
>>>       IntBag xs = new IntBag( (int) Math.pow(2 * (range + 1), 2) );
>>>       IntBag ys = new IntBag( (int) Math.pow(2 * (range + 1), 2) );
>>> 
>>>       state.agentscape.getNeighborsMaxDistance(
>>>               this.getLocation().x,
>>>               this.getLocation().y,
>>>               range, true, neighborBag, xs, ys);
>>> 
>>>       System.out.print(neighborBag.numObjs + ": ");
>>>       for(Object o : neighborBag) {
>>>           System.out.print(((SimpleFirmAgent) o).getId() + ", ");
>>>       }
>>>       System.out.println();
>>> 
>>>       // Randomize the order of the neighbors to ensure that interactions
>>>       // aren't predictable.
>>>       neighborBag.shuffle(state.random);
>>> 
>>>       // Cast the bag to a list of agents and ensure that an agent it not its
>>>       // own neighbor. This casting makes it a lot easier to do other things.
>>>       for(Object o : neighborBag) {
>>>           if((SimpleFirmAgent) o != this)   // don't add THIS agent
>>>               neighbors.add(new Neighbor((SimpleFirmAgent) o));
>>>       }
>>> 
>>>       System.out.println("Agent ID " + this.id + ": " +
>>> neighbors.size() + ";; " + neighbors);  // Neighbor.toString prints
>>> the neighbor agent's ID
>>>   }
>>> 
>>> 
>>> And this is the output:
>>> 
>>> 
>>> 45: 9, 9, 9, 7, 7, 3, 3, 2, 5, 2, 5, 8, 8, 0, 1, 6, 0, 1, 6, 4, 4, 9,
>>> 9, 9, 7, 7, 3, 3, 2, 5, 2, 5, 8, 8, 0, 1, 6, 0, 1, 6, 4, 4, 9, 9, 9,
>>> Agent ID 9: 36;; [8, 4, 5, 0, 4, 6, 4, 0, 3, 3, 4, 2, 2, 1, 7, 7, 6,
>>> 2, 8, 8, 7, 1, 8, 3, 5, 2, 0, 1, 7, 0, 3, 6, 1, 5, 6, 5]
>>> 49: 9, 4, 9, 4, 9, 7, 7, 3, 3, 2, 5, 2, 5, 2, 8, 8, 0, 1, 6, 0, 1, 6,
>>> 9, 4, 9, 4, 9, 7, 7, 3, 3, 2, 5, 2, 5, 2, 8, 8, 0, 1, 6, 0, 1, 6, 9,
>>> 4, 9, 4, 9,
>>> Agent ID 9: 40;; [2, 4, 2, 6, 3, 3, 2, 8, 7, 4, 4, 8, 2, 2, 5, 6, 1,
>>> 7, 2, 4, 0, 0, 6, 3, 0, 1, 8, 8, 5, 3, 5, 4, 1, 6, 4, 7, 7, 5, 0, 1]
>>> 49: 3, 3, 3, 2, 5, 2, 5, 8, 8, 6, 0, 1, 6, 0, 1, 6, 9, 4, 9, 4, 7, 7,
>>> 7, 3, 3, 3, 2, 5, 2, 5, 8, 8, 6, 0, 1, 6, 0, 1, 6, 9, 4, 9, 4, 7, 7,
>>> 7, 3, 3, 3,
>>> Agent ID 3: 40;; [0, 2, 4, 7, 6, 8, 4, 7, 8, 1, 4, 9, 6, 7, 6, 2, 7,
>>> 2, 6, 7, 0, 9, 4, 6, 2, 5, 1, 1, 8, 0, 5, 5, 6, 8, 7, 0, 1, 9, 9, 5]
>>> 49: 3, 3, 3, 5, 2, 5, 2, 5, 8, 8, 8, 0, 1, 6, 0, 1, 6, 4, 9, 4, 9, 7,
>>> 7, 3, 3, 3, 5, 2, 5, 2, 5, 8, 8, 8, 0, 1, 6, 0, 1, 6, 4, 9, 4, 9, 7,
>>> 7, 3, 3, 3,
>>> Agent ID 3: 40;; [6, 9, 5, 6, 0, 9, 1, 8, 5, 6, 8, 1, 4, 1, 4, 6, 9,
>>> 8, 4, 2, 7, 7, 8, 2, 7, 8, 0, 5, 1, 0, 4, 8, 0, 5, 7, 2, 2, 9, 5, 5]
>>> 49: 2, 5, 2, 5, 2, 8, 8, 0, 1, 6, 0, 1, 6, 9, 4, 9, 4, 9, 7, 7, 3, 3,
>>> 2, 5, 2, 5, 2, 8, 8, 0, 1, 6, 0, 1, 6, 9, 4, 9, 4, 9, 7, 7, 3, 3, 2,
>>> 5, 2, 5, 2,
>>> Agent ID 2: 40;; [6, 3, 3, 3, 5, 5, 7, 6, 7, 0, 7, 6, 1, 9, 5, 9, 4,
>>> 0, 9, 5, 4, 3, 4, 5, 9, 5, 1, 8, 4, 1, 0, 6, 9, 7, 1, 8, 8, 9, 8, 0]
>>> 49: 2, 4, 9, 2, 4, 9, 2, 7, 7, 3, 3, 5, 5, 8, 8, 0, 1, 6, 0, 1, 6, 2,
>>> 4, 9, 2, 4, 9, 2, 7, 7, 3, 3, 5, 5, 8, 8, 0, 1, 6, 0, 1, 6, 2, 4, 9,
>>> 2, 4, 9, 2,
>>> Agent ID 2: 40;; [4, 7, 0, 3, 8, 9, 0, 8, 9, 8, 7, 1, 0, 6, 5, 5, 9,
>>> 9, 3, 5, 4, 1, 3, 0, 7, 4, 9, 9, 1, 4, 6, 6, 6, 1, 8, 3, 7, 4, 4, 5]
>>> 49: 5, 5, 5, 8, 8, 8, 0, 1, 6, 0, 1, 6, 2, 4, 9, 2, 4, 9, 7, 7, 3, 3,
>>> 3, 5, 5, 5, 8, 8, 8, 0, 1, 6, 0, 1, 6, 2, 4, 9, 2, 4, 9, 7, 7, 3, 3,
>>> 3, 5, 5, 5,
>>> Agent ID 5: 40;; [8, 0, 7, 1, 9, 1, 1, 0, 7, 7, 3, 3, 9, 8, 4, 2, 3,
>>> 2, 4, 6, 2, 8, 3, 0, 4, 6, 9, 6, 8, 6, 8, 4, 1, 3, 0, 2, 9, 8, 3, 7]
>>> 49: 5, 5, 5, 3, 3, 8, 8, 6, 0, 1, 6, 0, 1, 6, 9, 2, 4, 9, 2, 4, 7, 7,
>>> 7, 5, 5, 5, 3, 3, 8, 8, 6, 0, 1, 6, 0, 1, 6, 9, 2, 4, 9, 2, 4, 7, 7,
>>> 7, 5, 5, 5,
>>> Agent ID 5: 40;; [7, 2, 4, 2, 7, 6, 3, 0, 7, 0, 2, 6, 6, 8, 1, 6, 6,
>>> 4, 7, 4, 9, 7, 3, 3, 9, 4, 1, 3, 6, 0, 9, 0, 2, 8, 8, 9, 1, 8, 1, 7]
>>> 51: 1, 6, 0, 1, 6, 0, 1, 4, 9, 2, 4, 9, 2, 4, 7, 7, 5, 5, 3, 3, 8, 8,
>>> 1, 6, 0, 1, 6, 0, 1, 4, 9, 2, 4, 9, 2, 4, 7, 7, 5, 5, 3, 3, 8, 8, 1,
>>> 6, 0, 1, 6, 0, 1,
>>> Agent ID 1: 42;; [9, 2, 5, 8, 9, 5, 0, 3, 9, 3, 2, 6, 3, 7, 8, 6, 9,
>>> 5, 0, 4, 0, 6, 2, 6, 4, 8, 5, 4, 0, 3, 7, 2, 7, 6, 0, 0, 8, 6, 4, 7,
>>> 4, 4]
>>> 51: 1, 6, 0, 1, 6, 0, 1, 4, 9, 2, 4, 9, 2, 4, 7, 7, 5, 5, 3, 3, 8, 8,
>>> 1, 6, 0, 1, 6, 0, 1, 4, 9, 2, 4, 9, 2, 4, 7, 7, 5, 5, 3, 3, 8, 8, 1,
>>> 6, 0, 1, 6, 0, 1,
>>> Agent ID 1: 42;; [5, 6, 6, 2, 4, 3, 0, 0, 8, 2, 2, 4, 7, 9, 4, 5, 9,
>>> 0, 8, 4, 3, 4, 7, 2, 0, 0, 3, 6, 8, 6, 9, 9, 3, 8, 6, 7, 5, 0, 6, 4,
>>> 5, 7]
>>> 49: 7, 7, 7, 5, 5, 5, 3, 3, 8, 8, 6, 0, 1, 6, 0, 1, 6, 9, 2, 4, 9, 2,
>>> 4, 7, 7, 7, 5, 5, 5, 3, 3, 8, 8, 6, 0, 1, 6, 0, 1, 6, 9, 2, 4, 9, 2,
>>> 4, 7, 7, 7,
>>> Agent ID 7: 40;; [5, 0, 5, 4, 9, 2, 4, 9, 9, 0, 3, 6, 2, 2, 2, 3, 1,
>>> 4, 3, 5, 3, 8, 8, 6, 6, 0, 0, 5, 5, 9, 4, 1, 1, 5, 8, 6, 1, 6, 8, 6]
>>> 51: 7, 2, 4, 9, 7, 2, 4, 9, 7, 5, 5, 3, 3, 8, 8, 0, 1, 6, 0, 1, 6, 7,
>>> 2, 4, 9, 7, 2, 4, 9, 7, 5, 5, 3, 3, 8, 8, 0, 1, 6, 0, 1, 6, 7, 2, 4,
>>> 9, 7, 2, 4, 9, 7,
>>> Agent ID 7: 42;; [2, 1, 5, 8, 6, 4, 9, 6, 8, 0, 4, 9, 3, 2, 4, 6, 2,
>>> 0, 5, 3, 4, 5, 6, 3, 1, 2, 1, 4, 0, 1, 4, 3, 2, 9, 9, 2, 0, 5, 8, 9,
>>> 9, 8]
>>> 
>>> 
>>> When this was run, the range was set to the size of the grid (it's
>>> 10x10). There are 10 agents total.
>>> So, it clearly getNeighborsMaxDistance is doing something a bit odd...
>>> In a world with 10 agents, they can have 40-50 neighbors?
>>> 
>>> 
>>> 
>>> 
>>> On Thu, Aug 9, 2012 at 7:38 PM, Sean Luke <[log in to unmask]> wrote:
>>>> Christopher, I'd need a concrete and simple example of this.  I presume you're referring to SparseGrid2D.
>>>> 
>>>> getNeighborsMaxDistance(x, y, dist, toroidal, result, xPos, yPos) just calls getNeighborsMaxDistance(x, y, dist, toroidal, xPos, yPos), which returns all the <X,Y> locations that are [dist] away from <x,y>.  Then it just looks up the hash for each location and returns the objects in that hash.  It's a pretty straightforwrd function.  The only ways it could possibly return multiple objects would be:
>>>> 
>>>> - A given <X,Y> location is being returned multiple times.  This might be possible in the toroidal code -- are you doing toroidal? -- but it seems unlikely in the non-toroidal code on first glance.
>>>> 
>>>> - The hash is broken (unlikely).
>>>> 
>>>> Sean
>>>> 
>>>> On Aug 9, 2012, at 7:08 PM, Chris Hollander wrote:
>>>> 
>>>>> So, I'm not sure if this is a bug or intended... and it's been around
>>>>> for a LONG time, so it might be fixed already on the SVN... but when
>>>>> you call getNeighborsMaxDistance with a sufficiently large distance
>>>>> (say, the size of the grid width or height), you get duplicates in the
>>>>> returned bag.
>>>>> 
>>>>> So if I have 10 agents with a unique ID 1, 2, .. 10 on a 10x10 grid
>>>>> and I call getNeighborsMaxDistance with a radius of 10, I'll get back
>>>>> a bag that has multiple copies of each agent... which means I can't
>>>>> exactly iterate over the raw bag. Of course, this is easy enough to
>>>>> handle by simply dumping all the elements in the bag in to a set, but
>>>>> should that have to be done? Shouldn't the returned list of neighbors
>>>>> be guaranteed to not contain duplicates?
>>>>> 
>>>>> 
>>>>> Christopher Hollander
>>>>> University of Central Florida