Programming Lab 2: Artificial Intelligence and Pathfinding

Return to CIS 300.

Announcement: Bugs Found

Ship.cs

The method

  public bool CanFireNow() {
    return (COOLDOWN == 0);
  }

  public bool CanFireNow() {
    return (currCooldown == 0);
  }

AIControl.cs

Inside the method GetAction(GameTime gameTime), the code block

  if ((me.UniqueNum + gameTime.ElapsedGameTime.Ticks) % 10 == 0) {
    MarkGoalTiles();
    move = GetMoveAlongShortestShortestPathToAGoalTile();
  }

  if ((me.UniqueNum + gameTime.TotalGameTime.Ticks) % 10 == 0) {
    MarkGoalTiles();
    move = GetMoveAlongShortestShortestPathToAGoalTile();
  }

Objective

For this lab, you will take a game that has already been (hastily) constructed, and make it interesting by adding computer opponents. These opponents must be able to figure out how to move around the game board, acquire targets, fire at other ships, and generally try to win.

You will be designing the AI for the computer opponents. This will be done using a Finite State Machine (FSM) for each opponent. You must choose the nodes to use for your FSM's, direct when the AI shall change between states, and program behavior for each state.

While this may seem overwhelming, we have actually done a lot of the hard work for you already. Furthermore, this is not the only time you will see AI; we will have lectures on this later in the semester. The purpose of this lab is to simply give you enough tools so that you can "fake it" until you learn more.

Once again, this lab is not due during this lab period, but it is to your advantage to work through (and/or learn) as much as you can now, while assistance is immediately available. If you run into problems finishing the lab project later, please feel free to contact a staff member for help (Preferably a programming TA).

The Game

File: ShipAILab.zip

We have already set up the game mechanics for you. In this game, the player controls a ShipDemo ship on a large, 2-dimensional game board made out of tiles. You move the ship around the board by using the arrow keys. The spacebar fires photons in all directions from the ship. When a ship is hit by a photon, it gets pushed backward and the tile it used to be hovering over falls out of the board into space. If a ship is pushed by a photon off the board, the ship falls into oblivion and loses the match. The objective is to be the last ship remaining on the game board.

The photons blasting from a ship will be more powerful when the ship is above a "power tile." The power tiles are the blue tinted-tiles. If a ship is above a regular tile, it will fire photons in four directions. A ship over a power tile fires in eight directions.

You should start out this lab by unzipping the source somewhere convenient. You should know how to get this working from the previous lab. If you compile and run the game as-is right now, you'll notice a bunch of ships just sitting around, waiting to be shot off the edge by you. These are obviously the ships that need some intelligence.

There should be a pre-compiled executable binary of an example solution to this lab in the main directory. Run that to get a feel for how hectic the game can get when the computer-controlled ships know what they're doing (or at least look like they do). The example solution is not meant to tell you exactly what you need to make the game like, and it could certainly be improved upon, it is just included to give you a better idea of what this lab is about.

When running, you can press 'R' at any time to reset the game, which may be a time-saver when creating and testing your AI. In addition there should be a pre-compiled executable binary of an example solution to this lab in the main directory. You can run that to get a feel for how hectic the game can get when the computer-controlled ships know what they're doing (or at least look like they do.

Important: The example solution is written in GameX, the engine that this course used before XNA. Note that it looks very different. GameX has many faults, but it is much easier to mix 2D and 3D in GameX than it is in XNA. To simplify the engine, we have made the XNA version of the lab 2D only, so the games will look very different, even though the play is much the same. In addition, the example solution is not meant to tell you exactly how your AI should behave; it could certainly be improved upon. It is just included to give you a better idea of what this lab is about.

The Code

As before, the file GameEngine.cs controls most of what goes on in the game. Feel free to check it out if you want to learn about any of the game logic or the graphical effects (which have been considerably reduced for the XNA version of this game).

Other than the main code file, this project contains the following classes:

Board

This class contains all the tiles and their states. It also holds information on which tiles have been marked as goals or visited for the pathfinding algorithm you will need to use. Make yourself familiar with the functions available to you, as your ship AI will need to use them.

Photons

This class simply manages all the photons in the game.

Ship

This class contains collision checks for ships, keeps track of when they can fire photons, and of course holds their positions and status. Each Ship also has a ControlUnit.

