要致富,先修路。
本节为人话版解读『逍遥行』的概念、组成、实现。
逍遥行由数据、寻路算法、行走三个大部分组成。
以北京坐公交一路换乘到上海为喻:
- 数据:公交站牌路线内容。
- 寻路算法:广撒网多捞鱼。
- 行走:乘车到达下一站。
一直换乘就可以到达目的地。
概念在脚本制作中相当重要,实现方式则是多种多样的。
建议先速览一遍『TINTIN++中文手册』,
以便于掌握常用命令的用法和实际操作。
数据的来源是多种多样的:
自行探索收集、自动探索收集、其他来源转化等。
以自行探索收集为例:
经过一段时间游戏,已经掌握不少城市间的路径,
使用时只需复制粘贴、或保存为别名执行即可。
在 TinTin 中,数据用表变量保存,便于操控。
#nop 出发节点:钵夫(bofu)=>目标节点:大轮谢客亭(xieketing);
#var Route_bf_xkt {{cn}{钵夫;大轮谢客亭}{long}{bofu;xieketing}{path}{nu;n;n;nd}};
#nop 出发节点:北京(beijing)=>目标节点:北京别墅(beijingbieshu);
#var Route_bj_bjbs {{cn}{北京;北京别墅}{long}{beijing;beijingbieshu}{path}{n;n;n;n;n;e;s;xy.home}};
在上表中,新节点只需按照格式即可方便添加。
数据表应当单独存放,以方便修订转化。
节点数据应当自动生成关系索引表。
索引数据对节点间的关系进行整理,节约搜寻时间。
寻路算法参考:「知乎专栏」
广度优先搜索
广度优先搜索以广度做为优先级进行搜索。
从起点开始,首先遍历起点周围邻近的点,然后再遍历已经遍历过的点邻近的点,逐步的向外扩散,直到找到终点。
这种算法就像洪水(Flood fill)一样向外扩张。
在执行算法的过程中,每个点需要记录达到该点的前一个点的位置(可以称之为父节点)。
这样做之后,一旦到达终点,便可以从终点开始,反过来顺着父节点的顺序找到起点,由此就构成了一条路径。
定义三个集合列表:出发节点 a、目标节点 z、连接关系 x。
定义三级循环:
1)循环 100 次深度并检查 x,超过 100 次深度或在 x 中找到 z 则结束循环。
定义 a 可以到达的所有节点 b1,并给 b1 建立一个缓存 b2,然后清空 b1。
2)在上一层循环中循环 b2,并定义下级节点集合 c。
3)在上一层循环中循环 c,假如 x 中没有找到 c,则使用拼接变量技巧在 x 中拼接 {{x}{c}{b}},第一次拼接时 x 为空,最终拼接结果是 {{c}{b2}{c}{b2}..}。
同时将节点 c 添加到第一级循环的 b1。
4)第三级和第二级循环结束后,如果 x 中存在 z,结束循环,否则继续循环新的 b2。
c 在 x 中是唯一的值,当 c 为 z 时,即可轻松追溯至 a。
5)第一级循环超过 100 次且无法在 x 中找到 z,则认定为无法找到路径。
其中深度判断 100 不是必须的,主要条件是:找到目的地和没有新的可用节点。
示例:
未完待续...