Simple graph class

Unity Engine
,
1

Pathfinding, AI and many other tasks involve the use of graph structures. I’ve attached a class that implements a simple but extensible and efficient graph structure. One of the advantages of the approach is that the graph is stored entirely in two integer arrays - this makes the data easy to set and use within editor scripts (ie, links between node objects are not required).

Bon appetit!

401485–13787–$SimpleGraph.cs (3.08 KB)

2

Sounds great!

I would like to create a graph from a file imported as a TextAsset and then access the graph at runtime. I would like to avoid to create the graph at runtime, i.e in a Start() function of a script attached to a GameObject. Any idea how to do that?

3

An easy way to store the graph data as text is to let each line represent a node (so the first line will be node 0, the second node 1, etc). Each line’s content will then just be a space-delimited list of the arcs:-

1 2 3
0 1 2 3
0 1
2 3
...

You can use a function like the following to read the text line by line and add the arcs to the graph:-

function GraphFromText(text: String) {
	var reader = new System.IO.StringReader(text);	
	var builder = new SimpleGraphBuilder();
	var line = reader.ReadLine();

	while (line != null) {
		builder.NewNode();
		var arcs = line.Split();
		
		for (i = 0; i < arcs.Length; i++) {
			var arcNum = System.Int32.Parse(arcs[i]);
			builder.AddArcs(arcNum);
		}
		
		line = reader.ReadLine();
	}
	
	return builder.Build();
}

There are other ways to split up the text, of course. For example, you may want to build an array of lines using String.Split rather than use the System.IO.StringReader class.

4

Thanks for your answer.

I guess reading a text file takes a lot of I/O resources. Is there a way to load binary file instead of text file?

5

A text file does take up more space than a binary file and takes more time to read in, but the difference won’t be noticeable unless the graph is enormous (maybe tens of thousands of nodes). However, if loading efficiency is an issue, you can treat the data in a text file as binary by using the bytes property. The main drawback with this is that you will need to write code to generate the binary data.

Another way to go might be to set up the graph data in the editor. The SimpleGraph class is designed so that the data is stored in two arrays. If you declare a public variable of type SimpleGraph in your script then you can populate the arrays yourself from an editor script and it will be retained for use in the game (like setting a variable from the inspector).

6

been looking for something like this for a while, but i have a question: “Am i free to use this for a tool that i use in a commercial project?” =)