Godot Engine (godotengine/godot on GitHub) is an open-source, primarily C++-based game engine. It supports both 2D and 3D. As a C++ programmer, I decided to generate a dependency graph of the #include “…” and try to determine the most important files in the graph.

By doing so, I hope to uncover what files are important to look at for beginners who want to contribute to Godot.

godot-engine-full.PNG
The final graph, as visualized in Gephi.

Methodology

I used cinclude2dot2, a Python-based script, to parse the C/C++ source files directly from the Godot source files from its GitHub repository and detect lines with file inclusions. The data was manually cleaned and stripped of its directory paths, leaving only the filenames. This means that files that have duplicate names are merged into one single node in the graph. This is undesirable.

I used Gephi to perform the visualizations and all of the metric calculations, running OpenOrd and ForceAtlas2 on the graph with various settings.

 

Results

First of all, let’s introduce a few concepts.

  • In-Degree is how many times a file is included by other files.
  • Out-Degree is how many times a file includes other files.
  • Degree is the sum of both In-Degree and Out-Degree
  • PageRank is the famous Googley algorithm for ranking web pages, but it can also be applied to graphs, in general! Here, we use it to rank files in the dependency graph.

In-Degree

godot-all-in-degree
The top 20 Godot C++ source files (with directory names stripped) ranked by In-Degree, or by how many files include these files.

 

 

First of all, according to our ranking, we can see that the configuration and access setting files config.h and project_settings.h are quite popular. Unfortunately, config.h is an amalgam of 5 different files at this time, but all reside within the thirdparty/ directory:

./thirdparty/squish/config.h
./thirdparty/pcre2/src/config.h
./thirdparty/opus/config.h
./thirdparty/mbedtls/include/mbedtls/config.h
./thirdparty/libvpx/vpx_ports/config.h

So, we can conclude that Godot (or, rather, code that Godot uses) is focusing on these libraries quite a lot. Nothing too big, but possibly something we may want to break up later if we want a closer look at it.

os.h is quite an important file, as it is a class that deals with changing video modes, querying the operating system for memory usage, and so on and so forth.

Strangely enough, important classes like Object are not showing up here! In-Degree is quite a naive measurement for important of nodes in a graph — you’ll see better ones later.

Out-Degree

godot-all-out-degree
The top 20 files in Godot according to Out-Degree, or how many times it references other files.

We can interpret out-degree as “the most complex files to understand” if we assume that we must understand the content coming from headers that it references. It is fitting, then, that the Godot editor, and scene manager show up in this list. However, the large numbers become less scary if we consider that register_types.cpp is actually the name of over 30 distinct files…

You may have noticed that certain files with the “bt” prefix keep coming. What is this? This is the Bullet physics engine that has been used in many open-source projects, as well as in commercial projects (even movies!) It makes sense that Bullet files show up quite highly here, as physics and collision are no simple tasks to accomplish and understand.

PageRank

godot-all-pagerank

PageRank is an algorithm that derives a node’s weights based off of the weights of other nodes, favoring connections that direct to the node rather than away from the node. Thus, PageRank not only creates a more “global” metric, but it also favors nodes on the receiving side of a dependency reference.

We can see quite a large change from the other metrics. We can see more important files like Godot’s reimplementation of vector, “basic functions and definitions to be used everywhere” in typedef.h, and Godot’s String class.

So, perhaps, when one is going through Godot, it would be helpful to keep an eye out for some of these! Odds are you’ll encounter a header file on this list, and odds are that most other people will too.

Betweenness Centrality

godot-all-betweenness-centrality-unnormalized
The top 20 files in Godot ranked by betweenness centrality or by the number of shortest paths between nodes in the graph that pass through a vertex.

Centrality metrics are great for figuring out what nodes are at “the core/central point” of the graph. Here, we can finally see that Object, “the base class for almost everything,” takes a fitting place at the top of the ranking — even the official documentation thinks its important! Variant, “the most important class in the engine,” also shows up at #2. One result that isn’t well-documented with a custom guide for it within the documentation is the GUI-focused class, Controlcontrol.h is influenced by and influences a large amount of the codebase, which is fitting if we consider that Godot Engine’s editor is built within its own GUI framework.

  • Sidenote: I personally think that Godot’s feat of building its own editor as a Godot game is quite a cool and unique thing! I think this deserves more exposure.

editor_node.h and node.h seem to form the backbone of the editor and the scene engine, respectively — they are, perhaps, prime candidates for study for getting an intimate look at Godot.

Many of the classes here hint at fundamental systems such as imaging, the main engine loop, or the editors themselves.

Important Clusters/Modules

In Gephi, I ran the modularity detection to attempt to cluster the Godot codebase into different clusters, except, this time, I decided to weight the node size based on betweenness centrality because it tended to agree with the official documentation’s placement of importance on Variant and Object. Below is the new picture, with only the 7 largest clusters colorized:

godot-engine-full
The new graph layout with betweenness centrality ranking the size of the nodes.

Cluster 1: Core and Editor (26%)

godot-cluster-1.PNG
The largest unsupervised cluster detected by Gephi. It accounts for 26% of the files in Godot, and seems to encompass Object, Node, Control, and various other nodes in the core/ directory.

Cluster 2: main, config, and libraries (14.53%)

godot-cluster-2
The second largest cluster seems to encompass main.h and various other libraries that are external to Godot.

Cluster 3: Object, Variant (14.11%)

godot-cluster-3.PNG
Strangely enough, this cluster may belong with the first one, but it could very well easily form its own with the documentation-proclaimed “two very important classes” Variant and Object present here.

Cluster 4: Bullet library (9.2%)

godot-cluster-4.PNG
Although the labels are hard to read even in the PDF, this cluster represents the Bullet physics library that Godot uses. Many of their files are prefixed with “bt”.

Cluster 5: libvpx (6.75%)

godot-cluster-5
This cluster seems to include the influential vpx_config.h, a sign that this cluster most likely represents the sub-part of Godot that relies on libvpx. This is a video encoding library.

Conclusion

One interesting thing we found out about Godot is that a significant amount of its codebase is not even particularly a part of Godot itself. There is at least 10-15% of Godot engine code within the repository that one can expect to be fairly isolated but still heavily referenced by other libraries — perhaps worker who begin to encounter these high-influence files may find themselves having to learn these libraries to push their development to the next level.

We have revealed that a majority of the code in Godot is rightfully influenced by and influences many of the files under the core/ directory, and have identified some important candidates that may be suitable for further documentation. This analysis confirms the notion that Variant and Object are two extremely important classes in the Godot engine, though there are many other important ones which influence their areas of the codebase quite significantly as well.

Files

Many, but not all of the pictures and data is included in the zip file below:

godot-all-graph-analysis

Advertisements