AI and Pathfinding Overview
The AI in Covert Cosmos is physics-based, and AI drifting out of the built-in navmesh can cause issues of the AI getting lost. To solve this problem I programmed a rudimentary A* Pathfinding system in C++ that has the control we needed to allow for cases where the AI drifts out of the grid. The AI uses a spline patrol path and has a simple detection system.
Pathfinding
In UE4 the default navigation system is Navmesh. Navmesh works by building geometry around obstacles and then using the triangles of that geometry as an irregular grid to find a path between two points. Navmesh has two downsides. First, it only works if there is a ground to "walk" on due to how this geometry is built. This would have caused an issue if we had gone the route of full 3D movement, because the AI pathfinding would be constrained to a plane. Secondly, major issues can arise when the AI leaves the navigation area. We wanted the AI to exist in the same logical space as the player, so it didn't seem right to have the player sliding around, but the AI flying perfectly. We decided to use a physics-based AI that drifts around and, therefore, potentially leaves the navigation area accidentally while pursuing the player.
In order to solve this problem, I researched the basics of pathfinding algorithms and their history from Breadth-First Search to Dijkstra's Algorithm and A*. I decided to build an A* pathfinding system that was flexible and had checks for the start and end points not being within the traversable grid.
I based my pathfinder on the above pseudo code. I began by using the Manhattan Distance heuristic for efficiency, but after some testing I found that the Manhattan Distance resulted in a sort of stair-stepping in the resulting path due to the diagonals having a greater hCost than the cardinals. Because the AI can move in any direction independently of the grid, I changed the heuristic to the Euclidean Distance. The Euclidean Distance is a more expensive calculation than the Manhattan Distance, but we immediately saw better results.
Above is the actual C++ pathfinding algorithm which is implemented into an actor component. Due to time constraints, I didn't have time to implement a heap sort to the part that checks the nodes in the open set. However, the code gets the job done, and the performance hit is not noticeable in most situations on modern hardware.
The main difference between my code and the pseudo code is the checks for whether the start and end nodes exist and are traversable. This is what allows the pathfinder to allow the start and destination points to account for being outside the grid. Basically, if no path can be found on this check, the pathfinder tells the AI to basically continue doing what it was doing until a valid check is made. This avoids endless loops, avoids checking the entire grid, and avoids checking for a new path too often.
The pathfinding algorithm works by making a parent/child hierarchy between all of the nodes. After the end point has been found, this parent/child relationship is used to retrace the path back to the beginning and store the nodes along the way. After doing this the path is obviously backwards, and must be reversed. In order to save some time, I used UE4's built-in reverse array algorithm in the Algo class.
At this point, the path also contains many unnecessary points. The path is simplified by comparing the movement direction and removing points if the path doesn't change directions. If not due to time constraints, this step may have been handled during the retrace step which would probably result in a small performance increase, but the cut and dry code shown here is sufficient.
AI
The AI in Covert Cosmos has a few different states, but always follows the same basic principal. Basically, the AI always has a destination and it uses physics forces to move closer to that destination. Whenever that destination is reached (or close enough because physics can cause the AI to miss their target by a bit), the AI figures out a new location to move towards. There were many features for the AI planned that did not make release like Avoidance, Squad Mentality, and more complex decision making.
Passive State - Spline Path Patrol
The Passive State is the default state where the AI is not searching for or pursuing the player. In this state, the AI follows a preset spline path.
The splines are simplified by evaluating points on the curves at an interval. This greatly increases performance by reducing the number of times each AI requests a new destination.
Detection
The detection in this game is a very simple stealth game type detection.
Originally, the detection was supposed to be based on more complex stealth game detection systems, and include things like peripheral vision, but this was ultimately scrapped due to time frames.
Here, we have a primary vision cone of a particular angle and distance. Whenever an alert state is triggered, the vision range increases. When in a passive state, if the player passes by an enemy with their engines on within the "hearing" range, the AI will investigate that location. When in the pursuit state, if the player is within the ignore path distance, the AI will bypass pathfinding and make a beeline for the player. This is done to account for inaccuracies in the pathfinding while the player is moving quickly (the player quickly moves away from the end point of the found path).
Alert State - Investigation
The investigation action is triggered by two events. First, if a player is detected by a satellite, nearby patrols will investigate the last known location of the player. Second, if the player is being pursued and the enemy loses sight of the player, the AI will extrapolate a location based on the player's last known position and velocity. It then searches random points in a radius around that point.
Above is the function used to get a random traversable node point within a radius.
Pursuit State
The pursuit state is activated as long as the enemy can see the player. The enemy will pathfind to the players location and attempt to catch the player. If the player moves far enough away from the found path, a new path will be found and this is where the bulk of the performance hit from the pathfinding can be seen. This action is based on the "Find Path to Actor Location" functionality in UE4's built-in Navmesh. Due to how this works, the AI will also bypass the path altogether if the player is in close proximity in order to actually keep up with the player.