Trouver un objet spécifique à une coordonnée spécifique dans ArrayList

Question

Je travaille actuellement sur un jeu basé sur une dalle 2D et j'en suis arrivé à un point où j'ai besoin d'optimiser mon code. Im ajoutant beaucoup d'éléments différents dans la liste de javas tels que des arbres, des roches et ainsi de suite. La raison pour laquelle les éléments ne sont pas une tuile statique est parce que je veux que le joueur puisse interagir avec des éléments. Par conséquent, tous les éléments doivent être leur propre objet et stockés dans une liste. Le problème est que chaque fois que je veux interagir avec un élément spécifique dans la liste intégrée en java, je dois créer une boucle for et parcourir chaque élément de la liste pour trouver le bon élément aux bonnes coordonnées. (Comme la collision et ainsi de suite.)

La façon dont je le fais est comme ceci:

List<Element> elements = new ArrayList<Element>(); 


public Element getElementOnPixel(int x, int y){` 

     for(int i = 0; i < elements.size(); i++){ 

      int xx = elements.get(i).getX() * Game.TILE_SIZE; 
      int yy = elements.get(i).getY() * Game.TILE_SIZE; 
      int w = xx + elements.get(i).width; 
      int h = yy + elements.get(i).height; 

      if(x >= xx && x < w && y >= yy && y < h) { 
       return elements.get(i); 
      } 

     } 
     return null; 
    } 

Comme vous pouvez le voir ci-dessus, je dois aller pensé toute la liste jusqu'à ce que je trouve l'élément droit à la coordonnée droite. Voici où le problème apparaît parce que j'ai beaucoup d'éléments dans mon jeu. Ma question suit:

Existe-t-il un autre moyen de trouver un élément spécifique à une coordonnée spécifique dans javas intégré dans les listes?

Answer 1

Vous pourriez faire imaginaire faire une sorte de grille de votre jeu:

Comme ici avec 8, 4 lignes Col. // 8 X-positions, 4 Y positions

[E][ ][ ][ ][ ][ ][ ][ ] 
[ ][ ][ ][ ][ ][E][ ][ ] 
[ ][ ][E][ ][E][ ][ ][ ] 
[E][ ][ ][ ][ ][ ][ ][ ] 

et aligner en une ligne (liste) ->

[E][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][E][ ][ ][ ][ ][E][ ][E][ ][ ][ ][E][ ][ ][ ][ ][ ][ ][ ] 

Si vous voulez activer l'élément (x, y). Vous prenez alors l'élément:

(x,y) -> List.get(y-1 * "overall row-length" + x) 

Exemple:

If you want to get the element in position x = 5, y = 3 
(5,3) -> List.get(3-1 * 8 + 5) = List.get(21) 

Answer 2

Vous devriez envisager une structure de données de partitionnement spatial comme un arbre BSP (voir Apache Commons Math), un arbre KD, QuadTree ...

Answer 3

Je pense que la meilleure façon serait de stocker tous les éléments dans une matrice bi-dimensionnelle:

Element[][] allElements=new Element[maxHeight][maxWidth]; 

... où maxHeight et maxWith sont exprimés en pixels.

Et les procédures pour stocker et enlever:

private void addElement(Element element) 
{ 
    // Calculate the range X and Y occupied by the new element: 
    int posXLeft=getXPosition(element); 
    int posYTop=getYPosition(element); 
    int posXRigth=posXLeft+element.width; 
    int posYBottom=posYTop+element.height; 

    // Iterate the range X and Y in the allElements in search for old elements: 
    for (int y=posYTop;y<posYBottom;y++) 
    { 
     for (int y=posYTop;y<posYBottom;y++) 
     { 
      if (allElements[y][x]!=null) 
      { 
       // Collision detected: There was already an element in that pixel. 
      } 
     } 
    } 

    // No collision detected: 
    allElements[getXPosition(element)][getYPosition(element)]=element; 
} 

private void removeElement(Element element) 
{ 
    // This is a safe operation: There is no need to search for collisions. 
    int posXLeft=getXPosition(element); 
    int posYTop=getYPosition(element); 
    allElements[posYTop][posXLeft]=null; 
} 


private int getXPosition(Element element) 
{ 
    return element.getX() * Game.TILE_SIZE; 
} 

private int getYPosition(Element element) 
{ 
    return element.getY() * Game.TILE_SIZE; 
} 

Answer 4

Vous pouvez convertir vos coordonnées X/Y à une clé de hachage et de stocker les éléments d'une carte au lieu d'une liste. Lorsque vous faites votre recherche, vous faites la même conversion pour trouver votre élément. Par exemple,

private static String findHashKey(int x, int y) { 
    return "" + x + "_" + y; 
} 

Map<String, Element> elements = new HashMap<>(); 

public Element getElementOnPixel(int x, int y) { 
    return elements.get(findHashKey(x, y)); 
}