# Storing visibility graph for path-finding: do redundant and non-visible pairs of points have to be saved?

Using C# in Unity, I have recently implemented an algorithm that determines during run-time the visibility graph of a given scene in my game project (visibility between corners of obstacles). Now I am in doubt about the best way to save the result.

So, considering that I want the visibility graph for path-finding, I would like to know the following:

1) Suppose that points A and B are visible to each other. Then, AB and BA both detect the same visibility line. It happens to all mutually visible pairs in my case. So, in order to perform an A* algorithm do I really need all these redundant pairs or can I get rid of the redundant ones, leaving only AB or only BA?

2) Now suppose that points A and C are NOT visible to each other. Do I have to save AC and/or CA? It is, to apply an A* algorithm do I have to save pairs of points that are not visible?

I ask that because if the answer to both questions is "yes", then the final array storing the graph becomes NxN, where N is the number of points (corners of obstacles) in the scene, with each cell holding the value 0 for non-visible pairs or a value equal to the distance between each visible pairs. I think technically it is called an Adjacency Matrix.

However, if the answer to any or to both of these questions is "no", then I would be able to save a lot of memory because the final results would require a much smaller array. The reason is that I would then not save redundancy and also most points are not visible to each other (it's technically a non-dense graph), so they would not be included.

But I am not sure I can go that route for path-finding. So, in case the answer to any of the 2 questions above is "no", what is the logical format I should use for saving the results, in order to perform an A* algorithm in the visibility points?

Many thanks for your time.

• For memory use, (2) is far more important than (1). Answers to your questions: (1) You don't need both AB and BA but it will save memory to have both because you can use a more compact representation, a (dense) array. (2) No, you don't store the unconnected edges. In any case, memory (and cpu) profiler is your friend. – amitp Oct 19 '15 at 19:18
• Many thanks, @amitp, that's hepful! Since mine is a sparse graph, I agree 2 is more important. But otherwise, it wouldn't necessarily be the case, right? About your observation regarding (1), that's exactly what I've been fighting with. So, what you mean is that although not including AB and BA might look cheaper in terms of memory usage, the structure for that (e.g. list, dictionary) would end up more expensive than the structure to include both (e.g. array)? – MAnd Oct 19 '15 at 22:15
• A compact representation could be an array of arrays. Neighbors[A] would be an array of {vertex_id:int, cost:float}, where one of those elements would be {B, __}. If you store B in A's array, but don't want to store A in B's array, how are you going to find A without some additional data structure indexed on B? Even a single pointer (8 bytes on a 64-bit architecture) is going to be as big as the entire {vertex_id, cost} structure in the original array. Now maybe you have a lot more data per edge, and you want to put it elsewhere, but the data A* needs is pretty small. – amitp Oct 20 '15 at 17:53

If most nodes see almost all nodes (a forest for example), you would lose a lot memory by not going matrix - while saving one edge in matrix would take 1 bit, saving and Edge object would take at least 3 pointers (assuming 1. was no), that is at least 96 (192 for 64-bit) times more.