战地模拟器(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/battlefield-simulator-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 20 分钟阅读 - 9922 个词 阅读量 0战地模拟器(译文)
原文地址:https://www.codeproject.com/Articles/43751/Battlefield-Simulator
原文作者:Christ Kennedy
译文由本站 robot-v1.0 翻译
前言
KOEI-like old-school war game and battlefield simulator, with infantry, artillery, and cavalry units.
类似于KOEI的老派战争游戏和战场模拟器,带有步兵,炮兵和骑兵部队.
介绍(Introduction)
此应用程序是一款具有三种单位的战场模拟器游戏:步兵,骑兵和炮兵.该地图由排列在"六边形"网格中的几种不同的地形类型组成,这在许多基于回合的视频游戏中都可以看到.计算机玩家的人工智能对玩家具有挑战性,并且可以通过定期使用广度优先搜索算法的几种变体以及一种深度优先搜索移动顺序求解算法为程序员提供洞察力,下面将对此进行说明. .(This application is a battlefield simulator game with three types of units: Infantry, Cavalry, and Artillery. The map consists of several different terrain types lined in a ‘six-sided-square’ grid as seen in many turn-based video games. The computer player’s artificial intelligence is challenging to the player, and may provide insight for programmers with the regular use of several variations of breadth-first-search algorithms as well as one depth-first-search move-sequence solution algorithm, which are explained below.) 作为类和DLL,战场项目可用于构建具有自身经济和角色转换的大型战争游戏,以丰富游戏玩法.(As a class and DLL, the battlefield project can be used to build a larger war game with its own economy and cast of characters to enrich game play.)
背景(Background)
的(The) 小荣(Koei) 该公司可能尚未发明基于计算机的视频游戏,但将其带入PC并操纵了一些有史以来最出色的基于回合制的战争游戏.我玩过很多乐曲:信长的野心,三个王国的浪漫史,古代中国的土匪国王,成吉思汗,皇帝,自由或死亡,等等…我可以说很多,但是我想你可以理念.这些游戏都非常相似,但是它们各自为您带来了过去的不同部分,您可以重演,并且通常会改变历史记录.(company may not have invented the computer based video games, but they brought to the PC and console some of the greatest turned-based war-games ever seen. I’ve played a bunch: Nobunaga’s Ambition, Romance of the Three Kingdoms, Bandit Kings of Ancient China, Genghis Khan, L’Empereur, Liberty or Death, and … I could name a bunch more, but I think you get the idea. These games are all very similar, and yet they each bring a different part of the past to life for you to reenact and, more often than not, alter the recorded course of history.) 我在这里所做的事情是我多年来一直想要做的事情,写着类似Koei的战争游戏,但是大约在五年前,我在此所做的最后一次尝试从一开始就注定了.我花了一个月的时间建立一个除了战斗屏幕之外的所有东西,包括角色,经济以及在意大利半岛上下旅行的商人,这是我称之为"(What I’ve done here is something that I’ve been meaning to do for ages, write a Koei-like war game, but the last attempt I made at this, about five years ago, was doomed from the start. I spent a month building everything except the battle screen, including the characters, the economy, and the merchants that travelled up and down the Italian peninsula, in a project I called)**Borgia(Borgia)**它原本应该设在意大利文艺复兴时期,但是当我进入战斗画面,即行动的核心时,我就被野外部署的复杂性所困扰,整个项目陷入了困境.(which was supposed to be based in Renaissance Italy, but when I got to the battle screen, the heart of the action, I was stumped by the complexity of field deployment, and the whole project went bunk.) 但是,<战地风云>则完全相反.这里没有商人,也不必担心与教皇结盟或破坏托斯卡纳的自由城市,因为这里您所拥有的只有红色和蓝色连队,步兵,骑兵和炮兵部队,还有六个军事队伍.您可以加载已经为您绘制的地图,也可以使用地图编辑器绘制自己的地图,选择要带到现场的单位,然后播放声音!你要去战斗了.(Battlefield, however, is the complete opposite. There are no merchants here, and no need to worry about being allies with the Pope or upsetting the free-cities of Tuscany either, because all you have here are Red and Blue companies, Infantry, Cavalry, and Artillery units, and a half dozen military ranks. You can load a map already drawn for you, or use the map editor to draw your own, pick the units to take to the field, and sound reveille! You’re off to battle.)
游戏(The Game)
启动应用程序时,将出现一个屏幕,其中有一幅战场地图位于中心,左侧为蓝色单位列表,右侧为红色单位列表.可以通过单击相应的列表框并按照用户友好的说明来编辑单位.在这些列表框下面,您会找到用于为每个红色和蓝色公司设置计算机或播放器控件的选项.红色单位是侵略者,蓝色单位是防御者.因此,红色单位还可以选择从哪个方向入侵.只需单击红色控件组框左侧的指南针图标,程序就会相应地放置红色单位.地图上方有一个组合框,您可以从中选择要进行下一场战斗的地图.当您选择好船员并准备战斗时,请按地图下方的"开始"按钮,战斗便会开始.(When you launch the application, a screen appears with a battle map at center and a list of units in blue on the left, with another list of units in red on the right. The units can be edited by clicking the respective list boxes and following the user-friendly instructions. Below these listboxes, you’ll find the options to set computer or player controls for each red and blue companies. The red units are the invaders, and the blue units the defenders; therefore, the red units also have an option to choose in which direction they are invading from. Simply click on the compass icon to the left of the red-controls groupbox, and the program will place the red units accordingly. There’s a combo box above the map which allows you to choose the map on which your next battle will be fought. When you’re done picking your crew and you’re ready for a fight, press the ‘Go’ button below the map and the battle will be launched.)
如果您让计算机自己玩,那么整个战斗将进行,并且观看者将决定赢家.但这只是乐趣的一半.尝试打红色,您会注意到,蓝队有一些防守策略,如果您不准备的话,有时很难被击败.(If you let the computer play itself, the entire battle will be fought, and a winner decided while you watch. But that’s only half the fun. Try playing red, and you’ll notice that Blue’s got some defensive strategies that are sometimes difficult to beat if you’re not prepared.)
您会在图像中注意到每个单元上的数字.最上面的"分数"描述了本机的运动点.组成战场的不同类型的地形需要不同数量的移动点才能穿越.这些移动点也与单位用来攻击的点相同.最高分数的"分子"是该单位目前具有的移动点数,最高分数的"分母"是该单位在每转开始时获得的总移动点.底部部分相似,但是反映了部队的实力或仍在战斗的士兵人数.每个单元都有一个类型.这些类型使它们都非常不同,它们在战场上的行为受其各自类型控制.炮兵部队很容易受到近战攻击,在接近敌人时会克制住部队,这在很大程度上取决于步兵和骑兵的支援.步兵部队是您的核心部队,只不过用强力和蛮力进行战斗,而您的骑兵部队的移动速度更快,但在战斗开始时却较弱,因为它们的数量仅是步兵的一半,因此尽管他们比步兵每人,您不想浪费您的骑兵或让他们被困在后膛中.(You’ll notice in the image above the numbers on each unit. The top ‘fraction’ describes this unit’s movement points. The different types of terrain that make up the battlefield require different amounts of movement points to traverse. These movement points are also the same points your unit uses to attack. The ‘numerator’ of the top fraction is the number of movement points this unit has at the moment, and the ‘denominator’ of the top fraction is the total movement points this unit gets at the start of every turn. The bottom fraction is similar, but reflects the unit’s strength, or number of soldiers still fighting. Units each have a type. These types make them all very different, and their behavior on the battlefield is governed by their respective types. Artillery units are vulnerable to melee attacks, and use restraint when approaching the enemy, relying heavily on infantry and cavalry support. Infantry units are your core units, and fight with nothing but brawn and brute force, while your cavalry units travel more quickly, but are weaker at the beginning of the battle since their number is only half that of infantry, so though they fight harder than infantry man-per-man, you don’t want to waste your cavalry or get them trapped charging into the breech.)
在野外执行命令的军官对与敌人交战的部队造成的伤害和打击有很大影响.(The officers executing your commands on the field have a great impact on the amount of damage their units incur and mete when they engage the enemy.)
以下是地形类型.道路比草更容易通过,草比森林更光滑.城堡比其他方式更多地是目的地,水和山地地形基本上是您的单位必须穿越的障碍.放置单元时,请考虑利用这些障碍.我已经在这张图片中(Here are the terrain types. Roads are easier to travel than grass, and grass is smoother than forest. A castle is more of a destination than a means, and the water and mountain terrains are basically obstacles your units have to go around. Consider making use of these obstacles when positioning your units. I’ve included in this image the) getMovementCost()
该功能完全取决于地形类型,因此每个地形对于所有单位都是相同的.(function which relies entirely on the terrain type, making each terrain the same for all units.)
人工智能(Artificial Intelligence)
程序员可能对查看单元如何决定做什么以及如何做感兴趣.红色单位的战略很简单,他们的生意就是以一种万无一失的幸福来猎杀敌人,以抛弃等级和阵型,并继续流血的欲望.为此,他们首先需要找到敌人和最短的屠杀道路.到目前为止,该项目中使用最广泛的功能是:(Programmers may be interested in seeing how the units decide what to do and how to do it. The red-units have a simple strategy, and go about their business hunting the enemy in a free-for-all happy to leave rank and formation behind, and get on with the blood-lust. To do this, they first need to find the enemy and the shortest path to carnage. By far, the most widely used function in this project is:)
public string getShortestPath(classBattle.udtCartesian udrStartLoc,
classBattle.udtCartesian udrTargetLoc,
bool bolIgnoreMovementCost,
bool bolIgnoreEnemyUnits,
bool[,] bolAvoidMap)
它使用广度优先搜索(BFS)算法,该算法在2D地图类型搜索中可能很常见,但是如果您从未听说过,我将给您做一个简短的解释.它运行在一个队列和一个与地图大小相同的二维数组上. BFS算法的这种特殊应用搜索两点之间的最短路径.创建一个Q元素以在以下位置开始搜索(It uses a breadth first search (BFS) algorithm which is probably very common in 2D map-type searches, but I’ll give you a brief explanation if you’ve never heard of it. It runs off a queue and a two-dimensional array the same size as the map. This particular application of the BFS algorithm searches for the shortest path between two points. A Q-element is created to start the search at the)目标位置(Target location),即单位行驶到的广场.将此Q元素插入到最初为空的Q中,然后算法开始.(, that is, the square to which the unit is travelling to. This Q-element is inserted into the initially empty Q, and the algorithm begins.)
它是Q中的下一个元素,然后它测试一个单元是否可以沿它的每个方向行进.然后,它考虑从该地图位置到相邻地图位置的旅行费用,将此费用添加到存储在Q元素中的运行费用中,并测试它是否小于二维数组中保存的费用该位置(初始值过高).如果以这种方式旅行比较便宜,则将一个新的Q元素插入Q中,指向我们当前正在使用的Q元素的方向,并承担新的移动成本. Q插入既不能是LIFO(后进先出),也不能是FIFO(先进先出),因为地形的旅行成本各不相同,并且您希望弹出Q的下一个元素是在Q中的总旅行费用最少.当尝试从该位置向每个方向尝试并将所有新位置插入Q时,该算法会循环并从Q中拉出下一个元素以再次执行相同操作,直到将Q中的一个元素拉离对应于"开始"的位置为止位置.此时,它通过沿二维数组向后移动而退出搜索并写入结果.(It deQ’s the next element in the Q, then it tests if a unit could travel each direction around it. Then, it considers the travel cost from this map location to the adjacent one, adds this cost to the running cost which is stored in the Q-element, and tests if this is less than the cost which is held in the two-dimensional array for that location (initialized at some excessively high value). If it is cheaper to travel this way, then a new Q-element is inserted into the Q pointing in the direction of the Q-element we’re currently working and carry the new movement cost. The Q-insertion cannot be neither LIFO (Last-in-first-out) nor FIFO (First-in-first-out) because the terrain’s travel cost varies and you want the next element that pops-off the Q to be the one in the Q with the least total travel cost. When it has tried every direction from this location and inserted all the new locations into the Q, the algorithm loops around and pulls the next element off the Q to do the same again until it pulls one off the Q which corresponds to the ‘start’ location. At this point, it quits the search and writes the results by travelling backwards along the two-dimensional array.)
下图描述了这种变化:(A variation of this is described in the picture below:)
您在地图上看到的额外信息描述了二维数组中每个元素的内容,包括移动以从该正方形返回起始位置的方向(黑色箭头),移动成本(黑色数字) ,在某些情况下,还包括每个Q元素输入Q的顺序(红色数字).由于此示例仅显示草地,因此它们看上去都一样,都具有相同的旅行成本.(The extra information you see on the map depicts the contents of each element in the two-dimensional array, including the direction in which to move in order to return to the start location from that square (black arrows), movement cost (black numbers), and in some cases, the order in which each Q-element was entered into the Q (red numbers). Since this example only shows grassy terrain, they all appear the same as they all have the same travel cost.)
在此应用程序中,通常情况下,单位只是在寻找战斗.因此,要找到最近的敌方单位,只需朝相反的方向执行BFS算法即可说出"给我到最近的敌人的路径".它从自己的位置开始,向外扩展直到找到任何敌方单位.这为它提供了从该单元到其自身的路径,但是它需要朝相反的方向前进.然后,它可以将该单元的位置及其自身的位置插入到(Often times in this application, a unit is just looking for a fight. So, to find the nearest enemy unit, it can just say ‘give me the path to the nearest enemy’ by doing the BFS algorithm in the opposite direction. It starts with its own location, and spans outwards until it finds any enemy unit. This gives it the path from that unit to itself, but it needs to go in the opposite direction. It could then plug that unit’s location and its own into the) getShortestPath()
上面提到的算法,但这比仅反转已找到的路径要慢.为此,它只是读取了错误的路径,但是一边喝一杯水一边将其向后偏右.(algorithm mentioned above, but that would be slower than just reversing the path it has already found. To do this, it simply reads the wrong path, but rights it backwards on its head while drinking a glass of water.)
不,不是真的,但是有点.它只是向后读取路径,并将每个步骤的相反步骤添加到输出的前面,如下所示:(No, not really, but sorta. It just reads the path backwards and adds the opposite of each step to the front of the output, like this:)
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);
}
收敛点(Points of Convergence)
如上所述,防守方有一些技巧可以抵御Red的袭击.我要解释的第一个是收敛点(POC).这些是地图上可以相遇并结成单位的位置,有点像伏击.您可能已经看过电影'300',其中Lacedaemonius和他的斯巴达勇士小乐队阻止了穿越山脉,屠杀了成千上万的波斯人,他们认为少数几个希腊人不会成为问题.那真的发生了.希腊人在Thermopylae的优势使他们拥有足够长的百万级波斯入侵力量,足以使其他希腊人陷入困境,这是事实,他们选择了他们坚持的"融合点".(As mentioned above, the defending side has a few tricks to fend off Red’s attacks. The first one I’ll explain is the Points-of-Convergence (POC). These are locations on the map where units can be met and ganged-up on, kind of like an ambush. You may have seen the movie ‘300’ where Lacedaemonius and his small band of Spartan warriors block a pass through the mountains and massacre untold thousands of Persians who didn’t think a handful of Greeks could be a problem. That actually happened. And the Greek advantage at Thermopylae, what allowed them to hold the million-strong Persian invasion force long enough to call the other Greek Polis into the fray, was the fact that they picked this ‘Point of convergence’ on which they held their ground.)
以类似的方式,尽管不那么英勇,但该战场中的蓝色部队首先在其城堡与入侵的敌方部队之间寻找汇合点.为此,它会获得最接近其城堡的红色单位的最短路径,然后一次沿着该路径行进一步.在每一步中,它都会询问自己是否阻挡了前面的下一个步骤,然后轻松地沿着同一路径进一步前进了两个步骤.当它遮挡一个正方形并且无法轻松地找到周围的方法时,程序会将这个正方形视为POC.(In like manner, though much less heroically, the blue units in this battle field first search for points of convergence between their castle and the invading enemy units. To do this, it gets the shortest path to the red-unit which is nearest to their castle, and then travels along this path one step at a time. At every step, it asks itself if it can easily reach two steps further along the same path after it has blocked the next one in front of it. When it blocks a square and can’t easily find a way around it, then the program considers this square to be a POC.)
但是算法并不止于此.它会沿着路径继续前进,直到到达敌人或到达敌人可能到达的位置为止(根据当前的部署位置),然后它将最近发现的POC保留下来.而且,这仍然不会实现,因为山上可能有一条小山羊路,这些虚拟的波斯人可以用来包围山路,尽管不幸,但是英勇的蓝调乐队阻止了通行证.因此,程序随后使用布尔数组来阻止找到的POC,并将其传递给(But the algorithm doesn’t stop there. It continues along the path until it reaches the enemy or it reaches a point where the enemy would get there before it can, given the current deployment positions, and then it keeps the POC it found most recently. And, that still won’t do it because there may be a small goat’s path over the mountain which these virtual Persians can use to surround the by then hapless though valiant band of blues blocking the pass. So the program then obstructs the POC it has found using a boolean array which it passes to the) getShortestPath()
功能((function () bolAvoidMap[,]
),并寻找到达敌人的另一种方法.它沿着那条路径行进,并重复相同的过程,直到找到所有POC并将其全部阻止之后,再也找不到找到战斗的方法了.敌人也无法到达他们.(), and searches for another way to reach the enemy. It travels along that path, and repeats the same process until, after finding all the POCs and blocking them all, there’s no way to find a fight anymore. And the enemy can’t reach them either.)
在上图中,忽略了桥上的第二个POC,因为红色单位已经在其顶部,而蓝色无法安全到达它.(In the image above, the second POC located on the bridge is ignored because the Red units are already on top of it and Blue couldn’t reach it safely.)
所以您会以为是,不是吗?但是不,事实并非如此.蓝色醉汉喜欢仔细考虑几个选项,因此,当找到第一组POC时,它们会存储在数组中,并且整个过程会再次开始,仅这次,已经找到的POC被忽略,并且因此,如上所述,算法中的"找到的最新POC"可能位于与城堡相比完全不同的POC组中.这一直持续到所有可行的POC集,即蓝色端可以在红色端之前到达,保持和防御的所有POC集.找到所有这些集合后,将它们进行比较.(So you’d think that would be it, wouldn’t you? But no, that’s not quite it. The Blue drunk-in-charge likes to mull over a few options, so when this first set of POCs is located, they’re stored in an array and the whole process starts again, only this time, the POCs already found are ignored and so ‘the most recent POC found’ in the algorithm, as explained above, may be in a completely different set of POCs that are located nearer to the castle than the previous set. This continues until all viable sets of POCs, that is all sets of POCs which the blue side can reach, hold and defend before the Red side. When all these sets are found, they are then compared.)
但是你如何选择呢?你可能会问.理想情况下,您需要一条路径,一道通行,一个融合点.但这并不总是会发生.因此,要在不同的POC集之间进行选择,该程序首先计算往返于每个集中的每个POC的往返移动成本,然后将该数字乘以POC的数量.然后,可以根据给定的每个集合之间的距离进行比较,有时,一个集合中三个非常接近的POC可能比两个更远的POC更易于防御.但是1(POC的数量)乘以0(POC之间的旅行成本)等于0,因此单个POC始终是最好的.(But how do you choose? You might ask. Ideally, you want one path, one pass, one point of convergence. But that doesn’t always happen. So to pick between different sets of POCs, the program first calculates the movement cost for a round trip to every POC in each set, then multiplies this number by the number of POCs. Each set can then be compared given the distance between them, and on occasion, three very near POCs in a set may be easier to defend than two more distant POCs. But 1 (number of POCs) multiplied by 0 (travel cost between POCs) equals 0, and so a single POC is always the best.)
在下面的这些图中,您将了解蓝色的一面对红色的配置有何反应.(In these next diagrams, you’ll get an idea of how the blue side reacts to Red’s disposition.)
野外防御部署(Open Field Defensive Deployment)
与任何防御工事的城墙,高架的山丘或山口相比,开阔的土地在许多方面都难以防御.为了模拟军事秩序的外表,我开发了这种算法,将炮兵编队放置在步兵后方,骑兵在侧翼或后方直到黄昏,而削弱的敌军则使其暴力指控更加残酷.为此,程序首先为每种类型的单元选择"理想"位置,然后找到将单元移动到分配位置的最佳方法.(An open-field is in many ways more difficult to defend than any fortified rampart, elevated hill, or mountain pass. In order to simulate the semblance of military order, I developed this algorithm which places artillery units in formation behind infantry, with cavalry either on the flanks or in the rear until dusk, and a weakened enemy force makes their violent charges all the more brutal. To do this, the program first chooses the ‘ideal’ locations for each type of unit, then finds the best way to go about moving the units to their allocated positions.)
炮兵阵地是优先事项,因此首先选择这些阵地.为此,将第一个火炮放置在城堡上,然后将其位置放置在Q中(实际实现使用数组),然后拉出Q中的第一个可用位置,并在该位置和敌人.遍历该路径,直到到达未选择的正方形,即此"理想部署图"上的正方形,而不是实际战斗位置.当找到"未选中的正方形"时,它会随机向左或向右转,并做一些接近于掉头的操作并测试该位置.如果未设定该位置,则下一个炮兵部队进入该位置;如果已设置,则它将尝试另一个方向并将其放置在那里.设置好两侧后,将在算法中沿该算法进行这些虚拟调头的路径设置第一个未选择的步骤.(Artillery positions are a priority, so these positions are selected first. To do this, the first artillery is placed on the castle, then its position is placed in a Q (actual implementation uses an array), then the first available location in the Q is pulled out, and a path is cut between that location and the enemy. The path is traversed until an unselected square, that is a square on this ‘ideal deployment map’, not the actual battle disposition, is reached. When it finds an ‘unselected square’, it turns either left or right at random, and does something close to a u-turn and tests that position. If that position is not set, then the next artillery unit goes there; if it is set, then it tries the other direction and puts it there. When both sides are set, then that first unselected step, along the path about which the algorithm does these virtual u-turns, is set in the) bolAvoidMap[,]
数组告诉(array which tells the) getShortestPath()
避免在此炮兵部署的下一次迭代期间避开这个正方形的算法.(algorithm to avoid this square during the next iteration of this artillery deployment.)
当它再也找不到要放置更多炮兵单位的地点时,或者当所有炮兵单位都已经分配了自己的位置时,它便开始放置近战单位.(When it can no longer find any spots to place any more artillery units, or when all artillery units have been allocated positions of their own, then it starts to place the melee units.)
近战部队属于战斗热力,在这里,他们可以妥善保卫炮兵并让炮兵从后方支援他们.因此,为了选择步兵和骑兵部队的最佳位置,虽然使用了非常相似的算法,但是使用了不同的算法.的(Melee units belong in the heat of battle, where they can properly defend the artillery and have artillery support them from the rear. So to select the best positions for the infantry and cavalry units, a different algorithm is used, though it is quite similar. The) bolAvoidMap[,]
阵列将重置为默认地形图.然后,从城堡中找到通往最近敌人的路径,然后沿着这条路径行进,直到找到"未选中的正方形"为止.这是下一个步兵/骑兵部队的所在地;相同平方的布尔变量(array is reset to the default terrain map. Then, a path to the nearest enemy is found from the castle, then this path travelled until an ‘unselected square’ is found; this is where the next infantry/cavalry unit is placed; this same square’s boolean variable in the) bolAvoidMap[,]
设置数组,以便下一个'(array is set so that the next ‘) getShortestPath()
搜索将不得不解决它.最终,面对敌人排成一线的炮兵部队被步兵部队包围,两侧为骑兵.(’ search will have to go around it. Eventually, the artillery units, which are lined up facing the enemy, are surrounded by infantry units, with cavalry on the flanks.)
那是容易的部分(That was the Easy Part)
void OFD_setBestOpeningMoves()
现在这些单位必须搬到那里.在正常情况下,由计算机控制的每个单元按其订购的顺序旋转(炮兵通常首先射击其齐射,但没有特定的顺序).但是,让他们自己移动到这些"理想"位置并不一定总是使他们成为他们所需要的地方.为了解决此问题,我使用了深度优先搜索算法(DFS).听起来应该像BFS,但实际上并非如此.它更像遍历二叉树,只是它不是二叉树,并且树的每个节点或叶子都具有任意数量的子节点.(Now these units have to move there. In normal circumstances, each unit controlled by the computer plays its turn in whatever sequence they are ordered (artillery usually fire their volleys first, but there’s no specific order). But letting them move by themselves to these ‘ideal’ locations doesn’t always end up with them being where they need to be. To solve this problem, I used a depth-first-search algorithm (DFS). This sounds like it should be like the BFS, but really it is not. It is more like traversing a binary tree, except this isn’t a binary tree, and each node or leaf of the tree has any number of child-nodes.) 本质上,这里发生的是我们要么需要:(Essentially, what happens here is that we either need to:)
-
将单位移离优先位置(move a unit away from a priority position)要么:(or:)
-
将单位移至优先位置.(move a unit into a priority position.) 首先需要确定职位的优先级.这需要在搜索的每个点(树中的每个节点)完成.(The positions first need to be prioritized. This needs to be done at every point in the search (every node in the tree).)
udtOpenFieldDefense_Position[]
OFD_getPrioritizedLocs(udtOpenFieldDefenseInfo udrOFDInfo,
udtOpenFieldDefenseSearch_UnitInfo[] udrUnitInfo)
该功能可以对存储在(This is the function that prioritizes the positions stored in the) udtOpenFieldDefenseInfo
变量在这里作为参数接收.为此,它首先计算每种类型的多少位置未被其预期类型的单元占用.然后,当知道所有炮兵单位是否都到位并且仍需要确定哪种单位类型时,便设置一个(variable it receives as a parameter here. To do this, it first counts how many positions of each type are not occupied by units of their intended type. Then, when it knows if all artillery units are in place or not and which unit types still need to be settled, it sets a) PriorityType
变量将在整个函数的其余部分中使用,以调节接下来要关注的单元类型.(variable which it uses throughout the rest of the function to regulate which type of unit to concentrate on next.)
当它遍历接收到的数组中的所有位置时,它会设置"(As it cycles through all the positions in the array it received, it sets ‘) bolSearchComplete
对于那些没有未平仓头寸的头寸.这意味着由于先前的"空缺优先权"举动而结清的任何头寸,或者在"理想地图"被首次起草时已经结清的任何头寸,如果相同单位类型的所有头寸都被考虑,则不再需要考虑被其相应类型的单元占用.发生这种情况时,会将这些位置从需要结算的位置列表中删除,并且该算法将继续使用其他优先级类型.(’ for those positions of types that have no unsettled positions. What this means is any position that was settled due to a prior ‘vacate priority pos’ move, or was already settled when the ‘ideal map’ was first drafted, no longer needs to be considered if all the positions of that same unit type are occupied by units of their corresponding type. When this happens, these positions are removed from the list of positions that need to be settled, and the algorithm continues with other priority types.)
传递给该函数的第二个参数在搜索中此时保留了单位信息.这是我们下一步处理优先顺序相同的位置所必需的(The second parameter passed to this function holds the unit information at this point in the search. This is required for our next step which deals with prioritizing the positions of the same) PriorityType
尚未通过先前的"占据优先位置"的举动解决的问题.为此,每个单位都使用类似于发现最近敌方单位的BFS算法远离自己进行搜索,但会在开放野外部署地图上搜索自己类型的位置.搜索受到旅行成本及其移动点(单位到达搜索树中的此节点时仍具有的移动点)的限制.这意味着:仅考虑这些单位相对于敌人的当前位置以及它们离开的移动点,它们仍然可以到达的位置.然后,当统计完成后,所有单元都已探查到尽头,跟踪找到的位置,然后知道可以到达每个位置的单元数.首先需要确定的位置(优先位置)是最少数量的单位可以到达的位置.(that have not yet been settled by a prior ‘occupy a priority pos’ move. To do this, each unit searches away from itself using a BFS algorithm similar to the one used to find the nearest enemy unit, but it searches for positions of its own type on the open-field-deployment map. The search is limited by travel costs and their movement points which the units still have when they reached this node in the search tree. What this means is: only the positions which these units can still reach, given their current positions relative to the enemy as well as the movement points they have left, are counted. Then, when the tally is done, and all the units have explored as far as they can reach, keeping track of what positions they find, then the number of units which can reach each position is known. The position which needs to be settled first, the priority position, is the position which can be reached by the least number of units.)
使用快速排序对输出位置数组进行重新排序,以使最高优先级位置在该数组中首先出现,这意味着pos [0]是下一个优先级位置.(Reorder the output positions array using quick-sort so that the highest priority positions appear first in the array, which means that pos[0] is the next priority position.)
回到我们的老朋友,(Getting back to our old friend,) void OFD_setBestOpeningMoves()
:(:)
我选择将"最佳"解决方案定义为解决最多职位数的解决方案,或者,如果找到一个完整的解决方案,那么该完整解决方案将为整个Blue Company单位带来最多的剩余移动点.(I chose to define the ‘best’ solution as the solution that either resolves the most number of positions or, if a complete solution is found, then the complete solution that results in the most remaining movement points for the entire Blue company of units.)
此功能具有一个计数器,该计数器跟踪自搜索开始以来采取的步骤数.在当前情况下,将其设置为无穷大(不考虑它)将导致最佳解决方案.目前,此计数器变量:(This function has a counter which keeps track of the number of steps taken since the beginning of the search. Setting this to infinity (disregarding it) results in the best possible solution, given the current circumstances. For the moment, this counter variable:)
int intStepsCount = 0;
int intMaxSteps = 2000;
在2000个步骤之后缩短搜索范围.随意将其更改为任何设置,并考虑根据现场的剩余职级选择一名执行官,然后设置(cuts the search short after 2000 steps. Feel free to change this to whatever setting, and consider selecting an Executive Officer according to the ranks remaining on the field, and then setting the) intMaxSteps
根据最高级别官员的级别而变化.(variable in accordance to the rank of the highest ranking officer.)
它不是"末日",但肯定胜过"傍"!(It’s not ‘Doom’, but it sure beats ‘Pong’!)
历史(History)
- 13(13)日(th)2009年11月:初始职位(November, 2009: Initial post)
- 15(15)日(th)2009年11月:更新的源代码(November, 2009: Updated source code)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# .NET Windows Dev AI 新闻 翻译