Using a gradient to influence A* Algorithms decisions

Hi, I am currently working on a solution where I want to create a circular gradient out from the end node to influence decisions that A* makes. An example of this would be if I have a blank map with no obstacles I want A* to follow a curved path rather than a straight line to the end.

image

I came up with a few solutions to this where I could create a “cone” in front of the part which would discount all the scores in that area. This solution did not work.

If anyone has any ideas or solutions please feel free to help. :slight_smile:

You could pretend that the two points are part of a circle with the centre being in the middle. You could increase/decrease the curvature of the curve by moving the centre horizontally either side. The radius would obviously be the distance between a point and the centre point.

Seems like you’d want to specify/generate a point and increase the cost of a path inversely proportional to the nodes’ proximity to that point.

If you don’t want to place artificial points, you could also try just increasing the cost as the length of the path becomes closer to the distance between your start and goal. May not result in a smooth curve though.

It doesn’t have to be smooth.
Thanks for the reply

So should I even be using the cone in this case?
Also should I be applying this to the final score of the nodes?

I’m not sure what you mean by a cone. If you’re talking about a 3d part, that probably wouldn’t factor into the algorithm result unless you’re using some sort of dynamic nav mesh to generate your nodes.

You could think of a cone as a 3d representation of the cost of navigating through a circular zone. The closer a node is to the center point of the circle, the higher/lower the point would be on the surface of the cone, and thus added/removed score from the overall score of the path. This would incentivize the algorithm to choose a path formed more closely around the base of the cone.

Basically you just need to adjust your scoring to factor in proximity to certain points.

I am using an artificial cone through code and applying the discount within that cone

I don’t really know what an artificial cone looks like programmatically, but the concept sounds fundamentally right. I would have to see your implementation to understand why it isn’t working.

I would also help to know the use case

in a nutshell, I want to prioritize walking forward.
This allows my object to move in more of a “smooth” path.
image

So you want a path that takes the initial orientation of the agent into account?

Yeah, that’s what I want, Is there a better way to do this than what I am doing?

Could you just do something like:

local straightness = directionToTarget:Dot(directionToOpenNode)

Add a multiplier, and add that to your hueristic? That would add a cost to walking in a straight line. You’ll need to play with the multiplier.

Edit: This doesn’t work great. It does makes your path avoid the goal, but doesn’t do it smoothly:

image

I then tried subtracting this:

f_cost = f_cost - directionFromLastNode:Dot(directionToOpenNode)

To try and discourage turns back and forth, but the best I get by playing with multipliers is this:

image

Which is closer, but not quite right.

Anyways, I don’t even think this is the right path (hah) to go down OP. Why do you actually want to do this?

My code to test

I modified this random a* I found: https://github.com/lattejed/a-star-lua

Setup:

image

The modified module (Added the straightness function):

-- ======================================================================
-- Copyright (c) 2012 RapidFire Studio Limited 
-- All Rights Reserved. 
-- http://www.rapidfirestudio.com

-- Permission is hereby granted, free of charge, to any person obtaining
-- a copy of this software and associated documentation files (the
-- "Software"), to deal in the Software without restriction, including
-- without limitation the rights to use, copy, modify, merge, publish,
-- distribute, sublicense, and/or sell copies of the Software, and to
-- permit persons to whom the Software is furnished to do so, subject to
-- the following conditions:

-- The above copyright notice and this permission notice shall be
-- included in all copies or substantial portions of the Software.

-- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
-- IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
-- CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
-- TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
-- SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-- ======================================================================

local module = {}

----------------------------------------------------------------
-- local variables
----------------------------------------------------------------

local INF = 1/0
local cachedPaths = nil

----------------------------------------------------------------
-- local functions
----------------------------------------------------------------

function dist ( x1, y1, x2, y2 )

	return math.sqrt ( math.pow ( x2 - x1, 2 ) + math.pow ( y2 - y1, 2 ) )
end

function dist_between ( nodeA, nodeB )

	return dist ( nodeA.x, nodeA.y, nodeB.x, nodeB.y )
end

function heuristic_cost_estimate ( nodeA, nodeB )

	return dist ( nodeA.x, nodeA.y, nodeB.x, nodeB.y )
end

function is_valid_node ( node, neighbor )

	return true
end

function lowest_f_score ( set, f_score )

	local lowest, bestNode = INF, nil
	for _, node in ipairs ( set ) do
		local score = f_score [ node ]
		if score < lowest then
			lowest, bestNode = score, node
		end
	end
	return bestNode
end

function neighbor_nodes ( theNode, nodes )

	local neighbors = {}
	for _, node in ipairs ( nodes ) do
		if theNode ~= node and is_valid_node ( theNode, node ) then
			table.insert ( neighbors, node )
		end
	end
	return neighbors
end

function not_in ( set, theNode )

	for _, node in ipairs ( set ) do
		if node == theNode then return false end
	end
	return true
end

