bit_gossip

bit_gossip, named after its implementation technique, is a simple pathfinding library for calculating all node pairs' shortest paths in an unweighted undirected graph.

Once the computation is complete, you can retrieve the shortest path between any two nodes in near constant time; I'm talking less than a microsecond!

This library is for you if your game:

• has decent number of nodes/tiles (~1000), and
• has hundreds or thousands of entities that need to find paths to a moving target.

If you have a static map of large number of nodes (>10,000), you can use this library to compute all paths during the loading phase.

Also, computation is fast enough to be used not only in static maps but also in dynamically changing maps in games.

• Computing all paths for 100 nodes takes only a few hundred µs on a modern CPU.
• Computing all paths for 1000 nodes takes less than 50 ms on a modern CPU.
• Computing all paths for 10000 nodes takes less a few seconds.

See benchmarks for more details.

Table of Contents

Basic Usage

Small Graphs

For small graphs with less than 128 nodes, use Graph16, Graph32, Graph64, or Graph128.

In GraphN, like Graph16, N denotes the number of nodes that the graph can hold.

0 -- 1 -- 2 -- 3
|         |    |
4 -- 5 -- 6 -- 7
|         |    |
8 -- 9 -- 10 - 11

use bit_gossip::Graph16;

// Initialize a builder with 12 nodes
let mut builder = Graph16::builder(12);

// Connect the nodes
for i in 0..12u8 {
    if i % 4 != 3 {
        builder.connect(i, i + 1);
    }
    if i < 8 {
        builder.connect(i, i + 4);
    }
}

builder.disconnect(1, 5);
builder.disconnect(5, 9);

// Build the graph
let graph = builder.build();

// Check the shortest path from 0 to 9
assert_eq!(graph.neighbor_to(0, 9), Some(4));
assert_eq!(graph.neighbor_to(4, 9), Some(8));
assert_eq!(graph.neighbor_to(8, 9), Some(9));

// Both 1 and 4 can reach 11 in the shortest path.
assert_eq!(graph.neighbors_to(0, 11).collect::<Vec<_>>(), vec![1, 4]);

// Get the path from 0 to 5
assert_eq!(graph.path_to(0, 5).collect::<Vec<_>>(), vec![0, 4, 5]);

Large Graphs

For graphs with more than 128 nodes, use Graph, which can hold arbitrary number of nodes.

If the environment allows multi-threading, Graph will process paths in parallel for faster computation.

In this example, let's create a 100x100 grid graph.

use bit_gossip::Graph;

// Initialize a builder with 10000 nodes
let mut builder = Graph::builder(10000);

// Connect the nodes
for y in 0..100u16 {
    for x in 0..100 {
        let node = y * 100 + x;

        if x < 99 {
            builder.connect(node, node + 1);
        }
        if y < 99 {
            builder.connect(node, node + 100);
        }
    }
}

// Build the graph
// This may take a few seconds
let graph = builder.build();

// Check the shortest path from 0 to 9900
// This is fast
let mut curr = 0;
let dest = 9900;

let mut hops = 0;

while curr != dest {
    let prev = curr;
    curr = graph.neighbor_to(curr, dest).unwrap();
    println!("{prev} -> {curr}");

    hops += 1;
    if curr == dest {
        println!("we've reached node '{dest}' in {hops} hops!");
        break;
    }
}

Updating the Graph

You cannot update the graph directly, but you can convert the graph back into the builder, update the number of nodes and add/remove edges, then build the graph again.

I have not tested the resizing of graph yet, so please open an issue if you find any bugs.

use bit_gossip::Graph;

// Initialize a builder with 10000 nodes
let mut builder = Graph::builder(10000);

... build graph

// Build the graph
// This may take a few seconds
let graph = builder.build();

... do some work

let mut builder  = graph.into_builder();

// Resize the graph to 5000 nodes
builder.resize(5000);

// add/remove edges
builder.disconnect(0, 1);
builder.connect(0, 3000);

... 

/// Build the graph again
let graph = builder.build();

Graph Types

• Graph16, Graph32, Graph64, Graph128: Uses primitive data types for bit storage and are highly efficient.

  • In GraphN, N denotes the number of nodes that the graph can hold.
  • Use these types for fixed node sizes less than 128 nodes.

