C++实现的航路计算工具——BravoFinder

前言

很早我就想做一个离线的航路计算程序。

网上有不少模拟飞行航线计算工具，国内有虚航运营网的全球航路查询及飞行计划辅助系统、AIRCN的AIRCN全球航路查询系统，国外有AsaLink的RouteFinder。这些都是大家真切用过的。

全球航路查询及飞行计划辅助系统是老牌了，好用，我接触FS时就是一直用着它来的。然而它的导航数据版本有些老旧，现在还是Cycle 1311。

AIRCN全球航路查询系统是近几年上线的系统，有着全球航路查询及飞行计划辅助系统的影子，且同时支持NAIP和AIRAC数据，用户界面也是体验最好的。AIRCN全球航路查询系统最新的数据版本为Cycle 1606，不能说过时，但也算不上新。

RouteFinder有收费版本，也开放了免费版本。更新得非常勤快，昨天才收到Navigraph发来的数据更新通知邮件，现在它就已经更新到Cycle 1609了。不支持NAIP是一个缺憾之外，也许就是外国网站访问比较慢吧。笑。

这次开工时，看到了GitHub仓库的日期，最后一次提交在2014年。我确实是早有想法的，我想编写一个离线的、用户提供数据的航路查询系统。这一次终于是下定决心，把主要功能完成了。GitHub在这里：Bokjan/BravoFinder。功能还在陆续完善中，我本身提供了一个简陋的CLI方式供大家使用。在编写时考虑到这个小工具可以嵌入其他的项目，有意封装了API，在Intefaces.hpp里。

本项目使用知识共享4.0-署名-非商业性使用国际公共许可证开源。

本文主要对技术方面的细节进行介绍。

数据的导入

概论

考虑到PMDG是使用非常广泛的插件机厂商，程序利用的就是PMDG的数据。

数据结构

我们将机场、各类导航台、航路点均看作一个顶点。以下是顶点的结构：

struct Node
{
    int id;
    char name[8];
    double lat, lon;
    Node(int id, double lat, double lon):
        id(id), lat(lat), lon(lon) { }
};

其中，id是整个有向图中顶点的编号，稍后会详细介绍分配的方法。

有向图中，还有重要的一个数据结构，就是边。边的结构定义如下：

struct Edge
{
    int to, way;
    double dist;
    Edge(int to, int way, double dist):
        to(to), way(way), dist(dist) { }
};

其中，to是有向边指向的顶点的编号，way是这条边所在的航路的编号。dist当然就是距离了。

防冲突算法

导航台的代码不长，比如VOR导航台是三个字母，那么算一下全排列，只有$26^{3}=17576$种；并且通常VOR与地名有关，因此部分VOR台的代码存在冲突。例如：LLC，一个在中国；而另一个，在南半球。

程序需要一个功能：根据顶点的名字反查顶点的编号。重名现象不能视而不见，因为它会直接导致运算结果的错误。因此，我自己实现了一个简易的散列表来解决。采用的字符串哈希算法是BKDRHash，得到哈希值后，对于潜在的哈希冲突要进行处理。维护一个合适大小的std::vector<HashNode>数组来处理冲突。HashNode结构的定义如下：

struct HashNode
{
    int id;
    double lat;
    HashNode(int id, double lat):
        id(id), lat(lat) { }
};

id就是对应的顶点编号，lat存的是这个编号顶点的纬度，当哈希冲突发生时以纬度作为判断的依据。

数据导入时需要维护的数组和容器

extern std::vector<HashNode> nodemap[];
extern std::map<string, int> routemap;
extern std::vector<Node> nodes;
extern std::vector<string> routes;
extern std::vector<Edge> g[];

上面截取了Finder.hpp中声明的变量。nodemap是顶点用的字符串反查表，routemap是航路用的字符串反查表，而nodes和routes是保存的顶点和航路的详细信息。g是整个世界的有向图邻接表。

机场信息

实现：void Internal::InitializeAirports(std::string file)

机场信息存在于NAVDATA/airports.dat文件中。在这个文件里，注释行以;开头；而机场数据以ICAO LATITUDE LONGITUDE的形式一行一个。机场信息的导入非常简单，把读取到的数据存好就行了。

航路信息

实现：void Internal::InitializeNavigationRoutes(std::string file)

航路信息存在于NAVDATA/wpNavRTE.txt文件中。读取航路，在图论中来说就是连边，要维护好g邻接表。这个文件里数据是这么组织的：ROUTE_NAME POINT_SEQUENCE POINT_NAME LATITUDE LONGITUDE。

