CODEWITHSUNDEEP
javadata-structures
jmasterx
jmasterx

Reputation: 54193

Ideal data structure for these requirments?

My game is divided into a grid of regions. Each region has an List of objects in it. Each object can be in more than 1 region (up tp 4).

When an object moves, I check which regions it is in and if they change I remove them from the regions they were in and add them to the new ones. Order of objects is not important. I need fast insertion and removal. I will never need random element access.

What would be the ideal data structure for this?

Upvotes: 0

Views: 79

Answers (2)

Kevin K
Kevin K

Reputation: 9584

In each entity:

HashSet<Region> regions;

In each region:

HashSet<Entity> entities;

Your regions and entities should define hashCode and equals properly for the best performance.

When your entity changes regions, remove it from the old region before removing the region from the entity, and add it to the new region after adding the new region to the entity.

Iterating either set is simple. You don't have a guaranteed iteration order, but you said that doesn't matter. And HashSet insertion/removal is constant time, assuming properly defined hashCode and equals.

for(Entity entity: entities) {
    // do something
}

Upvotes: 1

SomeWittyUsername
SomeWittyUsername

Reputation: 18368

Simple array of 4 pointers to the Lists corresponding to each region seems fine to me.

Upvotes: 0

Related Questions