Simple Pathfinding

From Garry's Mod
Jump to: navigation, search

Contents

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()

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

Personal tools
Navigation