For my capstone project at Sheridan College, my team and I developed a platform-fighting game called Fandominion. As online multiplayer was deemed out of scope, the team decided that having A.I. opponents to fight against would be a good alternative for when players didn’t have others around in-person to play with. I took ownership of providing the AI with movement behaviour, so I got to work on planning and implementing an effective system.
Based on my level design experience with Valve’s Source Engine, I figured making a node-based path system would be a simple yet effective solution to pathfinding, and one I have experience in setting up. When making maps for Half-Life 2, you place just enough nodes to form straight-forward paths among all traversable areas, then the map editor takes care of linking them together. Nodes can also carry additional information for NPCs, known as “hints”, which I’ll get into later. This was the basic design philosophy of the node system that I would end up implementing in Fandominion.
An example of node placement (the yellow squares) in Valve’s Hammer Editor. Image courtesy of Valve Developer Union.
Whenever an AI player chooses a target and an attack to execute, they then form a path to their target and proceed to follow it. I started by looking into different pathfinding algorithms typically used in data management. I ended up implementing a form of the shortest-path algorithm to achieve an efficient means of finding the shortest path from the AI player to its target. Let's go through a quick breakdown of my implementation!
I start the pathfinding process by getting the closest node to the AI (the starting node) and their target (the final node). Beginning with the starting node, I compare the distance between itself and its neighbouring nodes, proceeding to the neighbour with the shortest distance, and repeating until we get to the final node.
The speed of pathfinding was a worry for me since the planning stage, as there could be up to four AI players in a match, all forming paths numerous times within seconds. To keep things efficient, each node contains a list strictly comprised of their neighbours to ensure that distance-checking is restricted to relevant nodes. Since each stage is moderately-sized and only features a few platforms, I could also be very conservative with node placement and still get desirable movement results!
The node setup for the fantasy stage. I implemented an editor function in Unity to automatically link nodes together. The little grey icons represent the nodes in-editor.
Stage size and minimal node placement also meant that setting up the node paths for each stage was painless – it only takes a few minutes to place nodes, debug in-game, then adjust accordingly!
Once basic pathfinding was in a workable state, I wanted to make their movement behaviour seem more believable and less rigid. To accomplish this, I split nodes into different types that allowed for more specific functionality.
Generic ground nodes only connect to other nodes that are within a direct line of sight or have the jump type. These are mainly used for the main floor(s) of the stage as jumping isn’t necessary there. Other node types are an extension of this basic functionality.
Jump nodes connect to any node within a specified radius (regardless of line of sight) and have a “jump radius” that tells the AI player when they are eligible to jump to this node. This node is placed on any platform or ledge to ensure everywhere is reachable for the AI.
As a platform-fighting game, jumping is pretty important – being able to fine-tune the allowed jump distance for each node meant more natural jumping behaviour for the AI, and less debugging for me! Originally, AI would determine if they should jump based on a hard-coded calculation, which became trouble as new stages and more intricate platform layouts became prevalent.
Jump nodes use the “Jump Detect Dist” to determine at what distance can AI players consider jumping to it. This is visualized by the blue wireframe sphere surrounding it.
Hazard nodes send out a “warning message” to all AI players, causing them to retreat to a designated “retreat zone” and avoid the node in pathfinding until it is deemed safe again. Using Unity’s event action system, game objects can tell specific hazard nodes to both start and stop being considered hazardous.
The concept of hazard nodes was derived from Half-Life 2’s “hint nodes”, a node variant that provided an NPC with a hard-coded piece of information about the environment (i.e. telling the NPC the surrounding area is interesting to look at). For the sake of Fandominion, I found this type of node implementation efficient since stages are essentially boiled down to floors and hazards, so how the AI interacts with a stage is quite limited.
Retreat Zones go in tandem with hazard nodes and damaging stage hazards (like electric floors). When a hazard node is set to hazardous, any AI players switch to a retreating state where they seek out the nearest “retreat zone”, an invisible game object that represents a safe spot for them to hang out at until the hazard node is safe once more.
While the laser charges up and becomes active, the node below it is considered hazardous, so the AI (on the right) refuses to go further until the laser is gone.
With the different node types in play, I felt that AI players exhibited more natural behaviour and made debugging even easier. If an AI was jumping to a node too soon, I knew it was likely because the jump distance of the target node wasn’t far enough, and setting it higher would fix the issue. Being able to use hazard nodes meant that the AI wouldn’t just blindly wander into the laser hazard in the middle of the game’s sci-fi stage, making them seem smarter. Implementing retreat functionality extended the believability further, and really made the AI feel “human” at times.
I suspected debugging would consume most of my time working on AI. While that was true, I found I was still able to surpass my own expectations in terms of what I was able to implement and just how effective the AI's movement could be. Some of my favorite moments working on this project were whenever another team member or player asked which character was the AI. The fact that we could be eluded by the AI meant we did a good job emulating human behaviours!
I was fortunate to be familiar with node-pathing and AI state machines beforehand, allowing me to plan out an implementation rather quickly. The small scope of the game’s levels also catered well to the node-based system, since not many nodes would be needed to get functional navigation. Knowing the extent of your game’s scope and environments influences your implementation, and reinforces the importance of planning. I definitely learned a lot from this experience and I'm glad to have it under my belt now!
Did you like this post? Tell us
Leave a comment
Log in with your itch.io account to leave a comment.