Dependency Graph Layout

Class overview

Map Dependency Graph

PackBSP's dependency-graph system uses a set of directed graphs, where often one graph is used per map-file. Graphs may contain cycles as they are being built, but are generally post-processed to break cycles with warning placeholder-nodes. It is possible for a graph to have a symbolic placeholder Node which refers to the root of another graph.

Nodes

On the most basic level, a Node represents a step of work within a dependency graph. Examples include:

• A map which is under consideration for packing (Often the root-node)
• A relative asset-path, like materials/brick01.vmt
• A concrete asset, like c:\game\materials\brick01.vmt
• A non-asset file which specifies other dependencies, like a PackBSP settings file for a map
• A decision between different alternatives, such as taking an ambiguous texture path (materials/foo) and deciding whether that should match materials/foo.spr or materials/foo.vmt depending on which is available.

Nodes are immutable and are considered equal if they are of the same type and contain the same "core" information.

Edges

An Edge connects two Node objects in a single direction, and has a flag to specify whether it is an implicit or explicit linkage.

Like Nodes, each Edge must be immutable and have a suitable equals() contract.

NodeHandler

A NodeHandler is responsible for iteratively expanding graphs when presented with the graph and a target Node. Each NodeHandler implementation is responsible for skipping Nodes it cannot usefully process, as well as the effort of tracking the work it has already done and avoiding unnecessary work when presented with the same Node within anotehr graph.

Graph traversal and connections

To traverse a graph, every node should be visited at least once. To efficiently detect and prevent cycles in the graph, traversal order is depth-first, maintaining a list of nodes along the current path.

When visiting a particular Node, the creation of new successor nodes is delegated to an ordered collection of NodeHandler objects, where each NodeHandler is offered the opportunity to suggest new additions to the graph. (It is also possible for a handler to signify that no further handlers should be called, as a performance tool.)

Cyclic errors

It is possible for "legitimate" cycles to occur in the assets being analyzed, where they explicitly describe a cyclic relationship. Sometimes this results in errors for the game being played, other times it does not. When a cycle is detected, we model it with a placeholder Node containing meta-information about the problem. The placeholder may be used later to emit a warning to the user.

Explicit vs Implicit edges

Most dependencies are explicit: It is completely certain that a particular asset is required, because another asset specifies its name explicitly. Others are implicit: The game may use them if they are present, but we cannot know for sure whether they are necessary or desired. One example of an implicit resource would be a map description file that has a similar file-name to the map, but which has a prefix or another extension.

The dependency graph stores implicit/explicit state on Edge objects, since a node may be implicitly linked through one path, but explicitly linked through another. Node objects themselves can be considered "explicit" whenever there exists any path to them which is composed only of explicit Edges.

This distinction does not matter much during general graph construction, but comes into play during the packing phase, where we want to strongly warn users about missing explicit assets while only gently suggesting implicit ones.

Determining connected states

When graph creation is completed and no more Nodes can be added, we need information about how each node is connected to the root of its graph.

This is accomplished by a single depth-first search of the graph, where a Set is kept of Node instances which are explicitly-connected (via only explicit Edges) and another Set is kept for "implicit" Nodes (linked but with one or more implicit links in the path.) Nodes may be "promoted" to the explicit-set as necessary.

TODO: Continue connection description? Is this better just in code?