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

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.

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.

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.

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:

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:

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:

The modified module (Added the `straightness` function):

``````-- ======================================================================
-- Copyright (c) 2012 RapidFire Studio Limited
-- 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!