• Graph: Supports arbitrary node sizes and is optimized for parallel processing.

  • Enum of SeqGraph and ParaGraph. If environment supports multi-threading, ParaGraph is used; otherwise, SeqGraph is used.

• SeqGraph: Uses Vec<u32> or Vec<u64> to store bits depending on the target architecture, and generally about 3 times slower than primitive data types.

• ParaGraph: Uses Vec<AtomicU32> or Vec<AtomicU64> for bit storage, which is slower but benefits from parallel processing, making it more efficient as the number of nodes increases.

For fixed node sizes less than 128 nodes, prefer primitive-data-type-backed graph types.

The library exposes a generic Graph type that automatically selects the parallel or sequential version based on the environment, with manual selection also available.

How It Works

Graph Representation

Building the Graph

0 -- 1 -- 2
|    |
3 -- 4
|
5

[ ][ ][ ][ ][ ][ ] // 0 -> 1
[ ][ ][ ][ ][ ][ ] // 0 -> 3
[ ][ ][ ][ ][ ][ ] // 1 -> 2
[ ][ ][ ][ ][ ][ ] // 1 -> 4
[ ][ ][ ][ ][ ][ ] // 3 -> 4
[ ][ ][ ][ ][ ][ ] // 3 -> 5

[ ][ ][ ][ ][1][ ] // 0 -> 1

[ ][ ][1][ ][ ][ ] // 0 -> 3

[ ][ ][ ][ ][1][ ] // 0 -> 1

flips to

[ ][ ][ ][ ][0][ ] // 1 -> 0

[ ][ ][ ][ ][0][1] // 1 -> 0

flips to

[ ][ ][ ][ ][1][0] // 0 -> 1

[ ][ ][ ][1][ ][ ] // 1 -> 2

[ ][ ][ ][0][1][ ] // 2 -> 1

[ ][ ][ ][ ][1][0] // 0 -> 1
[ ][ ][1][ ][ ][0] // 0 -> 3
[ ][ ][ ][1][0][ ] // 1 -> 2
[ ][1][ ][ ][0][ ] // 1 -> 4
[ ][1][0][ ][ ][ ] // 3 -> 4
[1][ ][0][ ][ ][ ] // 3 -> 5

[ ][ ][ ][ ][1][0] // 0 -> 1
[ ][ ][1][ ][ ][0] // 0 -> 3

[ ][ ][ ][ ][1][0] // 0 -> 1
[ ][ ][1][ ][0][0] // 0 -> 3

[ ][ ][0][ ][1][0] // 0 -> 1
[ ][ ][1][ ][0][0] // 0 -> 3

[ ][ ][1][ ][0][1] // 1 -> 0
[ ][ ][ ][1][0][ ] // 1 -> 2
[ ][1][ ][ ][0][ ] // 1 -> 4

[ ][ ][1][ ][0][1] // 1 -> 0
[ ][ ][ ][1][0][0] // 1 -> 2
[ ][1][ ][ ][0][0] // 1 -> 4

[ ][ ][1][0][0][1] // 1 -> 0
[ ][ ][ ][1][0][0] // 1 -> 2
[ ][1][ ][0][0][0] // 1 -> 4

[ ][0][1][0][0][1] // 1 -> 0
[ ][0][ ][1][0][0] // 1 -> 2
[ ][1][ ][0][0][0] // 1 -> 4

[ ][ ][0][ ][1][1] // 3 -> 0
[ ][1][0][ ][ ][ ] // 3 -> 4
[1][ ][0][ ][ ][ ] // 3 -> 5

[0][0][0][ ][1][1] // 3 -> 0
[0][1][0][ ][ ][0] // 3 -> 4
[1][0][0][ ][ ][0] // 3 -> 5

[ ][0][ ][1][1][1] // 4 -> 1
[1][0][1][ ][ ][1] // 4 -> 3

[ ][0][0][1][1][1] // 4 -> 1
[1][0][1][ ][0][1] // 4 -> 3

