Artificial Intelligence and Pathfinding
For this lab, you will take a game that has already been 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).
Warning
This is an extremely old lab, going back to two decades now. It is a port of a port. The rendering system (which you should not touch) is held together with bailing wire. All of the other labs have been modernized for 2021, while we have left this one alone. That is because we do not dare touch it without adding significantly more classes to LibGDX.
We say this because sometimes students are tempted to borrow the code from this lab to use in their game (it is the only lab that uses 3d, and the only lab with a top-down view). Other than the finite state machine, do not use the code in this lab as an example of anything. You will regret it later.
Table of Contents
Game Rules
Download: Solution.jar
To help you understand the game, we have provided you a solution jar file for you to play. Do not decompile the solution. We know how easy it is to decompile Java (and have caught many people with Moss in the introductory courses). Doing so is a violation of the Academic Integrity policy of the course. It is not too late to replace you with someone from the wait list. Do not be that person.
In this game, the player controls a 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.
There are some pretty obvious strategies here. You want to fire at other players near when they are near an edge in order to push them off. You also want to avoid edges yourself. If a player avoids edges, try to circle the player so that you shoot out a tile on one side and then push them back into the hole on another.
Important: 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. Once again, do not decompile this solution as that is a violation of the honor code, and will be considered cheating.
Project Files
Download: AILab.zip
You should start out this lab by unzipping the project file 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.
Much of the architecture of this project has a lot in common with the
previous lab. You will notice that classes
are clearly broken up into model/view/controller. We have a lot of familiar classes
like Ship, InputController GameCanvas. However, there are some
notable differences.
GameCanvas
This class is very similar to the GameCanvas class from the
previous lab. However, this time you will notice
that the code is less general. Instead of a multi-purpose draw method, there are
specific methods to draw the various model types (tiles, ships, photons).
This is actually not a good way to structure your drawing code. However, there
are a lot of complicated issues in 3D drawing and we wanted to hide the details from
you as much as possible. This lab was ported from XNA back in 2015 and we have not
had time to really clean up the drawing code. Do not touch this file, as it is
very easy to break this. We will see a better GameCanvas next lab.
SoundController
This is another archaic class. Both the previous lab and the future labs use a brand new audio engine that we wrote last year to be used with the rhythm games. Do not touch this file or even emulate this file in future projects. This class is not how we work with audio any more.
PhotonPool
Instead of a PhotonQueue, we now have a PhotonPool which acts in
much the same way. We can no longer guarantee that photons are deleted in order.
Therefore, the pool has some more sophisticated rules for disposing of photons in the
list. In addition, this class implements the
Iterable
interface, which makes it easy to access the photons directly. In particular, you
can use the object in a for-each loop. We have added some code to the
Iterable implementation so that for-each loops skip over all deleted photons.
Photon is now a reguler class instead of an inner class. We had to do this
so that PhotonQueue could implement Iterable. The Java type system will
not allow you to make a class be Iterable over its own inner class.
ShipList
In addition to the Ship class, there is also a ShipList class.
This manages all the ships in the game just as PhotonPool manages
all the photons. It is less complicated because we only delete ships, we do
not reallocate them. It is also an implementation of
Iterable
interface, and for-each loops will skip over deleted ships.
When determining whether or not a ship is dead, keep in mind that there is a difference
between the Ship methods isAlive() and isActive(). If a
ship is not alive, it is as if it has been deallocated. It is not drawn on the screen,
or even present in a for-each loop over ShipList. On the other hand, inactive
ships are drawn on the screen and are not yet dead; a ship becomes inactive when it
starts to die and begins the tumbling animation. Inactive ships cannot be collided
with and should not be targeted by the AI. This is very important for your AI.
Board
This model 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. With that said, you should not modify this file.
GameplayController
The GameplayController controls all of the ships in the game. It reads from
the InputController for each ship, determines a move, and “makes” that move.
However, it does not actually move any of the ships. It changes the velocity, so that
when the velocity is applied, the ship will move forward. Movement itself is handled
by the CollisionController
This is an example of something called the Sense-Think-Act cycle that we will learn
about later in class. When you process game AI, you want to separate making a decision
from carrying out the decision. GameplayController makes the decisions
(using PlayerController or AIController) and CollisionController
carries them out.
PlayerController
This PlayerController takes input from the keyboard and uses that to directly
decide what the ship should do. This class also supports an X-Box controller, like in the
previous lab. Only one ship in the game is currently set to use PlayerController;
the other ships are AI-controlled.
AIController
The AIController implements the same interface that the keyboard input
control does. This design avoids the problem of the AI being able to cheat or do
things the player cannot. Of course, you could cheat by arbitrarily calling functions
that modify the game within getAction() instead of just calculating the next
move. Do not do this.
This file is the only file you should modify. While you should be aware of the other files in the project, you do not need to modify them. In addition, we will deduct points if you modify any other files.
Troubleshooting
If you are having problems running this project, the solution is the same as for the previous one. Create a new project, typing in exactly what you see below (except Destintation, which can be anything you want).
Once you have done that, copy the directories core/assets, core/src and desktop/src
into your new project. Edit the configurations and run
the new project.
Lab Instructions
In this lab, you will be modifying the file AIController.java to provide some basic
AI functionality for the ships. You should take a look at AIController.java
to learn what functions and data members it has available. One of the most important
elements 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 several stubbed functions in the AIController.java file. These
are clearly indicated by the comments FSM Code for Targeting and
Pathfinding Code. You will need to add code in the various areas marked
PUT YOUR CODE HERE (these areas start with //#region and end with
//#endregion).
If you want, you are allowed to make major changes to AIController if you
think you can come up with a better structure. We only demand three things. First, the
game must meet the criteria described at the end of this lab. Second, AIController
must implement InputController (so you must implement getAction()
properly). Finally, you may not modify any file other than AIController.java.
Before starting anything, you may want to look at the method getAction(),
which is already completed for you. This method calls all of the other major
methods in this controller. 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.
FSM Targeting Code
The code grouped in this region is used to set goals for the ship. It choses a ship to target (if necessary), and a goal tile to move towards. Goal tiles are potentially far way; this code does not determine how to reach the goal. That is the purpose of the pathfinding code.
bool canShootTargetFrom(int x, int y)
This method 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.
Shots only travel about 6 tiles in the x or y direction before it fading out.
Therefore, this method should also return false if the target is too far
away from the given x,y position. Recall that power tiles add
the ability to shoot diagonally, which you must take into account. There are
constants in AIController.java to help you with these values.
bool canShootTarget()
This method 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, we want to simplify the AI as much as possible. 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 (e.g. 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.
When selecting a target, be sure a ship does not target itself or any inactive ships (not just dead, but inactive). Also be certain you do not get into an infinite loop when there are no valid targets, and make sure it does not 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: Again, be sure ships do not target themselves or inactive ships. Do not put your program in an infinite loop.
void changeStateIfApplicable()
This method simply switches the ship’s state if it needs to according to the way you have designed your FSM and its state change conditions. Obvious things apply: a ship with no target cannot attack.
You do not 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. Similarly, just because a ship has a target to attack does not mean it should stay in the same attacking state (since that could lead to “cheap” behavior and/or very predictable battles). For example, you might want a ship to 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.
Pathfinding Code
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 iss 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 getMoveAlongPathToGoalTile()
This is possibly the most complex function, and has a 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 2110 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. There is one provided by LibGDX.
We know that there is also a Queue class provided in the base Java distribution.
However, you should be very careful with java.util classes in this course.
They allocate a lot of memory whenever you add and delete from them.
There is a reason why PhotonPool is so complicated. However, we do not
want you to worry about that in this lab. We have optimized the rest of this
lab so that you are free to allocate objects in AIController. You can use
new wherever you want and we will not take off points.
Besides the queue, you also need something to keep track of where you have
already checked so you don’t get into an infinite loop. In 2110 you might have
remembers the concept of a marking set. In this lab we want you to use the
gameboard as its own marking set. You should use the setVisited()
and isVisited() methods in Board for this purpose.
Please try to make your BFS code simple and concise. We should not need to scroll very much to read it. You may add additional functions or methods to help you with this algorithm.
Lab Hints
Now that you understand the main methods, 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 the method
drawTile() in Board. Notice how it changes the color of power tiles. We recommend
that you use similar techniques to keep track of goal and marked tiles. For example,
you might want to display goal tiles with a red color. 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 compile
so that this code is not included with your executable.
In this lab, you do need to worry about speed of execution. Your AI should not cause the whole game to drastically slow down or skip lots of frames. While memory allocation should not be too much of a problem, the breadth-first-search itself can be quite slow. It is better to take shortcuts that are not 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. In other words, 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, and so on.
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 do not do that. Also make sure everything continues working normally after you press “R” to restart; if it doesn’t, you probably have a bug.
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. This is harder in some ways and easier in others. Keep working at it, and see what you can come up with!
Submission
Due: Wed, Feb 09 at 11:59 PM
For this assignment, you will submit another ZIP file, containing exactly three files.
The only code file that you need to change is AIController.java. The example
solution was created without modifications to any other files from the way they are
given to you.
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, your ZIP file should contain an executable JAR of your game so that we can play it. Once again, read the intructions on the main programming resources page to see how to do this.
Submit this zip file as lab2code.zip to CMS