ControllUnit

A ControlUnit tells a ship what to do. Or rather, it tells the rest of the game what the ship is requesting to do. The ControlUnit here is simply as an abstract class to get input from either the keyboard or the AI, determined by the actual class (either PlayerControl or AIControl).

PlayerControl

This ControlUnit takes input from the keyboard and uses that pretty much directly to decide what the ship should do. Only one ship in the game is currently set to PlayerControl; the other ships are AI-controlled.

AIControl

This ControlUnit calls AI functions to decide what the ship should do. This is the only class you should be concentrating on for this lab.

Note that by forcing all AI control to ultimately be given as a return value in the same way as player keyboard control, we completely avoid the problem of the AI being able to cheat or do things the player cannot. That is, unless you start arbitrarily calling functions that modify the game within the function that is supposedly just calculating the next move, which you obviously should not do.

AIControl

Take a look at the AIControl.cs file to learn what functions and data members it has available. Of particular note is the FSMState enum. This contains values for all the states used in the example solution. You may change these if you like. Which state a ship is in determines what type of behavior it will follow.

There are also stubbed functions in the AIControl.cs file. Your objective in this lab is to complete all of these functions and make sure the resulting game meets the criteria described at the end of this lab. Alternatively, you may replace these with your own functions if you think you can come up with a better AI or a better structure for your AI, as long as you achieve the same overall goal (again, see below).

ControlCode GetAction ()

This function is already finished, but you should look at it to see what is going on. The Ship AI will decide whether it needs to change states, and do so if it determines it should. Then, it will sometimes search the board for tiles it wants to get to, and figure out the best move to get there. Finally, it will try to move and possibly fire. Of course, this is only the high-level code that initiates these actions - you need to implement the lower-level functions that this one calls to get the AI working.

bool CanShootTargetFrom (int x, int y)

This should return true if a hypothetical shot fired from board position (x, y) might hit the target, and false otherwise. You do not need to take into account whether the target is moving (although you would want to do this, called "leading shots", in a game that requires significantly more precision). This function should return false if the ship has no target or if the tile is no longer on the board. The target also cannot be too far away from the given x,y position (because a shot only travels about 6 tiles in the x or y direction before it fades out). Recall that power tiles add the ability to shoot diagonally, which you must take into account.

bool CanShootTargetNow()

This should return true if the ship can hit the target from where it is now. Keep in mind that a ship cannot shoot if it has shot very recently, due to the shot cooldown.

void SelectTarget ()

Because there can be many ships on the board at once, to simplify the AI each ship will choose a "target" ship and focus solely on that one target. This function should change the target of the ship when necessary (it is necessary to select a new target when the current one is defeated or becomes impossible to attack). Every once in a while, to keep things interesting, you may also want to change the target even when it's not necessary to select a new one. In any case, be sure a ship does not target itself or any dead ships. Also be certain you do not get into an infinite loop when there aren't any valid targets, and make sure it doesn't flip between targets so fast it never gets a chance to attack them. A smart AI may prefer to target a ship near it, but then again smart AI's are not always the most fun to play with. It is okay if a ship ends up with no target after this call.

Important: Be sure ships do not target themselves or dead ships. Do not put your program in an infinite loop.

void MarkGoalTiles ()

This function needs to go through the board and mark all the tiles the ship wants to get to, depending on the ship's state. For instance, if the current state is "Attack", you should probably mark all the tiles that you could attack the target from. If the state is "Wander", you might instead mark some random tile until you get there, or mark the tile next to your current location, etc. This function can get fairly pretty complicated if you let it, but keep in mind that its purpose is simply to pick some places your AI wishes it could be at, you do not need to choose the best place or decide if it's even possible to get there, that is the job of another function. However, you should at least make sure not to mark any tiles that have fallen off the board.

ControlCode GetMoveAlongShortestShortestPathToAGoalTile ()

This is possibly the most complex function, and has a ridiculously long name to match. The idea here is to do pathfinding and return a direction which will get the ship to a tile marked as a goal tile. The twist is that there are usually multiple goal tiles, and there is a shortest path to each one that is reachable, but this function should return the direction of the first step along the shortest one of these shortest paths. You may be tempted to find the path to every goal tile and return the direction along the one that turned out to be shortest, but there is a much simpler and more efficient way which you should use instead.

