Game Algorithms (Part 3)

Introduction

In my previous two blog posts on game algorithms, I showed how to search for a ship in a battleship game.  Now, I’m going to show how to sink a ship as soon as your search algorithm gets a hit.  In this article, I’m only going to discuss possible algorithms, there will be no accompanying code.

Ship Length and Direction Unknown

One of the challenges to battleship is that you don’t know what size the ship is that you hit, once you have made the first hit.  You also don’t know which direction it is facing.  So the first step is to figure out the direction (and hope it’s a PT boat, so you can sink it at the same time you discover the direction).

So the first thing to do is find the direction.  We all learned this technique after playing battleship the first few times in our lives.  Basically, we fire on each square above, below, to the left and right of the location that we got a hit.  Ignoring any squares that are already hit.  I usually follow a circular pattern until I get another hit, but you can do a cross pattern too.  In order to reduce the amount of shots you need to take, you can do some analysis of the board and determine if you need to shoot each square, or possibly, any remaining ship is too long to fit in the direction that you might test.  For example, here is a 5×5 map with one destroyer:

We managed to get a hit at square 1,1.  If we next fire on square 0,1, we might get a hit, but we could also get a miss.  Same with square 1,0.  However, if you shoot at square 1,2 or square 2,1, you’ll notice that we will get a hit, no matter where the destroyer is positioned (remember a destroyer occupies 3 squares).  So we only need to fire on 1,2 and if that was a miss, then 2,1 to find the direction of the destroyer.  

This indicates that we could create an algorithm that checks each possible position of a destroyer that contains square 1,1 and determine what the probability is that it would be located in any of the possible surrounding squares.  Then we can choose the most probable squares first.

Now, let’s assume we shot square 1,2 and got another hit.  We’re also assuming that we only have one destroyer on the board.  So the board looks like this:

Now we have a 50% chance that we can sink the ship by firing on square 1,0 and a 50% chance that we can sink the ship by firing on square 1,3.  So we just take a chance and shoot one side, then, if that didn’t sink the ship, fire on the other side.  Ship sunk.


Multiple Ships on Map

OK, now we have a map containing two or more ships, let’s say a destroyer and a PT boat on the same 5×5 map.  Now, what would happen if the map looked like the above map and you fired on square 1,0 and 1,3 and both missed?

You guessed it.  There’s a PT boat facing vertical on the right side of a vertically facing destroyer.  The PT boat is a no-brainer, since there is only room for it to fit in squares 0,2 and 1,2.  The destroyer could still occupy 0,1 or not.

So we would need an algorithm to determine that if we shot on both sides of a ship and it didn’t sink, then we hit two ships.  The algorithm could get a bit tricky once we have figured out that we hit more than one ship, because the second ship could be facing the other way.  However, any ship facing horizontally, will eventually get sunk.  According to the rules of battleship you must announce which ship was sunk.  So now we’ll also need to verify that the ship sunk matches the number of squares shot at.  Here’s an example:


In this example, once square 1,3 is shot the announcement that the PT boat was sunk should indicate that square 1,1 doesn’t belong to the PT boat (assuming we fired square 1,3 last).  At this point, we would know that the destroyer is vertical with one of the squares on location 1,1.

Here’s another scenario:

In this scenario we got our first hit on square 1,1, then we fired 1,2 followed by 1,3, then sunk a destroyer at 1,4.  So now, the cell at 1,1 is the PT boat.  However, it could still occupy any of the remaining 3 squares (0,1 or 1,0 or 2,1).

Other possibilities include scenarios where several ships are lined up in parallel, causing a row of hits that don’t sink any ship, but are actually hits on many ships.

Conclusion

I believe I have covered all possible scenarios that will occur in battleship.  However, it would be wise to write a simulator that randomly positioned all the ships on a 10×10 map and then used the seek until hit algorithm followed by the algorithms described above to sink your ships.  Executing this simulator in a loop thousands of times followed by a test that scans the map and ensures that all ships have been sunk would be a good way to verify your algorithms are correct.

Also, if you are writing the game itself, then unit tests are a must.  You should set up each scenario and run a unit test based on the scenario to make sure each algorithm executes correctly.

One other aspect to keep in mind (assuming you’re going to write a battleship game and use these algorithms) is that this will be a very hard game to beat.  So you might want to have an adjustable game difficulty and dumb down a few of the algorithms when in easy mode.  You’ll also want to randomize your shots when seeking ships.  If you don’t, then the algorithm will always shoot in the same pattern and the person playing the game could catch on to the best places to hide their ships.

To make the game more difficult, you could get even more sophisticated and record the patterns that the human player uses when they hide their ships (assuming it’s only one person playing the game).  After a few dozen games, ship position rankings can be recorded, like battleship positioned near edge of map 80% of the time, or PT boat positioned near the middle of the map 60% of the time.  Then the computer can take random shots near the edge or in the middle first to increase the likelihood of hitting a ship early.