[ ][1][0][1][1][0] // 0 -> 1
[1][1][1][ ][0][0] // 0 -> 3
[ ][0][ ][1][0][0] // 1 -> 2
[ ][1][1][0][0][0] // 1 -> 4
[0][1][0][ ][1][0] // 3 -> 4
[1][0][0][ ][ ][0] // 3 -> 5

Path Retrieval

0 -- 1 -- 2
|    |
3 -- 4
|
5

[0][1][0][1][1][0] // 0 -> 1
[1][1][1][0][0][0] // 0 -> 3
[0][0][0][1][0][0] // 1 -> 2
[1][1][1][0][0][0] // 1 -> 4
[0][1][0][0][1][0] // 3 -> 4
[1][0][0][0][0][0] // 3 -> 5

[1][1][1][0][1][1] // 2 -> 1

[1][0][1][0][0][1] // 1 -> 0
[0][0][0][1][0][0] // 1 -> 2
[1][1][1][0][0][0] // 1 -> 4

[0][0][0][1][1][1] // 4 -> 1
[1][0][1][1][0][1] // 4 -> 3

[0][0][0][1][1][1] // 3 -> 0
[0][1][0][0][1][0] // 3 -> 4
[1][0][0][0][0][0] // 3 -> 5

Benchmarks

The benchmarks below illustrate computation times for different graph sizes and types. They serve to highlight the performance characteristics of various graph representations rather than providing absolute metrics.

Note that different types of graphs will take different amount of time; For example, maze graphs took a bit more than just tile grids.

Machine Specs: Apple M3 Pro, 12-core CPU, 18GB RAM

The benchmarks were performed on tile grids where each node is connected to its four neighbors.

Here, n denotes the number of nodes, e the number of edges, and (WxH) the grid dimensions. For a grid of size WxH, there are W*H nodes and 2*W*H - W - H edges.

Processing Time

Memory Usage

Below are the theoretical memory requirements for different graph types based on the number of nodes.

The function for calculating edge bits' memory usage is n * m / 8 bytes, where n is the number of bits of data type and m is the number of edges.

The function for calculating nodes neighbors data memory usage is:

• For GraphN, n * N / 8 bytes, where N is the number of bits of data type, and n is the number of nodes.
• For SeqGraph and ParaGraph, e * 2 * 2 bytes for graph less than 65536 nodes using u16 for nodeID, and e * 4 * 2 for graph more than 65536 nodes using u32 for nodeID where e is the number of edges.

The value in chart below is the sum of edge bits and node neighbors data memory usage.

It does not account for memory overhead of atomics, hashmap or vector structures.

So in reality, the memory usage will be much higher than the values shown below.

Below chart shows memory usage in bytes B.

Features

• parallel: Enable parallelism using Rayon; this feature is enabled by default.

Examples

I have made a simple maze game using bevy to compare bit_gossip and astar.

The game will create a 80x80 grid maze.

You can move the "player" (green dot) using the arrow keys.

Whenever you press the <space> key spawns 200 more enemies (red dots) that chase the player.

When the player and enemies collide, the enemies are removed.

note: for bit_gossip, building a graph initially with 80x80 grid maze takes a few seconds, and the enemies will not move until built. When built, it will log graph built in ...s to the console.

You can run the bit_gossip version with:

cargo run --release -p maze

You can run the astar version with:

cargo run --release -p astar_maze

This is just to show how bit_gossip can be used in a game.

For me, at around 1000 enemies, I start to notice a lag in the astar version whenever the player moves. bit_gossip version, however, does not show any lag regardless of the number of enemies.

I went up to more than 50000 enemies, and it shows no degradation in performance.

Still, it is amazing how well astar performs even with 1000 enemies chasing the player. This means that for most games, astar is more than enough.

you can change the size by going into examples/maze/src/main.rs for bit_gossip version, and examples/astar_maze/src/main.rs for astar version.

Change the values in MazePlugin::new(50, 50) to change the maze grid width and height.

Astar Recording

https://github.com/user-attachments/assets/b1ddf4da-c885-4b86-b114-a2cce7ff7e98

Bit Gossip Recording

https://github.com/user-attachments/assets/be9378f4-e3c8-452b-b94c-900b7a94b45a

Optimization for Large Graphs

