# Data Structure for Small Number of Agents in a Relatively Big 2D World

I'm working on a project where we will implement a kind of world simulation where there is a square 2D world. Agents live on this world and make decisions like moving or replicating themselves based on their neighbor cells(world=grid) and some extra parameters(which are not based on the state of the world). I'm looking for a data structure to implement such a project.

My concerns are : I will implement this 3 times: sequential, using OpenMP, using MPI. So if I can use the same structure that will be quite good.

The first thing comes up is keeping a 2D array for the world and storing agent references in it. And simulate the world for each time slice by checking every cell in each iteration and further processing if an agents is found in the cell. The downside is what if I have 1000x1000 world and only 5 agents in it. It will be an overkill for both sequential and parallel versions to check each cell and look for possible agents in them. I can use quadtree and store agents in it, but then how can I get the information about neighbor cells then?

Please let me know if I should elaborate more.

• If there's only five agents, just store references to them (and their locations in the 2D array) in a collection. Commented Oct 23, 2013 at 22:34
• @RobertHarvey The problem is I don't know if there will be only 5 agents in time t. There can be 1 million agents too. Commented Oct 23, 2013 at 23:04
• Well, you didn't say that. If you have to look at all of the cells anyway, any attempt at optimizing the problem is moot. Commented Oct 23, 2013 at 23:13
• @I will parse the initial data from a text file, so I can come up with a guess of average agents in the world for a random time t. In any moment, I can state the exact number of agents in the world, too. My question is that in a situation like this which data structure is the best to use. I can keep agents in a collection, but I need their neighbors if there is any. Also agents can move so neighbors can change. I should find a data structure that is smaller than the keeping whole 2D world and flexible to store information about the world nearby at the same time. Commented Oct 23, 2013 at 23:20
• it looks like in any cell with no agent, nothing happens, so the number of cells is irrelevant. In that case all you need to do is schedule attention to a list of agents Commented Oct 24, 2013 at 1:33

Sounds like you basically have a cellular automaton. Have a look at Hashlife: A quad tree based algorithm that can be used to simulate spatially sparse, structurally similar cellular automata very very quickly. Depending on your exact problem you can use it directly or at least draw some inspiration.

You have quoted the following paramenters for your world,

• You have a 2D world (NxN grid where N=1000).
• There are Agents located in the world, each agent at a grid location.
• Agents can move.
• There can be few agents (5) to many agents (1M).
• The world may be sparsely to densely populated.
• You need to find the locations which have agents, and process then.
• You need to cover all agents.
• You would like to process as few grid elements as possible.
• You want a data structure amenable to parallelization
• You need to be able to find neighbors, and agents within neighbors

Exhaustive scan of the entire 2D world will find you agents, but it might be inefficient (looking at 1M grid locations for only 5 agents is wasteful).

Questions:

• Is there a priority to agents? assume no.
• Can you skip some agents? assume no,.
• Does it matter what order you examine agents? assume any.
• What is the most agents you expect in any one grid location? suppose 50.

Suggestions:

Keep a data structure (grid or tree) counting the number of agents in a given grid location. Only 1M locations is simple enough, and you could use a single byte per grid location to count up to 2^7 (0-127), agents. Use an overflow area for locations with more agents (assuming you seldom have more than 127 agents in a location - do you have an expected average?). lock/parallelize based upon regions of the grid (10x10) areas.

Keep the agents ordered in some tree (quadtree, trie based upon grid location), but tree is not as parallel-izable. My suggestion here would be a 2D list of lists (or vector of vectors) ordered by grid coordinates.

You want to pick a coordinate system where you can easily compute neighbors, and find out whether agents are in neighbors - note that the counts structure mentioned will be valuable here.

What you are looking for is a topological sort of your data, and a quadtree is one approach. But you care about everybody 'nearby'. The problem you discuss is similar in some respects to the finite element analysis.

You mention move and replicate, which both change state not just of self, but other grid elements and tree analysis. These methods would affect how parallelization is done.

The data structure will become obvious after you analyze the problem and constraints.

You have three implementation targets: sequential, OpenMP, and MPI. Of these, MPI is the most constrained, IMO. Work through how the sim can be built using MPI, and you will see that a key issue is the process control model (you have already alluded to this). From what you have said, IMO the Actors should be the active elements. Challenge that idea.

As you build up your conceptual model of the processes and their communication, you will encounter issues of concurrency, data locality, and message bandwidth. Work through those, and you will have your data structures.

The other two models will be simplified versions of that.

To start with, just keep a list of all the agents with their locations. When working with one agent, scan the list to find all the other agents close enough to be of interest. Skip creating an actual world grid array; it limits you too much and wastes too much memory.

Next, as your agent list gets real big and you waste too much time looking at agents too far away, impose a grid on your world. With a 1000x1000 world, maybe a 100x100 grid would work. Each element will hold a list of agents that are within its 100 world-cells. Now to check for neighbors, look in the agent's grid cell and take all the occupants who are also in adjacent world-cells. In some cases, you may need to check certain adjacent grid cells also. This grid lets you handle 100,000 items as if they were only 100 or so regarding which agents are in adjacent, or even near-by, world-cells.

A quadtree might work better if your agents tend to cluster together, but that gets tricky even without "parallelism". My guess is the combination of a list of all agents, each agent with its world-grid cell location, and the mid-sized grid with lists of agents within each cell boundary, should work okay.

(The mid-sized grid's size needs to based on a combination of your world size and the total number of agents. Getting the perfect size is tricky, but just about any size is going to be vastly superior to the extremes of not using a grid and using a world-sized grid.)

(Note that with this technique your world-grid could become truly vast--trillions of cells on a side--without causing any difficulty. Mind, your agents would need to be able to see across quite a log of cells in order to find each other.)