Pathfinding Basics, Concepts, Tips and Ideas

Pathfinding is the process of navigation that is used in moving an object from one point to a second distinct point in space and the logical steps to do so.

The simplest form of pathfinding is between two points with empty space in between. More usually however we generally tend to have objects (Such as walls, objects and other terrain) in between those two points. Pathfinding can get even more advanced when the computer has to detect moving objects (also known as dynamic objects) as end points or moving end points, as well as other more advanced situations where we need to simulate human style realism within the AI Pathfinding that we choose to use.

In this article we will go over several pathfinding methods (There are many, I’ll just focus on a few I’ve learnt and used personally) as well as some amazing assets that can help you with pathfinding as well in your own games!

REFERENCE LINKS:
https://docs.unity3d.com/Manual/Navigation.html
https://gamedev.stackexchange.com/questions/28041/path-finding-algorithms
http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php
https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/
https://gamedev.stackexchange.com/questions/28041/path-finding-algorithms
http://jceipek.com/Olin-Coding-Tutorials/pathing.html#finding-paths

SEVERAL PATHFINDING METHODS

Basic pathfinding involves finding the SHORTEST path between two points. Given a starting point and an ending point, we would provide the logic or code to the computer to calculate the shortest distance. As easy as this is, it’s not realistic as most games rarely have a straight path between two points and generally tend to have many obstacles in between. Other things to consider is if we are using pathfinding for our PLAYER characters (Ex. using touch based input or allowing a player to navigate, in this case the end points are chosen by a player) or if we are going to have pathfinding for our friendly NPCs (Ex. A Pet or a Friendly Character) or for actual Enemy Characters (Ex. A monster or something that is trying to attack the player).

In pathfinding we use the terminology of NODES (Which is simply saying a point in space), however many articles and stuff you may find in regards to pathfinding will use the node terminology.

There are some very extensive mathematcial calculations involved with finding the shortest path which I wont go into in this article (You can check the reference links above for a more in-depth look at it all), but understand that when you have obstacles in between, finding the path becomes more challenging.

Lets break down the various pathfinding concepts based on the following:

a. Player node pathfinding
b. NPC node pathfinding
c. NPC node follow player via BREADCRUMBS
d. Enemy node pathfinding
e. Enemy AI style node pathfinding

After that we will go into Unity 3D and how we implement basic pathfinding using the NavMesh system as well as several assets available on the asset store to help you with all the pathfinding concepts I have listed above and including even more advanced pathfinding methods like A*.

1. PLAYER NODE PATHFINDING

Player node pathfinding is when we have a player move from one node to another in the shortest possible way. This is a great method that is useful for point and click style games such as many strategy games (Ex. Starcraft) and moba games (Ex. League of Legends). You’ll find that the challenge lies in obstacles in the way and how to avoid such obstacles.

The key thing here that is specific to this form of pathfinding is that it is PLAYER DRIVEN. That means that the user specifies WHERE the final node is placed. It is in general not a consistently moving/dynamic item but is changed ONLY when the player decides to move the end node. For example in League of Legends, when a player clicks in an area, the hero will move to that point. If they do not do anything, the end node is set and no other calculations will be done other than finding the shortest path between that last clicked point and current location of the player.

I personally use things like the Unity NavMesh system that allows players move around these obstacles. It can be a challenge however when trying to have players move between two points as you can run into various issues, such as for example when there are no paths (Something blocking the player from moving or no paths could be calculated) or if your navmesh in unity is not setup correctly (If you miss an area when defining your navmesh, it wont be walkable, OR if you miss adding the right layers, it wont be baked correctly OR if you forget to bake your navmesh…ya you can tell I’ve done this several times LOL!).

2. NPC NODE PATHFINDING

Similar to the player node pathfinding, npc node pathfinding uses input from several sources which could be user input, computer input or environmental input or a mix of several input types.

a. User Input
This is the exact same as player pathfinding where the actual player clicks on a location for their NPC to go to. Think of a strategy game like Starcraft where you click on a location that your various NPC characters all go to. In other games this could be a pet or other character you can control that is NOT your main playable character.

