Programming Lab 2 - Artificial Intelligence and Pathfinding

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.

As before, you must work individually on this lab. Please contact the TAs if you run into any problems or have any questions along the way.

The Game

We have already set up the game mechanics for you. The game works as follows:

The player controls a ShipDemo ship on a large, 2-dimensional game board made out of tiles.  Move the ship around the board by using the arrow keys. 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 obvious glowing multicolored ones. 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.

Start out 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.

(Note: 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. Pressing 'T' will teleport all the ships to random locations without resetting the board. Holding 'H' will hide any onscreen text messages. Holding 'T' will give you a headache.)

The Code

The main.cpp file 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. (Note that this stuff should typically be abstracted away from your main file, though....) You may notice that the board is 2-D, but is drawn using 3-D drawing functions.  It turns out that this is very easy to do in GameX and makes for a very cool looking game.

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

1. 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.
2. Photons
   This class simply manages all the photons in the game.
3. 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.
4. ControlUnit
   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:
   1. 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.
   2. AIControl
      This ControlUnit calls AI functions to decide what the ship should do. This is the class you will 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's supposedly just calculating the next move, which you obviously should not do.)

AIControl

Take a look at the AIControl header 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 stubbed functions in the aicontrol.cpp 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's 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 doesn't target itself or any dead ships.  Also be certain you don't 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. Be sure ships do not target themselves or dead ships. No infinite loops, either! It is okay if a ship ends up with no target after this call.



• 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's 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++ standard template library already has one.
  
  The syntax to declare a queue of ints is: std::queue <int> myQueue; Of course, you can replace "int" with a more complicated datatype to make a queue of those instead. For instance, you could make a queue of Vec2i objects to let you store 2 ints (x and y) in each item of the queue, or you could make a queue of objects of your own custom class or structure. Key functions of queue are push(), front(), and pop(). Look in MSDN or the Visual Studio .NET help files to learn more about how a queue works. (You can do this in VS.NET by highlighting the word "queue" and pressing F1, if you have help installed.) 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 shouldn't need to scroll very much if at all to read it). And please don't use 'new' or 'malloc' - if you think you need to use these to do a BFS, you should ask a TA for help with C++.



• 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 shouldn't 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'll 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 when debugging your AI, the board-drawing code is set to highlight in blue any tiles your AI marks as goal tiles, and to draw a bright red square over any already-fallen tiles your AI marks. This will only happen when you compile the game in the Debug configuration of Visual Studio - building in Release mode will hide this visual debugging information. You must test to make sure that the game works and the AI operates in full capacity in both Debug AND Release mode, as you should with any game (because some bugs appear in only one of the two modes).

(A clarification: 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. 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.cpp. 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 can't simply remove all the power tiles to make the AI easier to program, and 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 and your readme.txt, and submit as "lab2programming.zip" on CMS.

This lab project is due Friday, September 15th by 11:59pm via CMS.