基于高生存度的末世求生规划模型

An Eschatological Survival Programming Model Based on High Survivability

摘要: 本文研究了虚拟游戏背景下，确保生存度尽可能高，完成区域穿越任务尽可能快的末世求生问题。通过引入等效距离，构建了基于行走的消耗矩阵，以及基于火把制作的舒适度和饱食度消耗矩阵，从而使得终点生存条件为线性约束。分途经补给点个数最少和行走总路线长度最短两种情况，以生存度最大为目标，建立了两个线性整数规划模型，并对求得的全局最优解进行生存条件检验，验证通过。本模型准确，并通过引入标识矩阵设计隐枚举过滤条件，模型简单，算法效率高，问题中共计给出补给点588个，模型求解用时不多于8秒。

Abstract: This paper studies the problem of survival in the eschatology of virtual games, which ensures the survival as high as possible and completes the task of region crossing as quickly as possible. By introducing equivalent distance, the consumption matrix based on walking and the consumption matrix of comfort and satiety based on torch manufacturing are constructed, so that the terminal survival condition becomes a linear constraint. Two linear integer programming models are established for the minimum number of supply points and the shortest length of the total route. The survival condition test of the global optimal solution is carried out, and the verification is passed. The model is accurate, and the implicit enumeration filter conditions are designed by introducing the identity matrix. The model is simple and the algorithm efficiency is high. A total of 588 supply points are given, and it takes 8 seconds to find the global optimal solution.

1. 背景和问题介绍

某虚拟游戏以末世为背景，为了能够在末世中生存下去，幸存者必须要集结起来，为了达到聚集地，游戏人物需要完成区域穿越任务。在游戏中，游戏人物有两类必要的行为：

1) 寻找食物以维持自身生存能力；

2) 寻找火源来降低寒冷程度提高生存能力。

将这两种行为量化为两个指标：饱食度——刻画人物的饥饿状态；舒适度——刻画人物的寒冷程度。两项指标值越低，生存难度越大。

游戏地图场景中存在588个补给点，分为两类——篝火点和食物点。游戏人物在篝火点只能提高舒适度，补给量介于2~4个单位之间；在食物点只能提高饱食度，补给量介于2~5个单位之间，补给点类别、补给量和三维坐标数据已知。

游戏人物移动将会消耗舒适度和饱食度，且两者消耗相同：平地上移动，每走100米消耗5个单位；上坡行走，每走100米消耗6个单位；下坡行走，每走100米消耗4个单位。由于补给点之间的间隔很近，可以近似地认为游戏人物在两个补给点间行走的距离为该两点间的直线距离。

游戏人物会在篝火点制作火把，制作火把将降低人物的饱食度0.5个单位，但是可以确保后续20米行走时不消耗舒适度。

设游戏人物从1号篝火点出发，穿越地图区域聚集到588号目标篝火点，完成穿越之旅，在行进过程中游戏人物要确保生存状态：

1) 若游戏人物到达补给点前，饱食度和舒适度均低于−5，则认为人物死亡。

2) 游戏人物抵达目标点时，饱食度和舒适度均不得小于−3，否则认为穿越任务失败。

假设游戏人物在1号篝火点准备出发时，舒适度和饱食度均为10。如何确定行动路线，使得游戏人物在抵达目标篝火点时饱食度和舒适度尽可能高的前提下尽快完成穿越任务。

该问题研究了游戏场景中的路径规划问题，可抽象为网络模型下移动对象有约束的路径规划问题，不同于约束最短路问题，路径长度尽可能短或路径途经节点个数尽可能少是约束条件。对于这类问题常用的路径搜索算法有A^*算法 [1] [2] [3]，双A^*算法 [4] 和IDA^*算法 [5]，A^*算法是一种基于广度优先搜索的启发式搜索算法，搜算效率高，但受到搜索空间制约，搜索空间的增大会严重影响搜索效率。IDA^*算法是A^*算法的迭代延伸算法，通过适当构建节点扩展方式来适应特定的顺序，防止回溯，但以牺牲搜索速度为代价，速度慢于A^*算法。本文通过制定删选策略，压缩了搜索空间规模，同时将生存条件约束线性化，对路径搜索中出现的回溯、分叉等情况进行约束，最终构造0~1线性整数规划问题，可求全局最优解。

2. 补给点删选

由问题背景可知，游戏人物的饱食度和舒适度是相互独立的，互相之间不存在影响关系，行进过程对两者的消耗是相同的，但篝火点只能补给舒适度，食物点只能补给饱食度，两者可以单独计算。为确保游戏人物抵达目标点的同时保持尽可能高的饱食度和舒适度，同时尽可能快的完成穿越人物，游戏人物路线选择会采取如下策略：

