Pathfinding is, of course, an incredibly useful feature within game development.
If all AI controlled characters simply stayed in one place or ran mindlessly into walls then, whilst it may initially prove to be mildly amusing, combat would be far too easy and any suspension of disbelief would be ruined.
Occasionally it would make sense for AI characters to follow a pre-defined path, such as a guard following a patrol route, but in most circumstances a more dynamic approach is required.
Even in the scenario of a guard following a patrol route, once the guard was made aware of the player's presence they should break from their route to hunt the player down.
Pathfinding can also be useful for slightly less obvious situations than an enemy chasing down the player.
In scripted sequences you may require a character to travel to a particular location.
This is something you could fully script or animate but, with pathfinding, you could simply give the command for the character to walk to the location you need them at and allow pathfinding to get them there safely.
Another possible scenario would be where the player may have a companion or follower who needs to stay near to the player as they move around.
Unless they followed with truly supernatural reaction times then there is a chance that the player could move such that a direct path between them and their follower would be blocked and pathfinding can step in to save the day again.
There are a number of ways pathfinding can be approached.
One, on the face of it, quite straightforward way is to track the location of the player and use their history of positions as the path for the AI to follow.
There are some serious drawbacks with this approach, however.
Firstly, there is a requirement on a direct path existing between the AI's position and one of the positions along the history of positions as this system doesn't actually provide any ability to construct a path from scratch.
Additionally, as the AI is blindly retracing the steps of the path, without some not-so-straightforward extra work, a more obvious and direct path to the player would be ignored if it became available leading to situations where the player could be a couple of metres away around the next corner but the AI is traipsing off on the path it saw the player took which takes it through a small maze off to the right before eventually getting back to the player's new location.
For The Case Files of Harvey Benson, I require:
- the ability to calculate a path between any 2 points in 3-dimensional space
- the ability to calculate that path at any time, without any knowledge of historic position information or requiring direct line of sight at any point
- the ability to calculate that path efficiently enough that it can be recalculated frequently based on a moving target or shifting obstacles
- the time and effort to make a level "pathfinding friendly" should be as low as possible
To cover these requirements, I will be implementing a version of the A* algorithm.
At a basic level, the algorithm works by having a collection of nodes representing the places that can be travelled to.
Connections exist between the nodes showing which nodes it is possible to directly travel between.
These connections have a "cost" which is normally calculated as the approximate distance between the 2 nodes.
This cost calculation can be extended though and, in my case, I'm adding an additional penalty for vertical movement to encourage the path to favour a few additional steps over climbing over a wall.
Via an iterative process from the node that the AI entity is starting from, a best route is calculated to the target node where the total cost is as minimal as possible.
As a first test of the pathfinding system, I've created a simple test project which contains some simple level geometry, a user-controllable camera, and an AI character that utilises the pathfinding to travel towards the area of the level that the user clicks on.
To make the level ready for pathfinding, some objects are added to the level to represent areas that can be walked on and areas that should block paths.
These objects are immediately deleted when the game is run after their position and size data has been used to calculate the pathfinding nodes.
They are also added to a "pathfinding" layer so that they can be hidden easily within the editor as well.
This is still a little extra setup work than would be ideal but it certainly isn't that labour-intensive and it grants quite a bit of control over the paths that will be available over a fully-automated system.
These early tests have been quite promising as the paths are being calculated consistently without issue and efficiently enough to be recalculated every frame if it were required.
Which it isn't.
Still, I'm a bit of a perfectionist so I'm sure I'll end up revisiting this but, for now, on to the next feature!