Lab 2 - Artificial Intelligence and Pathfinding

CIS 300, Fall 2004 -- The Computer Game Design Project, Part 1

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 may work in pairs if you wish.  Feel free to use the course newsgroup or email the TAs if you run into any problems along the way, and we'll be happy to help you out.

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.

Go ahead and download the lab source code off the Assignments page of the course website (http://www.cis.cornell.edu/courses/cis300).  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.

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.  Notice how 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 (hint hint).

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. TextPrinter
   This class draws text. That's it.
4. 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.
5. 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 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.

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). Obviously this function should not return true 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.



• 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.



• 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...
  
  Anway, hopefully you remember something called "Breadth First Search" (BFS) from your CS 211 days. While most real games use A* search, BFS is the algorithm we recommend you use in this lab and in similarly simple situations. 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 Vector2DI 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).  Besides the queue, of course 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.



• 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 exactly 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.

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 use CMS. 

This lab project is due Wednesday, September 22.