2
\$\begingroup\$

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.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – amitp Oct 19 '15 at 19:18
  • \$\begingroup\$ 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)? \$\endgroup\$ – MAnd Oct 19 '15 at 22:15
  • \$\begingroup\$ 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. \$\endgroup\$ – amitp Oct 20 '15 at 17:53
1
\$\begingroup\$

To answer your main questions:

  1. Does your A* implementation expect undirected graph? Do you have one-way mirrors?
  2. no, unless you require logic for finding not-visible-paths

And about saving memory, it all depends - how spare the adjacency matrix would be? (profile!)
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.
Additionally, you can optimize the matrix memory as well: using the knowledge that it is triangular matrix you already cut the memory requirements in half. Moreover, there are techniques to compress spare matrices to take even less space.
On the other hand, storing edges has it upsides, for very sparse matrices(interiors, dungeons) it would probably take less space and offer superior comfort.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Many thanks for your answer, @wondra. So, 1) not necessarily, it isn't important the direction of the path. 2) great. My scenario is interiors of buildings, so a more sparse adjacency matrix. I got specially interested in 3 things you've said: a) "cut memory requirements in half": in C# or C++, would I have to change the way I create arrays or are you talking about the automatically halved use of memory due to matrix being triangular? b) by tech to compress sparse matrix are you thinking of something like citeseerx.ist.psu.edu/viewdoc/… ? \$\endgroup\$ – MAnd Oct 19 '15 at 22:09
  • \$\begingroup\$ And @wondra: c) since I'm working with interiors, by storing edges you mean something like and adjacency list/dictionary? In such case, I thought of storing the example AB as the same entry as BA, I'm only not sure which would be the Key or ID of that for search when applying the A* (i.e. the key or ID to make it properly direction-independent) \$\endgroup\$ – MAnd Oct 19 '15 at 22:12
  • \$\begingroup\$ The matrix is triangular, like you suggested M[a,b] = M[b,a] - if you wrote such matrix on paper you would find one half is not necessary because it is "mirrored" by diagonal. How do you implement this? In similar manner you implement indexing in two-dimensional matrix stored in flat array, except the indexing will be a bit more complicated, but not hard to find by yourself. \$\endgroup\$ – wondra Oct 19 '15 at 23:48
  • \$\begingroup\$ @MAnd To be honest I did not study the article much, but there is quite a few ways - as far as I remember there are at least three different ones(RLE for example) depending on situation and the article seemed like one of them. As for non-matrix storing, I would got for List or even flat array(how often visibility change?) - because you dont need lookup by target node, do you? A* will be iterating over all edges from node anyway of node(right?). If you need lookup for something else I would suggest using (target)Node as key and not having Edge class at all (Set instead of Dictionary). \$\endgroup\$ – wondra Oct 19 '15 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.