function remove_node ( set, theNode )

	for i, node in ipairs ( set ) do
		if node == theNode then 
			set [ i ] = set [ #set ]
			set [ #set ] = nil
			break
		end
	end	
end

function unwind_path ( flat_path, map, current_node )

	if map [ current_node ] then
		table.insert ( flat_path, 1, map [ current_node ] ) 
		return unwind_path ( flat_path, map, map [ current_node ] )
	else
		return flat_path
	end
end

local function straightness( last, current, node, goal, turn, straight )
	
	local ax = node.x - current.x
	local ay = node.y - current.y
	local bx = goal.x - current.x
	local by = goal.y - current.y
	local cx = current.x - last.x
	local cy = current.y - last.y
	
	return turn * (ax*bx + ay*by) - straight * (cx*ax + cy*ay)
end


----------------------------------------------------------------
-- pathfinding functions
----------------------------------------------------------------

function a_star ( start, goal, nodes, valid_node_func, turn, straight )

	local closedset = {}
	local openset = { start }
	local came_from = {}

	if valid_node_func then is_valid_node = valid_node_func end

	local g_score, f_score = {}, {}
	g_score [ start ] = 0
	f_score [ start ] = g_score [ start ] + heuristic_cost_estimate ( start, goal, start )

	while #openset > 0 do

		local current = lowest_f_score ( openset, f_score )
		if current == goal then
			local path = unwind_path ( {}, came_from, goal )
			table.insert ( path, goal )
			return path
		end

		remove_node ( openset, current )		
		table.insert ( closedset, current )

		local neighbors = neighbor_nodes ( current, nodes )
		for _, neighbor in ipairs ( neighbors ) do 
			if not_in ( closedset, neighbor ) then

				local tentative_g_score = g_score [ current ] + dist_between ( current, neighbor )

				if not_in ( openset, neighbor ) or tentative_g_score < g_score [ neighbor ] then 
					came_from 	[ neighbor ] = current
					g_score 	[ neighbor ] = tentative_g_score
					f_score 	[ neighbor ] = g_score [ neighbor ] + heuristic_cost_estimate ( neighbor, goal, start ) + straightness( came_from[current] or start, current, neighbor, goal, turn, straight )
					if not_in ( openset, neighbor ) then
						table.insert ( openset, neighbor )
					end
				end
			end
		end
	end
	return nil -- no valid path
end

----------------------------------------------------------------
-- exposed functions
----------------------------------------------------------------

function module.clear_cached_paths ()

	cachedPaths = nil
end

function module.distance ( x1, y1, x2, y2 )

	return dist ( x1, y1, x2, y2 )
end

function module.path ( start, goal, nodes, ignore_cache, valid_node_func, turn, straight )

	if not cachedPaths then cachedPaths = {} end
	if not cachedPaths [ start ] then
		cachedPaths [ start ] = {}
	elseif cachedPaths [ start ] [ goal ] and not ignore_cache then
		return cachedPaths [ start ] [ goal ]
	end

	local resPath = a_star ( start, goal, nodes, valid_node_func, turn, straight )
	if not cachedPaths [ start ] [ goal ] and not ignore_cache then
		cachedPaths [ start ] [ goal ] = resPath
	end

	return resPath
end

return module

The test code (I achieved the above results with a turn multiplier of 0.5 and a straight multiplier of 5).

local astar = require(script.ModuleScript)

local width, height = 30, 30
local nodes = {}

for r = 1, height do
	for c = 1, width do
		local gui = Instance.new("Frame")
		gui.Size = UDim2.fromScale(1/width, 1/height)
		gui.Position = UDim2.fromScale((c-1)/width, (r-1)/height)
		nodes[(r-1)*width + c] = {
			x = c,
			y = r,
			gui = gui
		}
		gui.Parent = script.Parent.Frame
	end
end

script.Parent.TextButton.MouseButton1Click:Connect(function()
	for _, node in pairs(nodes) do
		node.gui.BackgroundColor3 = Color3.new(1, 1, 1)
	end
	
	local turn = tonumber(script.Parent.Turn.Text)
	local straight = tonumber(script.Parent.Straight.Text)
	
	print("turn =", turn, "straight =", straight)

	local path = astar.path ( nodes[1], nodes[#nodes], nodes, true, function(a, b)
		local dx = math.abs(a.x - b.x)
		local dy = math.abs(a.y - b.y)
		return dx <= 1 and dy <= 1
	end, turn, straight)

	if path then
		for _, node in ipairs(path) do
			node.gui.BackgroundColor3 = Color3.new(1, 0, 0)
		end
	end
end)
2 Likes

You have three options:

  1. Use normal straight-line pathfinding and when the path turns, track it with a curve. This may cause issues, but it is simple.
  2. Use RRT* which can handle computing paths with curves. Modern robotics uses this.
  3. Use vector fields for obstacle avoidance, including cliffs. This is easy but may require specific parameters per obstacle / map.

I will be implementing a RRT* pathfinder for Roblox soon, you can learn more about the project and talk about how the Roblox pathfinder doesn’t fit your use case here: Polaris-Nav

2 Likes

Sure ill take a look at it!
Thanks for the reply.