How to implement a graph where edges have attributes

Unity Engine
, , ,
1

I’m making a game in Unity

I have a building with a bunch of rooms, and rooms are connected to each other by doors

Obviously if there are rooms A, B, C and D then the graph is just a simple graph linking nodes representing each room

So an edge is technically a door between two rooms. I want to give the edge an attribute. bool isOpen. When isOpen == false, then traversal over that edge is not allowed

If I have a Room A and Room B, my graph would be A ↔ B

How do I store the information that the edge between A and B is closed aka isOpen == false

I want a fast time complexity solution. I have one solution below but I don’t know if it’s the most efficient

Have a Dictionary doors that will represent the doors between two rooms, and their open / close status. The key is a tuple (Room1, Room2) and the value is true or false

So if my graph traversal algorithm is on Room A and the next room is Room B, then it will go to Room B if doors( (RoomA, RoomB)) == true

I don’t know if this is an issue, but the space taken has to be double the number of doors because the algorithm has to be allowed to access the dictionary no matter the order of the rooms in the key tuple

So the time complexity is that of a hashtable, the space complexity is O(2N) N = number of doors

I’m wondering if there is a more efficient way of doing this . Maybe I have opened myself up to a common bug, or a way to do it with less space taken etc

Thank you!!

2

AStar operates on a graph and you can put cost attributes on nodes, or break them entirely.

https://arongranberg.com/astar/

3

Maybe Im missing something, because the solutions seems obvious… if you need edges with attributes, why not store these attributes directly on the edges?

In your example the edge is represented by a door?
The doors should have a reference to all connected roorms and the rooms should have a reference to all connected doors, now you can simply store the “isOpen” value (and all other variables you need) directly on the door.

1 Like
4

My thought is you could do it two ways:

  1. each room has 4 pieces of data, one for each wall. Could use true/false for doors open/closed, or maybe use -1=no door (just a wall), 0=closed door, 1=open door. That is, if it’s important to differentiate a wall from a closed door. So this could be either a dictionary or a 2D array [room index][4 data points]. Or a 3D array if you want the room indices to be in a grid form. Advantage=intuitive, rooms are individual data containers. Disadvantage=one door changes state, you have to update the adjoining room’s door states. Though once you figure out the mapping from one room to the next that’ll be easy.

  2. store the wall/door data in rows/columns, with the overall grid size being the bounding box of your structure. Advantage=you’re only changing the door/wall data. Disadvantage=maybe not as clear? Though I think I’d use this method if it works with the rest of the design.

Sounds like a fun project. I’ve dabbled a bit with procedural mazes/grids where you generate them randomly based on probability of row or column segments to be created, lots of possibilities. Having additional data like “wall is/isn’t destructible” would add even more options, sounds kind of similar to your door data.

Also I can’t imagine there being any reason to worry about the time complexity. Much more important that the system you create makes sense and is flexible.