Pathfinding

 

---

Pathfinding

This deals with the NPC’s ability to calculate the best route between two traversable points in your Panda3D environment.  It requires the creation of a navigation mesh (see “Navigation Mesh” description below), which is placed on the surface over which your NPC will be moving.  The navigation mesh allows the system to recognize “traversable nodes” around the mesh, as well as areas which cannot be traversed (areas occupied by an impediment or obstacle for instance), represented by a lack of traversable nodes, as seen in the video below.

 

Video description:  A player-controlled character (red) is moved around a simple navigation mesh while a non-player character (blue) pursues it.  The plain’s traversable nodes are represented by the yellow spheres in the grid, and the NPC uses pathfinding to dynamically calculate the best route to its target across the legal areas (that route is continuously shown with a red line).  Notice, that the NPC is not able to move over the areas which are free of any traversable nodes – the boarders and the blank space in the center of the plain – which can be representative of obstacles or walls.

 

 

Video Description:  Four NPCs of varying colors (yellow, blue, green, and purple) travel back and forth between two stationary points of their respective colors.  At the same time, five black NPCs patrol the perimeter of the scene, moving between the colored pyramids in each of the four corners.  All characters are using pathfinding to calculate their fastest routes and navigate around obstacles.

 

 

Video Description:  A player-controlled character (red) is moved around the environment (sometimes through obstacles since no collisions have been set) while a non-player character (blue) pursues it, using pathfinding to calculate the best route to its target.  The NPC’s path is continuously drawn as a white line, and you can see that it recognizes all obstacles in the environment and calculates a path around them.

 

Navigation Mesh

This mesh starts out as a simple plain, which can be created using a 3D graphics program like 3D Studio Max, Maya, or Blender.  Objects placed on the plain that are meant to represent impeding obstacles should have their bottom faces removed so that the nav mesh is able to recognize the areas where the obstacle stands as non-traversable spaces.  See the 2-part video below for a detailed tutorial/walk-through for how to create a proper navigation mesh. 

Part 1

Video Description:  A member of our team walks you through the necessary steps for creating a proper navigation mesh required for Pathfinding. This video explains all the steps up to the generation of the navmesh.csv file from the model.

 

Part 2

Video Description: This video explains how the navmesh.csv file generated is used with the pathfinding system.

 

Obstacle Avoidance vs. Pathfinding

 

When to use Pathfinding:

In certain situations, obstacle avoidance is not the best solution for getting a non-playable character to intelligently navigate around an object/impediment.  This usually occurs with concaved objects, as shown in the video above.  The best solution here would be to use pathfinding, which results in more intelligent obstacle navigation from the NPC, as seen in the video below.

 

Video Description:  The NPC (white egg) is seeking the static red egg.  At first, it uses obstacle avoidance to attempt to get around the concave obstacle, which results in the character getting stuck in the object.  In the second half of the video, another attempt to seek the target is made, but this time the character uses pathfinding and “intelligently” finds its way around the concave impediment. 

Note:  The inefficiency of obstacle avoidance in this situation is not a flaw in our code, but rather a common feature of the behavior.

 

When to use Obstacle Avoidance:

Pathfinding is not the ideal choice when you want many NPCs (a flock for instance) to navigate around several obstacles.  In this scenario, obstacle avoidance works best, as seen in the video below.  While one or two of the characters in the flock will get caught up on an obstacle from time to time, the overall desired effect is there.

 

Video Description:  A player-controlled character (yellow egg) is moved around the plain, while a flock of NPCs (white eggs) all pursue and use OBSTACLE AVOIDANCE to navigate around the moving obstacles (tress).   

 

 

 

 

 

:: Team Pandai ::