One other detail to note: I didn’t mention if each side takes one shot per turn or multiple shots per turn.  The algorithms described above assumed one shot per turn.  If you’re taking multiple shots per turn, then the above algorithms still apply, except it’s best to try and sink the discovered ship as quickly as possible.  If you can determine the direction that the ship is probably facing, then you can shoot an entire line to try and hit any possible positions that the ship is in.  It’s better to waste a shot or two and sink a ship as fast as possible, which would reduce the number of shots the enemy can take.
 




 

Game Algorithms (Part 2)

Introduction

If you read my last game algorithm blog post you’re probably screaming at me “Where’s the rest of the game AI ?!!”  So in this post I’m going to go more in depth on searching for a ship to sink.  In a future post, I’ll show how to figure out where to fire once a ship has been hit once in order to sink it with the fewest moves possible.

What About the Destroyer?

First, I’m going to demonstrate what happens if the size of the ship has changed.  If you downloaded the sample code from the last game algorithm blog post, you’ll see that there is a variable name that you can pass into the main method called lengthOfShip.  If you change that to a 3, you’ll see a resulting map firing solution like this:

Which is not the solution we’re looking for.  We are expecting something like this:

Which is one less shot and equal to 25 / 3 (rounding up to capture the last location).  The reason for the mapping error is due to the fact that we have more than one possible arrangement for choosing the next shot.  In this case the edge shots are all equally ranked and the algorithm went off course when it chose the first edge case of 0,2.  Here’s what the list looked like at this point:

0,2 [3]
0,3 [3]
1,4 [3]
2,0 [3]
2,4 [3]
3,0 [3]
4,1 [3]
4,2 [3]
0,0 [2]
0,1 [2]
0,4 [2]
1,0 [2]
1,3 [2]
3,1 [2]
3,4 [2]
4,0 [2]
4,3 [2]
4,4 [2]
1,2 [1]
2,1 [1]
2,3 [1]
3,2 [1]


If the algorithm had chosen 0,1 or 0,3 first, then it would have worked out.  In order to ensure that we get the best outcome, we could implement a look-ahead algorithm, but I’m going to move on for now, because there are other issues to consider and this whole problem could work out on its own.

So I ran this with a battleship (4 spaces) and this is the resulting pattern:

It appears that ships with even number lengths work and odd does not.  I can try a carrier, but I’ll have to increase the map size, otherwise it’s just a trivial diagram.

My purpose in pointing out the fact that even numbered ships happen to work out is that we are going to eventually be searching for the PT boat (unless we get lucky when we search for another ship and hit it early on).  Let’s say we start with the carrier and we get a hit, then we switch to the battleship and we get a hit (I’m assuming we don’t hit a different ship).  Once the carrier and battleship are sunk we can search every 3 squares to find the destroyer and sub.  The problem with this algorithm is that we will eventually start hitting odd numbered squares.  If we start by searching by every four squares, we’re guaranteed to hit a carrier or a battleship.  For a 10×10 box, we will hit both of these within 26 shots.  Then we can switch to the 2 square search mode and we are guaranteed to hit the remaining ships within an additional 34 shots (for a total of 50 shots).

But, I’m not happy to just guess at which search algorithm would be best, so I’m going to write a dumb and dirty program to randomly position all the ships on a 10×10 board and use a step-down pattern of 5,4,3 and 2 to see how many shots it would take to sink all ships.  Then I’m going to try and use only even numbered patterns 4 and 2) to do the same.  Then I’ll compare.  To make sure I get the maximum shots, I’ll have to loop and put in random ship positions thousands of times.  I could create a program that finds every combination of ship positions, but I think random positions will save time and get close.

So I ran the loop 20,000 times for each algorithm to see what I could come up with.  Then I re-ran each algorithm several times to see if the max number would change and I came up with this:

Step down algorithm (5,4,3,2,): 59 shots, max
Even algorithm (4,2): 40 shots, max

The difference between the two algorithms is much larger than I expected, but it seems conclusive to me that an algorithm that searches every 4 squares until the largest un-sunk ship is a length of three, then every 2 squares is the most efficient algorithm.


Download the Code

If you want to experiment with the code yourself, or you want to use my methods as part of your own battleship game, you can download the code from my GitHub account by clicking here.

 

Game Algorithms

Intro

I have a few blog post subjects in progress, but they’re going to take some time to develop the sample applications that I’ll need in order to explain the techniques that I’ll be blogging about.  In the mean time, and due to a little A.D.D. on my part, I’m going to do a blog subject that is more of an analysis process.  I’ll show some of the complex ideas that go into designing an algorithm and ensuring it’s success.

