bevy_graph Requirements Gathering

[alice-i-cecile]

Throughout the engine, we keep running into graph data structures. We see them cropping up in:

• scheduling
• animation
• rendering
• audio
• plugins
• assets

By standardizing on a single implementation, we can:

• reduce compile times
• share optimizations
• ease learning for both users and contributors
• reduce code complexity
• share visualization tools
• make it faster to test out new graph-driven features

This discussion is an attempt to gather requirements for each of those areas, in order to plan out the base API and architecture needed. Note that while we may eventually use relations (#3742) to store these, this conversation is orthogonal: these are straightforward, centralized data structures.

[alice-i-cecile]

General Requirements

• each consumer must be able to return its own error messages
• performance should be good (petgraph is often too slow)
• API should be clear, and minimally generic
• each type of graph should have its own data structure, in order to allow for fine-tuned performance constraints
• APIs across graph types should be consistent: traits may work well
• these graphs should generally be wrapped in their own custom struct, exposing an API (and error messages) specific to the consuming crate

[dmyyy]

@alice-i-cecile I wonder if it could make sense to fork petgraph for Bevy's purposes. Petgraph has a maintainer issue unfortunately (lots of un-addressed issues/pr's) and just from looking in from the sidelines over the years that doesn't look like it will change anytime soon. What's there at its core is pretty good/well tested which is why petgraph is the go to for most graph applications despite the general jankiness/lacking documentation in some parts/lack of maintenance. The issues/pr's over the years shows that there is a demand for a well-maintained general purpose graph crate - I feel like there's some opportunity for Bevy to step in and be that for the Rust community here.

[alice-i-cecile]

I definitely think we should aim to expose a general-purpose graph crate :) Much like bevy_reflect, I think this is something we can and should make with stand-alone usage in mind. I don't think that forking petgraph is the way though: I don't think we should be tied to the existing API.

[dmyyy]

I don't think we should be tied to the existing API.

Of course - forking would involve stripping out/refactoring what we do/don't need. Just the question of whether it's easier to refactor something that's 90% there to our purposes vs. writing everything from 0. General purpose graph libraries can be tricky to write.

Edit: I think it can be helpful to start with petgraph and think about what we might want to do differently

[maniwani]

I really don't want us to use anything from petgraph, except maybe its implementations of various graph algorithms. Its graph data structure APIs are just bad (they're impressively inconsistent), and that was (and still is) my main motivation to have us develop our own crate.

The API in #7130 is one that I'd find acceptable (although that's because I more or less came up with it), it just hasn't been a priority for review.

[maniwani]

