游戏知识实验课:依次选择出生点时的最近距离最大化——14乘11地图的五轮间距选择(练习13)
从候选位置中逐个选择出生点时,只让新点远离某一个旧点并不够。先看它离所有已选位置中最近的一个有多远,再选择这个最小距离最大的候选,可以明确表达分散布置的局部目标。
本篇用一组独立输入把规则展开为可重复核对的记录。先确认单位、编号及边界,再自行尝试推演,然后寻找与下面过程第一次不同的位置。所有结果只在这里写明的规则下成立,不能当作所有游戏的统一实现。
规则与输入
在二维整数地图中,两个固定位置先被占用。每轮给剩余候选计算到所有已占用点的距离平方,取最小值作为分数;选分数最高者,同分取原候选编号较小者,共选五轮。选中后立即加入已占用集合。
两固定点[[0, 0], [14, 11]] 十二候选按编号[[12, 4], [1, 2], [5, 10], [14, 2], [6, 4], [2, 6], [9, 8], [0, 4], [2, 7], [10, 5], [6, 10], [14, 3]]
逐步推演
第1轮剩余候选[编号,最近距离平方]为[[0, 53], [1, 5], [2, 82], [3, 81], [4, 52], [5, 40], [6, 34], [7, 16], [8, 53], [9, 52], [10, 65], [11, 64]],选中2号[5, 10],得分82;更新后的占用点[[0, 0], [14, 11], [5, 10]]。
第2轮剩余候选[编号,最近距离平方]为[[0, 53], [1, 5], [3, 81], [4, 37], [5, 25], [6, 20], [7, 16], [8, 18], [9, 50], [10, 1], [11, 64]],选中3号[14, 2],得分81;更新后的占用点[[0, 0], [14, 11], [5, 10], [14, 2]]。
第3轮剩余候选[编号,最近距离平方]为[[0, 8], [1, 5], [4, 37], [5, 25], [6, 20], [7, 16], [8, 18], [9, 25], [10, 1], [11, 1]],选中4号[6, 4],得分37;更新后的占用点[[0, 0], [14, 11], [5, 10], [14, 2], [6, 4]]。
第4轮剩余候选[编号,最近距离平方]为[[0, 8], [1, 5], [5, 20], [6, 20], [7, 16], [8, 18], [9, 17], [10, 1], [11, 1]],选中5号[2, 6],得分20;更新后的占用点[[0, 0], [14, 11], [5, 10], [14, 2], [6, 4], [2, 6]]。
第5轮剩余候选[编号,最近距离平方]为[[0, 8], [1, 5], [6, 20], [7, 8], [8, 1], [9, 17], [10, 1], [11, 1]],选中6号[9, 8],得分20;更新后的占用点[[0, 0], [14, 11], [5, 10], [14, 2], [6, 4], [2, 6], [9, 8]]。
五轮选中编号[2, 3, 4, 5, 6],每一轮都基于此前实际选择重新比较。
怎样独立检查
逐个枚举候选与当前占用点的配对距离,找出每个候选最不利的近邻,再比较这些最小值。核对选中点在当轮确实没有更高分的替代,但不要把逐轮局部最优误称为所有点组合的全局最优。
距离平方保持距离的大小次序,本例不需要开方。障碍物、视线、路径长度和队伍平衡都没有包含在这个几何模型中;实际关卡的出生安全性不能只靠这个分数判断。增加新点后,剩余候选必须重新评分。
练习时先保存原始输入及中间结果,再只改变一个条件观察差异。重点检查空状态、相同数值、恰好到达边界和最后一步。不要为了凑出相同的最终结果而忽略较早出现的偏差,过程和结论都应能由同一套规则解释。