1) 尽可能沿着从起点到终点的直线方向走，虽然同样长度的路段，上坡、平地、下坡的消耗不同，但是走的越多消耗越大，尽量少绕路。

2) 尽可能多地选择补给量大的点进行补给。

3) 尽可能减少补给的次数或选择总长度短的路径。

将补给点数据可视化，在xoy平面绘制补给点位置，其中红色五角星表示篝火点，蓝色五角星表示食物点，带有圈的表示补充能量最大的篝火点或食物点。红色三角形表示起点，黑色三角形表示终点。补给点的投影分布如图1所示。从图像可以看出，在连接起点到终点的直线附近，均有补充量最大的篝火点和食物点。根据上述补给策略，补给点应当在该直线附近选择。

Figure 1. Projection distribution of food points and bonfire points on xoy plane

图1. 食物点和篝火点在xoy面的投影分布

设第i个补给点坐标为 $\left(x_i,y_i,z_i\right)$，在xoy面上的投影坐标为 $\left(x_i,y_i\right)$， $i=1,\cdots ,588$。起点投影坐标 $\left(0,500\right)$，终点投影坐标 $\left(1000,555.67\right)$，连接起点和终点的投影直线方程为

$y=0.05567x+500.$

为刻画第i个补给点与投影直线的位置关系，计算

$L_i=\left|y_i-0.05567x_i-500\right|,$

给定范围阈值l，当满足 $L_i\le l$ 时，第i个补给点为备选补给点。最终从588个补给点中确定篝火点和食物点的个数为n。

3. 高生存条件模型的建立

以删选出来的n个补给点为节点，构建网络模型，要解决的问题即在该网络中寻找从起点到终点途经节点个数最少，能够满足游戏人物满足生存条件的路。

引入补给点类别标识向量 $F=\left(f_1,f_2,\cdots ,f_n\right)$ 和补给量向量 $T=\left(t_1,t_2,\cdots ,t_n\right)$，其中 $t_i$ 表示第i个补给点的补给量，

$f_i=\{\begin{array}{l}0,第i个补给点为篝火点,\\ 1,第i个补给点为食物点.\end{array}$

计算任意两个补给点之间的距离矩阵 $D={\left(d_{ij}\right)}_{n\times n}$，其中

$d_{ij}=\{\begin{array}{l}\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2+{\left(z_i-z_j\right)}^2},i\ne j,\\ 0,i=j.\end{array}$

由于上坡、下坡、和平地行走100米的消耗分别为6，5，4，可以将实际距离折算为平地距离，得到任意两个补给点间的等效距离矩阵 $H={\left(h_{ij}\right)}_{n\times n}$，其中

$h_{ij}=\{\begin{array}{l}1.2d_{ij},z_j>z_i,\\ d_{ij},z_j>z_i,\\ 0.8d_{ij},z_j<z_i.\end{array}$

若构造火把，可以有20米不消耗舒适度，但上坡、平地和下坡消耗有区别，可以构造20米等效距离矩阵 $Q={\left(q_{ij}\right)}_{n\times n}$，其中

$q_{ij}=\{\begin{array}{l}1.2\times 20=24,z_j>z_i,\\ 20,z_j>z_i,\\ 0.8\times 20=16,z_j<z_i.\end{array}$

走平地100米的消耗为5，得到基础消耗矩阵 $W={\left(w_{ij}\right)}_{n\times n}$，有

$W=0.05H.$

同时可求20米消耗矩阵 $V={\left(v_{ij}\right)}_{n\times n}$，有

$V=0.05Q.$

构造识别矩阵 $R={\left(r_{ij}\right)}_{n\times n}$，其中

$r_{ij}=\{\begin{array}{l}1,f_i=0,i\ne j,\\ 0,f_i=0,i=j.\end{array}$

$r_{ij}=1$ 表明从第i个补给点到第j个补给点的时候，是从篝火点出发。于是舒适度的消耗矩阵为 $W_{sh}={\left(w_{ij}^{sh}\right)}_{n\times n}$，有

$w_{ij}^{sh}=w_{ij}-v_{ij}{r}_{ij},$

饱食度的消耗矩阵为 $W_{bs}={\left(w_{ij}^{bs}\right)}_{n\times n}$，有

$w_{ij}^{bs}=w_{ij}+0.5r_{ij}.$

构造任意两个节点间的补给矩阵 $E={\left(e_{ij}\right)}_{n\times n}$，其中

$e_{ij}=\{\begin{array}{l}{t}_i,i\ne j,\\ 0,i=j.\end{array}$

除了对角线元素外，E的每行元素均相同，第i行元素为第i个补给点的补给量。

游戏人物在第i个补给点获得补给后，继续行进到第j个补给点，这个过程中如果消耗大于补给，对游戏人物生命存在威胁，当游戏人物的舒适度和饱食度同时低于−5时，游戏人物死亡。如果在行进过程中，选择补充量低于消耗量的边会增加游戏人物生命的威胁程度，构造标识矩阵 $C={\left(c_{ij}\right)}_{n\times n}$，其中

$c_{ij}=\{\begin{array}{l}1,e_{ij}-w_{ij}^{sh}>\alpha ,e_{ij}-w_{ij}^{bs}>\alpha ,i\ne j,\\ 0,其他.\end{array}$

若游戏人物到达补给点时，舒适度和饱食度同时达到−5及以下，则游戏人物死亡，阈值 $\alpha$ 取值越大，游戏人物生存的可能性越大，最小取为−5。标识为0的边，补给量与消耗量的差距超过5，为了确保游戏人物生存，求解路径时，这样的边将不会选择。

引入0~1变量

$u_{ij}=\{\begin{array}{l}1,选择从第i个补给点走到第j个补给点,\\ 0,否则.\end{array}$

其中 $i,j=1,\cdots ,n$。

第1个节点为起点，第n个节点为终点，要求在满足生存条件的情况下，游戏人物到达终点时的舒适度和饱食度尽可能大，故目标函数为

$\max 20+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(1-f_i\right)e_{ij}{u}_{ij}}}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_{ij}^{sh}{u}_{ij}}}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{f}_i{e}_{ij}{u}_{ij}}}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_{ij}^{bs}{u}_{ij}}}.$

