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 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 as of 2023, but we have left this one alone. That is because we do not dare touch it without adding significantly more classes to LibGDX. We had hoped to have this in place by 2024, but we could not recruit a student to work on it.
We say all 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. Do not make me run an AI hearing.
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. We have cleaned up
DesktopLauncher a bit with a simplified version of the game settings, and we
added a command to the gradle so that -XstartOnFirstLab should no longer be
necessary. But beyond that, the classes like GDXRoot, GameCanvas,
InputController and Ship should be familiar. 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.
Unfortunately, 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 Game-X even before that) 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 it. 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 in 2021 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 07 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