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

Posted by Seçkin Savasçi on Programmers See other posts from Programmers or by Seçkin Savasçi
Published on 2013-10-23T22:26:40Z Indexed on 2013/10/24 4:07 UTC
Read the original article Hit count: 273

Filed under:

data-structures

|

Parallelism

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.

© Programmers or respective owner

Related posts about data-structures

Clever ways of implementing different data structures in C & data structures that should be used mor

as seen on Stack Overflow - Search for 'Stack Overflow'
What are some clever (not ordinary) ways of implementing data structures in C, and what are some data structures that should be used more often? For example, what is the most effective way (generating minimal overhead) to implement a directed and cyclic graph with weighted edges in C? I know that… >>> More
Is there a way to track data structure dependencies from the database, through the tiers, all the way out to a web page?

as seen on Programmers - Search for 'Programmers'
When we design applications, we generally end up with the same tiered sets of data structures: A persistent data structure that is described using DDL and implemented as RDBMS tables and columns. A set of domain objects that consist primarily of data structures, usually combined with business-rule… >>> More
Why are data structures so important in interviews?

as seen on Programmers - Search for 'Programmers'
I am a newbie into the corporate world recently graduated in computers. I am a java/groovy developer. I am a quick learner and I can learn new frameworks, APIs or even programming languages within considerably short amount of time. Albeit that, I must confess that I was not so strong in data structures… >>> More
Thread-safe data structures

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I have to design a data structure that is to be used in a multi-threaded environment. The basic API is simple: insert element, remove element, retrieve element, check that element exists. The structure's implementation uses implicit locking to guarantee the atomicity of a single API call.… >>> More
Data Structures

as seen on Stack Overflow - Search for 'Stack Overflow'
There is a large stream of numbers coming in such as 5 6 7 2 3 1 2 3 .. What kind of data structure is suitable for this problem given the constraints that elements must be inserted in descending order and duplicates should be eliminated. I am not looking for any code just ideas? I was thinking… >>> More

Related posts about Parallelism

Parallelism in .NET – Part 3, Imperative Data Parallelism: Early Termination

as seen on Reed Copsey - Search for 'Reed Copsey'
Although simple data parallelism allows us to easily parallelize many of our iteration statements, there are cases that it does not handle well. In my previous discussion, I focused on data parallelism with no shared state, and where every element is being processed exactly the same. Unfortunately… >>> More
Parallelism in .NET – Part 2, Simple Imperative Data Parallelism

as seen on Reed Copsey - Search for 'Reed Copsey'
In my discussion of Decomposition of the problem space, I mentioned that Data Decomposition is often the simplest abstraction to use when trying to parallelize a routine. If a problem can be decomposed based off the data, we will often want to use what MSDN refers to as Data Parallelism as our… >>> More
Parallelism in .NET – Part 4, Imperative Data Parallelism: Aggregation

as seen on Reed Copsey - Search for 'Reed Copsey'
In the article on simple data parallelism, I described how to perform an operation on an entire collection of elements in parallel. Often, this is not adequate, as the parallel operation is going to be performing some form of aggregation. Simple examples of this might include taking the sum… >>> More
Parallelism in .NET – Part 6, Declarative Data Parallelism

as seen on Reed Copsey - Search for 'Reed Copsey'
When working with a problem that can be decomposed by data, we have a collection, and some operation being performed upon the collection. I’ve demonstrated how this can be parallelized using the Task Parallel Library and imperative programming using imperative data parallelism via the Parallel… >>> More
Code for Parallelism Features Tour

as seen on Daniel Moth - Search for 'Daniel Moth'
Last year I linked to a screencast that shows off many VS2010 features delivered by the Parallel Computing team.There have been requests for the code used to demonstrate the features. Like with all my screencasts, you can see all the code in action, so you could simply type it in. To save you doing… >>> More