In Java (Swing), say I've got a 2D game where I have various types of entities on the screen, such as a player, bad guys, powerups, etc. When the player moves across the screen, in order to do efficient checking of what is in the immediate vicinity of the player, I would think I'd want indexed access to the things that are near the character based on their position.
For example, if player 'P' steps onto element 'E' in the following example...
| | | | | |
| | | |P| |
| | |E| | |
| | | | | |
... would be to do something like:
if(player.getPosition().x == entity.getPosition().x &&
entity.getPosition.y == thing.getPosition().y)
{
//do something
}
And thats fine, but that implies that the entities hold their positions, and therefor if I had MANY entities on the screen I would have to loop through all possible entities available and check each ones position against the player position. This seems really inefficient especially if you start getting tons of entities.
So, I would suspect I'd want some sort of map like
Map<Point, Entity> map = new HashMap<Point, Entity>();
And store my point information there, so that I could access these entities in constant time. The only problem with that approach is that, if I want to move an entity to a different point on the screen, I'd have to search through the values of the HashMap for the entity I want to move (inefficient since I dont know its Point position ahead of time), and then once I've found it remove it from the HashMap, and re-insert it with the new position information.
Any suggestions or advice on what sort of data structure / storage format I ought to be using here in order to have efficient access to Entities based on their position, as well as Position's based on the Entity?
