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?
