Add a Graph data structure to Godot

[cIymax]

Describe the project you are working on

Just reopening, in the GIP tracker, an old proposal that was closed in the main tracker with the migration to the GIP tracker.

I have conducted a search in the GIP tracker and did not see any similar proposal listed. And as far as I'm aware, this feature has not been implemented. The old proposal was by @willnationsdev and is at:
godotengine/godot#15647

Sample game uses can include modeling any of the following:

• a network of roads in a town sim
• a network of conveyor belts in a factory sim
• a network of pipes in a puzzle game
• a network of spaces on a board game

( https://godotengine.org/qa/108704/best-approach-to-model-a-road-network
https://www.reddit.com/r/godot/comments/pm4mao/how_to_auto_tile_a_topdown_conveyor_belt/ )

Describe the problem or limitation you are having in your project

As noted in the old proposal, there can sometimes be a need to get access to a graph or tree data structure in the script code without having to rely on Control nodes like Tree or GraphNode and without having to rely on the Astar class. Astar is use-case oriented in that it is basically a graph for the sole purpose of pathfinding,

A graph data structure can have more uses than the Astar class, such as when no pathfinding is necessary. Furthermore, using Control nodes for this might be more computationally expensive than rolling a custom implementation in GDScript.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

As noted in the old proposal, Godot could benefit from providing a Reference object type that gives access to a graph data structure of vertices and edges. Both undirected edges and directed edges should be supported. The same goes for both unlabeled and labeled edges, as well as for both unlabeled and labeled vertices.

The advantages of exposing this to scripting could be pretty awesome for making data structures in projects. You could create scripts that use it as a graph or convert it into a binary search tree, a splay tree, or whatever you want.

An example from the Python world would be NetworkX: https://github.com/networkx/networkx

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

It can be like how TreeItems work with the Tree, we could have a DataGraph (Reference, facade), DataGraphVertex (Object 0+ labels & a Variant meta), and DataGraphEdge (Object with 1 label & a Variant meta). This format would keep it as flexible as possible.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Rolling a custom implementation of a graph data structure in GDScript would involve more than just a few lines of code.

Is there a reason why this should be core and not an add-on in the asset library?

As for the placement, how about we create a module that is dedicated to providing generic data structure and algorithm extensions to the core? That would open things up for successive additions of a similar nature and give the DataGraph a comfortable place to live outside of core.

For instance, we can create a module specifically for "data_structures" and having a subdirectory for a DataGraph class and its associated classes.

[fire]

What game use are you using for your project?

[cIymax]

@fire I've updated the writeup to indicate game uses. I've also asked the author of the original proposal, @willnationsdev, to chime in. Thanks!

[Zireael07]

Procedural city here, I end up doing the graph by hand just to be able to tell which intersection connects to which (for mapgen purposes, not actual pathfinding). So there are definite game uses

[fire]

@godotgamedeveloper I recommend prototyping a resource api and proposing the api here.

[KoBeWi]

Rolling a custom implementation of a graph data structure in GDScript would involve more than just a few lines of code.

Isn't graph just

class GNode:
    var name_maybe_idk: String

class Edge
    var node1: GNode
    var node2: GNode
    var weight_etc: float

var nodes: Array
var edges: Array

?

Plus some methods, but that depends on what you need. Could definitely be a plugin.

[willnationsdev]

Iirc, the original proposal ultimately did not go anywhere because all general purpose solutions can easily be made via script/plugins and all performance-optimized graphs have to be tailored for their specific use cases with custom implementations. Thus, making a low-level implementation in core that can be generally used for all games isn't really conceivable.

Edit: now, GUI nodes for connectable nodes as a graph would be useful, but I already have a separate proposal for that.

[Zireael07]

Considering the Astar implementation, which is already in core, needs some sort of a graph too, it makes more sense to expose that graph to scripts instead of requiring plugins?

[Xrayez]

As for the placement, how about we create a module that is dedicated to providing generic data structure and algorithm extensions to the core?

Such a module exists, it's called Goost, and I'm a maintainer/creator of it. 😉

This is certainly a feature worth to be implemented (added to the list of approved proposals in goostengine/goost#7 now), even if it won't cover all possible use cases.

For very basic single path graphs, you can also use a LinkedList currently implemented in Goost (you can also nest lists to create trees). See also relevant Godot proposal:

• Facilitate implementing core data structure such as linked list via modules or plugins #1522

---

Plus some methods, but that depends on what you need. Could definitely be a plugin.

The methods that you omit are the actual meat behind graph data structures, more than any other data structure that you could stumble upon, in my experience.

I've done some procedural generation myself using single path graphs (racing game), generated minimum spanning tree for generating caves and so on (in GDScript). Those algorithms are not really specific, but of course could easily become specific.

Thus, making a low-level implementation in core that can be generally used for all games isn't really conceivable.

If we come up with an implementation which could be useful for at least 30-40% of use cases, that's a win in my book! But of course, that goes against Godot's development philosophy somewhat. Therefore, implementing a data structure like this is likely better implemented in https://github.com/goostengine/goost, but of course that's up to Godot core developers to decide. At any rate, I think it's better that we first implement such a data structure in Goost as an experimental feature first, see if it works in practice, and then let Godot core developers reconsider this proposal. 🙂

But before starting to code, this actually requires quite serious design work. I'd study existing Graph APIs and come up with an API suitable for solving procedural generation specifically. Just posting this so people know about such possibility. I'm not completely proficient with graph theory, unfortunately, but I'm certainly interested.

[sairam4123]

As a city building game developer, I had to roll out my own implementation of graph system. But I made it as similar as Godot's AStar Graph implementation, (except some features that are very specific to my game). You can find it here.

I think that just exposing the underlying graph data structure of the AStar should be good enough for most purposes.

[Xrayez]

The notion of vertices and edges are implementation details of AStar itself. The API previously proposed in godotengine/godot#15647 looks like a collection of separate classes that extend Reference for a graph, and then Object for both vertices and edges. I'm not sure what kind of approach would be best to take, but all of my implementations for a graph involved proper separation. Data structures like LinkedList operate exactly this way.

I'm leaning towards using separate classes for graph/vertex/edge as well. The most prominent advantage that I could think of right now is that it's much easier to navigate the graph:

• With AStar-like API, you basically have to use Graph.get_points_connections() which returns the IDs of neighborhood vertices, and then you have to query the attribute of a vertex that you're interested in using those IDs. Does not feel intuitive.
• With separate classes, you just call GraphVertex.get_neighborhood() returning an array containing GraphVertex instances. An attribute simply becomes a member of that class. Moreover, an Object allows to encore metadata with set_meta(), making it even more versatile.

By the way, VisualScript can also be seen as a graph, the API looks quite reminiscent and also leans towards distinguishing graph and its vertices via VisualScriptNode derived classes, so VisualScript/VisualShader etc are another examples of a graph structure used in Godot.

[Xrayez]

Thus, making a low-level implementation in core that can be generally used for all games isn't really conceivable.

By the way, when people try to use AStar for non-pathfinding purposes as a general-purpose graph or try to mimic it in some way, this already signifies that we need a dedicated solution (not necessarily a general-purpose one, if that's a concern).

Here's to illustrate my point. I recall there was a discussion for decoupling state machine logic into a general-purpose StateMachine class (see godotengine/godot#25021). I think that users should not be tempted or forced into using classes that are meant to solve specific set of use cases, because that could potentially lead to the bloat of those classes, which goes against Godot's principles of remaining small. I realize that there are many ways to implement a StateMachine, so this still leaves the blind spot so to speak (see goostengine/goost#96), but again, it does not mean that there's no useful general purpose solution.

In fact, when I stumble upon some general-purpose solution (like, a library which handles various degeneracies in input), I feel good because I no longer need to worry about validating or fixing my input (heck, it might not be in my control what kind of input I have), Of course, this almost always has a cost of a lower performance, but again, based on specific use case, this is could be acceptable.

I feel discussions like this tend to derail from the original proposal, so feel free to chime in a meta proposal: #3864.

[Xrayez]

Should a graph allow self-loops and multiple edges? Some call it a pseudograph, but some recognize it as a general graph, and call a graph without self-loops and multiple edges just as a simple graph.

Whatever the naming convention, does it make sense to impose some kind of constraints to a graph, or should it be users' responsibility?

I think that a general-purpose graph should be allowed to have any kind of structure in my opinion, but maybe we could add several properties like allow_self_loops and allow_multi_edge. Or just add methods like find_self_loops() -> Array and find_multi_edges() -> Array that you could validate yourself (since there are also loopless graphs that have multi-edges but no self-loops).

[Zireael07]

I think that a general-purpose graph should be allowed to have any kind of structure in my opinion, but maybe we could add several properties

This is the way to go imho. Properties (or methods) that allow optional specialized things, but the core should be general.

[Xrayez]

I have created an initial implementation of a graph, see goostengine/goost#172 (still work-in-progress), I'm interested in early feedback since it's about coming up with core API.

An example from the Python world would be NetworkX

I took some inspiration from it, and adapted to some naming conventions in Godot.

I think it's time to actually solve some concrete problem with current implementation, and see how it works out.

[Xrayez]

Still working on goostengine/goost#172, API so far:

Graph

Connected components were requested by godotengine/godot#15647 (comment) using DisjointSet data structure. The connectivity is not dynamic, but it's possible to make it so. Since DisjointSet does not allow removing elements, it's only possible to implement incremental connectivity. Due to this, we could use dirty flag optimization in the future. But all in all, it's always possible to get all connected components at once by calling get_connected_components().

I'd like to eventually implement Kruskal algorithm for finding MST which utilizes the same data structure.

The find_connected_component(vertex) currently does not take into account incremental connectivity, it actually searches through the given vertex. I think that perhaps the method should be renamed to something else, because currently it works by running depth-first search algorithm (which eventually returns the connected component, but which starts from the given vertex). Then, find_connected_component(vertex) could promptly return all members (connected component) this vertex belongs to. And for the actual searching, you could use GraphIterator (see below).

Not sure about is_strongly_connected() name, as it applies to directed graph and not sure whether it can be used interchangeably with undirected graph. But is_connected() is already taken by Object... 😛

GraphVertex

The neighbors apply both to directed and undirected edges.
The successors and predecessors apply to directed edges.

GraphEdge

GraphIterator

You can search the graph by using an iterator, either built-in or scripted. The built-in ones are DFS and BFS (depth-first and breadth-first search):

var G = graph.iterator
G.initialize(root)  # Some arbitrary vertex in an existing Graph

while G.has_next():
	var v = G.next()
    print(v)

I could eventually simplify this down to using GDScript custom iterators:

for v in graph.iterator
    print(v)

P.S. I've learnt a lot. 😃

[Xrayez]

Implemented Kruskal's algorithm for finding minimum spanning tree in goostengine/goost#172:

Or a maximum spanning tree, all you have to do is to inverse the weights for each edge:

The performance is acceptable for moderate number of edges (takes 100 msec given 10000 edges).
UPDATE: I had a bad XOR hash functions implemented, so only 10 msec given 10000 edges now (x10 improvement).

For the particular case of generating Euclidean minimum spanning tree (like above), this could be improved with Delaunay triangulation for general case. I've seen https://github.com/rakai93/godot_voronoi module that allows to do something like this, and apparently uses a graph structure as well. So at some point it would be probably better to find a way to do Delaunay triangulation while retaining the structure, like in https://github.com/hiulit/Delaunator-GDScript.

Note that I had to fork Godot's DisjointSet data structure because it didn't have the essential find() operation exposed, unfortunately.

Also added serialization support for Graph, so you can save and load graphs as resources.

I'd say the current implementation is quite usable already.

[Zireael07]

@Xrayez: I have a GDScript delaunay implementation around, but no idea how performant my shoddy job is.

One general graph thing I would request is finding loops. Python NetworkX library does it and I always planned to implement it using NetworkX as reference, for my procedural city, but never got around to it ;)

[fire]

I recommend using the delaunay triangulation in godot math.

1. https://github.com/godotengine/godot/blob/master/core/math/delaunay_3d.h
2. https://github.com/godotengine/godot/blob/master/core/math/delaunay_2d.h

[Xrayez]

One general graph thing I would request is finding loops.

I'm sure there has to be a way to do this with current API. The solution depends on whether you'd like to:

• detect that there's any cycle in the graph (use depth-first search algorithm)
• prevent cycles to appear in the first place (use union-find algorithm)
• find or iterate through all cycles

Note that trees should not contain cycles by definition. Therefore, you can run minimum_spanning_tree() (with or without weights), and check edges that are present in the original graph, but not in the tree. If you add any such edge back to the original, it will produce a cycle. The actual process of extracting cycles is another task, and appears to be NP-hard. 😃

There's an answer at StackOverflow which suggests to use Johnson's algorithm, which NetworkX appears to implement.

I recommend using the delaunay triangulation in godot math.

Note that there exist the geometric Delaunay triangulation I've exposed previously in godotengine/godot#29127. I think the output of Delaunay2D/3D could be converted to a Graph in Geometry2D/3D singletons in order to retain the structure and allow for further graph processing.

[Zireael07]

I think of the three options you mentioned,

find or iterate through all cycles

is the best since it allows achieving 1 and 2 also (if there's more than 1 cycle found, you have a cycle)

Good point about trees not containing cycles, though - I might try that trick.

[Xrayez]

Implemented Dijsktra's algorithm in goostengine/goost#172 (via Graph.shortest_path_tree(root)):

This actually constructs an entire shortest path tree, from which you can collect all shortest path starting from any source root:

The main use case is certainly procedural generation and simple path finding. I think this won't be efficient to use compared to AStar class in Godot (haven't tested), but the performance is good enough: 30 msec for 10000 edges. This may be faster in some cases since this pre-computes the entire tree.

There's an answer at StackOverflow which suggests to use Johnson's algorithm, which NetworkX appears to implement.

Jonhson's algorithm uses Dijsktra's algorithm as a subroutine, so I guess this could eventually help to implement a method to find cycles in the graph.

find or iterate through all cycles

is the best since it allows achieving 1 and 2 also (if there's more than 1 cycle found, you have a cycle)

but again, this doesn't seem to be a trivial problem to solve, akin to finding longest path in the graph which is NP-hard. I may be wrong, though. I found a snippet if someone would be willing to implement: https://github.com/qpwo/python-simple-cycles/blob/master/johnson.py

[Xrayez]

The Graph class is available in gd3 development branch now: https://github.com/goostengine/goost, see documentation for Graph as well. Testing and feedback welcome, of course.

For the particular case of generating Euclidean minimum spanning tree (like above), this could be improved with Delaunay triangulation for general case.

This was actually more or less straightforward to implement:

The naive implementation would involve generating a complete graph (every possible edge between vertices) and generating MST from that. Using Delaunay triangulation first, I confirm that this produces identical trees, and is much faster to generate (up to x100 faster or more depending on point count).

func delaunay_mst():
	var points = generate_points()
	var I = Geometry.triangulate_delaunay_2d(points)

	graph = Graph.new()
	var V = []
	for p in points:
		V.push_back(graph.add_vertex(p))

	for idx in range(0, I.size(), 3):
		var tri = [V[I[idx + 0]], V[I[idx + 1]], V[I[idx + 2]]]
		for i in tri.size():
			var a = tri[i]
			for j in range(i + 1, tri.size()):
				var b = tri[j]
				if not graph.has_edge(a, b):
					var w = a.value.distance_to(b.value)
					graph.add_edge(a, b, w)

	return graph.minimum_spanning_tree()

See example project at:

https://github.com/goostengine/goost-examples/blob/9ec8600af5b521da1f73fe9ad4b2af41c9764dd4/2d/geometry/scenes/triangulate_delaunay.gd

[fire]

While working on manifold I found https://github.com/haasdo95/graphlite.

References

elalish/manifold#91

[Zireael07]

Bump bump.

I find myself needing a heap/priority queue. I understand AStar uses one since godotengine/godot#28925

Also would be nice to have documented somewhere what data structure Astar uses for neighbors (and potentially exposed so that we can use it for Dijkstra/BFS)

[m21-cerutti]

Since now goost isn't maintained anymore for godot4, would need either extract goost graph into a module or extension, create one from scratch, or make a wrapper from an other library.

Is there someone who have tried the last solution ? I have seen librairies like BGL, Melon that could be good candidates for a more general purpose graph (I would also be curious about a benchmark beetween this solutions and the legacy AStar)
https://www.boost.org/doc/libs/1_82_0/libs/graph/doc/index.html
https://github.com/fhamonic/melon

[nirahiel]

Tried to make a pure GDScript version of the goost graph for godot 4 but it's complicated. the source being in C++, there's a lot of things I don't really understand. I'm still searching online if there's something someone made already but, well, no luck so far. I guess i'll have to implement that code myself. (painfully ...)