Skip to content

Instantly share code, notes, and snippets.

@Glatharth

Glatharth/gist:443f2fe0307bfdb01649dcb35a6bd468

Created March 3, 2021 13:06
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Glatharth/443f2fe0307bfdb01649dcb35a6bd468 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Glatharth/443f2fe0307bfdb01649dcb35a6bd468 to your computer and use it in GitHub Desktop.
Download ZIP
astar example (Lua)
Raw
gistfile1.txt
-- https://www.youtube.com/watch?v=o5_mqZKhTvw&t=308s&ab_channel=CarlosMingoto
-- local clock = os.clock()
local cartesian = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
}
local function debugMapCart(area)
local top_x = "\t "
for i = 1, #area[1] do
top_x = top_x .. tostring(i) .. " "
end
print("\t"..top_x)
for _, y in pairs(area) do
local map = "\t"..tostring(_).."\t"
for __, x in pairs(y) do
map = map .. " {"..tostring(x).."}"
end
print(map)
end
end
function getInfoXY()
local y = #cartesian
local x = #cartesian[1]
return y, x
end
local init, dest
function setInitPos(y, x)
init = {y = y, x = x}
cartesian[y][x] = "I"
end
function setDestPos(y, x)
dest = {y = y, x = x}
cartesian[y][x] = "D"
end
function pathFinder(area, init, dest)
local node = {
openList = {
[1] = {
y = nil,
x = nil,
cost = {
g = nil,
h = nil,
f = nil,
}
}
},
closedList = {
["y"] = {
["x"] = {
cost = {
g = nil,
h = nil,
f = nil,
}
}
}
},
fatherList = {{
}}
}
node.openList = {}
node.closedList = {}
node.fatherList = {}
function calcCostH(init, dest)
local y = init.y - dest.y
local x = init.x - dest.x
if y < 0 then
y = y * -1
end
if x < 0 then
x = x * -1
end
return x + y
end
function calcCostF(g,h)
return g+h
end
function getAroundPos(pos)
local around = {
[1] = {1, 0},
[2] = {0, 1},
[3] = {-1, 0},
[4] = {0, -1},
-- [5] = {1, 1},
-- [6] = {-1, 1},
-- [7] = {-1, -1},
-- [8] = {1, -1}
}
local convertPos = {}
for i, v in ipairs(around) do
convertPos[#convertPos+1] = {
y = pos.y + v[1],
x = pos.x + v[2]
}
end
return convertPos
end
node.openList[#node.openList+1] = {
y = init.y,
x = init.x,
cost = {
g = 0,
h = calcCostH(init, dest),
f = calcCostF(0, calcCostH(init, dest))
}
}
while true do
local currentNode
-- print(node.closedList[currentNode.y][currentNode.x])
-- print(node.openList[1].y, node.openList[1].x)
while true do
currentNode = node.openList[1]
if node.closedList[currentNode.y] == nil then
node.closedList[currentNode.y] = {}
end
if area[currentNode.y][currentNode.x] == "D" then
local path = {}
local cache_path = node.fatherList[currentNode.y][currentNode.x]
while true do
path[#path+1] = {y = cache_path.y, x = cache_path.x}
if node.fatherList[cache_path.y] ~= nil and node.fatherList[cache_path.y][cache_path.x] ~= nil then
cache_path = node.fatherList[cache_path.y][cache_path.x]
else
break
end
end
return path
end
table.remove(node.openList, 1)
if node.closedList[currentNode.y][currentNode.x] ~= nil then
table.sort(node.openList, function(a, b) return a.cost.f < b.cost.f end)
else
break
end
end
node.closedList[currentNode.y][currentNode.x] = {
cost = {
g = currentNode.cost.g,
h = currentNode.cost.h,
f = currentNode.cost.f,
}
}
local around = getAroundPos(currentNode)
-- area[currentNode.y][currentNode.x] = _
for i, v in ipairs(around) do
if area[v.y] ~= nil then
if area[v.y][v.x] ~= nil then
if area[v.y][v.x] ~= "X" then
if node.closedList[v.y] == nil then
node.closedList[v.y] = {}
end
if node.closedList[v.y][v.x] == nil then
local tablePos = #node.openList + 1
if node.fatherList[v.y] == nil then
node.fatherList[v.y] = {}
end
node.fatherList[v.y][v.x] = {
y = currentNode.y,
x = currentNode.x
}
node.openList[tablePos] = {
y = v.y,
x = v.x,
cost = {
g = 0, -- currentNode.cost.g + 1, -- Está melhor com 0
h = calcCostH({y = v.y, x = v.x}, dest),
}
}
node.openList[tablePos].cost.f = calcCostF(node.openList[tablePos].cost.g, node.openList[tablePos].cost.h)
-- area[v.y][v.x] = node.openList[tablePos].cost.f
-- print(node.openList[tablePos].y, node.openList[tablePos].x)
-- if area[v.y][v.x] == "D" then
-- print("foiiiii", _)
-- local path = "Path: "
-- local cache_path = node.fatherList[v.y][v.x]
-- while true do
-- path = path.." "..tostring(cache_path.y)..", "..tostring(cache_path.x).." | "
-- if node.fatherList[cache_path.y] ~= nil and node.fatherList[cache_path.y][cache_path.x] ~= nil then
-- cache_path = node.fatherList[cache_path.y][cache_path.x]
-- else
-- break
-- end
-- end
-- print(path)
-- return true
-- end
end
end
end
end
end
table.sort(node.openList, function(a, b) return a.cost.f < b.cost.f end)
end
end
setInitPos(1, 1)
setDestPos(11, 15)
cartesian[3][4] = "X"
cartesian[3][5] = "X"
cartesian[3][6] = "X"
cartesian[3][7] = "X"
cartesian[3][8] = "X"
cartesian[2][8] = "X"
cartesian[3][3] = "X"
cartesian[3][2] = "X"
cartesian[3][1] = "X"
local clock = os.clock()
pathFinder(cartesian, init, dest)
-- print(string.format("elapsed time: %.5f\n", os.clock() - clock))
debugMapCart(cartesian)
print(string.format("elapsed time: %.5f\n", os.clock() - clock))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment