CODEWITHSUNDEEP
javaarraylistiterationpoint
Jerry
Jerry

Reputation: 470

Fast way to get a coordinate(x,y) from an ArrayList?

I am working on a game that uses several HashMap<Point, Integer> to store values assigned to coordinates. In order to make it more simple and reduce duplication, I extended the Point class with an own class, called GamePoint. It has an equals() method that compares only x and y, which works with Point as well. As I don't need the key-value relation from the HashMap anymore, I simply put it into an ArrayList.

With the HashMap I had this:

HashMap<Point, Tile> tileMap; //already built at that stage

public static Tile getTile(int x, int y) {  
        Point p = new Point(x,y);
        if(matrix.containsKey(p)){
            return tileMap.get(p);
        } else return Tile.BOUNDS;
    }

From that Tile (which is an enum) I would get the image Index. Now I do this to get my value from the ArrayList:

ArrayList<GameTile> gameTiles; //already built at that stage

public static int getGameTileIndex(int x, int y) {
    Point p = new Point(x,y); //only for finding the coordinates
    for(GameTile gt : gameTiles){
        if (p.equals(gt)){
            return gt.getImageIndex();
        }
    }
    return 0; //empty tile
}

Unfortunately there is no direct method that can return the GameTile. Iterating is really, really slow, as I have 1.000.000 entries and there will be more in the final game.

Here's what I need to know: Is iterating the ArrayList the right way for retrieving the GameTile? Should I stay with the HashMap and use something like HashMap<Point, GameTile> ? Or could I somehow use the get(int index) method, knowing that the array is filled with a nested loop similiar to this:

List<Point> referencePoints; 

for (int x; x<width; x++){
   for (int y; y<height; y++){
      Point p = new Point(x,y);
      height = calculateHeight(x,y);
      tileMap.put(p, height);
      referencePoints.add(p);
   }
}

for (Point p: referencePoints){
    GameTile tile;
    if (float height = getHeight(p) > THRESHOLD){
        tile= new GameTile.GrassTile(p.x,p.y);
    }
    else {
        tile= new GameTile.WaterTile(p.x,p.y);
    }
    gameTiles.add(tile);
}

Note: I really feel that there is a very logical way to use the x,y variables for index retrieval, but I can't get my mind together right now.

Edit: I went with a HashMap which works as a charm right now. The answers, while giving me a new perspective, couldn't help me solve the problem and it still stands as it is. I found a workaround that works for my case and will be using that for now.

Upvotes: 1

Views: 4465

Answers (2)

Anderson Vieira
Anderson Vieira

Reputation: 9049

If you have a fixed number of points and you know that each one will have a tile, one option is to make 2-dimensional array and store your tiles in there, like this:

GameTile tiles[][] = new GameTile[n][n];

In this way, you can quickly access the tile at (i, j) by doing

GameTile tile = tiles[i][j];

Of course, the memory complexity for this is O(n2).

If you have a small number of tiles compared to n2 then I think the HashMap is indeed your best option.

Upvotes: 0

gknicker
gknicker

Reputation: 5569

Is iterating the ArrayList the right way for retrieving the GameTile?

No way. Your HashMap implementation was far superior to iterating.

Should I stay with the HashMap and use something like HashMap ?

No. Indexing into an ArrayList is going to be much faster than using a HashMap.

Or could I somehow use the get(int index) method?

Yes. Honestly it would probably be easier to follow if you used a two-dimensional array , x by y. But it will work the way you laid it out in that bit of pseudocode. This will be your most efficient solution.

Upvotes: 2

Related Questions