<cat>Dev.AI</cat> # Pathfinding automatically for NextBots <page>NextBot</page>s use the <page>navmesh</page> to calculate how to get from their current position to their target. This is done using helper classes like <page>PathFollower</page> and most of the path construction is done internally. You can however influence where the <page>NextBot</page>s can and cannot go when computing the path with <page>PathFollower:Compute</page> by using its 3rd argument. ⤶ &lt;!-- Maybe add examples here later --&gt;⤶ ⤶ <!-- Maybe add examples here later -->⤶ Below you will find examples on how to have complete control over the path generation and so that it is not limited to <page>NextBot</page>s only. # Terminology * navmesh - [The navigation mesh](https://developer.valvesoftware.com/wiki/Navigation_Meshes). * 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 <page>CNavArea</page> 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: * <page>CNavArea:SetCostSoFar</page> * <page>CNavArea:GetCostSoFar</page> * <page>CNavArea:SetTotalCost</page> * <page>CNavArea:GetTotalCost</page> * <page>CNavArea:AddToOpenList</page> * <page>CNavArea:AddToClosedList</page> * <page>CNavArea:ClearSearchLists</page> * <page>CNavArea:IsOpenListEmpty</page> * <page>CNavArea:PopOpenList</page> * <page>CNavArea:RemoveFromClosedList</page> * <page>CNavArea:UpdateOnOpenList</page> * <page>CNavArea:IsOpen</page> * <page>CNavArea:IsClosed</page> 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](https://en.wikipedia.org/wiki/A*_search_algorithm): ``` function Astar( start, goal ) if ( !IsValid( start ) || !IsValid( goal ) ) then return false end if ( start == goal ) then return true end start:ClearSearchLists() start:AddToOpenList() 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 current:AddToClosedList() 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 neighbor:AddToOpenList() 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 return total_path end ``` In this example, Astar() fucntion takes 2 arguments: The starting <page>CNavArea</page>, for example where the player bot or NPC currently is, and the goal <page>CNavArea</page>, 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 <page>CNavArea</page>, it returns false * If the start <page>CNavArea</page> is the same as the goal <page>CNavArea</page>, it returns true * Otherwise it will return an array of <page>CNavArea</page>s which the bot/NPC has to travel through (one after another, the goal <page>CNavArea</page> being the very first entry in the array, use <page>table.Reverse</page> 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 <page>navmesh.GetNearestNavArea</page> to find closest <page>CNavArea</page> to your desired <page>Vector</page> 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 <page>CNavArea</page>s, not <page>Vector</page> positions. As a result, you will notice that examples here move the agent mostly from a center of one <page>CNavArea</page> 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 <page>CNavArea</page>s, 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 <page>debugoverlay</page>. ``` 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 <page>debugoverlay</page> 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.