Not Quite Immortal is a narrative-heavy 2D puzzle platformer set on the mystical haunted island of Creepy Hollow. The player, searching for the missing soul of their recently deceased necromancy mentor, possesses wild monsters with their spirit powers, then uses their abilities to solve puzzles and traverse the game world.
I am the AI programmer on the team, and I created a 2D Grid that can easily be modified by our designers in the Unity Inspector, and that includes a preview of the area of the map that the grid will cover once the level is loaded and built. On top of that, I implemented a slightly modified A* Pathfinding Algorithm as a basis for our enemies' movement, and architected the enemies' code in such a way as to support their unique special movement abilities in their FollowPath( ) method.
The Grid origin, size, and cell size can be modified in the
inspector before building the game.
Cells automatically get their costs assigned depending
on the environment behind them.
With the base grid set up, I was ready to implement a pathfinding algorithm. Going into it, however, I knew that each enemy had unique movement abilities, and wanted a way to accommodate for that. What I ended up doing was make all enemies use the same FindPath( ) method, but have each enemy implement and override for their pure virtual FollowPath( ) method, which allowed me to give enemies special movement abilities. The following video demonstrates the Voltergeist enemy, the yellow circle at the top, using its dash-reflect ability.
The Splash enemy, or the green enemy in the bottom-left, is also using its teleport ability when it reaches the last RoamTarget in its list, but that is not part of the FollowPath( ) method. That instead is handled in its SplashRoamBehaviour, which is implemented in a Finite State Machine controlling each enemy. The other enemies share the same RoamBehaviour, but the Splash has its own one because it needs to be able to teleport.
This enemy's movement ability that is incorporated in its FollowPath( ) method
is wall-jumping. Below is an example of how this logic is handled in the previously-mentioned function. Basically, we check if there is a vertical component to the final direction the enemy intends to move (which is the vector from the currentCell the enemy is on, and the destinationCell it wants to move to). If there is, we fire a ray forward and check for anything that is on the ground layer within close proximity. If it finds anything, it means there is a wall in front of the enemy. Once this is confirmed, we make the enemy "stick" to the wall, and perform a wall-jump by hopping upwards, briefly moving backwards, and then immediately going forward again.
Code to make Splash enemy wall-jump if necessary
in its FollowPath( ) method.
Grid Implementation:
The Grid is all contained in one class, the GridManager. This class deals with setting up the grid, managing cell costs, supporting multiple different terrain types, implementing the FindPath( ) function, etcetera. Below will be plenty of code snippets featuring comments I wrote to explain what I'm doing, and additional text to clarify what's going on and how these different code snippets are related.
I'm using Unity Gizmos to preview the Grid in the Scene view before pressing Play, and after the script is compiled as well. If the grid is not equal to null, it means that it has been built and exists. I use nested for-loops to iterate through the grid and draw each cell as a WireCube. I also added support to write each Cell's cost and/or identifier (pictured to the right) at its center, for debugging purposes. If the grid is null, however, it means that it is not yet build, so we have to instead simulate the cells and their dimensions from the data that is public to the developer (gridSize, gridOrigin, and cellDimensions). When the game is built, these variables get saved and the grid and cells are built using these same variables' values.
In the Awake( ) method, we set up the grid, effectively locking in the variables set in the inspector that were being actively previewed. We then initialise the costs of all the cells in the grid depending on the terrain behind them (which layers GameObjects are on), and finally initalise each cell's neighbours. We have a data structure holding this information in order to save resources and not have to find neighbours for each cell every time the FindPath( ) method is called, which in and of itself references the currentCell's neighbours numerous times, times the number of cells it checks when calculating a path.
GridManager::InitGrid( ) function initialises the grid.
GridManager::InitCosts( ), first image. This function checks for the layers underneath
each cell, and sets the cost of each cell. GetTerrainFromLayer( ) will be shown later.
GridManager::InitCosts( ), second image. This is the rest of the function, still in the
nester for-loops.
GridManager::GetTerrainFromLayer(int layer) finds the TerrainType that a layer
belongs in by checking the bits in the LayerMask.
GridManager::GetCostOfTerrain(TerrainType type) returns the cost associated with
a TerrainType so we can set the cell cost in the grid.
GridManager::InitNeighbours( ) adds cells and their neighbouring cells to a
SortedList<Cell, List<Cell>>, the list containing the cell's neighbours (it ignores itself).
GridManager::GetNeighbours(Cell origin), first image. This function returns a list of up to
eight cells that are neighbouring the origin cell (it excludes itself).
GridManager::GetNeighbours(Cell origin), second image. In the end, the function
returns the origin Cell's neighbours in a List<Cell>.
GridManager::GetCellAtWorldCoordinates(Vector2 worldPosition) returns the
cell in the grid at the worldPosition passed in.
Cell and FindPath( ) Implementation:
This section will show how the Cell class is composed, which is pretty simple.
I have cells track whether or not they have been explored, their cost for an enemy to reach, and which Cell they came from, and I reset the data in a ResetCell( ) function, in order to save CPU resources and avoid having an openList and a closedList. This was an efficiency improvement I added after my initial implementation proved to reduce framerate by a considerable amount if multiple enemies were in the same scene. Below is a comparison of the before and after this improvement was implemented. Keep in mind that this footage was recorded in the early stages of development, before my team got the Green Light to continue with development. This means that the game in the footage looks substantially different from the final build.
Before Efficiency Improvements, the Frame Rate would clearly
suffer when FindPath( ) was called.
After Efficiency Improvements, the Frame Rate would no longer
suffer when FindPath( ) was called.
Here is my implementation of the FindPath( ) function, which you now know how the functions it calls behave and what the properties it modifies do:
//Pseudocode followed from: https://www.redblobgames.com/pathfinding/a-star/introduction.html
public List<Cell> FindPath(Cell originCell, Cell destinationCell)
{
//Reset the cells
foreach (Cell cell in grid)
{
cell.ResetCell();
}
//Final path to return
List<Cell> finalPath = new List<Cell>();
//Initialise open list, came from dictionary, and costs dictionary
List<Cell> openList = new List<Cell>();
Dictionary<Cell, int> costSoFar = new Dictionary<Cell, int>();
//Put the origin cell on the open list and set came from and cost so far
openList.Add(originCell);
originCell.cameFrom = null;
costSoFar[originCell] = 0;
//Temp cell we are currently checking
Cell currentCell;
int currentIndex = 0;
bool foundValidCell = false;
//While the open list is not empty
while (openList != null)
{
//Get the next cell
currentIndex = 0;
currentCell = openList[currentIndex];
foundValidCell = false;
while (!foundValidCell)
{
//If it is explored
if (currentCell.isExplored)
{
//Skip it
currentIndex++;
if (currentIndex >= openList.Count)
{
Debug.LogWarning("No more unexplored cells on the openList.");
return null;
}
currentCell = openList[currentIndex];
}
else
{
currentCell = openList[currentIndex];
foundValidCell = true;
}
}
//Get the neighbours
List<Cell> neighbours = neighboursList[currentCell];
//Iterate through the neighbours
foreach (Cell currentNeighbour in neighbours)
{
//If the neighbour is on UNWALKABLE
if (currentNeighbour.GetCost() >= unwalkableTerrainCost)
{
//Set the currentNeighbour as explored
currentNeighbour.isExplored = true;
}
//Calculate the cost of the neighbour
int neighbourCost = (costSoFar[currentCell] + currentNeighbour.GetCost());
//If currentNeighbour is not in cost so far OR the new cost is less than the previous cost so far for that neighbour
if (!costSoFar.ContainsKey(currentNeighbour) || neighbourCost < costSoFar[currentNeighbour])
{
//Set the cost so far
costSoFar[currentNeighbour] = neighbourCost;
//Calculate the final cost (cost + heuristic)
int totalCost = neighbourCost + CalculateHeiristicSquared(currentNeighbour, destinationCell);
//Add the current neighbour to the open list
openList.Add(currentNeighbour);
//Set where the neighbour came from
currentNeighbour.cameFrom = currentCell;
//If found the destination cell
if (currentNeighbour == destinationCell)
{
//Add all the cells to the final path
Cell currentOrigin = currentNeighbour.cameFrom;
finalPath.Add(destinationCell);
while (currentOrigin.cameFrom != null)
{
//Add it to the path
finalPath.Add(currentOrigin);
//Update currentOrigin
currentOrigin = currentOrigin.cameFrom;
}
//Reverse the path (so that it starts at the first cell to go to and ends with the destination cell)
finalPath.Reverse();
//Clear the open list
openList.Clear();
openList = null;
//Return the path
return finalPath;
}
}
}
//Set the current cell as explored
currentCell.isExplored = true;
}
//In case of failure
return null;
}