战场模拟器
4.86/5 (39投票s)
KOEI风格的老派战争游戏和战场模拟器，包含步兵、炮兵和骑兵单位。
引言
这个应用程序是一个战场模拟器游戏，包含三种类型的单位：步兵、骑兵和炮兵。地图由一个“六边形网格”组成，包含多种不同的地形类型，就像许多回合制电子游戏中看到的那样。电脑玩家的人工智能对玩家来说很有挑战性，并且通过常规使用几种变体的广度优先搜索算法以及一个深度优先搜索移动序列求解算法，可能会为程序员提供见解，这些算法将在下面进行解释。
作为一个类和DLL，战场项目可用于构建一个更大的战争游戏，拥有自己的经济和角色阵容，以丰富游戏玩法。
背景
光荣公司可能没有发明电脑游戏，但他们却为PC和主机带来了有史以来最伟大的回合制战争游戏。我玩过很多：《信长的野望》、《三国志》、《中国古代的强盗之王》、《成吉思汗》、《皇帝》、《自由或死亡》，以及……我可以再举出更多，但我想你已经明白了。这些游戏都非常相似，但它们又各自将过去的不同部分带入生活，让你重演，并且，通常情况下，改变历史的既定进程。
我在这里做的事情，是我一直想做很久的事情，就是写一个类似光荣的战争游戏，但我上次尝试这个，大约五年前，从一开始就注定失败。我花了一个月的时间构建了除了战斗画面之外的所有东西，包括角色、经济和在意大利半岛上旅行的商人，在一个我称之为Borgia的项目中，该项目本应基于文艺复兴时期的意大利，但当我进行到战斗画面，也就是行动的核心时，我被战场部署的复杂性难住了，整个项目就此搁浅。
然而，战场则完全相反。这里没有商人，也不需要担心与教皇结盟或惹恼托斯卡纳的自由城市，因为你这里只有红蓝两军，步兵、骑兵和炮兵单位，以及半打的军衔。你可以加载一张已为你画好的地图，或使用地图编辑器绘制自己的地图，选择要投入战斗的单位，然后鸣号集合！你就可以出发战斗了。
游戏
当你启动应用程序时，会出现一个屏幕，中间是战斗地图，左边是蓝色单位列表，右边是红色单位列表。你可以通过点击相应的列表框并遵循用户友好的说明来编辑单位。在这些列表框下方，你会找到为每个红蓝军团设置电脑或玩家控制的选项。红色单位是入侵者，蓝色单位是防御者；因此，红色单位还有一个选项来选择他们是从哪个方向入侵。只需点击红色控制组框左侧的指南针图标，程序就会相应地布置红色单位。地图上方有一个组合框，允许你选择下一场战斗将在哪张地图上进行。当你选好了你的队伍，准备好战斗时，按下地图下方的“开始”按钮，战斗就会启动。
如果你让电脑自行对战，整个战斗将进行，并在一旁观看时决定胜者。但这只占乐趣的一半。试着扮演红色方，你会注意到蓝色方有一些防御策略，如果你没有准备好，有时会很难击败。当你看到上面的图片时，你会注意到每个单位上的数字。上面的“分数”描述了该单位的移动点数。构成战场的不同地形类型需要不同数量的移动点数才能穿越。这些移动点数也与你的单位攻击所使用的点数相同。“分子”代表该单位当前的移动点数，而“分母”代表该单位在每个回合开始时获得的移动点数。下面的分数类似，但反映了单位的实力，即仍在战斗中的士兵数量。每个单位都有一个类型。这些类型使它们各自不同，并且它们在战场上的行为由各自的类型决定。炮兵单位容易受到近战攻击，并且在接近敌人时会克制，严重依赖步兵和骑兵的支持。步兵单位是你的核心单位，它们只依靠力量和蛮力进行战斗，而你的骑兵单位移动速度更快，但战斗开始时较弱，因为它们的数量只有步兵的一半，所以即使它们单兵作战比步兵更强，你也不想浪费你的骑兵或让他们陷入冲锋的窘境。
你会在上面的图片中注意到每个单位上的数字。上面的“分数”描述了该单位的移动点数。构成战场的不同地形类型需要不同数量的移动点数才能穿越。这些移动点数也与你的单位攻击所使用的点数相同。“分子”代表该单位当前的移动点数，而“分母”代表该单位在每个回合开始时获得的移动点数。下面的分数类似，但反映了单位的实力，即仍在战斗中的士兵数量。每个单位都有一个类型。这些类型使它们各自不同，并且它们在战场上的行为由各自的类型决定。炮兵单位容易受到近战攻击，并且在接近敌人时会克制，严重依赖步兵和骑兵的支持。步兵单位是你的核心单位，它们只依靠力量和蛮力进行战斗，而你的骑兵单位移动速度更快，但战斗开始时较弱，因为它们的数量只有步兵的一半，所以即使它们单兵作战比步兵更强，你也不想浪费你的骑兵或让他们陷入冲锋的窘境。
指挥你命令的军官在战场上对他们的单位承受和造成的伤害有着巨大的影响，当他们与敌人交战时。
以下是地形类型。道路比草地更容易通行，草地比森林更平坦。城堡更像是一个目的地而不是一种手段，而水域和山地地形基本上是你的单位必须绕过的障碍。考虑利用这些障碍来部署你的单位。我在本图中包含了getMovementCost()函数，该函数完全依赖于地形类型，使每种地形对所有单位都相同。
人工智能
程序员可能会对单位如何决定做什么以及如何做感兴趣。红色单位有一个简单的策略，它们在自由混战中忙于追捕敌人，喜欢抛开阵型，专注于杀戮。要做到这一点，它们首先需要找到敌人以及通往屠杀的最短路径。到目前为止，此项目中被使用最广泛的函数是
public string getShortestPath(classBattle.udtCartesian udrStartLoc,
classBattle.udtCartesian udrTargetLoc,
bool bolIgnoreMovementCost,
bool bolIgnoreEnemyUnits,
bool[,] bolAvoidMap)
它使用了一个广度优先搜索（BFS）算法，这可能在二维地图搜索中非常常见，但如果你从未听说过，我会简要解释一下。它依赖于一个队列和一个与地图大小相同的二维数组。BFS算法的这个特定应用用于搜索两个点之间的最短路径。创建一个Q元素，以便从**目标位置**开始搜索，即单位要前往的那个格子。这个Q元素被插入到最初为空的Q中，然后算法开始。
它从Q中取出下一个元素，然后测试单位是否可以朝周围的每个方向移动。然后，它考虑从当前地图位置到相邻位置的移动成本，将此成本添加到存储在Q元素中的累积成本中，并测试这是否小于为该位置在二维数组中保存的成本（初始化为一个过高的值）。如果以此方式移动更便宜，则会创建一个新的Q元素，插入到Q中，指向我们当前正在处理的Q元素的那个方向，并携带新的移动成本。Q的插入既不是LIFO（后进先出）也不是FIFO（先进先出），因为地形的移动成本是变化的，而你希望从Q中弹出的下一个元素是Q中总移动成本最低的那个。当它尝试了该位置的每个方向并已将所有新位置插入Q后，算法会循环并从Q中取出下一个元素来执行相同的操作，直到它取出与“开始”位置对应的元素为止。此时，它会停止搜索，并通过沿二维数组向后移动来写入结果。
下面图片中描述了这个算法的一个变体
上面图片中显示的额外信息描绘了二维数组中每个元素的内容，包括返回到起始位置所需的移动方向（黑色箭头）、移动成本（黑色数字），以及在某些情况下，每个Q元素进入Q的顺序（红色数字）。由于这个例子只显示了草地地形，它们看起来都一样，因为它们的移动成本都相同。
在这个应用程序中，单位经常只是在寻找一场战斗。所以，要找到最近的敌方单位，它可以通过以相反方向进行BFS算法来简单地说“给我到最近敌人的路径”。它以自身位置为起点，向外扩展，直到找到任何敌方单位。这会给出从该单位到它自身的路径，但它需要以相反的方向行进。然后，它可以将该单位的位置和自己的位置插入到上面提到的getShortestPath()算法中，但这比反转已找到的路径要慢。要做到这一点，它只是读取错误的路径，但将其颠倒并将其添加到输出的前面，就像这样
不，不是真的，但差不多。它只是反向读取路径，并将每一步的相反方向添加到输出的前面，就像这样
while (!(thisPos.x == udrStartLoc.x && thisPos.y == udrStartLoc.y))
{
retval[retval.Length - 1].path
= battlefield.getOppositedirection(udrPathMap[
thisPos.x,
thisPos.y
].direction)
+ retval[retval.Length - 1].path;
thisPos = battlefield.getNextPos(thisPos,
udrPathMap[thisPos.x,
thisPos.y].direction);
retval[retval.Length - 1].intTotalMovementCost
+= battlefield.getMovementCost(thisPos);
}
汇聚点
如上所述，防守方有一些对付红色方攻击的技巧。我将解释的第一个是汇聚点（POC）。这些是地图上单位可以相遇并形成合围的地点，有点像伏击。你可能看过电影《300》，里面斯巴达国王列奥尼达和他一小队斯巴达战士在山间隘口设伏，歼灭了数以万计的波斯人，而这些波斯人却没想到 handful of Greeks could be a problem。这确实发生过。温泉关战役中希腊人的优势，使他们能够抵挡百万波斯大军，从而争取时间召集其他希腊城邦加入战斗，而他们选择的正是这个“汇聚点”，他们在那里坚守阵地。
同样地，虽然不那么英勇，但在这个战场上的蓝色单位首先会搜索位于其城堡和入侵敌方单位之间的汇聚点。要做到这一点，它会找到到离其城堡最近的红色单位的最短路径，然后沿这条路径一步一步地前进。在每一步，它都会问自己，在堵住前方的一步之后，是否能轻松地再走两步。当它堵住一个格子并且无法轻易绕过去时，程序就会认为这个格子是POC。
但算法并没有止步于此。它会沿着路径继续前进，直到遇到敌人，或者遇到敌人会比它先到达一个点，考虑到当前的部署位置，然后它会保留最近找到的POC。而且，这仍然不够，因为在山上可能有一条非常小的山羊小路，这些虚拟波斯人可以利用这条小路绕过当时无助但英勇的蓝色方阻挡隘口的队伍。所以程序会用一个布尔数组来阻止它找到的POC，并将这个数组传递给getShortestPath()函数（bolAvoidMap[,]），然后寻找另一种到达敌人的方法。它沿着那条路径前进，重复相同的过程，直到找到所有POC并阻止它们之后，就再也找不到战斗的方法了。敌人也无法到达它们。
在上面的图片中，位于桥上的第二个POC被忽略了，因为红色单位已经到达了它上面，而蓝色方无法安全到达。
所以你会认为那就是全部了，不是吗？但不是，还没完。喜欢琢磨几个选项的蓝色指挥官，所以在找到这组POC之后，它们会被存储在一个数组中，然后整个过程会重新开始，只是这一次，已经找到的POC会被忽略，所以上面解释的算法中“最近找到的POC”可能位于与前一组完全不同的POC中，它们更靠近城堡。这会一直持续到找到所有可行的POC组，即蓝色方能够到达、占领并守住，而红色方无法到达的POC组。当找到所有这些组之后，它们会被进行比较。
但你如何选择呢？你可能会问。理想情况下，你想要一条路径，一个通道，一个汇聚点。但这并不总是发生。所以为了在不同的POC组之间进行选择，程序首先计算往返每个POC的移动成本，然后将这个数字乘以POC的数量。然后可以根据它们之间的距离来比较每个组，有时，一组中三个非常近的POC可能比两个更远的POC更容易防守。但是1（POC的数量）乘以0（POC之间的旅行成本）等于0，所以单个POC总是最好的。
在接下来的图示中，你将了解蓝色方如何应对红色方的部署。
开阔地防御部署
在许多方面，开阔地比任何设防的城墙、高地或山隘都更难防守。为了模拟军事秩序的表象，我开发了这个算法，它将炮兵单位编队部署在步兵后面，骑兵则部署在侧翼或后方，直到黄昏，而削弱的敌军则会进行更猛烈的冲锋。要做到这一点，程序首先选择每个单位类型的“理想”位置，然后找到前往其分配位置的最佳方式。
炮兵阵地是优先事项，所以这些阵地首先被选择。要做到这一点，第一门炮兵被部署在城堡上，然后它的位置被放入一个Q中（实际实现使用数组），然后从Q中取出第一个可用位置，并在该位置与敌人之间切出一条路径。路径被遍历，直到到达一个未被选中的格子，即“理想部署图”上的一个格子，而不是实际战场部署上的格子。当它找到一个“未被选中的格子”时，它会随机向左或向右转，并进行类似U形转弯的操作，并测试该位置。如果该位置未被设置，则下一个炮兵单位就去那里；如果已设置，则它尝试另一方向并将其放在那里。当两边都设置完毕后，第一个未被选中的格子，即算法进行虚拟U形转弯的路径上的那个格子，被设置在bolAvoidMap[,]数组中，这告诉getShortestPath()算法在下一次炮兵部署迭代中避开这个格子。
当它再也找不到可以放置更多炮兵单位的地方，或者所有炮兵单位都已被分配了自己的位置时，它就开始放置近战单位。
近战单位属于战场的核心，在那里它们可以妥善地保卫炮兵，并由炮兵从后方支援。因此，为了选择步兵和骑兵单位的最佳位置，使用了另一个算法，尽管它非常相似。bolAvoidMap[,]数组被重置为默认地形图。然后，从城堡找到一条到最近敌人的路径，然后沿着这条路径前进，直到找到一个“未被选中的格子”；这就是下一个步兵/骑兵单位将被放置的地方；这个格子的bolAvoidMap[,]数组中的布尔变量被设置，以便下一个“getShortestPath()”搜索必须绕过它。最终，炮兵单位，它们面向敌人排成一列，会被步兵单位包围，骑兵部署在侧翼。
那是易事
void OFD_setBestOpeningMoves()
现在这些单位必须移动到那里。在正常情况下，每个由计算机控制的单位都会按照它们被命令的顺序执行其回合（炮兵通常先开火，但没有特定的顺序）。但让它们自行移动到这些“理想”位置并不总能让它们到达需要的位置。为了解决这个问题，我使用了一个深度优先搜索算法（DFS）。这听起来应该像BFS，但实际上不是。它更像是遍历二叉树，只是这不是二叉树，并且树的每个节点或叶子有任意数量的子节点。
本质上，发生的情况是我们要么需要
- 将一个单位移离优先位置
或
- 将一个单位移入优先位置。
这些位置首先需要被确定优先级。这需要在搜索的每一点（树的每个节点）进行。
udtOpenFieldDefense_Position[]
OFD_getPrioritizedLocs(udtOpenFieldDefenseInfo udrOFDInfo,
udtOpenFieldDefenseSearch_UnitInfo[] udrUnitInfo)
这是对它收到的作为参数的udtOpenFieldDefenseInfo变量中存储的位置进行优先排序的函数。要做到这一点，它首先计算每种类型有多少个位置未被其目标类型的单位占据。然后，当它知道是否所有炮兵单位都已到位以及哪些单位类型仍需确定时，它会设置一个PriorityType变量，该变量在函数的其余部分用于调节要优先处理哪种单位类型。
当它遍历收到的数组中的所有位置时，它会为那些没有未确定位置的类型的位置设置“bolSearchComplete”。这意味着任何由于先前“腾出优先位置”的移动而被确定的位置，或者在“理想地图”首次绘制时就被确定的位置，如果该单位类型的所有位置都已被对应类型的单位占据，则不再需要考虑。当这种情况发生时，这些位置将从需要确定的位置列表中移除，算法将继续处理其他优先类型。
传递给此函数的第二个参数保存了搜索时单位的信息。这对于我们处理未被先前“占领优先位置”移动确定的相同PriorityType位置的优先级排序的下一步是必需的。要做到这一点，每个单位都使用类似于查找最近敌方单位的BFS算法向外搜索，但它在开阔地部署地图上搜索其自身类型的单位位置。搜索受到移动成本和它们在搜索树的这个节点上到达时仍然拥有的移动点的限制。这意味着：只计算这些单位仍然可以到达的位置，这取决于它们当前相对于敌人的位置以及剩余的移动点数。然后，当计数完成，所有单位都已尽可能远地探索并记录它们找到的位置后，就知道有多少单位可以到达每个位置。需要首先确定的位置，即优先位置，是能够被最少数量单位到达的位置。
使用快速排序重新排序输出位置数组，使最高优先级的earliest positions出现在数组的前面，这意味着pos[0]是下一个优先级最高的位置。
回到我们老朋友那里，void OFD_setBestOpeningMoves()
我选择将“最佳”解决方案定义为能够解决最多数量位置的解决方案，或者，如果找到了一个完整的解决方案，则是有史以来最好的解决方案，它为整个蓝色军团单位留下了最多的剩余移动点数。
这个函数有一个计数器，用于跟踪自搜索开始以来已采取的步骤数。将其设置为无穷大（忽略它）会产生最佳可能解决方案，给定当前情况。目前，这个计数器变量
int intStepsCount = 0;
int intMaxSteps = 2000;
在2000步后会截断搜索。随意将其更改为您想要的任何设置，并考虑根据战场上剩余的军衔来选择一名执行官，然后根据最高军衔军官的军衔设置intMaxSteps变量。
它不是“毁灭公爵”，但肯定比“乓”好！
历史
- 2009年11月13日：初次发布
- 2009年11月15日：更新源代码