我采用了读两遍的偷懒写法。第一遍将所有的顶点维护好，第二遍再连边。连边时，需要利用之前做好的反查表获取顶点的编号，然后把边连上。

进离场信息

实现：void Internal::InitializeDAFixes(char *file, char *ICAO)

各个机场的进离场信息是独立地存在于对应的文件中的，比如北京首都国际机场的进离场文件是SIDSTARS/ZBAA.txt。

为何要读进离场信息？经过上面两次处理之后，机场、航点和航路均已就绪，但是机场和航点并没有建立联系。读取进离场信息，目的是找到机场的进离场点，使得整个图连通。

简单分析，一行以SID或STAR开头，则这一行描述了一个离场或进场程序。离场程序的情况下，最后一个FIX后的导航点就是一个离场点；进场程序的情况下，第一个FIX后的导航点就是一个进场点。偷懒的写法，使用std::map维护进离场点，最后再统一把边连好。注意是有向边。

读取进离场信息时的坑点

这个问题由Hans发现。

PMDG数据中，SIDSTARS里所有的NDB台都会在后面加上NB。比如：北京/首都附近的车道峪无向信标台（CDY NDB）在ZBAA.txt中均表示为CDYNB。若直接使用该字符串来反查编号，必定得到错误的甚至是引起非法内存访问的编号。

研究表明，在航路中的NDB均为两字母或三字母，因此加上NB后字符串必定至少长度为4；而查询可知，以NB结尾的导航点只有一个三字母VOR。因此我们可以大胆判断：四（含）字母以上的，且以NB结尾的进离场点，一定是个NDB台。把NB去掉，就可以反查到正确的编号了。

算法

地球上两点间距离的计算

地球近似是一个球体，显然平面上的两点间距离计算公式就不正确了。事实上，根据经纬度计算距离不是十分容易的事情，涉及到大量的推导与三角函数计算。项目中使用的代码如下，计算过程就不再赘述了。

const double PI = 3.1415926535898;
const double EARTH_RADIUS = 6378.137;
inline double rad(double x)
{
    return x * PI / 180.0;
}
double GetDistance_KM(double lat1, double lon1, double lat2, double lon2)
{
    double radLat1 = rad(lat1);
    double radLat2 = rad(lat2);
    double a = radLat1 - radLat2;
    double b = rad(lon1) - rad(lon2);
    double s = 2 * asin(sqrt(pow(sin(a / 2), 2) +
        cos(radLat1) * cos(radLat2) * pow(sin(b / 2), 2)));
    //Get the km value
    s *= EARTH_RADIUS;
    return s;
}
double GetDistance_NM(double lat1, double lon1, double lat2, double lon2)
{
    //1 nautical mile = 1.852 kilometers
    return GetDistance_KM(lat1, lon1, lat2, lon2) / 1.852;
}

其中，PI是$\pi$的近似值；EARTH_RADIUS是地球半径的近似值，单位是千米。rad函数将输入的角度转换为弧度。

单源最短路算法

项目采用的是优先队列优化的迪杰斯特拉算法，由于使用了大量STL，性能一般，但是编码非常容易。迪杰斯特拉是图论中非常基本的内容了，这里不再多说，但是我要提一下如何把整条航路生成出来。

要找出计算得到的航路，我们在做迪杰斯特拉的同时维护一个pre数组记录每个顶点的前一个顶点编号，最后再从终点回溯就行了。

回溯函数的编写

回溯函数编写十分简单，从顶点出发，不停地向前跳直到终点为止。将经过的顶点全部存到一个std::vector里面，使用反向迭代器即可正确取出。以下代码是回溯函数的一个演示：

void Path(int dep, int arr)
{
    std::vector<int> path;
    int pos = arr;
    for( ; ;)
    {
        path.push_back(pos);
        if(pos == dep)
            break;
        pos = pre[pos];
    }
    std::vector<int>::reverse_iterator it;
    for(it = path.rbegin(); it != path.rend(); ++it)
        printf("%s ", nodes[*it].name);
}

结语

目前实现的内容就是这些，其实也非常简单，无非就是字符串的处理和基本图论算法的应用。编写这个程序的目的，一是为了方便大家，二是希望可以作为一个小工具嵌入到其他模拟飞行应用中。希望对大家有所帮助。有兴趣进一步改进这个小项目的，欢迎Fork！大家也不要吝啬你们的Star呀~

Catalog