Battleship

So I was playing battleship on my iPad.  It’s a great time-killer and my goal is to beat the enemy with as few moves as possible.  In this rendition of Battleship, you start with 5 ships and you get one shot per ship per turn.  So you start the game with 5 shots per turn, until the enemy sinks one of your ships, then you only get four shots per turn.  The strategy of this version is a bit different from the one-shot-per turn variety.  First of all, if you expect to win, you need to cut down the number of shots that your enemy gets to take per turn, so it takes him longer to find your ships.  So that means that as soon as you get a hit, you need to sink that ship immediately, even if you waste a few shots.

Before I get to the strategy of what to do when you get a hit, I’m going to discuss how to minimize your shots to get that first hit.  In order to hit all ships with a minimum number of shots, you’ll need to account for the PT boat.  This is the smallest ship in the fleet and it takes up 1 square by 2 squares.  That means that you can technically shoot every other square in a checkerboard pattern and hit a PT boat with a maximum of 50 shots (10 x 10 / 2).  Here’s what the pattern might look like:

If the game board contained only one PT boat and you followed this pattern, then eventually, you’ll hit that boat within 50 shots.  This is much more efficient than just randomly shooting on the board because any shots next to each other is a wasted shot.

There is something else here worth considering.  First of all, what are the chances that a PT boat is in the upper left corner?  Since there are only two possible positions that a PT boat could occupy the corner square, there are only two possibilities of hitting a PT boat in that corner.  Contrast this with a square that is on the edge of the map and then there are three possibilities that PT boat is in that position.  If the boat is away from the edge, then there is the possibility that a PT boat could be positioned from four directions.  So it would seem that an algorithm that shoots the edges of the map and the corners last will eliminate more positions that the PT boat could be in.  Of course, this would make for a weak algorithm because sooner or later the opponent is going to catch on to this strategy and position their PT boat in one of the corners.  But let’s ignore that for now and go on the assumption that we want to fire the next shot and maximize the possibility of hitting the PT boat.

The first algorithm we’re going to need is to collect a list of each possible location of a PT boat on the board.  I’m going to cut the map down to a 5 by 5 map to make this easier to visualize, but here’s the list of possible PT boat locations:

0,0 (Vertical)
0,0 (Horizontal)
1,0 (Vertical)
1,0 (Horizontal)
2,0 (Vertical)
2,0 (Horizontal)
3,0 (Vertical)
4,0 (Vertical)
0,1 (Vertical)
0,1 (Horizontal)
1,1 (Vertical)
1,1 (Horizontal)
2,1 (Vertical)
2,1 (Horizontal)
3,1 (Vertical)
4,1 (Vertical)
0,2 (Vertical)
0,2 (Horizontal)
1,2 (Vertical)
1,2 (Horizontal)
2,2 (Vertical)
2,2 (Horizontal)
3,2 (Vertical)
4,2 (Vertical)
0,3 (Horizontal)
1,3 (Horizontal)
2,3 (Horizontal)
0,4 (Horizontal)
1,4 (Horizontal)
2,4 (Horizontal)

As you can see, I’m starting at zero, and the max coordinate is 4.  Now, let’s get all the cells that each of these ships could occupy and make a sorted list of these cells and how many times the cell can be occupied by a PT boat.  This is just a brute-force program designed to prove a point that we already know.  So here goes:

0,0 [2]
0,1 [3]
0,2 [3]
0,3 [3]
0,4 [2]
1,0 [3]
1,1 [4]
1,2 [4]
1,3 [4]
1,4 [3]
2,0 [3]
2,1 [4]
2,2 [4]
2,3 [4]
2,4 [3]
3,0 [3]
3,1 [4]
3,2 [4]
3,3 [4]
3,4 [3]
4,0 [2]
4,1 [3]
4,2 [3]
4,3 [3]
4,4 [2]


OK, so now we can see that squares like 0,0 (corner square) only occur twice and squares that are not near the edges (like 1,1 and 3,1) occur four times.  What this means is that if the user randomly positions their PT boat at any of the possible coordinates and orientations, then there is a greater chance of hitting that boat at square 1,1 than at square 0,0.

Here’s what a corner square looks like (showing 2 possible locations of a PT boat):


By creating an algorithm that spits out this list and then ordering the list by largest occurrences to smallest, we can choose which square to shoot.  Now we need to enhance this algorithm to ignore any squares that have already been shot.

So let’s say that position 2,2 was shot last turn and it was a miss.  Now what possible locations are left for our PT boat and what is the occurrences?

