RePath

RePath是一个快速且高效的路径查找库。它利用A*算法，在OBJ导航网格上提供快速且精确的路径查找解决方案，这对于在实时环境中管理大量NPC至关重要。

RePath是为Respark开发的，Respark是一款即将推出的开放世界MMO射击游戏。Respark结合了激烈的战斗、战略游戏和广阔的动态世界。加入我们的社区Discord，以获取最新新闻和发展动态。

描述

RePath是为了解决MMO游戏服务器中高性能路径查找的需求而开发的。鉴于游戏世界的复杂性和规模，路径查找可能会成为一个瓶颈。RePath通过预计算、缓存和高级搜索算法的组合来优化此过程，确保即使在需求较高的场景下也能快速准确地查找路径。它还可以用于其他需要高效路径查找的应用，如机器人技术、模拟和人工智能。

为什么它这么快

RePath的速度来自其预计算、高效的搜索算法和智能缓存的组合。通过预计算路径并将它们存储在LRU缓存中，RePath可以快速返回常见的路径查找查询，而无需重新计算。

特性

• A*路径查找算法：高效且精确的路径查找。
• 预计算：使用Rayon并行快速预计算随机路径，并将它们存储在缓存中。
• LRU缓存：高效的内存使用和快速访问最近路径。
• 可扩展：处理大型游戏世界和大量NPC。
• 多线程：利用多个线程进行预计算和路径查找。

使用

将RePath添加到您的项目中

将RePath添加到您的Cargo.toml

[dependencies]
repath = "0.0.9"

请确保您在项目目录中有一个包含导航网格的OBJ文件。

然后在您的项目中使用它

use repath::{RePathfinder, settings::RePathSettings};

fn main() {
    // Create a new RePathSettings instance with custom settings
    let settings = RePathSettings {
        navmesh_filename: "navmesh_varied.obj".to_string(), // Path to the navmesh file in Wavefront OBJ format
        precompute_radius: 25.0, // Higher this value, the longer it takes to precompute paths but faster pathfinding for long distances
        total_precompute_pairs: 1000, // Higher this value, the longer it takes to precompute paths but faster pathfinding
        cache_capacity: 1000, // Higher this value, the more paths can be stored in cache but more memory usage
        use_precomputed_cache: true, // Set to false to disable precomputation of paths
    };

    // Create a new RePathfinder instance
    let pathfinder = RePathfinder::new(settings);

    // Define start and end coordinates for pathfinding
    let start_coords = (0.0, 0.0, 0.0);
    let end_coords = (10.0, 10.0, 10.0);

    // Find a path from start to end coordinates using single thread (good for short distances)
    if let Some(path) = pathfinder.find_path(start_coords, end_coords) {
        println!("Found path: {:?}", path);
    } else {
        println!("No path found.");
    }

    // Find a path from start to end coordinates using multiple threads (good for long distances)
    // This should not be used for short distances as it can be slower than single thread because of segmentation and multithreading overhead
    let segment_count = 2; // Splits the path into two segments and calculates them in parallel
    if let Some(path) = pathfinder.find_path_multithreaded(start_coords, end_coords, segment_count) {
        println!("Found path: {:?}", path);
    } else {
        println!("No path found.");
    }
}

基准 - 单线程路径查找

以下图表显示了RePath在路径查找场景中的性能。基准测试是在i7-9700K CPU和16GB DDR4 RAM上进行的，这些设置如下

• 导航网格大小：4000 x 4000米
• 导航网格顶点：40 401
• 导航网格面：80 000
• 预计算半径：3 000米
• 总预计算对：100 000
• 缓存容量：100 000
• 使用预计算缓存：true

距离与时间

距离与时间（距离小于50米）

结果可能差异很大，这取决于路径是否已经被缓存。简而言之，找到的路径越多，未来的路径搜索将越快。

预计算目前处于实验阶段，并且似乎好处并不大，因为在大型地图上，找到相同路径的可能性非常低。然而，对于小型地图或顶点和面较少的navmesh，这可能很有用。对于短距离，您可以得到亚毫秒级的路径搜索时间。

您可以使用find_path_multithreaded方法并行计算路径。这对于长距离很有用，但不建议用于短距离，因为将路径分割成段并在并行计算中会产生开销。

许可证

RePath遵循MIT许可证。有关详细信息，请参阅LICENSE文件。