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