How to store a graph in unity?

Hello,

I just finished understanding the A* algorithm. Now I face a challenge before I can actually start implementing it: how exactly am I supposed to store a graph in Unity?

In real life, I'm a mathematician. I already worked with graphs many times: we store them as adjacency matrices in my field, it's easy to read/edit/understand. But correct me if I'm wrong, in unity you cannot have something else than a 4x4 matrix, thus adjacency matrices is not an option here. What do would you recommend?

 

I'm not too familiar with how matrices work, but could you use a multi-dimensional array?

like :

Code (CSharp):

1. int[][] matrix = new matrix[5][5];

 

What do you mean by storing? You can use any classes from c#, so the easiest representation of an adjacency matrix is just a 2D graph. The 4x4 is a built in type that's used in the internal representation of a lot of stuff, but feel free to make any array you want.

If you're talking about storing as serialization - writing stuff to disk - it becomes a bit harder. Unity automatically serializes a bunch of stuff, but multidimensional arrays are not one of them. In that case, simply use a normal array, and use maths to index it as if it was a 2D array, and use that as your adjacency matrix.

Side note:
I'm assuming that you are aware of the downsides of adjacency matrices; primarily the immense cost of stuff like finding all neighbours in a sparse graph. The storage size is also abysmal.

Furthermore, while the A* algorithm is really nice, you'll need to use it in a navmesh if you want any performance whatsoever. See, if you represent your world as a graph of navigation nodes, you'll either have to have very few nodes, or get a real bad slowdown when you're searching for paths. A navmesh is a representation of your world as a mesh - a set of triangles covering the area - and you use A* to search through the corners of that mesh. It's a lot faster.

 

@Mike_670 unfortunately, the size of the graph is not fixed, so an array will not work!
@Baste sorry I was not clear enough. I just need a graph representation I can use in scripting, mostly to use with the A* algorithm.
@Baste I didn't know adjacency matrices where expensive, I never encountered any problems with them in R (my working programming language as a mathematician). What representation would you recommend?
@Baste I watched the nice tutorials about navmesh and pathfinding on unity3d.com. However the navmesh must always be baked prior to the start of the game. This is a problem as the network of roads in my game can change based on user input (some road might be not available anymore while other might be added as the game progresses - and you never know in advance where some roads will disappear or be added). I read somewhere while searching Google that dynamic navmeshes are not part of unity yet, so I decided to start building everything myself (+ it's a good exercice for me as a newbie in unity I guess)

 

http://catlikecoding.com/unity/tutorials/graphs/ maybe?

 

I've used QuickGraph on other c# projects before, though I'm not sure that it will work with Mono. However, it's open source, so you might be able to use some of the source code to help get up and running quickly. It's an excellent library, with many shortest path algorithms including A*.

 

Way to miss the point completely

You could still make it work with List of Lists, but the problem i see with adjacency matrices is a whole bunch of wasted zeros
Better to have a class 'Node' with a member List<Node> adjacents, kept in a List<Node> allNodes

 

I believe I will go with a list of lists, I found several places on the internet where they suggest to do that as well.

Another idea is to put an empty game object at each intersection of roads and then to have a KeyPairValue, where the game object is the key and the value is a class where I store the direct neighbors and the length of the related edges.

I'll let you know how it works out.

 

Haha, sorry... Bumped the post if nothing else

 

Hey Thomas12,

Can you add links / resources where you found out how to use Lists of Lists to create graphs?

Thanks!

 

Alternatively, I found an adjacency list implementation, but don't quite know how to use it.

See:

http://forum.unity3d.com/threads/freebie-a-c-adjacency-list-implementation.41873/

EDIT: I learned how to use the implementation and documented it in the above post.