寻路

unity/c++ mmo大型多人在线游戏开发系列教程，本节代码在此。

在添加怪物AI之前，需要先把一些基础给补上，寻路算是一个。

建模

寻路的基础是对场景进行建模，以表示可行走区域、区域连通性之类的概念。常见的方案有:

格子地图

对2D游戏来说，可以用一个矩形表示游戏场景，然后切分为固定大小的格子，每个格子记录自己的区域信息。优点是非常简单，缺点是格子数量一多，消耗会比较大。

路点

路点是人为编造好的一份线路图，就像地铁线路图一样，适用于路线固定的情况，例如赛车之类。优点是数据量通常非常少，缺点是需要人工维护，这也是通常数据量少的原因，毕竟人工维护不了复杂的东西。

寻路网格

寻路网格是一种仅针对寻路的建模，它用多边形网格来表示可行走区域，并且仅保留了这些区域。一个网格可以表示很大的一片区域，所以对比格子地图，在大场景中的消耗会低很多。缺点是生成寻路网格的算法、流程相对复杂，以致于后面想做定制化修改、或者仅仅只是查些寻路问题，都相对困难。

寻路算法

当有了场景的建模表示之后，就能在这些模型上实现寻路算法了。以上三种建模本质上都是一个图，所以寻路算法就是图的路径寻找，而经典的算法就是Dijkstra与A*算法，网上有一堆关于这两个算法的分析研究，这里就不再介绍了。实际应用中，可能还需要对这两种算法得出的路径进行路径平滑，使之更像是人会走的路径。

无论如何，我们这里选用了开源的recastnavigation，它有离线生成寻路网格的组件，也有提供配套的寻路的算法，下面记录一下这个库的使用流程。

Recast Navigation

导出场景

首先，离线网格生成，需要一份场景的网格表示，所以要先将场景的网格信息从unity中导出。这里参考了一下其他人之前写的导出插件，将代码复制到客户端工程中，即可实现导出。

离线生成寻路网格

把unity导出的场景文件扔到开源的recast网格生成器中，设置好参数（这里选择的是最简单的solo mesh），生成寻路网格文件。

服务端加载寻路文件

把寻路网格文件放到服务端的目录下，在space创建时，按照demo代码来加载该文件，在space销毁时释放寻路资源:

Space::Space(size_t w, size_t h) : _width(w), _height(h)
{
    // ...
    _nav_mesh = dtAllocNavMesh();
    _nav_mesh = loadAll("DemoScene.bin");
    assert(_nav_mesh);

    _nav_query = dtAllocNavMeshQuery();
    dtStatus status = _nav_query->init(_nav_mesh, 2048);
    if (dtStatusFailed(status)) {
        spdlog::error("nav query  init failed\n");
        assert(0);
    }

    _nav_filter.setIncludeFlags(0xFFFF);
    _nav_filter.setExcludeFlags(0);
}

路径更新

要进行寻路时，先通过recast的接口获取到一条可行走路径，然后让怪物定期更新到路径的下一个点，直到路径结束:

void NavigationComponent::move_to(const Vector3f& pos)
{
    MovementComponent* movement_comp = get_owner()->get_component<MovementComponent>();
    assert(movement_comp);

    SpaceComponent* space_comp = get_owner()->get_component<SpaceComponent>();
    assert(space_comp);

    reset();

    Vector3f start_pos = movement_comp->get_position();
    _path = space_comp->get_space()->find_path(start_pos, pos);

    if (_path.empty())
        return;

    if (_path.size() == 1) {
        movement_comp->look_at(_path[0]);
        movement_comp->set_position(_path[0].x, _path[0].y, _path[0].z);
        return;
    }

    _update_timer = G_Timer.add_timer(33, [this]() {
        this->update(0.033f);
    }, true);
}

文章一开始的gif是一个简单的寻路测试，用鼠标选择要到达的点，通知服务端进行寻路，红色的线即是服务端计算出的路径。

小结

至此，我们引入的寻路组件，可以满足简单的寻路需求。但其实寻路还能讲很多，例如:

1. 超远距离寻路
2. 大世界寻路
3. 跳点与传送
4. 动态阻挡
5. 空中寻路、水中寻路

每一个都可以深挖，后面有机会再展开聊一聊，下一节我们先继续把基础的物理补上。