约束条件构造如下：

1) 为了确保各自的生存极限条件，只能在标识矩阵为1的元素对应的边中选择，于是有约束条件

$u_{ij}\le c_{ij},i,j=1,\cdots ,n.$

2) 终点生存条件

游戏人物在行进过程中，对舒适度和饱食度的消耗是相同的，到达终点时，游戏人物的舒适度和饱食度均不得低于−3，在起点游戏人物舒适度与饱食度均为10，故在从起点到终点的过程中，舒适度和饱食度的补充总量应满足约束

舒适度： $10+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(1-f_i\right)e_{ij}{u}_{ij}}}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_{ij}^{sh}{u}_{ij}}}\ge -3,$

饱食度： $10+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{f}_i{e}_{ij}{u}_{ij}}}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_{ij}^{bs}{u}_{ij}}}\ge -3.$

3) 路径约束条件

对于路的起点和终点，约束如下 [6]：

$\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{1j}=1,}\\ {\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{j1}}=0,\\ {\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{jn}=1}.\end{array}$

由于要求途经补给点数量最少的路，不会出现绕圈的情况，即补给点不会到达2次，对于路径的中间补给点，约束如下：

$\{\begin{array}{l}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ji}},i=2,\cdots ,n-1,i\ne j,\\ {\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}}\le 1,i=2,\cdots ,n-1,\\ {\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ji}}\le 1,i=2,\cdots ,n-1.\end{array}$

为了避免出现图2所示的情况，增加约束条件

$u_{ij}+u_{ji}\le 1,i,j=1,\cdots ,n,i\ne j.$

4) 途经补给点个数约束或行走总路线约束

① 若考虑途经补给点个数最少，可构造约束条件

${\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}}}\le b,$

其中b为补给点个数限制系数。

② 若考虑线路总长度最短，可构造约束条件

${\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{u}_{ij}}{d}_{ij}}\le \beta L,$

其中起点到终点的空间直线距离为L = 1003.2 m， $\beta$ 为距离估算系数。

5) 由于制作火把相当于降低了舒适度消耗而提升了饱食度消耗，考虑到终点舒适度和饱食度要尽可能均衡，可构造约束条件

$\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(1-f_i\right)e_{ij}{u}_{ij}}}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_{ij}^{sh}{u}_{ij}}}\right)-\left({\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{f}_i{e}_{ij}{u}_{ij}}}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_{ij}^{bs}{u}_{ij}}}\right)\le 2.$

Figure 2. Error path sketch map

图2. 错误路径示意图

根据条件(3)的不同，可以得到两个目标函数相同的线性整数规划模型

4. 模型求解、验证及结论

起点到终点的空间直线距离为L = 1003.2 m，若按照最低下坡消耗，估算其总消耗为40.128，若按照最大上坡消耗，估算其总消耗为60.192，篝火点的最大补给为4，食物点的最大补给为5，游戏人物初始舒适度和饱食度均为10，为了确保到终点舒适度和饱食度均不小于−3，均按照最大补给量进行补给，估算需要经过的篝火点个数为7~12个，食物点个数为6~10个，途经补给点的个数在13到22个，故参数b的取值范围在15到24。

