Structure de données intégrée Java pour mapper des pièces adjacentes

Question

Je recherche une structure de données intégrée Java qui serait la meilleure pour gérer les pièces adjacentes. J'ai une grille/sol divisé en pièces générées au hasard comme ceci:

+ + + + + + + + + + + + + + + + + + + + 
+       +   + 
+       +   + 
+       +   + 
+       +   + 
+       +   + 
+       +   + 
+       +   + 
+ + + + + + + + + + + + + + + + + + + + 
+   +   +     + 
+   +   +     + 
+   +   +     + 
+   +   +     + 
+   +   +     + 
+ + + + + + + + + + + + + + + + + + + + 
+   +    +    + 
+   +    +    + 
+   +    +    + 
+   +    +    + 
+ + + + + + + + + + + + + + + + + + + + 

et je suis à la recherche d'une structure de données dans laquelle il serait le plus rapide/plus facile à stocker cette grille et la carte ce voisin des chambres ce pièces.

Est-ce que quelqu'un a une suggestion?

grâce

Answer 1

Vous pouvez utiliser un graphique pour représenter les chambres comme des noeuds et des relations voisines comme bords.

Vous pouvez représenter les graphiques de différentes manières. Dans ce cas, étant donné que la relation est éparse, il est préférable d'utiliser la liste d'adjacence au lieu de la matrice d'adjacence.

En Java, le graphique peut être représenté avec Map<Room,List<Room>>. Fondamentalement, c'est ce qu'il dit: c'est une carte d'un Room à une liste de ses voisins Room s.

Sinon, si vous préférez travailler avec des nombres entiers de base et les tableaux, vous pouvez utiliser une représentation matricielle de contiguïté boolean[][] adj, où adj[i][j] == true si et seulement si la chambre et la salle ij sont voisins.

Answer 2

Vous avez juste besoin de stocker:

1. les coins opposés de chaque chambre
2. la adjacency graph/matrix du graphe formé par les chambres que les noeuds et contiguïté comme le bord.