坐标系选取
地图是一个平面六边点阵。(学过化学竞赛的同学应该对此比较熟悉) 最小单位(晶胞/元胞)是一个点与和其联通的六个点的路径的一半。 这么规定后,我们仅通过对最小单位进行平移操作就可以得到足够大(或无限大)的平面。
在六边形网格上的两点最短距离公式及其推导
首先,距离公式应满足下列条件:
1. 始终存在最短路径
2. 点的联通情况
3. 距离公式的量纲应该是一次的,且 x, y 应齐次
我们现在觉得对于行的奇偶进行分类讨论比较繁琐
其实,它是一个仿三维距离公式的退化形式。
此处,我们不能只使用 x, y 坐标,因为每隔一行移动半个正交单位基。
可以想象,每一个基底向量与六边形的边垂直。
我们的解决方案是添加第三个基底 z 并使用三维斜交系来描述距离。
(对高中地理记忆残存的同学应该可以认出这和比率三角和六角图的原理是一致的,恰恰因为地理中的三/六角图所要表示的数据类型就是下图的形式)
综上所述,有距离公式:
(有趣的是,这种定义下的从一点出发的等距点集全都在一个正六边形的边上,二维欧几里德空间有且只有一个圆) (我能说这是曼哈顿距离的拓展吗?) (薛定谔的猫会走出切比雪夫距离吗?)
小猫的策略
非常遗憾,这是一只贪心猫。 经过观察,我们发现:小猫总是会从当前点的联通邻居中选择最短路,递归执行,撞墙前或路线树根(这里不是指没有父亲的树根,而是指 root 节点所有只有一个子节点的连续的子节点们)被墙切割前不会反悔(即退回上一格) 同时,当有多条最短路径时,小猫会选择距边缘相同距离下路线数最多的邻居。
在此前提下,如果仍有重复路线,反常的是,小猫 !不会! 选择路径点下标排列中字典序最小的,而是会遵照正左,左上,右上,右,右下,左下,这一顺序。
显而易见的,如果无路可走,小猫会躺平并投降,此时游戏结束。
小猫的反制策略
我们小猫很爱学习,它学会了A*搜索。
A搜索算法(A search algorithm)是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或网络游戏的BOT的移动计算上。 该算法综合了最良优先搜索和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评估函数)。
猫可以用Python中的pygame库(这里的地图数组压位降维了)
def get_pass(self, num):
ways = []
gi = [1, -1, 11, -11]
for i in gi:
if crc.is_crc_aly(crcs[num + i]):
ways.append(crcs[num+i])
if self.pos[1] % 2 == 0:
if crc.is_crc_aly(crcs[num+10]):
ways.append(crcs[num+10])
if crc.is_crc_aly(crcs[num-12]):
ways.append(crcs[num-12])
else:
if crc.is_crc_aly(crcs[num+12]):
ways.append(crcs[num+12])
if crc.is_crc_aly(crcs[num-10]):
ways.append(crcs[num-10])
return ways
人类玩家是否一步也不能下错?
小猫主要面对着一个困境:被人类下套。 即人类构建出一面有洞的墙,遗憾的是,由于小猫的寻路算法的第一排序项是距离,小猫总是会尝试钻洞,而人类玩家只需在其过洞前最后一步将洞封住就好。
考虑人在最后一步下错,肯定完蛋。
人在建墙犯错,此时要考虑猫的决策状态,如果猫经历了方向放弃,即上文的反悔,此时可以下错,其他情况下,基于距离公式可以说明,是不能犯错的。因为猫可以在向下(上)一行行动时,选择两个不同的横坐标,可以理解为不损失步数又进行左右平移。
是否存在必胜策略?
这个结论比较有名,
结论:在平面无限大的情况下,人类玩家一定存在必胜策略。
证明后补。