1

I have a World which can contain multiple Bullets, all of the Bullet has a Position (Center). Which basically is the following

class Position{
    private double xCoordinate;
    private double yCoordinate;
}

We need to implement a function in O(1) (nearly constant time) which retrieves the corresponding bullet in the World by giving a position.

I've tried to use HashMap to store the key/value (Position/Bullet) paires. However, after change the coordinate of a Bullet, I am unable to retrieve this anymore using his updated Position like:

this.bullets.get(new Position(bullet.getX(), bullet.getY())))

gives null as result

Initally, I thought that the problem was caused by the problem of hashCode and equals method I've implemented:

@Override
public boolean equals(Object other) {
    if (other == null) return false;
    if (other == this) return true;
    if ((other instanceof Position)) {
        if (((Position) other).getXCoordinate() == this.getXCoordinate() &&
            ((Position) other).getYCoordinate() == this.getYCoordinate()) return true;
        }
    return false;
}

@Override
public int hashCode(){
    return Objects.hash(this.getXCoordinate(),this.getYCoordinate());
}

But later, I realised that the datastructure I used is not suitable for this kind of problem. Namely, the Position of the Bullet can change anytime, but the key in the bucket will however, not be updated.

I've searched for a while, but I cannot find a suitable datastructure to do that. So I want kindly ask if there is a good datastructure/ implementation that I can use to solve this problem in O(1) time?

Li Jianing
  • 11
  • 4
  • 1
    Do you really need to query by position? There are a lot of positions. Or do you just want to know what bullets are in a particular area? See also: [Spatial data structures for moving objects](http://stackoverflow.com/questions/235637/spatial-data-structures-for-moving-objects). – Andy Thomas Apr 03 '17 at 17:25
  • @AndyThomas Sorry for not specifying the question, what I basically mean by Position is the center of the Bullet, what I need is to check whether the given Position coincides with the center of this Bullet | Assignment was: The class World shall also provide a method to return the ship or the bullet, if any, at a given position, i.e. the objects whose centre coincides with the given position. This method must return its result in nearly constant time and must be worked out in a total way. – Li Jianing Apr 03 '17 at 17:35
  • Are the dimensions of the world small enough to allow the creation of a 3D array through which bullets move? – Andy Thomas Apr 03 '17 at 17:41
  • 1
    Just remove and reinsert it whenever the position changes? Although using doubles as part of a map key generally seems like a terrible idea, because floating point precision. – Bernhard Barker Apr 03 '17 at 17:45
  • Thanks @AndyThomas World is by standard 1920 * 1080, but I don't know exactly why we would need use a 3D array – Li Jianing Apr 03 '17 at 17:49
  • @Dekeling indeed, it is a possiblity, but the Position changes constantly, by doing so will make the performance of this program even worse ;) – Li Jianing Apr 03 '17 at 17:54
  • @LiJianing - Okay, if positions were integral, that would be about 2 million positions for your 2D world. Say the JRE takes 8 bytes per reference, worst-case, that's under 17 megabytes, which will fit within a JRE environment with default heap size. Does the assignment explicitly specify that positions are real rather than integral? If positions are integral, this is a simple problem. If positions are real ... you could store all the bullets within a 1x1 square in the corresponding cell in the array, but that's not going to give you O(1). – Andy Thomas Apr 03 '17 at 17:55
  • @AndyThomas Since that we need use `double` to store values, so I think that the positions are real... – Li Jianing Apr 03 '17 at 18:07
  • @LiJianing - With double coordinates, there are many, many more positions. And testing equality of floating point values is usually frowned upon. It might be worth clarifying with your teacher whether real coordinates are required, and what "nearly constant" means. Algorithms that partition space like quadtrees or R-trees are going to have at least logarithmic cost for querying. That brings us back to Dukeling's suggestion above -- when a bullet moves, remove it from the HashMap and re-insert with the new position. – Andy Thomas Apr 03 '17 at 18:15
  • Thanks, @Dukeling + Andy Indeed, this is the most effective method by now, I would use the solution of Dukeling as temporary solution. Thanks guys ;) – Li Jianing Apr 03 '17 at 21:00

0 Answers0