Java built-in data structure for mapping adjacent rooms

Question

Hi

I'm looking for a Java built-in data structure that would be the best at handling adjacent rooms. I have a grid/floor divided into randomly generated rooms like so:

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

and i'm looking for a data structure in which it would be fastest/easiest to store this grid and map out what rooms neighbour what rooms.

Does anyone have a suggestion?

thanks

Answer 1

You can use a graph to represent rooms as nodes and neighboring relationship as edges.

You can represent graphs in many different ways. In this case, since the relationship is sparse, it's better to use adjacency list instead of adjacency matrix.

In Java, the graph can be represented with Map<Room,List<Room>>. Basically, it is what it says: it's a map from a Room to a list of its neighboring Rooms.

Alternatively, if you prefer to work with basic integers and arrays, you can use an adjacency matrix representation boolean[][] adj, where adj[i][j] == true if and only if room i and room j are neighbors.

Answer 2

You just need to store:

1. the opposite corners of each room
2. the adjacency graph/matrix of the graph formed by rooms as nodes and adjacency as the edge.