Partitioning

Partitioning the graph into smaller graphs can help with memory usage and computation time.

With astar, I believe this is called hierarchical pathfinding?

If you have over 10000 nodes, you should definitely consider partitioning the graph.

Dividing the Map Better

Instead of making tiles into graphs, think about dividing your map into rooms and doors.

A room is a space where any point is reachable from any other point trivially, like by drawing a straight line.

A door is an edge that connects two rooms.

This way, you can just find a path from room to room, at which point you can just move straight to the more specific point in the room.

Personally, I think this is a better approach than partitioning the graph.

Future Plans

When I was developing the algorithm, I found some interesting points about the algorithm that I could explore further to find more ways to optimize the algorithm.

Node with A Single Neighbor

When a node only has a sinlge neighbore, that neighbor is the shortest path to all other nodes.

Furthermore, if that neighbor only has two neighbors, that node's only other neighbor is the shortest path to all other nodes.

This can be a good optimization point for maze-like graphs.

Delta/Flow of Information

I'm not sure what to call this yet, but this is related to partial updates of the graph.

Say, after the graph is built, we want to remove an edge.

How can we update the graph without rebuilding the entire graph? Which nodes should be updated?

One idea that I have not explored far enough is thinking of the graph as a flow of information.

The information lost due to removing that edge is the nodes that were reachable only through that edge.

lost bits = (merged bits of all other edges) ^ (bits of the edge to be removed)

Does this make sense?

So for the node's neighbors and their neighbors, we only unset the bits that were uniquely set by the edge that was removed.

And, for any node affected, if their neighbor also has the shortest path for any of the lost bits, we don't propagate it.

It seems not too hard... but I need to think about it more, and also about how much compute it will actually save?

GPU/SIMD Acceleration

I'm not an expert on GPU or SIMD, but maybe it could be possible?

Finding Dangling Nodes

It should also be trivial to find the nodes that are unreachable from all other nodes.

In a node, any node, merge all edges' bits together, and, if some bit are still 0, that node is unreachable.

Moving Away from a Destination

It is also very easy to find a path to move away from a destination.

It's just the opposite of finding a path to the destination.

Find an edge with the bit set as 0, and move to that node. It's uncertain whether it is the furthest path from the destination, but at least you won't get closer faster than the shortest path.

What Paper Did I Base This On?

Short Answer: None.

Of course, I tried looking into precomputed pathfinding in gamedev communities, but the only similar concept that I could find was written back in 2003; Richard "superpig" Fine published an article that uses matrices to store the shortest paths between all pairs of nodes, although he does not give detail on how to actually compute the matrix.

Even after starting the project, I had no idea that there was a huge field of mathematics called All-Pairs Shortest Paths (APSP) that is dedicated to solving this problem.

Only after I finished the initial implementation did it occur to me that maybe this is a well-known problem with established solutions, and I just didn't look hard enough.

So, then, I started looking into graph theory and found out about APSP, as well as papers on this topic. I learned about Floyd-Warshall and Johnson's algorithm, and I found some papers on APSP.

There are some similar thoughts with Floyd-Warshall and Johnson's, but the implementation is quite different as far as I know.

I tried reading papers on this topic, but either:

1. they were behind paywalls, or
2. I just could not understand them; how can the pseudo code be less readable than my actual code?
3. and none of them have actual code implementation nor real-life benchmarks.

So, at some point, I lost complete interest and gave up on reading papers; I decided I'm just too dumb for academic life.

So, long answer: Also, none.

This implementation is original as far as I know, though there may be some similar concepts; I also scraped the github repos to find any similar concepts or implementations, and found none.

It is entirely possible that someone already wrote a paper on this implementation, and I just couldn't find it; if so, please email me at jackyldev@gmail.com

If you could also explain what the paper is in simple terms, I would be grateful, because I do want to understand what they are saying.

With that being said, here are some papers that I wish I had access to or had the ability to understand:

• On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
• Original optimal method to solve the all-pairs shortest path problem: Dhouib-matrix-ALL-SPP - ScienceDirect
• Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time | Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

If anyone wants to explain what any of these papers are talking about, please email me at jackyldev@gmail.com