Posted October 02, 2023 by Shambles
#ai #platform-fighter
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.
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!
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.