Hopefully you remember something called "Breadth First Search" (BFS) from your CS 211 days. While most real games use A* search for this purpose, and there are other algorithms out there, BFS is the algorithm we recommend you use in this simple lab. You may recall that a Queue is a data structure that is very useful for BFS. You do not need to implement your own queue class; the C# Collections library already has one.

Besides the queue, you also need something to keep track of where you've already checked so you don't get into an infinite loop - you should probably use the Board.SetVisited() and Board.IsVisited() functions for this purpose.

Please try to make your BFS code simple and compact (i.e. we should not need to scroll very much if at all to read it).

ChangeStateIfApplicable ()

This function simply switches the ship's state if it needs to according to the way you've designed your FSM and its state change conditions. Obvious things apply - a ship with no target can't attack. You don't want your AI to be too good or too predictable, so you may want to put in things like random delays between state switches and things. For example, a ship that just spawned probably should not always instantly start killing you, and just because a ship has a target to attack doesn't mean it should stay in the same attacking state (since that could lead to "cheap" behavior and/or very predictable battles - maybe it should occasionally slip away and wander or randomly become more aggressive and get in its opponent's face). Experiment with various states and state change conditions to make the game fun.

You will probably want to start out by deciding how your states are going to work and exactly what the behavior is for those states. Once you have that figured out, try coding the spawning and wandering states, and don't switch out of those states until they work well. Marking the tiles and getting the search for goal tiles correct will take some effort. Once you get each state working, focus on making sure they all work together in an interesting way.

To help you with debugging your AI, we suggest that you play around with Board.DrawTile(SpriteBatch s, int x, int y). Notice how it uses tinting to change the color of a power tile. We recommend that you use similar techniques to keep track of goal and marked tiles. For example, you might want to make goal tiles with a red color, or to draw another, smaller square on top of these tiles. This will allow you to track how your BFS algorithm is working. However, when you submit your project, you should either remove this debugging code from your project, or ensure that all this drawing code is inside a [Conditional("DEBUG")] so that this code does not compile in release mode.

It is important to note that you do need to worry about speed of execution if your AI is causing the whole game to drastically slow down or skip lots of frames. In particular, if you are not careful, breadth-first-search can be quite slow. It is better to take shortcuts that aren't noticeable most of the time than to not take them if that causes the whole game to be unplayable. Also, your AI code should be fairly general (i.e. your AI may not treat the human player as special, it may not assume that the board is always a specific size, it may not assume there are never more than a certain number of ships, etc).

Double-check that your algorithm is implemented correctly. If your AI ever attempts to move over a hole, or if it ever fails to move to a location it could reach to shoot another ship from within a reasonable amount of time, then something is wrong. We often get lab submissions where the AI performs a correct BFS and then ignores the results of the search and just moves in the general direction of the goal, so make sure you don't do that. Also make sure everything continues working normally after you press R to restart - if it doesn't, you probably have a bug.

The Overall Goal

The real objective here is to make an AI that is tough but still beatable, and thus fun to play against. If your AI poses no threat to a human player, or if it is impossible to beat, you'll probably want to change some things. Also, you should make your AI unpredictable (random numbers are your friend here) even when fighting against itself, which should be entertaining to watch and not reliably result in short-lived battles. Essentially, you are not trying to make the most efficient killing-machine possible; you are trying to make the most engaging and entertaining killing-machine possible, which is harder in some ways and easier in others. Keep working at it, and see what you can come up with!

Submission

The only file you need to change is AIControl.cs. The example solution was created without modifications to any other files from the way they are given to you. But you should feel free to edit the AI header file as well if you want to add any more functions or states.

You must also create a readme.txt file that describes all the states your AI uses, including the logic for marking goal tiles and switching among states. Describe the code you added to each function, and why. If you made any new functions or states, be sure to describe them, too. If you made any changes outside of the AI (which is not necessary), you must justify them here. Not all changes are acceptable; for instance, you cannot simply remove all the power tiles to make the AI easier to program. Furthermore, please don't make private variables public to bypass getter and setter functions. Extra-credit type changes are welcome, however.

Finally, tell us your impression of how well your AI works and if you can think of anything it could do better.

To submit, zip up all your code and header files, together with your readme.txt, and submit as "lab2prog.zip" to CMS.

Due Thursday February 7, 2008 at 11:59pm