How to implement a graph where edges can be "closed"?

[curiousaboutcsharp]

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!!

 

[Skydiver]

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

I take this to imply that that all connections from rooms are bi-directional if a door is open. Is that correct?

Anyway, if doors are always bidirectional, you can always normalize the tuple so given a tuple (Room r1, Room r2), you ensure that r1.Id is always less that r2.Id assuming that Room.Id is some kind of sortable scalar. By always normalizing before doing your dictionary lookup, you can reduce your dictionary size down to just N, instead of 2N.

But how large does N really get? Are you looking at 16, 32, 64. 128, 256, 512?

You've probably already encountered this, but there are 2 classical ways of representing graphs: adjacency matrices or edge lists. You're current dictionary approach is effectively an edge list. The true or false values just happen to be the "weight" of the edges that shows the cost of trying to use that edge. True happens to mean that it's cheap to access the other node via that edge, and false means that the cost is infinitely high making it impassable.

How many rooms will you have? Just like the theoretical time access into a hash table is O(1), the theoretical time access into an array (be it one dimensional, two dimensional, three dimensional, or n-dimensional) is also O(1). The space cost of using an adjacency matrix for N rooms in theoretically O(N^2). So if you had 128 rooms, you'd need 16,384 bools. So at least 16K bytes. A quarter of a Commodore 64's RAM. That's negligible given our modern hardware where people only start worrying about gigabytes of RAM being used, but 16KB is still 16KB.

But notice that a bool only has a true or false value. That can be represented by 1 or 0. So imagine an array of 128 128-bit integers, where each of the bits stores those 1's and 0's. So now that will only take 2KB. That's half the size of a modern page size. And with the other 2K you can have a bitmap off all doors, while the first 2K has a bitmap of all open doors.

 

[Skydiver]

Anyway, this all maybe premature optimization. I highly suggest using a profiler to determine where your CPU time is going overall in your game -- not just in a micro benchmark. Fast is always nice. Then use the profiler to look at memory usage if you are facing memory constraints, or you are seeing the time is spent loading memory outside of the cache, or shuffling memory around, or garbage collecting.

But yes, I do agree it is fun to think about theoretical stuff like this, and then seeing how reality faces theory. (Try to search for Bjarne Stroustrup's talk about how the theoretical linked list insert O(1) operations not always matching reality.)