Path Finding: It's Not Actually AI
Entry posted by Road Kill Kenny ·
4,857 views
::::BE WARNED THIS IS A LONG ONE::::
Path finding is a technique used in many games that allows an object to find its way around obstructions to get from one point to another. There are a lot of miss understandings regarding this technique and many treat it as a mystery that is best left for the more experienced programmers. However, the big scary word 'AI' is not nearly as scary or complex as some may think. My entire path finding system only contains 4 classes, 1 struct and about 450 lines of source excluding comments. I'm sure you'd agree that this isn't really that much.
On that note I'd like to point out that path finding isn't even AI itself despite popular belief and the fact that it is written about in many AI books. Path finding is simply a tool that AI utilizes to determine several points that an object must go through to physically get from 'A' to 'B' in the shortest or most favorable route possible. The AI comes in firstly when the object decides where it has to go for starters dependent on its behavior and secondly when it decides what to do with the path given to it by the path finding system. Another reason I disagree that it is AI is because the path finding doesn't belong to an object at all. It is an single external system that the objects AI consults for information.
Well now that that is out of the way I'll get on with it. Today I completed a full path finding system for my game. The path finding network is nodal and it utilizes the A* path finding algorithm. The most important feature of the system is the following funtion:
std::vector<Node*> GetPath(LE::TVec3 startPos, LE::TVec3 endPos)
This function simple returns a list of Nodes that the object must traverse in order to get from the startPos to the endPos. How the object uses that information is up to that objects AI behaviors.
Here is a quick video of it working in the game:
In my mind are three important sides to path finding including:
- The Node Network
- Heuristic Calculation
- The path finding algorithm that uses the Node network as an input and outputs a path
The Node Network
The node network or path finding graph is simply a bunch of nodes (i.e. 3D points in space) with Links between each other representing paths that are possible to be taken without hitting obstructions. The below screenshot shows a visual representation of the nodal network.
Each node contains a list of links that are Outgoing from themselves. That way when the algorithm assesses a node it can quickly and easily access its outgoing links.
Each link contains a pointer to its start Node and its end Node as well as a cost. The cost is important for the sake of the A* algorithm as it needs to know how difficult each link is so that it can pick the optimal route. Most costs are usually calculated by distance between nodes. However, they can be increased or decreased for different reasons. For example, you may consider a higher costs than normal for travelling uphill and a lower cost for travelling downhill. The choice is up to you.
I have utilized my level editor to facilitate the creation of this path network in a quick and efficient way. This way the path finding network can utilize DDD (Data Driven Design).
The classes I made for nodes and links are as follows:
class Node {
public:
Node::Node(u_int id, u_int subID, std::string origin, LE::TVec3 Pos);
Node::~Node();
void SetPosition(LE::TVec3 Pos);
std::vector<Link*> GetLinks();
void CheckLinks();
void AddLink(u_int destId);
void AddLink(std::string destOrigin, u_int destID);
void AddLink(Node* node);
void AddLink(Link* link);
void DrawNode(); // Needs more work here
LE::TVec3 pos;
std::string origin;
u_int id;
u_int subID;
private:
std::vector<Link*> nodeLinks;
PathMan* pMan;
};
class Link {
public:
Link::Link(u_int NodeIDA, u_int NodeIDB);
Link::Link(Node* start, Node* end);
Link::~Link();
Node* GetStartNode();
Node* GetEndNode();
void SetCost(float cost);
void CalcCost(); //Editor only
float GetCost();
bool CheckLink();
void SetBlocked(bool block);
void DrawLink(); //Debugging only
private:
Node* startNode;
Node* endNode;
float linkCost;
bool blocked;
PathMan* pMan;
};
Excuse all the overloading functions. I wasn't sure which method I would want to use to AddLinks so I made a bunch of them. Now you may not understand it all as some of the stuff is specific to my game. However, you should be able to get the general gist.
The Heuristic Estimation
The heuristic estimation is the estimation of how far it is from any given node in the network being assessed to the destination node. The closer this estimate is to the actual distance the better. However, it does not need to be perfect. Now don't take me the wrong way this is an estimate of the distance that the object needs to travel to get from A to B not the birds eye distance.
The A* algorithm will behave differently depending on if the heuristic is under or over estimated:
- Underestimating will cause the A* algorithm to take longer. The more it is underestimated the longer the process time will be. However, under estimating will always return the shortest path.
- Overestimation will cause the A* algorithm to not necessarily take the best path. However, it will finish quickly and is not a problem if the overestimation is minor.
- Getting the estimate just right will give the best balance of processing speed and accuracy. However, in order to estimate this distance perfectly you have to solve the path finding problem.... which is just stupid.
There are a number of ways that the heuristic can be estimated including Euclidean distance, look up tables or by solving a "High Level Bucket Nodes" path.
-
Euclidean Distance:This is the distance from point A to point B in a straight line. This has the potential to be either fairly accurate or grossly under-estimating depending on the geometry of your level. However, it is always garunteed to under-estimate so if you don't mind a bit of lacking in speed Euclidean distance is the way to go.
-
Look Up Tables: A level can be broken up into bigger sections or buckets. The distance from each bucket to another bucket is pre-determined in a level file and the heuristic estimation simply looks up in the table the approximate distance from the bucket that start Node belongs to to the bucket that the end Node belongs to.
-
High Level Bucket Nodes: Just like the look up tables, the level is broken up into big sections or buckets. A node is put in the middle of each bucket and a quick path finding algorithm is run to find the distance from the the bucket containing the start node and the bucket containing the end node. This means running a high level path finding algorithm using Euclidean Distance as the heuristic. Depending on the size of the level buckets and how many their are this usually is very quick and will provide a pretty close estimate.
Each method has its pro's and con's. I guess it is just very dependent on how your level is set out and how much performance you are willing to play with. As the Euclidean heuristic will always give a good path I decided to use it just to get the path finding going. However, I may change to another to improve performance when it gets to optimization.
The A* Algorithm
The A* algorithm is a very well known and common algorithm used for many games path finding. As it is so common I'm not going to talk about it very much. It can be found in many places on the internet but beware, you will get the best information from an AI book as internet sites tend to leave out bits and pieces of information.
This blog has gone long enough and I don't think I could do the A* justice without making this 3 times longer. I may write a tutorial on it using C++ someday but that's a big maybe.. I have a game to make XD.
I shall bore you no further. Check out the path finding network being created in the editor. Enjoy
-
6
11 Comments
Recommended Comments