b. Computer Input
This is where the computer calculates an end node or point for the NPC. Things such as roaming characters or randomly moving NPC characters are a great example of this. You can use this method to have the computer place an end node a certain distance away from the start point randomly and then have the NPC go between those points back and forth and do that again. This method is usually known as guard mode or random movement mode and you can set the radius for the NPC to move back and forth in. For example imagine people inside of a little town who are moving around a zone randomly or friendly NPC’s that move back and forth seemingly guarding an area. As stated, these NPC characters have a predetermined radius of movement and depending on what they are (A character that can attack others or simply a bot in your game for helping the player) they may even have activation ranges and zones (Ex. if an enemy were to come within this NPCs activation zone while it’s moving, it may be attacked. For example think of a minion in Starcraft such as a zergling or a zealot that attacks automatically when another enemy character comes within a certain ‘activation’ distance).

c. Environmental Input
This is where the environment determines the end node. You can think of a boulder for example coming down to hit your NPC characters, and then based on that the NPC characters are either pushed or move out of the way if that boulder is within a certain activation distance. At that point the path that those NPC’s take is determined by the direction of the environment obstacle. There are several places you can use this method which is still under the computer input category in general however no action or movement takes place UNTIL an environmental change.

There are many more variations that occur and even mixtures of types of input but these are just a few I decided to put in that I’ve personally used or seen in games.

3. NPC NODE FOLLOW PLAYER VIA BREADCRUMBS

So you have a pet or other NPC characters that need to follow each other (Think of Starcraft groups of minions who need to follow each other at times or in League of Legends where the minions all follow a line pattern and follow each other based on the last position of the NPC ahead of it). In these situations where we want to track a path that has already been taken either by the player or another NPC we would use a breadcrumb system.

Simply put, just like in the childrens stories about breadcrumbs to follow them back home, a similar concept is used where the NPC character or player character drops nodes of their last position as they move to their next position.

At that point the computer or NPC character goes to that dropped node as the end point and then converts that node to a start point while looking for the next dropped node that the Player or NPC character will drop.

This is used heavily in many old school games that have enemy NPC’s that follow the player around. It gives a more realistic feel without having the computer go directly to the player in one shot but follow the player path. In a racing game for example, you could use this method to get a recording of the player or simply put an enemy car in the last node points to simulate a very basic enemy system in a racing game.

