bit_gossip

bit_gossip，以其实现技术命名，是一个简单的路径查找库，用于计算无权无向图中所有节点对的最短路径。

计算完成后，您可以在几乎恒定的时间内检索到任意两个节点之间的最短路径；我指的是少于一微秒！

如果您游戏的

• 节点/瓦片数量适中（约1000个），并且
• 有数百或数千个实体需要找到移动目标的路径。

如果您有一个大量节点（>10,000个）的静态地图，您可以在加载阶段使用此库计算所有路径。

此外，计算速度足够快，不仅可以用于静态地图，还可以用于游戏中动态变化的地图。

• 在现代CPU上计算100个节点的所有路径只需几百微秒。
• 在现代CPU上计算1000个节点的所有路径需要不到50毫秒。
• 在现代CPU上计算10000个节点的所有路径需要不到几秒钟。

有关更多详细信息，请参阅基准测试。

目录

基本用法

小图

对于节点数少于128的小图，请使用Graph16、Graph32、Graph64或Graph128。

在GraphN中，如Graph16，N代表图可以包含的节点数。

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]);

大图

对于节点数超过128的图，请使用Graph，它可以包含任意数量的节点。

如果环境支持多线程，Graph将并行处理路径以加快计算速度。

在这个示例中，让我们创建一个100x100的网格图。

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;
    }
}

更新图

您不能直接更新图，但可以将图转换回构建器，更新节点数并添加/删除边，然后再次构建图。

我尚未测试图的调整大小功能，因此如果您发现任何错误，请提交问题。

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();

图类型

• Graph16、Graph32、Graph64、Graph128：使用原始数据类型进行位存储，效率非常高。

  • 在GraphN中，N代表图可以包含的节点数。
  • 这些类型用于小于128个节点的固定节点大小。

• Graph：支持任意节点大小，并针对并行处理进行了优化。

  • SeqGraph和ParaGraph的枚举。如果环境支持多线程，则使用ParaGraph；否则，使用SeqGraph。

• SeqGraph：根据目标架构使用Vec<u32>或Vec<u64>来存储位，通常比原始数据类型慢大约3倍。

• ParaGraph：使用Vec<AtomicU32>或Vec<AtomicU64>进行位存储，这比原始数据类型慢，但得益于并行处理，随着节点数的增加而变得更加高效。

对于小于128个节点的固定节点大小，请优先使用基于原始数据类型的图类型。

库公开了一个泛型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

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

cargo run --release -p maze

cargo run --release -p astar_maze

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