0,0 [2]
0,1 [3]
0,2 [3]
0,3 [3]
0,4 [2]
1,0 [3]
1,1 [4]
1,2 [3]
1,3 [4]
1,4 [3]
2,0 [3]
2,1 [3]
2,3 [3]
2,4 [3]
3,0 [3]
3,1 [4]
3,2 [3]
3,3 [4]
3,4 [3]
4,0 [2]
4,1 [3]
4,2 [3]
4,3 [3]
4,4 [2]

Notice how there are only 24 squares above.  That’s because we’ve already shot at square 2,2 and that doesn’t appear in the list anymore due to the fact that a PT boat can’t be located at that square.  Also notice how square 1,2 (adjacent to 2,2) has been reduce to a 3 from a 4.

What would happen if our algorithm was changed so that we would just grab the first largest hit count square and fired a shot, then recomputed and continued until all hit counts reached zero?  Would the computer take 25/2 shots in total?  What would be the shot pattern that results?

Here are the results:

1,1
1,3
2,2
3,1
3,3
0,2
2,0
2,4
4,2
0,0
0,4
4,0
4,4


That’s 13 shots, which is correct and here’s what it would look like on the map:


The next algorithm to consider is an algorithm to sink a ship after it has been discovered, but I’m not going to go over that algorithm in this blog post.


Get the Code

You can download the code at my GitHub account here.  I have commented logging as I went along but you can uncomment the log statements and view the raw data in the log file which will be located in the C:logs directory.


 

 

The Game – Artillery


Summary

So BattleField One has gotten a little more serious.  My goal in this project is to design and build a strategy game engine.  Eventually I’ll demonstrate how to modularize the interface so that the game can operate with DirectX instead of a web-based interface using SVG.  My method of development is to do this in tiny chunks the way that XP programming is performed.  I never want to get into a situation where I need to do months worth of work in order to get the program back into a playable position.  So I’m building a feature and making the game playable, then building a feature, etc.




Artillery Units


In this blog post I’m going to show how to incorporate the unit range feature by adding artillery.  For those who have no military knowledge, artillery is nothing more than a large cannon with lots of range.  Artillery positions are normally miles away from the target.  But artillery and their crew cannot see very far away, so they need a spotter.  There is also a movement restriction on artillery, but I’ll be ignoring that for now (most artillery need a vehicle to tow it into position). 


So I drew a unit type and modified the game to include this unit in it’s case statement (see the UnitClass.cs file).  Here’s what the new unit looks like:


This unit has an attack strength of 14 a defense of 2, the range is 3 hex cells and it is able to move one cell per turn.  The tiny “14” at the top is the unit number, which I use for troubleshooting purposes.  I have updated the javascript side of this program to prevent this unit from attacking an enemy unit that is not visible.  I also updated the SnapTo() javascript function to allow a range greater than 1.



New Map

I designed a new map to represent a beach invasion scenario.  The new map looks like this:


The ocean cells will block any unit from passing.  The beach cells act the same as grass.  The goal of this game is to take all cities that the German units are protecting.  So I modified the CheckForEndOfGameCondition() method to call a new object that can be initialized with different goal conditions.  The new object is called VictoryCalculator().  It can be setup to a condition where the enemy (or allies) must defend a given number of cities instead of just destroying all enemy units.  I have also designed to to be extendable to allow game conditions where German or Allied units must retain a certain number of units to win.  I don’t currently have a game turn limit and (number of turns to meet objective) but it could also be added to this object in the future.

Getting the Code

You can go to my GitHub account and download the zipped up version of this project (Click Here).



 

The Game – Forest Terrain

Summary

In my last blog post on the game I demonstrated how to setup blocked terrain cells (aka mountains).  Now I’m going to introduce a forest cell that will block tanks but not infantry.


The Forest Terrain Type

I wanted to introduce a forest terrain type so that I could prevent tanks from penetrating (assume this is a forest of very large trees), but allow infantry to penetrate.  First, I used the same Google Maps screen shot technique to create a forest hex cell:


Then I setup a test map to test my shortest path algorithm:


Modifying the Code

In my previous code, I created a property to handle the blocked terrain.  This was located inside the GameMap object.  In order to test both the terrain and unit combinations I had to change this into a method that uses the unit type integer as a parameter.  The forest terrain number is 7 and a tank is unit type 2.  So I setup the Blocked() method to check for this combination and return true (as in, terrain will block this unit type).  Eventually, I’ll need to extend this simplistic method to include an array of terrain types verses unit types.  Before I do that, I’ll probably introduce a technique of slowing down the progress of a unit.  For this instance I’ll make the unit travel slower through the forest.  For now though, I’m going to just provide a flag for blocked or not blocked.

Now that the Blocked property has been converted to a method, any calling methods need to be re-factored to pass the unit type.  Then I tested to see if the tank went around the wall of forest and the unit went through the forest.


Adding Unit Tests