1) 线性整数规划模型(I)

当阈值 $\alpha =-4$，b的最小取值为18时，可求得全局最优解，除了起点和终点外，途经补给点16个，其中食物点9个，篝火点7个，行走路径长度1071.4米，以 $l=200$ 米作为删选条件，选择270个补给点进行计算，用时4.7秒，其路径为

$\begin{array}{l}1\to 26\to 122\to 192\to 201\to 233\to 255\to 271\to 297\to 308\\ \to 339\to 403\to 412\to 435\to 453\to 519\to 538\to 588.\end{array}$

当b小于18时，无法找到可行路径。其路线图见图3所示，线路图在xoy面投影见图4。

可以计算游戏人物到达每个补给点时的舒适度和饱食度，见表1，可见游戏人物沿着该路径行走，抵达任何一个补给点时，舒适度和饱食度均为同时小于−5，在抵达终点时舒适度和饱食度均同时大于−3，满足生存条件。目标函数最优值为−5.8460，终点处舒适度最大值为−2.873，饱食度最大值为−2.973。

Figure 3. The path with the highest terminal survival and the least number of supply points

图3. 终点生存度最高且途经补给点个数最少的路径

Figure 4. Path projection with the highest terminal survival and the least number of supply points

图4. 终点生存度最高且途经补给点个数最少的路径投影

Table 1. Comfort and satiety of game characters at each supply point

表1. 游戏人物到达每个补给点时的舒适度和饱食度

当 $\alpha \le -3.5$ 时，最优解不发生变化，但随着 $\alpha$ 取值减小运算时间会增长。参数 $\alpha >3.5$ 时，无法找到满足生存条件的路径，说明若途经补给点个数少于16，则无法满足生存条件。

2) 线性整数规划模型(II)

当阈值 $\alpha =-4$， $\beta$ 的最小取值为1.05时，可求得全局最优解，行走路径长度1052.6米，除了起点和终点外，途经补给点19个，其中食物点12个，篝火点7个，以 $l=200$ 米作为删选条件，选择270个补给点进行计算，用时7.2秒，其路径为

$\begin{array}{l}1\to 26\to 122\to 192\to 233\to 297\to 308\to 327\to 346\to 375\\ \to 403\to 412\to 435\to 480\to 502\to 519\to 538\to 570\to 588.\end{array}$

当 $\beta$ 小于1.05时，无法找到可行路径。其路线图见图5所示，线路图在xoy面投影见图6。

可以计算游戏人物到达每个补给点时的舒适度和饱食度，见表2，可见游戏人物沿着该路径行走，抵达任何一个补给点时，舒适度和饱食度均为同时小于−5，在抵达终点时舒适度和饱食度均同时大于−3，满足生存条件。目标函数最优值为−3.3952，终点处舒适度最大值为−2.0976，饱食度最大值为−1.0976。

Table 2. Comfort and satiety of game characters at each supply point

表2. 游戏人物到达每个补给点时的舒适度和饱食度

当 $\alpha \le -3.5$ 时，最优解不发生变化，但随着 $\alpha$ 取值减小运算时间会增长。参数 $\alpha >3.5$ 时，无法找到满足生存条件的路径，说明若总长度最短的路线需途经19个补给点，总路线长度再短，无法满足生存条件。综上得到两种穿越路径方案见表3。

Table 3. Crossing route scheme

表3. 穿越路径方案

5. 模型评价和扩展

本文将行走在坡面上的距离等效为平面距离，从而构建了基础的行走消耗矩阵，同时基于距离等效分别构建了基于火把制作的舒适度和饱食度消耗矩阵，从而得到独立的舒适度和饱食度总消耗矩阵，使得终点生存条件可线性化。在考虑途经补给点的生存条件时，将舒适度与饱食度至少应有一个大于−5的条件进行放松，转化为标识矩阵，同时也相当于设置了0~1整数规划问题求解隐枚举的过滤条件，极大提高了算法的运行效率。该模型简洁易求解，稳定性高，并可以通过模型参数调整过滤隐枚举条件的范围，

Figure 5. The path with the highest terminal survival and the shortest total route length

图5. 终点生存度最高且路线总长度最短的路径

Figure 6. Path projection with the highest terminal survival and the shortest total route length

图6. 终点生存度最高且路线总长度最短的路径投影

极大提高了算法效率。分别以途经补给点个数最少或行走总路线长度最短两种不同条件约束，基于终点生存度最大且均衡建立了两个线性整数规划问题，可以求得全局最优解。等效矩阵与过滤条件的构造方法可在类似规划问题中推广，可作为飞行器位置矫正问题中的基础模型，并针对此问题做进一步研究。