【开源】离线航路计算工具BravoFinder
本帖最后由 2425 于 2016-12-30 13:51 编辑网上有不少模拟飞行航线计算工具，国内有虚航运营网的全球航路查询及飞行计划辅助系统、AIRCN的AIRCN全球航路查询系统，国外有AsaLink的RouteFinder。这些都是大家真切用过的。
[*]全球航路查询及飞行计划辅助系统是老牌了，好用，我接触FS时就是一直用着它来的。然而它的导航数据版本有些老旧，现在还是Cycle 1311。
[*]AIRCN全球航路查询系统是近几年上线的系统，有着全球航路查询及飞行计划辅助系统的影子，且同时支持NAIP和AIRAC数据，用户界面也是体验最好的。AIRCN全球航路查询系统最新的数据版本为Cycle 1606，不能说过时，但也算不上新。
[*]RouteFinder有收费版本，也开放了免费版本。更新得非常勤快，昨天才收到Navigraph发来的数据更新通知邮件，现在它就已经更新到Cycle 1609了。不支持NAIP是一个缺憾之外，也许就是外国网站访问比较慢吧。笑。
这几天花了一点时间做了一个航路查询小工具，CLI前端比较简陋，各位看官莫笑。
上面提供了两份二进制文件，感谢 @9963 帮忙在Windows下编译。一份是中文的、一份是英文的，请根据需要下载。
使用说明：
[*]下载、解压。
[*]本工具使用PMDG导航数据。编辑navdata.txt文件，将你的PMDG的导航数据路径写入，例如：E:\Prepar3D v3\PMDG\。注意最后的反斜杠不能少。运行程序时会检测这里的路径配置是否正确。
[*]双击exe文件运行或从命令行运行。
由于程序使用的是你自己正在用的导航数据，所以完全不必担心计算出来的航路无法输入等问题。目前功能比较简陋，只能输出航路和沿途的航点。大家如果有什么其他的需求也欢迎提出来，后续可以继续完善。如果大家有兴趣，可以一同参与改进！
欢迎反馈Bug和提供建议。
感谢 @9963 在开发过程中给予的Debug帮助！
本项目使用知识共享4.0-署名-非商业性使用国际公共许可证开源。
GitHub地址在这里。
http://static2.cdn.sinofsx.com/image/hrline/1.gif
BravoFinder考虑到可以作为一个附带工具以动态链接库的形式整合进其他项目，在Interfaces.hpp中提供了API，目前不够完善。
对这个小工具有兴趣进一步了解实现细节的，可以来看看我写的一些分析。
友情支持，别换马甲呀（逃 已测试，东西不错
嗯，感谢分享~ zsyfairytale 发表于 2016-8-20 15:13
请问一下是怎么计算的呢？是算最近的还是输入最少的？
有没有航路规则，比如说，在习俗上的习惯，某些航路 ...
你提到的这个问题非常关键，也非常复杂。感谢你的提出。
先做一下回答：目前是以距离最短为计算的依据。
在debug的时候我和9963也有讨论这些问题，包括进离场、单向航路等。结论来说，通用的算法肯定无法解决人为规定的东西。现在BravoFinder只写了两三天六七百行代码，做了个基础出来，我确实没有办法添加这些详细的规则。
虹桥机场，SASAN这个点既有离场也有进场程序，但是现实中这个点只用作进场不用做离场，那你这个航路计算会不会因为数据有SASAN离场程序所以就给出了SASAN作为航路第一个点？
如果使用SASAN离场能够算得最近的道路，那么会使用SASAN离场。
测试时，得出的航路与AsaLink RouteFinder免费版比较基本上都是一致的。可以大致推断算法差不多。因为存在机器计算导致的不规范性，因此所有的工具都会有“不适用于真实情况”这类声明。
总之还是非常感谢你的回复，如果有什么好的解决方法，欢迎来讨论。 输完ICAO就停止工作这个好尴尬…… 本帖最后由 2425 于 2016-8-20 18:36 编辑
1755407999 发表于 2016-8-20 16:54
输完ICAO就停止工作这个好尴尬……
按道理来说是做了检查的。
请检查一下：
1. ICAO需要是半角大写；
2. PMDG目录的SIDSTARS目录里是否有该机场对应的进离场数据。
---------
2016年08月20日18:35:57补充：
另外能否请您贴出一下您的导航数据所在的路径，这个可能也与您所遇到的问题有关。
鄙人也想请教君您一个问题，就是这个航路计算插件是用什么样的一个系统，包括AIRCN的航路查询系统。它是不是也是基于这样某个开源系统架构来的。 飞行器2代 发表于 2016-8-20 18:03
鄙人也想请教君您一个问题，就是这个航路计算插件是用什么样的一个系统，包括AIRCN的航路查询系统。它是不 ...
你好，感谢你的回复！
请问“什么样的一个系统”具体指什么呢？我不是特别明白它指代的意思。
BravoFinder本身实现的算法是比较简单的，没有很大的实现难度。AIRCN的航路查询系统应该是9318他们自己实现的，算法生成+人工调整，具体的我也不清楚，只是一个猜测。
BravoFinder的具体实现和注释在上面GitHub链接和我的分析里都有提到，有兴趣的话可以看一看。 本帖最后由 2425 于 2016-8-20 19:18 编辑
飞行器2代 发表于 2016-8-20 18:03
鄙人也想请教君您一个问题，就是这个航路计算插件是用什么样的一个系统，包括AIRCN的航路查询系统。它是不 ...
算法方面的解释：
正如主楼里面我提到的技术实现分析所说，目前航路计算使用的是优先队列优化的迪杰斯特拉算法。这是图论中非常基础的一个单源最短路算法，实现起来也比较简单所以在分析中没有详细解释。
不知你程序设计水平如何，但我还是给出一段代码。下面给出的是根据《挑战程序设计竞赛》（秋叶拓哉 ，岩田阳一，北川宜稔）中Dijkstra相关示例修改而来的说明代码：
#include <queue>
#include <vector>
#include <utility>
struct edge{
int to;
int cost;
};
typedef std::pair<int, int> P;//first 最短距离, second 顶点编号
int v;
std::vector<edge> g;
int d;
void Dijkstra(int s)
{
std::priority_queue<P, std::vector<P>, std::greater<P> > que;
for(int i = 0; i != v; ++i)
d = INF;
d = 0;
que.push(P(0, s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(d < p.first)
continue;
for(unsigned int i = 0; i != g.size(); ++i){
edge e = g;
if(d > d + e.cost){
d = d + e.cost;
que.push(P(d, e.to));
}
}
}
}
就航路计算来说：
我们将机场、航路上的点均作为图中的顶点看待，由导航数据可以建立一个有向图。
数组d中存放的是计算过程中由源点到达各个顶点的距离，首先将它们都初始化为无穷大，并将源点放入优先队列中。
不断地从优先队列中取出顶点-最短距离对并判断当前是否存在更优解，若不存在，遍历该顶点的邻接表中所有顶点，存在更优解情况时进行更新并将其加入优先队列。优先队列优化的迪杰斯特拉算法复杂度为O(E logV)。
对于寻找航路的情况，在每次更新更优解时，维护一个pre数组，更新到达该顶点的前一个顶点。Dijkstra运行完后，从终点出发不断地根据pre数组存储的前一个顶点编号回溯一直到达起点，将得到的顶点全部反向就得到了正向航路。
具体的实现，都在Finder.cpp里，可以到GitHub上查看。
我的输入完ICAO就出错了~~ fxlt1601 发表于 2016-8-21 11:58
我的输入完ICAO就出错了~~
请检查一下，PMDG\SIDSTARS这个目录里面有没有对应机场的进离场数据呢？
还有，ICAO代码需要是半角的大写。
方便的话麻烦贴一下你的导航数据所在的路径，也便于我分析。谢谢。 fxlt1601 发表于 2016-8-21 11:58
我的输入完ICAO就出错了~~
ZBAA-ZGGG，ZGGG-ZBAA在编写的时候都是测试过的，没有出现问题。
您提到的出错是哪种呢？
1. 如果是操作系统提示的“已停止工作”这类，是程序编写的问题，您是使用的自己修改过的导航数据吗？如果是可否提供一下供我调试？
2. 如果是程序提示的“初始化失败”这类，则是由于无法读入数据引起的。看您提供的路径，考虑到可能是权限问题，请尝试使用管理员身份运行。 fxlt1601 发表于 2016-8-21 11:58
我的输入完ICAO就出错了~~
请发到i@bokjan.com
只发修改过的地方就好啦 本帖最后由 2425 于 2016-8-31 00:29 编辑
fxlt1601 发表于 2016-8-21 11:58
我的输入完ICAO就出错了~~
以下内容已通过邮件形式回复给你。
----------------
你好，
我已使用你所发送的导航数据进行调试，目前问题已经解决。
1. 我的开发测试环境是OS X El Capitan，大小写敏感。Windows下理应无此问题，但仍然说明一下。若下述方法仍未奏效，请尝试将两个文件夹的名称改为全大写，NAVDATA下的wpnavrte.txt改为wpNavRTE.txt。
2. 导致你运行程序崩溃的原因是程序没有正常计算出航路，因此终点（到达机场）的前驱节点为0，输出结果时造成无限回溯，std::vector容器不断变大导致内存占用过高被操作系统杀死。
3. 无法计算航路是因为读入机场数据时经纬度数据出现错误导致进离场点无法与机场建立联系，造成有向图不连通。
4. 解决方法：用记事本等文本编辑器打开NAVDATA/airports.dat，删除该文件头部所有以“//”（两个斜杠）开头的内容或在以“//”开头的每一行最前面加上一个半角分号“;”。
5. 造成错误的代码已经修正，但没有发布相应的升级程序。
感谢你的反馈，也对你造成的不便表示抱歉。
2425 发表于 2016-8-31 00:27
以下内容已通过邮件形式回复给你。
----------------
感谢你的修改，不过我按上述方法测试却出现同样错误。我试验了重新安装一个标准的AIRAC数据是可以使用的，我将所有文件的大小写安装标准格式修改了也不奏效，可能是我那个版本的数据还是有某个问题。 fxlt1601 发表于 2016-8-31 22:13
感谢你的修改，不过我按上述方法测试却出现同样错误。我试验了重新安装一个标准的AIRAC数据是可以使用的 ...
数据内容上并没有什么问题，如果有问题飞机也会读不了嘛。但是你的数据，文件组织、注释方面确实和AIRAC的数据存在一定的差异，所以还是造成了一些问题。总之麻烦你啦~ 谢谢分享 航路查询的确是个好东东 数据新 解决好多问题 感谢 HI 我想把你这个小程序集成到我的小软件中去，但是我不是很懂C++，你是否可以将这个小程序编译成ATL形式的DLL发给我，谢谢。邮箱：dwhsmart@163.com 我在重新编译您的代码时出现如下错误
dwhsmart 发表于 2016-12-19 16:34
HI 我想把你这个小程序集成到我的小软件中去，但是我不是很懂C++，你是否可以将这个小程序编译成ATL形式的D ...
抱歉，如果你有看过GitHub仓库会发现它是在*nix环境下开发的。目前我不使用微软的技术，也没有微软的环境。你可能需要自己对源码做一点修改才能应用到自己的程序上。 dwhsmart 发表于 2016-12-19 17:33
我在重新编译您的代码时出现如下错误
本主题帖中提供的二进制是我委托他人使用Visual Studio的工具链编译的，生成没有产生任何问题，本代码与ISO C++98（ISO/IEC 14882:1998）或更高版本不存在兼容性问题。
可能是你的工程配置方面有一些问题，由于我并不熟悉Windows下的Visual Studio环境，在这方面不能帮到你。 很感谢。。很细心。。。
页:
[1]