In this lab you will work with three or more group members to make a game that automatically plays it self. Besides improving your programming skills, I hope that you learn:
· Different implementations and cost of priority queues
· Different implementations and cost of maps
· Basic structure of a turn based game
· The use of interfaces to organize a large programming effort
To prepare for this lab, before the lab you should
· Read text chapters about priority queues, maps and dictionaries.
· Read this lab description
· Meet as a group and divide the work (more on this)
· Submit your component of the game program to cs2321, secGlab or secIlab, preLab3, where secGlab is for students participating in a group labs and secIlab is for students participating in an individual labs.
If you are performing this lab alone you are to do all parts of the lab individually before the due date.
The instructor will divide the class into groups of 4 or 5 students. You will initially meet on your own to divide the programming. I expect you to divide the coding by:
· 2 or 3 students program their own army using the Army interface
· 1 student programs the board using the Board interface
· 1 student programs the game using the Game algorithm below
You may meet additional times on your own in order to coordinate your work. At the time of lab you will assemble the code and play the game. We will compare the results of all the games.
Battling Priority Queue is a turn based game, where armies deploy squads for skirmishes and retreat after each skirmish, and of course soldiers are lost during a skirmish. The battlefield, or board, also affects the army by increasing or decreasing the armies’ numbers. In effect the armies live on the land, so that their numbers are increased while the land is fresh, and as the land is used more armies can not find food and starve, decreasing their numbers.
The battlefield, or land, is called the board. The board layout is a nXn grid of locations, or nXn array, much like a checker board but the squares on opposite ends of a row or column are adjacent to each other; this can be accomplished by using circular arrays, or modular arithmetic. In affect the check board is warped around a sphere. Each location keeps track of its board type in the board layout; the board type will change as armies reside at the location. The board type is specified by a string and is mapped to an integer in the board map. The integer specifies the number of soldiers to add or remove to the resident army. This may seem like a lot of overhead for such a small affect but game designers plan to develop more elaborate board affects in the future, so a map is appropriate interface; the map values could be pointers to functions.
Armies are composed of three types of soldiers, men, elves, and dwarfs. Each soldier type is stored in a priority queue keyed by the soldier strength or skill. Squads of three soldiers are formed for skirmishes by removing the best soldier from each priority queue. During the skirmish warrioring soldiers are paired off by soldier type, and the stronger soldier defeats, kills, the weaker soldier. After the skirmish the squads retreat to their armies, defeated soldiers are not inserted back into the priority queue. Note that squads receive an advantage during skirmishes dependent on how fast they deploy and retreat. The time for deploying and retreating is determined by counting the number of priority queue instructions, more on this later
The Game, which is the game engine, manages the turns of the game. Initially the game reads the number of armies, board size, initial board type map, and lay out, the game engine randomly locates the army. Each turn will consist of boardAffect, which adds or remove soldiers to the armies, followed by determining the result of a skirmish. Finally the Game moves the armies. See algorithms below. When one army is victorious the summary information is printed out
· Victor, average count per turn
· Defeated, average count per turn
· Board Map average count per turn
· Total count, and turns
For this lab we will want to keep track of the number execution. We will accomplish this by implementing all data structures by extending CountingArrayList, which extends java.util.ArrayList and implements CountingDS. ArrayList is a sequence implemented with an Array that has amortized constant insertion into the array. Studying CountingArrayList and CountingDS, you will notice that it keep tracks of two integers, totalCount, and recentCount. totalCount stores the number of instruction execution since creation of the ArrayList, while recentCount keeps track of the number instruction execution since the last call to recentCount(). Also look at the other methods in CountingArrayList, they first update the counts and then call the super’s same method. You may want to study the cost of each method, while designing your data structure. Note that you can implement trees with CountingArrayList by using level numbering.
Study the interfaces in Board.java. Board has two data structures:
· Layout
· Map
Layout is an nXn array of strings, which specifies the board type at a location using Point. Layout should perform modular arithmetic so that all integers, positive or integers, map to a board location. Layout does not need to count instructions.
Map defines the affect of a board type. The affect is an integer that specifies the number of soldiers to add to the army, so strings are mapped to integers. Map should count the number of instructions executed for an operation. If Map is a compound data structure, for example a hash table using separate chaining, then all data structure components should be implemented using CountingArrayList. Map should update count by summing all counts of the involved data structures. Make sure it is accurate.
The board should be programmed for any size layout or map.
You should program your board by extending Board, give it a good name. An appropriate name should end with Board, for example EuropeanBoard. This java file is submitted to the pre-laboratory submission.
Study the interfaces in Army.java. There are three soldier types
· man
· elf
· dwarf
Each has its own priority queue, which should be implemented using CountingArrayList, and CountingDS. I do not imagine that you will use compound data structures. All three priority queues in an army can and probably should be implemented the same, but different armies should implement different priority queues. Note that you can implement tree structures with CountingArrayList by using level number.
Empty priority queues should return an entry with zero strength, which will be interpreted by the game engine has a solider with no strength.
You should program your army by extending Army, give it a good name. An appropriate name should end with Army, for example RedArmy. This java file is submitted to the pre-laboratory submission.
The game engine is the heart and soul of the game. Note this game engines plays automatically with little input from the players. The game engine general algorithm is:
Initialize the game, board and armies
Until victory or tie do
play turn, move armies, and resolve skirmish
Print summary info
Please study the algorithm, they should explain the details:
Algorithm Game
// Initialize game
int numArmy = read number of armies // probably two
// Note rest of the input specifies the board and could be read by the board
int n = read() // size of board
Make Board board = new Board(n)
While reading map do board.map().put( String(read key), read value)
// Note key is read in as a double or integer but converted to a string
For each point on the board do board.layout().replace(point, read type)
// End of board sepcification
Make Army[] army[numArmy] // Note that each army is different
For each army do
army[i].setLocation( randomly select vacant location on board);
int turns = 0 // counts the turns in the game
// Game loop
Until only one army not empty and turns != 0 do
turns++
For each army do
army[i].setLocation(
randomly move to an adjacent vacant location on board )
boardAffect( army[i] )
For each pair of army, army1 and army2 do
If
army1.getLocation().isAdjacent(army2.getLocation()) then
battle(army1, army2)
// identify tie
If both armies empty then tie
Print summary info // winner or tie, average count per turn
end Game
Algorithm int
boardAffect(army)
// Get location board type
Point location = army.getLocation()
int numSoldiers = board.map().get( board.layout().get(location))
// Create new board type by subtracting from current type
// Note this is only pseudo code, see the spike TestStrings.java for implementation detials
board.map().put(String(numSoldiers-1), numSoldiers-1)
board.layout().replace(location, String(numSoldiers-1))
If numSoldiers < 0 then
numSoldiers = -numSoldiers
While numSoldiers > 0 do
army.removeMax()
count = army.recentCount()
numSodldiers - -
Else
While numSodliders > 0 do
int strength = randomly selected strength between 1 and 5
army.insert(new Squad(strength, strength, strength))
count = army.recentCount()
numSoldiers - -
Return count
End boardEffect
Algorthm battle(army1, army2)
Squad squad1 = army1.removeMax()
count1 += army1.recentCount()
Squad squad2 = army2.removeMax()
count2 += army2.recentCount()
// Determine deployment advantage
If count1<count2 then
deployAdv1 = 1
deployAdv2 = 0
Else If count1 > count2 then
deployAdv1 = 0
depoyAdv2 = 1
Else // count1 = count2
deployAdv1 = 0
deployAdv2 = 0
// Determine foray result
For each soldierType do
If squad1.
soldierType+ deployAdv1 < squad2. soldierType+ depoyAdv2 then
squad1. soldierType = 0
If squad1.
soldierType+ deployAdv1 > squad2. soldierType+ depoyAdv2 then
squad2. soldierType = 0
// Ties are automatically handled and both soldiers retreat to the armies
// Retreat, Note insertion updates recentCounts
army1.insert(squad1)
army2.insert(squad2)
End battle
Please ask questions in lecture or on the email list. The game engine programmer does not have an interface to extend, please give your game engine a good name. The game engine should be designer to play any number of armies. An appropriate name should end with Game, for example CivilWarGame. This java file is submitted to the pre-laboratory submission.
The input will first specify the number of armies playing the game. Then the input will specify the board, and could be parsed by the Board constructor. There are two sections to the input, first the Map is specified then the Layout. The first line is the keyword Map followed by key value pairs; the key should be converted to a string. The Map specification ends at the keyword Layout, which indicates the start of the layout section. The following token is an integer, n, specifying the number rows and columns on the board. The following n2 integer tokens specify the key at the Layout location, assume that they keys are specified row wise. The integers should be converted to strings.
Armies 2
Map
1 1
5 5
10 10
3 3
7 7
2 2
9 9
4 4
Layout 5
1
5
10
3
7
1
2
9
10
4
1
5
10
3
7
1
2
9
10
4
7
1
2
9
10
During the lab your group will assemble the code and play the game several times. Keep track of the game summary.
At the end of the lab you should write text document, battlingPriorityQueue.txt, which contains
Submit battlingPriorityQueue.txt to cs2321, secGlab or secIlab, lab4, where secGlab is for students participating in a group labs and secIlab is for students participating in an individual labs.
After finishing the lab you must individually complete a short survey to receive full credit for the lab, links to the surveys are found on the course home page.