# Pathfinding automatically for NextBots

NextBots use the navmesh library to calculate how to get from their current position to their target.
This is done using helper classes like PathFollower and most of the path construction is done internally.

You can however influence where the NextBots can and cannot go when computing the path with PathFollower:Compute by using its 3rd argument.

Below you will find examples on how to have complete control over the path generation and so that it is not limited to NextBots only.

# Terminology

• navmesh - The navigation mesh.
• agent - The agent will use the generated path, for example a player bot or an NPC.
• path - The generated path, a set of nodes the agent must travel through to get to the goal
• node - Points which are connected with each other that signify the positions that can be reached

# Pathfinding manually using A* and navmesh library

The CNavArea provides you with methods which allow you to quickly set up a completely custom A* pathfinding algorithm for your own purposes, such as pathfinding for player bots.

These methods are:

All of these are basic functions that are using in A* pathfinding algorithm.

Here's an example on how to use these methods to implement a basic A* algorithm from wikipedia:

```function Astar( start, goal )
if ( !IsValid( start ) || !IsValid( goal ) ) then return false end
if ( start == goal ) then return true end

start:ClearSearchLists()

local cameFrom = {}

start:SetCostSoFar( 0 )

start:SetTotalCost( heuristic_cost_estimate( start, goal ) )
start:UpdateOnOpenList()

while ( !start:IsOpenListEmpty() ) do
local current = start:PopOpenList() // Remove the area with lowest cost in the open list and return it
if ( current == goal ) then
return reconstruct_path( cameFrom, current )
end

for k, neighbor in pairs( current:GetAdjacentAreas() ) do
local newCostSoFar = current:GetCostSoFar() + heuristic_cost_estimate( current, neighbor )

if ( neighbor:IsUnderwater() ) then // Add your own area filters or whatever here
continue
end

if ( ( neighbor:IsOpen() || neighbor:IsClosed() ) && neighbor:GetCostSoFar() <= newCostSoFar ) then
continue
else
neighbor:SetCostSoFar( newCostSoFar );
neighbor:SetTotalCost( newCostSoFar + heuristic_cost_estimate( neighbor, goal ) )

if ( neighbor:IsClosed() ) then

neighbor:RemoveFromClosedList()
end

if ( neighbor:IsOpen() ) then
// This area is already on the open list, update its position in the list to keep costs sorted
neighbor:UpdateOnOpenList()
else
end

cameFrom[ neighbor:GetID() ] = current:GetID()
end
end
end

return false
end

function heuristic_cost_estimate( start, goal )
// Perhaps play with some calculations on which corner is closest/farthest or whatever
return start:GetCenter():Distance( goal:GetCenter() )
end

// using CNavAreas as table keys doesn't work, we use IDs
function reconstruct_path( cameFrom, current )
local total_path = { current }

current = current:GetID()
while ( cameFrom[ current ] ) do
current = cameFrom[ current ]
table.insert( total_path, navmesh.GetNavAreaByID( current ) )
end
end
```

In this example, Astar() fucntion takes 2 arguments: The starting CNavArea, for example where the player bot or NPC currently is, and the goal CNavArea, where the bot or NPC wishes to get to.

The Astar() function will return one of the 3 values:

• If it is physically impossible to get to the goal CNavArea, it returns false
• If the start CNavArea is the same as the goal CNavArea, it returns true
• Otherwise it will return an array of CNavAreas which the bot/NPC has to travel through (one after another, the goal CNavArea being the very first entry in the array, use table.Reverse to reverse the array order if necessary) to get to the goal.

Below you will find a few examples on how to use this example function to move player bots using pathfinding to a certain target.

## Using vectors as start and goal positions

You can use the function navmesh.GetNearestNavArea to find closest CNavArea to your desired Vector position.

Here's an example function that takes 2 vectors are input for Astar() function:

```function AstarVector( start, goal )
local startArea = navmesh.GetNearestNavArea( start )
local goalArea = navmesh.GetNearestNavArea( goal )
return Astar( startArea, goalArea )
end
```

## A* works best with point nodes, not areas

In Garry's Mod, the navigation mesh is made of CNavAreas, not Vector positions. As a result, you will notice that examples here move the agent mostly from a center of one CNavArea to the center of another. This makes the generated paths look unnatural.

In order to achieve more natural paths, more advanced techniques will be needed when building positions the agent will need to traverse through, such as using the corners of CNavAreas, using Line of Sight checks to cut corners or discard certain positions, etc.

