MENU

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

August 19, 2016 • 程序

前言

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

网上有不少模拟飞行航线计算工具,国内有虚航运营网的全球航路查询及飞行计划辅助系统、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是航路用的字符串反查表,而nodesroutes是保存的顶点和航路的详细信息。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

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

简单分析,一行以SIDSTAR开头,则这一行描述了一个离场或进场程序。离场程序的情况下,最后一个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呀~

Tags: c/cpp, 算法
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 4 条评论
  1. Hi,很开心看到这个blog,现在也打算开发一个类似这样的pc软件或者website,要实现的功能就是输入起点和终点,规划出需要经过VOR NDB台,自动生成航线。请问有没相关的参考资料。Thanks a lot

    1. @chans这篇文章本身就是参考资料呀,描述了仅通过某导航数据生成航路的思路与部分实现。后续重写了第二版(https://github.com/Bokjan/BravoFinder/tree/v2/Library),风格应该比本文第一版要更好,整体思路、算法是一致的。

  2. dwhsmart dwhsmart

    HI
    我想把你这个小程序集成到我的小软件中去,但是我不是很懂C++,你是否可以将这个小程序编译成ATL形式的DLL发给我,谢谢。

    1. @dwhsmart抱歉,如果你有看过GitHub仓库会发现它是在*nix环境下开发的。目前我不使用微软的技术,也没有微软的环境。你可能需要自己对源码做一点修改才能应用到自己的程序上。