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.
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 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.
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 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)
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, 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.
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:
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.
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
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.
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.
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[,]), 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.
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.
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.
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.
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()
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 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.
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():
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;
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
- 13th November, 2009: Initial post
- 15th November, 2009: Updated source code
