Jump to content
  • entries
    13
  • comments
    80
  • views
    34,233

Path Finding: It's Not Actually AI


Road Kill Kenny

4,376 views

 Share

::::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:

  1. The Node Network
     
  2. Heuristic Calculation
     
  3. 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.

 

blogentry-3220-0-43192000-1352975169_thumb.jpg

 

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

  • Upvote 6
 Share

11 Comments


Recommended Comments

Really nice blog again, Scarlet! Loved it. I hope my videoblog will be as good. :)

You're doing a great job at it, man! Looks like the end of the tunnel is coming closer and closer. Keep it up! ;-)

Link to comment

Nice work Ken, as you say plenty good enough for that type of game and it certainly pays to keep things simple whenever possible.

 

I must admit, I don't generally class path finding as AI although when I think about it ... it actually can be considered as AI as you are simulating the characters perception of the environment and its ability to plot a path through it. Which, if you don't have a computer simulation and A* kind of requires intelligence. Either way, its all smoke and mirrors lol

Link to comment

Great work as always, Ken.

 

Don't worry about long blogs man, I enjoy reading them, and I'm sure others do as well. It's actually one of a handful of reasons I keep an eye out on the blogs page.

 

I personally also keep a clear separation of definition between path-finding and AI. I guess it's just personal taste. Just as I don't consider the actual movement of an object as part of path-finding or AI, leaving AI simply to the definition of behavior and decisions; which also work together.

 

All-in-all you have the results you were looking for, which look flawless, and done at a quick pace. Kudos, man. I look forward to more game-play mechanics you create and the blogs to follow, including long one's (or "blooks" lol).

Link to comment

Thanks guys. Appreciate it all.

 

@Paul: Yes I agree AI is more about behaviors and decision making. Movement along the path is just another step by step algorithm without any decisions to make.

Link to comment

Sleeping with one eye open requires effort ... I don't do effort smile.png ... besides .. irrespective of whether I sleep on the bus or do extreme calculus mathematics for fun on the bus ... I still get from A to B without having to concern myself with the journey wink.png

Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...