Like, this effort began with an assessment of petgraph and its API is too different from the "ideal". I think writing our own data structures and API from scratch (#7130)—maybe followed by porting things from petgraph::algo—is the best path.

[alice-i-cecile]

Scheduling

Used for

• representing dependencies between systems for ordering

Graph structures we need

• directed acyclic graph

Key operations

• topological sort
• pop next node in topological sort, and access its data
• check for and report cycles

Interesting quirks

• ordering edges can never be removed
• operations on sets of nodes are key

[SolarLiner]

• Extraction of independent task sets for automatic parallelization

[maniwani]

ordering edges can never be removed

This can't be true if we allow systems and system sets to be removed (removing a node removes its edges; removing a system set would remove the systems under it).

operations on sets of nodes are key

Technically speaking, we don't do any special batch operations. #6587 uses two "perpendicular" directed graphs to implement system sets. The vertical (hierarchical) graph is used to "flatten" the horizontal (dependency) graph.

We also wanted clique enumeration (example: https://github.com/Heychsea/CliquesRS) for nicer ambiguity reporting.

[alice-i-cecile]

Rendering

[alice-i-cecile]

Animation

[james7132]

• Directed acyclic graph is the only model needed.
• Multiple roots are not required within a single graph.
• Fast to do a full depth first traversal on a single thread. Each animator or group of animators will likely need to be evaluated at least once per game tick (if not more for rollback netcode).
  • Should be Send in the general case for easier parallelization opportunities.
• Preferably a way to do change detection on parts of the graph, tracable back up to the root nodes. This can help optimize the traversals.
• Edges need to hold some metadata (f32 weight, bool enabled/disabled).
  • Must be mutable after construction.
• Need to support multiple types of nodes (Mixer, Selector, Clip nodes).
  • Preferably this should be user-extendable too via trait.
  • Must be mutable after construction.
  • Need a fast-path that avoids trait objects.
• Graph topology does not need to support removal of edges or nodes after construction (mitigated by marking edges as disabled), but must support adding new nodes at runtime.

Prototype implementation: https://github.com/HouraiTeahouse/bevy_prototype_animation/blob/main/src/graph/mod.rs#L101

[alice-i-cecile]

Audio

[SolarLiner]

• DAG is fine, allowing cycles for feedback effects is desired, but the demand might not come up in a game engine context (and besides, a cyclic graph can be condensed into a DAG, provided we can transform cycles (in audio context, this means implementing feedback processing, which could be done with a custom node into the transformed DAG)
• Allow "compiling" the graph into a schedule - audio engines majoritarily are pull-based from the outputs and need a reverse topological sort, and the need to separate the graph and the schedule is needed to pre-allocate everything beforehand (as audio threads must be realtime-safe, which means lock-free and wait-free)
• Audio graphs can be multi-in and multi-out, but most games only care about a single output and no inputs (taking hardware devices to be in/out here; audio file playback can be considered an input but is most generally represented as a regular node with no inputs
• Node sockets are static and named
• Data flow is untyped (everything is an f32, even boolean logic, which uses a threshold at 0.5 usually)
• Graph is dynamic - even for the most basic usage (playing audio samples), nodes need to be added and removed dynamically, by the nodes themselves (to save on resources, nodes report when they're done)
• Edges don't require data, but convenience data can be added to them (volume/panning of an edge directly, without resorting to a separate node)
• Need two-way communication (main -> audio thread for parameter changes, audio -> main thread for reacting to/vizualizing audio data)

Prior art: https://github.com/ErikNatanael/knyst/

[ErikNatanael]

Looks good! For audio -> main thread communication a special node with a ring buffer can be placed just before the output, whereas for main thread -> audio communication more complexity is required for accuracy. Therefore IMHO audio -> main thread communication doesn't need much consideration in the design of the core technical implementation of the graph.

[harudagondi]

requirements lgtm. I also would like to suggest hexodsp (this is gpl btw), glicol, fundsp, and dasp for inspiration.

[alice-i-cecile]

Plugins

Used for

• plugin dependencies, much like how crates work

Graph structures we need

• directed acyclic graph

Key operations

• topological sort
• pop next node in topological sort, and access its data
• check for and report cycles

[DasLixou]

The sorting then would be the new bevy_graph. Idk but the plugin style with the rust constructor which matches up with bundles seems quite more fittable to me

[DasLixou]

I don't really know how easy it is to modify the current PluginSet thing for a custom bevy_graph. What do you think @alice-i-cecile ?

[alice-i-cecile]

Unsure. I'd need to look at the problem space again :)

[DasLixou]

because i just saw a help post in the discord. there is also not yet a possible way to add plugingroups inside of plugingroups. this could be fixed with an pr but would be quite messy. also it would be harder to use .set and so iguess. when we use my idea (yeah im very proud of myself coming up with an idea i didn't threw away 2 seconds later :] ) we could use smth like #[plugingroup] on top of a struct member just like #[bundle] for bundles.

[DasLixou]

When we want to have a graph of the plugins in the whole app instead of just in the plugins, what we I think want (like app.add_before would be quite nice), then we need the ability to:

• Merge Graphs together

[alice-i-cecile]

Assets

[SolarLiner]

• Nested assets (zip files or formats that embed other assets - eg. gltf)
• On the fly asset processing (via dependency graph)

[ameaninglessname]

Named reroute node is a must having for cleaner graph layout
a video demonstrating it

[DasLixou]

Thats just UI stuff. in behind its just one node when i understood that right.

[Diddykonga]

Lots of Graph Knowledge: https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/?ref=shm

[DasLixou]

We then could also make a debug tool that generates us for example a pdf file with every graph in the bevy project. would be pretty cool to see what connections it makes. you would also be able to see where improovements could be made :)

[djeedai]

Node Editor

Used for

All node based editing for e.g. animation, vfx, shaders, ...

Graph structures we need

• Undirected is enough, because the direction of edges is implicit based on the input and output slots of the connected nodes.
• At least acyclic, and possibly "weak cyclic" (cycles on a subset of nodes, which can be reduced to a no -cyclic graph once that subset has been processed)
• Support for sub-graphs

Key operations

• Full editing (add/remove nodes and edges, edit node content)
• Topological sort for processing
• Compacting/baking into another graph kind: Detect disconnected nodes and prune them, merge some nodes together (e.g. some high-level editing graph contains an "add" node and 2 "constant" nodes, we want to derive a runtime node with a single "a+b" expression baked for efficiency, or a shader graph contains a texture with a blending color, we want to bake that blending into the texture in the runtime data).

[djeedai]

See also discussion on Node Editor in the Editor discussion here: #7100 (comment)