I ended up adding the unit tests after I made this work.  Technically, I could have added them first and used the unit tests in order to build the code.  The purpose of adding unit tests after the fact is that I want to make sure that future changes don’t break this feature.  So you’ll see two new unit tests that will test an infantry unit and a tank unit path calculation for the sample map above.


Getting the Code

You can go to my GitHub account and download the zipped up version of this project (Click Here).

 

The Game – A* Algorithm

Summary

I’ve been working on this game called Battlefield One and it has a very simple algorithm for computing the next move that an enemy unit will take in order to reach it’s goal.  The algorithm used searched all 6 surrounding hex and eliminates illegal hex points (off the grid or occupied by a unit).  Then it computes the distance from each grid point to the destination and takes the shortest one.  In this blog post, I’m going to put in some obstacles in the game and demonstrate the flaw in the algorithm I chose.  Then I’m going to demonstrate how to use the A* algorithm to work on a hex grid instead of an 8-way or 4-way square matrix.

Adding Mountains

First, I painted a mountain hex in Photoshop.  You can make up any hex terrain you wish, but I just went to Google Maps and copied some of the Rockey mountains onto the clipboard and then pasted it into a hex block and erased to match the hex shape:


Then I turned off the green hex shape layer and saved my hex-shaped mountain terrain as a mountain.png file:


Fortunately, I had planned on having many terrain types, so I coded the DrawTerrain method to contain a switch for each terrain picture to render.  If you look at the code at GitHub you’ll see there are 4 grass terrains (I added some variety) and a new “mountains_01.png” terrain file type.


Next I modified the GameMap object to include a new “Blocked” property.  If the terrain is equal to 6 (representing a mountain terrain type), then Blocked returns true, otherwise it’s false.

The FindAdjacentCells(x,y) method inside the GameBoard object was modified to use this Blocked property.  This method will return all cells that are on the map board but not mountain cells.  There are several unit tests that check different conditions (edge of map, corner of map, near mountains and in the middle).


Now to setup a test board to test the blocked cells:


This is a 7 by 6 cell gameboard with a German unit on cell 0,3 a city on cell 6,3 a spare allied unit in the lower right corner (to keep the game from ending with a German win).  Finally, I put a line of mountains blocking the German unit from reaching the city.  With the simple straight line algorithm of navigation, the German unit will go to the wall and toggle between cells 2,3 and 2,2.  



The A* Algorithm

Next searched for an A* algorithm that I could adapt.  I ended up using this web site to explain the details and I wrote the entire thing from the ground up:

A* Pathfinding for Beginners

The A* algorithm uses two lists to contain search nodes.  The open list and the closed list.  I created an object that represented one search node and called it AStartNode.  This node needs to contain the F, G and H variables as described in the beginner guide (I set those to integers).  The F variable is nothing more than G + H, so I just made a getter that adds G and H and returns the result as F.  The next variables I needed was the X,Y coordinate of the cell that this node will represent and finally the location of the cell that was searched from (called Source).  The constructor for the AStarNode just stores the values in the getters and then it computes the distance to the destination (which is an approximation of the distance as the crow flies).

Next, I created a list to contain AStarNodes.  This generic list class is called AStarNodeList (yeah, not creative, but obvious).  Instances of this list becomes the open and closed lists.  That means that I can put all the methods I need inside this list to manipulate the nodes being processed.  The FindSmallestNode() method is very useful.  It finds the node with the lowest F value and returns it (after it removes it from the list).  This is where I will grab the smallest node and find all it’s surrounding nodes and then push it on the closed list.  I created a Contains() method to be used when I get surrounding nodes and I want to not save the ones that are already in the closed list.  I created a GetNode(x,y) so I can read the nodes off the list in order to build the way point list (the goal of this whole exercise).

Next is an object called ShortestPath.  This object is what does the work of putting the first node on the open list, then calling the FindPath() method which will recursively find the smallest node and find it’s neighbors until it runs into the destination point.  I put in an iterations counter and made sure I exited if it hit 50.  This max might need to be incremented if the map size is larger (you’ll know if the unit goes almost to its destination and stops).  I wanted to make sure I didn’t get an infinite loop while I’m testing.

There is a method called GetWayPoint(x,y) inside the ShortestPath object.  This is used by the game to get the next way point.  Basically, to ensure that I can provide backwards compatibility, I just made my CollectGermanMovementData() method call this method first.  This method will check to see if the WayPoint list has any nodes.  If not, then a null is returned and CollectGermanMovementData() will grab the coordinates using the old fashioned direct calculation method (because lCoordinates will be null).  If the first way point variable is equal to the unit x,y coordinates, then it is removed and the next coordinates are returned (but not removed from the list).  The reason this is left on the list is in case the unit runs into an allied or even a German unit and is temporarily blocked.  For now, it will stop and attack (if Allied unit) and continue on its way when it is no longer blocked.  In the future, I’ll make it recompute the path (if it’s just going around and not attacking).  Baby steps.


