Energy Distribution Grid: Graph Representation

[Indy2222]

As a first step, lets make this extremely simple:

• Energy distribution grid is represented as an un-directed graph.
• The graph may consist of multiple connected components.
• Edges in the graph represent energy interlinks. I.e. power may flow from node to node over the edges.
• Nodes in the graph are buildings & units.
• Every two neighboring nodes in the graph:
  • Are entities whose distance is less than X meters.
  • At least one of them is a power hub.
• The graph is maximal in respect to the above condition. I.e. when the conditions are met, then the two entities must be neighbors in the graph.
• The graph representation allows:
  • Updating with every game tick (despawned entities are removed, spawned entities are added, neighbors are updated for moving entities).
  • Is efficient: thousands of moving units should not cause massive resource usage.
  • Supports common graph algorithms. Especially maximum flow and related algorithms.

[Indy2222]

In the future we might use whatever comes out of bevyengine/bevy#3742. However, let's not get this blocked -> we might need custom implementation in the meantime.

[JackCrumpLeys]

I aim to cover my progress, thoughts and discussion I have had privately with @Indy2222 around this system in this comment to allow open discussion of this very essential system. Most of the code I have at this stage is here: https://github.com/JackCrumpLeys/DE/tree/feat/energy/graph. These are not final decisions but rather prototype code.

Data

Graph

The graph contains every every unit as its nodes and edges between nearby units.

• Graph is updated every frame.
• The graph system I am using is a Graph Map from petgraph.
• The graph is a single large graph.

/// The power grid resource is used to store the power grid graph.
#[derive(Resource, Debug, Clone)]
pub(crate) struct PowerGrid {
    /// The power grid graph.
    graph: GraphMap<Entity, f64, Undirected>,
}

• Graph parameters
  • The key for looking up nodes is Entity. This allows good integration into bevy.
  • Weight is represented by f64 (Pretty much just placeholder as I don't have a use for this yet).
  • Graph is undirected.
• Pros:
  • constant time edge look up due to underlying data being a hash map.
  • Relates to Entity allowing good integration into bevy.
• cons
  • Iterating a hash map is likely slow so algorithms interpreting it need to avoid iterating. (Iterating entities from an ecs query may suffice)

kdtree

This kdtree contains all entities with TrackedByKdTree and provides a way to look up nearby units.

• This is a possible alternative to using the already implemented AABB lookup.
• Faster lookup times?
• Representation:

#[derive(Debug, Resource)]
pub struct EntityKdTree {
   tree: KdTree<f32, u64, 2, 512, u32>,
   entity_to_last_loc: HashMap<Entity, ([f32; 2])>,
}

• KdTree parameters:
  • coords are in f32.
  • lookup index is in u64. (using Entity::to_bits())
  • we are using 2d coords so 2 dimensions
  • bucket size of 512 to allow a lot of units in the same dimension.
  • inner index of u32
• entity_to_last_loc is used to get the last known location of an entity so we can look them up.
• pros:
  • faster?
  • easy to look up in radius
• cons:
  • new system (keeping track of entities)
  • more data storage
  • could just use already implemented AABB

Components

The basic idea is that the EnergyReceiver component will be added to units that have a battery but do not produce or want to give away energy. The EnergyProducer component on the other hand indicates that the unit wants to provide the energy grid with power. Both of these components allow the unit to have energy pass though them in order to reach a EnergyReceiver.

/// The energy receiver component is used to mark an entity as an energy receiver.
#[derive(Component, Debug, Clone, Copy)]
pub struct EnergyReceiver;

/// The energy producer component is used to mark an entity as an energy producer.
#[derive(Component, Debug, Clone, Copy)]
pub struct EnergyProducer;

systems to design

nearby units component

Units all have a nearby component (maybe a smallvec with some enum like transmitters, receivers or enemy units),

• Either e.g NearbyReceiver(Entity) or NearbyReceivers(SmallVec)
• This component allows the graph to be assembled with more ease.
• A system that updates this component based on unit movements (Built with parallelism). One thing I noticed during testing is that the rotation that they like to do (pathfinding?) updates the graph way to much so we should check for real movement before processing.
  • We could solve the update issue by only Triggering an update if both a) Bevy change detection on Transform was triggered, b) the position was updated by at least x (so small changes & rotational changes do not lead to unnecessary re-computation)
• We should keep all nearby entities (not just the transmitters) in the component. That would enable reciprocal updates (i.e. you only update (de)spawned or moved entities and their reciprocals). Also, we could use such a data structure in movement (like hybrid reciprocal obstacle avoidance).
• Uses either KdTree or AABB to find nearby entities depending on profiling.

Graph updates

a system that builds/updates the graph for new entities and updated entities (Added<NearbyUnits> and Changed<NearbyUnits>). This system should be able to run very fast as all it does is add edges where there should be and remove edges were no connection exists. (What do we do with edge weight here?)

• The graph should be updated regularly but does not need to update at the speed of the frame rate (possibly 10 updates per second).

Energy processor

A system that uses the graph to transfer energy. This system is solely responsible for using and interpreting the graph. This system ultimately decides where energy is needed and tries to get it there. (probably the most performance heavy system)

• Maximum flow algorithm.
• Assign priory for where to put energy.
• This system still needs a lot of design and should mostly be covered by Energy Distrubution Grid: Power Flow #475

Video demo showing a visualization on my prototype branch