## Pathfinding is not easy

Please keep in mind that all of these examples are kept as simple as possible for educational purposes. It may not generate the absolutely most efficient paths. More work will be necessary to be put into the agents movement code for the paths to feel natural or be efficient.

## Example console command to test and visualize the generated path

This example code contains a function that will draw the generated path, directly from the Astar() function using the debugoverlay library.

```function drawThePath( path, time )
local prevArea
for _, area in pairs( path ) do
debugoverlay.Sphere( area:GetCenter(), 8, time or 9, color_white, true  )
if ( prevArea ) then
debugoverlay.Line( area:GetCenter(), prevArea:GetCenter(), time or 9, color_white, true )
end

area:Draw()
prevArea = area
end
end```

Please keep in mind that the debugoverlay library only works in multiplayer and only when the developer console command is set to a non zero value.

This example shows how you can use the Astar() and drawThePath() functions together to test and debug your path generation.

```concommand.Add( "test_astar", function( ply )

// Use the start position of the player who ran the console command
local start = navmesh.GetNearestNavArea( ply:GetPos() )

// Target position, use the player's aim position for this example
local goal = navmesh.GetNearestNavArea( ply:GetEyeTrace().HitPos )

local path = Astar( start, goal )
if ( !istable( path ) ) then // We can't physically get to the goal or we are in the goal.
return
end

PrintTable( path ) // Print the generated path to console for debugging
drawThePath( path ) // Draw the generated path for 9 seconds

end)
```

## Example usage with player bots

This example shows the most basic way to move a player bot (an agent) alongside the generated path:

```local rePathDelay = 1 // How many seconds need to pass before we need to remake the path to keep it updated
hook.Add( "StartCommand", "astar_example", function( ply, cmd )

// Only run this code on bots, and only if bot_mimic is set to 0
if ( !ply:IsBot() || GetConVarNumber( "bot_mimic" ) != 0 ) then return end

cmd:ClearButtons()
cmd:ClearMovement()

local currentArea = navmesh.GetNearestNavArea( ply:GetPos() )

// internal variable to regenerate the path every X seconds to keep the pace with the target player
ply.lastRePath = ply.lastRePath or 0

// internal variable to limit how often the path can be (re)generated
ply.lastRePath2 = ply.lastRePath2 or 0

if ( ply.path && ply.lastRePath + rePathDelay < CurTime() && currentArea != ply.targetArea ) then
ply.path = nil
ply.lastRePath = CurTime()
end

if ( !ply.path && ply.lastRePath2 + rePathDelay < CurTime() ) then

local targetPos = Entity( 1 ):GetPos() // target position to go to, the first player on the server
local targetArea = navmesh.GetNearestNavArea( targetPos )

ply.targetArea = nil
ply.path = Astar( currentArea, targetArea )
if ( !istable( ply.path ) ) then // We are in the same area as the target, or we can't navigate to the target
ply.path = nil // Clear the path, bail and try again next time
ply.lastRePath2 = CurTime()
return
end
//PrintTable( ply.path )

// TODO: Add inbetween points on area intersections
// TODO: On last area, move towards the target position, not center of the last area
table.remove( ply.path ) // Just for this example, remove the starting area, we are already in it!
end

// We have no path, or its empty (we arrived at the goal), try to get a new path.
if ( !ply.path || #ply.path < 1 ) then
ply.path = nil
ply.targetArea = nil
return
end

// We got a path to follow to our target!
drawThePath( ply.path, .1 ) // Draw the path for debugging

// Select the next area we want to go into
if ( !IsValid( ply.targetArea ) ) then
ply.targetArea = ply.path[ #ply.path ]
end

// The area we selected is invalid or we are already there, remove it, bail and wait for next cycle
if ( !IsValid( ply.targetArea ) || ( ply.targetArea == currentArea && ply.targetArea:GetCenter():Distance( ply:GetPos() ) < 64 ) ) then
table.remove( ply.path ) // Removes last element
ply.targetArea = nil
return
end

// We got the target to go to, aim there and MOVE
local targetang = ( ply.targetArea:GetCenter() - ply:GetPos() ):GetNormalized():Angle()
cmd:SetViewAngles( targetang )
cmd:SetForwardMove( 1000 )

end )```

This example will make all bots on the server move towards the first player on the server. The path generated is not pretty, but the point of this example to show how to use the path to move an agent alongside a generated path.