I’ve seen many games use this style of pathfinding to have a pet follow the player for example. There are many uses for breadcrumb pathfinding but it cannot be done without having at least one other object that is dropping breadcrumbs consistently (breadcrumbs in this case are simply empty 2D/3D empty objects in space that specify a location.

4. ENEMY NODE PATHFINDING

This is where an enemy character moves along a path. There are many methods, however I’ll be going over specifically the following methods => enemy to dynamic player, Breadcrumbs and enemy via waypoints.

a. Enemy To Dynamic Player
When a player is moving constantly (Such as in an FPS Shooter game), the computer must recalculate the end point (Where the player is) in a real time way. This can take a solid toll on the computer processor and so other methodologies such as estimation of the players next possible location or other methods are used to help reduce the ongoing calculations. Sometimes if an enemy character has an activation distance, then as long as the enemy character gets within range of that, the actual calculations wont have to be done as regularly. There are many methods that are used to help reduce the cpu load however keep in mind that it is very taxing on a computer processor to constantly calculate the end points of a moving object. As I said, there are several great methods out there that help. I personally use Unity NavMesh and even sometimes A* pathfinding however it is not needed for every type of game. Find which one works for your specific game as each game is different. Always keep in mind that dynamic pathfinding is costly on the processor and if you have a LOT of moving objects all trying to find a player, it can definitely slow things down.

b. Breadcrumbs (Enemy Follow Player)
As I outlined earlier, breadcrumbs are very useful methods to both reduce down the computer cpu usage and also still provide enough of an experience of enemies chasing your player. The concept once again is simply dropping a point in 2D/3D space over a given regular time or distance. For example I could drop a node every 5 units or I could drop a node every 5 seconds. My enemy would then use that node as the end point and go to that node and await another node OR attack if it is within range of the player.

c. Enemy Via WayPoints
Waypoints are a group of nodes that are generally PRE-DEFINED (but not always). The enemies will take those node paths and follow along those points. Great examples of uses for WayPoint systems include racing games (Where cars are meant to go around tracks which are pre-definied) or games such as Tower Defence (TD) games which have pre-built paths of movement.

5. ENEMY AI STYLE NODE PATHFINDING

This is more of an advanced style of pathfinding that includes things such as calculated emotions and is used in games to simulate a human style behaviour.

In the older days, games were very static and very unrealistic even with all the various movement types as I outlined above. The thing that was always missing was the human element.

To counteract that, some devs over the years started implementing things such as Emotion calculations into the mix and in today’s world we have even more advanced AI systems that make game play even more challenging.

I’ll go over the example of emotions but understand there are many new AI models for enemies being built all the time to really give players a challenge. Sometimes the shortest path to the player may not be the BEST path to the player. Be careful however as some of the methods you implement could become too hard for people to beat.

When it comes to emotions, if you put in calculations such as fear or anger you can add an additional dynamic to movement of your enemies. For example, maybe you could have the enemy move the path FASTER if it has an anger value of 80%+ or you could have the enemy run away to another node if it’s fear goes above 50% (At which point it could choose a new path back to its original position). Playing around with these types of values can give a more realistic enemy and/or npc movement and path and thus could make players truly enjoy certain things.

These are just ideas but I’ve seen several games that implement various pathfinding changes based on things like emotion. As I said these are more advanced forms of pathfinding that are available and should be researched based on your own game that you’re trying to make.

6. UNITY NAVMESH

In Unity 3D we implement pathfinding using the NavMesh system. To do this we would create walkable areas (Objects that we will have the player walk on) and then we would BAKE the NavMesh ontop of these objects (Shows up as blue ontop of the objects).

Once that’s done you would then mark your players/enemies/npcs or any object you want to navigate through the NavMesh as NavMeshAgents who would then be able to navigate over the NavMesh. Ofcourse this is just a simplification of the entire steps and process as you DO require code to make it all work.

For a detailed step by step for NavMesh creation please refer to the Unity Docs => https://docs.unity3d.com/Manual/Navigation.html

To get you started, Here are the steps to make a NavMesh in Unity 3D:
a. Select scene geometry that should affect the navigation – walkable surfaces and obstacles.
b. Check Navigation Static on to include selected objects in the NavMesh baking process.
c. Adjust the bake settings to match your agent size.
d. Agent Radius defines how close the agent center can get to a wall or a ledge.
e. Agent Height defines how low the spaces are that the agent can reach.
f. Max Slope defines how steep the ramps are that the agent walk up.
g. Step Height defines how high obstructions are that the agent can step on.
h. Click bake to build the NavMesh.
Your NavMesh will show up as blue overlay.

7. UNITY ASSETS

Here is a list of assets that you can use for navigation and ai. Keep in mind this is just a handful as the Asset Store has many others. Please do you research and look for assets that work well for your type of game 🙂

https://assetstore.unity.com/packages/tools/ai/a-pathfinding-project-pro-87744
https://assetstore.unity.com/packages/tools/ai/navigation2d-pathfinding-for-2d-games-35803
https://assetstore.unity.com/packages/tools/ai/polarith-ai-free-movement-steering-92029
https://assetstore.unity.com/packages/tools/ai/ai-designer-pro-80294
https://assetstore.unity.com/packages/tools/ai/love-hate-33063

CONCLUSION

Okay well there you have it, that’s just a very basic overview of such a complex topic of Pathfinding. Don’t forget, game dev is all about MASTERY (Ongoing learning)! Keep on learning and growing and don’t ever give up! As always, have a blast making awesome games!

Feel free to come watch me live on twitch where I teach game development and these same training’s using the top games such as League of Legends, Starcraft II, Hearthstone, Overwatch, Fortnite and many other top games! https://www.twitch.tv/academyofgames0

Until next time, keep on grinding at the code 🙂 You’re a super star!! Keep up the great work and NEVER GIVE UP! You Got This!! BE A CHAMPION!

Nav is a Unity Live Expert and Mobile Game and App Developer

LEARN TO MAKE GAMES FOR FREE! => Watch Me Live On Twitch => https://www.twitch.tv/academyofgames0

“I’m a game dev making fun awesome RPG and Fantasy Games. Check out my games on Steam and all major mobile platforms today => Game Scorpion Inc.!”