How to Build Something This Complicated

This algorithm is a bit complicated and there is a lot going on.  So I create a visio document with the test map fully numbered.  Then I plotted the F, G and H numbers for the first iteration:


I also put arrows on the diagram to point to the previous cell.  Then I put a breakpoint in my AStarNode object and I ran the program.  The first AStarNode was node 0,3.  Then 0,2.  That’s when I checked to make sure that G=1, H=6 and F=7 (the red numbers in the corners of each cell).  Then I checked the next cell, which turned out to be cell 0,4, and so on.  On the next iteration, things got a bit complex so I added Log4Net to my application, spit out the node being worked on and listed the nodes that were pushed onto the open list.  Eventually, I was able to walk through the log file and see the order that the algorithm was using to walk toward the goal of cell 6,3.  

The last task of this project was to make sure the list was read back into the way point list.  You have to walk the list backwards because the AStarNode contains the x,y coordinates for the previous node.  A simple while loop walked this back to the starting point and I just inserted it backwards into the WayPoint list, leaving the starting point out of the list (since the GetNextWaypoint() method takes care of that anyway.


Get the Code

You can go to my GitHub account and download the zipped up version of this project (Click Here).  Assuming you have Visual Studio 2012 or better, you should be able to re-build the project and make this work.  If you want to run the sample as shown in this blog post, you can go to the HomeController.cs file and change the GameData.InitializeGame(1) to a 3.  Then go to the GameBoard.cs file (in the core project) and at the top is a TestMode boolean variable that you should set to true.  Then run the game and you’ll see the map pictured earlier in this post.  You can just click the next phase button and watch the German unit navigate to the city on the right side of the map.  If you want to dig through the code, you can un-comment the log4net logging inside the ShortestPath.cs file and run the program, then look at the log file (which will be located in c:logs.

Last, you should take a look at how the non-A* algorithm failed.  You can do that by going to the GameClass.cs file.  Search for the SetEnemyStrategy() method and you’ll see two places where the ComputePath() method is called.  Comment these two lines and run the program.  You’ll see the German unit walk right up to the mountains and get stuck going back and forth.

 

Game Design, Back to Battlefield One

Summary

A while back I wrote a sample game called Battlefield One.  This game was a turn-based war game that was built on SVG, javascript and C#.  I have since converted this game into an MVC application (although it still uses the same code-behind techniques and I keep track of the game state with a session).  I have also refactored much of the game to expand it, add unit tests, make the dimensions more flexible and I added tanks.
 

Review

OK, here’s how the game was designed:

1. The game board is rendered in hex cells.
2. Game units do not stack, only one unit can occupy a cell at a time
3. Attack distance assumed to always be 1 for simplicity.
4. No terrain effects.
5. Capture all cities to win.
6. Destroy all enemy units to win.
7. Movement phase then attack phase.
8. Areas of board not visited will be blacked out.
9. Areas not visible to any unit will be dimmed and not display any enemy units.

I improved the AI some since the first game was written:

1. Enemy units will attack the lowest defense numbered unit.  This causes many enemy units to gang up on one nearby unit.  Reducing the number of Allied units quicker and reducing the number of future Allied attacks.

2. All enemy units will choose a city to move toward.  

3. There is a test flag in the GameBoard object that will allow you to turn off the masks so you can test the game.  This mode will also draw red lines between the units and the destination they have chosen.

4. If there are two allied units next to an enemy unit and one allied unit is on a city, the enemy unit will attack the unit on the city first.


Algorithms Used

The Die Roller object was improved.  Instead of using one 6-sided die, I used a combination of three die rolls.  The problem with one die is that the outcome is linear and the game is boring.  As you use more dice, the outcome becomes more like the normal distribution of events and your attack and defense outcomes become more realistic.  This was not much of a problem until I introduced tanks which could inflict a damage of 1 or 2.  I wanted to have a damage of 1 occur more often than a damage of 2.  Wolfram Alpha has an article on this here.  My interest was in this chart (from the wolfram article), which explains it all visually:




I added unit tests to complex parts of the game.  The original game was written without any unit tests.  This was due to the fact that the original game was only a demonstration of what can be done and I only needed it for an example in a blog post.  Now I intend to turn this into a project (aka hobby) that I will add features and blog about the features (like AI enhancements).

I added a unit list class.  This is a list of units for the entire game and it allowed me to refactor some methods that were performed against the list of units.   This object also has an AddUnit method to insert a unit into the list without referencing the list of units (called “Items”) directly.

I added a game board class to contain all the information and methods pertaining to the game board itself.  Each cell now references a GameMap object containing variables for the terrain, mask and visibility settings.  The previous version of this game contained three arrays to keep track of this information and I wanted a way to be able to change the game board size at game startup.

I changed the map background pieces into individual hex pictures so I could create a board of any size.  The original game had a large painted background that was fixed in size and had 4 cities painted in place.  By creating hex images of the green areas and a hex image of a city, I can just set the array at game start with the map size and city positions I want.  Future versions can contain a mixture of different textures to make the game more interesting.

There was a bug involving the movement of playing pieces.  The movement calculator would follow a straight line and then snap the unit to the closest board hex.  The problem with this algorithm is that any piece traveling close to the edge of the map would stop because the closest hex position was off the map and the edge detector prevented the unit from going off the board.  The new algorithm gathers a list of up to 6 surrounding hex squares.  It will eliminate any hex that is off the board and any hex that is already occupied by another unit.  The remaining list of hex positions is measured by distanced to the destination and the shortest one is chosen as the next hex to enter.  This allows units to go around each other if necessary and the destination will always be reached unless it is totally blocked.


Playing the Game

You can go here to play the game on-line, or you can download the source code and experiment with the code yourself.  To download the source code, go to https://github.com/fdecaire/BattleFieldOne and download the zip file (there’s a button in the lower right corner).

 

The Game (Part 4)

I have implemented the mask and view capabilities.  I’m calling this version 2.  Here’s a sample screenshot of how it looks in action:

The first thing you’ll notice about this map is that unexplored areas are colored in black.  These will uncover as allied units are moved around the map.  The darker areas are areas that are not visible but have been explored.  These areas could have enemy units hiding there.  Every time an allied unit is moved the view map is recomputed in JavaScript (and a duplicate array is maintained in C# in case the player refreshes their browser).  The unexplored areas are initialized at the beginning of the game and are cleared as units are moved.  Both the JavaScript and C# code have functions/methods to deal with this mask.  The difference is that the JavaScript doesn’t maintain an array of cells that are explored because they are just set to hide the mask whenever a unit passes by and they are never set back during the game.
The two masks are identical and use the same image to paint over top of the entire board.  I set the opacity to 0.3 for the view hex pictures so the player can see the terrain under it.  I also manually set the display value of each enemy unit to match the value of the view mask.
Here’s the code: Battlefield One Code V2
You can go directly to my website to play the game as is: (temporarily down).
I’ve played the game a few times and it is a bit more challenging than the first version without the masks.  I think my next enhancement will be adding a variety of different unit types.  I might have to enlarge the playing board to allow more playing pieces.
Stay tuned…
Note: I have recently upgraded my website to use MVC4 and .NET 4.5. I have refactored my code to make the game work on MVC4.  Click here to try it out.

 

Follow-Up on Designing a Game

So I designed and created a small game to demonstrate several techniques.  First, I demonstrated how to contain the scope of a project to ensure it gets out the door.  While this was only a tiny project, my goal was to create a working game over the span of a weekend or possibly a week (It took me about 24 man-hours of labor in total over a span of 5 or 6 days).  Technically, I did not track my hours and I did not estimate the development time of this project.  For any projects taking more than a week, estimates should also be included.  Also, if you review the design specifications and match it with the actual game, you’ll notice a few missing features.  Notably, there are not armor units, it’s legal to move past enemy units and the “next phase” indicator is not very visually appealing.  Chalk it up to time constraints.  I wanted to get this out the door so I could blog about it.  If this were a real game, I’d have to spend much more time polishing it to make it more visually appealing.

About the Game

One important thing I forgot to do in my last blog post was explain how to play the game.  It’s somewhat trivial to figure out, but for those who have never played any Avalon military board games, it goes like this:

1. The game phase controls what can be done on the board, starting with the allied move phase.
2. When in the move phase, you can move your units.  Each unit that has been moved will have their movement allocation decremented to zero.  So you can’t move the unit again for the current turn.
3. Once you are satisfied with your unit moves or you have no more units to move, you can click the “next” button to advance to the allied attack phase.
4. During the allied attack phase you can attack any enemy unit that is next to one of your allied units.  If you are not next to any enemy units, then you must skip the attack phase.  Each unit can only attack once for this turn.
5. Once you are satisfied with this phase, you can click the “next” button to advance to the next phase, which is the axis movement phase.
6. Now it’s the computer’s turn to move its units.  The computer will move units around the board and automatically advance the phase to the axis attack phase.
7. When the computer is in the axis attack phase it will attack any allied units that are next to one of its own units.  Then it will advance the phase to the allied movement phase.
8. Continue to step 2 until an end condition is met.

Game End Condition

The game ends when either all 4 cities are captured or all units on the allied or axis side are eliminated.

Weaknesses in the Current Game

If you play this game a few times you’ll notice that it’s about as difficult to play as tic-tac-toe.  It becomes predictable and it’s easy to formulate a strategy to beat the computer almost every time.  One problem is that the dice roll is biased toward the defense.  This is due to the fact that all units have an offense of one and a defense of two.  If you look at the ComputeBattleResult method of the GameClass object, you’ll notice that it’s just hard-coded at the moment.  I did that because there is only one type of unit on the board.  To expand this game it will be necessary to use the unit index parameters to lookup the offense and defense of the two units and use a lookup table (or a formula) to compute the odds.

The second problem is that the enemy only has one strategy.  Divide its units into 4 groups of units and march them to each of the four cities.  Attacking allied units along the way.  If you manage to destroy the 3 units heading to one particular city, the enemy will not dispatch additional units to reinforce the hole in its strategy.

Options for Fixing the Game Play

One option to fix the game play is to introduce a variety of different units.  Many of the methods that assume there is only one type of unit will need to be altered to make sure the defense and offense are accounted for.  New units should maintain the single movement allocation and range of one to keep this under control for now.

A second option is to add a mask to the play field.  This could be done by creating black hexagon images that can be written over the board positions not explored by the allied units.  Obscuring what has not been seen yet.  This will only have minimal impact for those who play the game more than once because they don’t need to re-explore a map they already have memorized.

An alternative or addition to the second option is to create a mask of areas not currently visible by allied units.  This can be accomplished by dimming the hex areas where allied units cannot see and not rendering any enemy units under the dimmed areas.  The background will be visible but enemy units not in visual range will not be seen.  Using this technique in combination with alternate enemy strategies has the potential to make the game more challenging.

Other Possible Enhancements

1. Allow stackable units.  The top unit could contain an icon with the word “stack” in it to indicate that it is a stack of different units.  Offense and defense numbers should be totaled for the top unit.  Complications arise from the fact that units must now be stacked and un-stacked.  Moving a stack needs to be accounted for.  Attacking an enemy unit should account for the entire stack.  I would propose doing the stack bookkeeping in the C# code and replacing all the units in the stack with a special unit in the JavaScript.  There is also the issue of attack.  This should be changed to provide a partial kill instead of all or nothing.  Offense and defense number would need to be decremented as the attack is occurring and units in the stack need to be destroyed if the defense level is too low to support them.

2. Combine attack and movement phases together.  There really is no reason to have a separate attack phase.  If the allied unit is moved into an enemy unit, then it would be considered an attack.  There is one possible issue:  If the range factor is used and a unit has an attack range of 2 or more, then there needs to be a control to determine if that unit is attacking an enemy.

3. Enhance enemy strategy.  The enemy AI can be expanded to provide 2 or more different strategies.  Even a un-sophisticated algorithm could use a random number at the beginning of the game to choose a strategy and then use that throughout the game.  Each strategy can be designed and tested one by one and then randomized when each strategy is completed for the final version.  Also, each strategy can have some intelligence built in.  For instance, in the current strategy of marching to each city, if a group of units is destroyed, then one unit from each other group can replace them.  if the enemy has too few units to hold all cities, then the AI can switch strategy to attempt to hold one city or just battle the allied units in the hope of destroying all allied units.

4. Allow longer movement allowances.  This is tricky because now we’ll need to implement the ability to block units so they can’t just slide past allied units (and vice versa). 

5. Add terrain effects.  One weakness of the map board is that it only has flat grassy fields with a  movement factor of 1.  Adding roads with double movement factors can make the game more interesting.  Also, a river with bridges.  Units can be blocked by rivers and must use a bridge.  Rivers can be used to form natural boundaries and choke points.  This will complicate the destination problem of the AI because now a path finding algorithm must be implemented (like the A* algorithm).  Mountains can be used as a 1/3 movement factor and forests a 1/2 movement factor, allowing for more choke points.

6. Weather factors.  Most physical board games have a random weather factor that changes for each turn.  Weather factors can modify movement (like snow, all movement cut in half) and offense effectiveness or visibility.

7. If a visibility mask is used, then scouts should be added to the game.  These would be fast units with long visibility, but possibly a zero defense and offense.

8 . Random map boards.  Civilization does this very well.  A completely random map can be generated at the beginning of the game.  This would improve the enhancement of obscuring the map until explored, since there is no way to be certain what terrain is under the obscured areas.  This also increases the challenge of the game for repeat players.  Every game is unique.

Conclusion

I think I’ve indicated how fast the scope of this game can expand to occupy all available free time of any programmer.  I’m sure anybody can think up other features to add to this game that would make it more interesting to play.  The best way to tackle a project like this is to prioritize the desired enhancements and focus on one enhancement at a time.  This will keep the game playable while each enhancement is added rather than attempting to do it all and working endlessly for months on a game that doesn’t work (not to mention attempting to debug it all at once).