Generate a maze in Java , not as a grid (i.e. Matrix NxN) , but as a Graph

Question

I need to generate a program that consists of building a maze , where the game involves players up-to 60-70. The thing is , I don't want to use a grid , because I think it would waste too much memory and the complexity of this representation (= grid) won't be so easy . So after some thinking , I've decided to use a graph , where :

• each Room of the maze would represent a vertex in the graph
• each Connector in the maze would represent an edge in the graph

A Connector can be : 1. an external door 2. an external room 3. an external wall

My question is , how can I build a graph from (x,y) coordinates (in run time , I want to build the maze , while the user insert the coordinates) ? I've never worked with a graph in Java(or any other language) before , so it's not so clear to me how to do that .

Can you please explain ?

EDIT: In the game , there are treasures , and every player needs to get at least one treasure. * Each player , has his own step in the game (probably something like priority queue that helps do decide which player is the next one) and each player , while making his move , can move one step in the maze .

Answer 1

You can use a Vertex list with an Edge Table to define the maze. Essentially your list of rooms would be vertices in the graph.

List<Room> rooms;  // vertex each room will have an x,y location
boolean[][] edges;     // the columns and row are indexes into rooms

So the edge list would be an edges = new boolean[ rooms.size ][ rooms.size ] matrix. If room 1 has a hallway connecting to room 2 then edges[1][2] = true ( you can also mark edges[2][1] = true too). That way you have room 1 connected to 2, and 2 connected to 1.

For you connector types you could use an Enum instead of a boolean. Enum.EXTERNAL_WALL,DOOR,NO_CONNECTION, etc.

Answer 2

Well, you could create a class for nodes, a base class for the connectors which might be subclassed for concrete types of connectors (or have a type flag) and then you add the relations between connectors and nodes at runtime.

Your description is a bit vague so that has to suffice. Basically there's nothing really special about graphs (unless you need really big graphs and search algorithms for those etc., but that would be overkill for now).