You can write your topic however you want, but you need to answer these questions:
-
What do you want to achieve?
I want to create a pathfinding function specifically for a grid system that returns an optimal path. -
What is the issue? Include screenshots / videos if possible!
I set the starting tile to “A12” and the goal tile to “H12”. The grid is 12*8 tiles in size. The optimal path is a straight line from A12 to H12 (same column):
{'A12', 'B12', 'C12', 'D12', 'E12', 'F12', 'G12', 'H12'}
However, I was returned this path:
{
[1] = "A12", [2] = "B12", [3] = "B11",
[4] = "B10", [5] = "B9", [6] = "B8",
[7] = "B7", [8] = "B6", [9] = "B5",
[10] = "B4", [11] = "B3", [12] = "B2",
[13] = "C2", [14] = "D2", [15] = "D3",
[16] = "D4", [17] = "D5", [18] = "D6",
[19] = "D7", [20] = "D8", [21] = "D9",
[22] = "D10", [23] = "D11", [24] = "D12",
[25] = "E12", [26] = "F12", [27] = "G12",
[28] = "H12"
}
A video of it in action. green tile is start, A12, red tile is H12, goal. White tiles are visited tiles.
-
What solutions have you tried so far?
I was originally using a euclidean heuristic but I switched over to manhattan hoping it would make a difference, but unfortunately it returned the exact same path.
Code:
--pathfinding function
-- We are using strings to reference the tile on the grid, e.g. 'A1' = grid:FindFirstChild('A1')
function module.Path(start, goal)
local function reconstruct_path(came_from, current)
local path = {current}
while came_from[current] do
current = came_from[current]
table.insert(path, 1, current)
end
return path
end
local function a_star_search(start, goal)
local function distance(p1, p2)
return (grid[p1].Hitbox.Position - grid[p2].Hitbox.Position).Magnitude
end
-- Manhattan heuristic
local function heuristic(point)
return math.abs(grid[point].Hitbox.Position.X - grid[goal].Hitbox.Position.X) +
math.abs(grid[point].Hitbox.Position.Y - grid[goal].Hitbox.Position.Y)
end
local open_set = PriorityQueue.new(function(a, b)
return (a and a[2] or 0) < (b and b[2] or 0)
end)
open_set:Add({start, 0})
local came_from = {}
local g_score = {}
g_score[start] = 0
while open_set:Size() > 0 do
local current = open_set:Pop()[1]
if current == goal then
return reconstruct_path(came_from, current)
end
-- Expand neighbors
local neighbours = TileModule.Neighbours(current)
for _, neighbor in ipairs(neighbours) do
local tentative_g_score = g_score[current] + distance(current, neighbor)
if not g_score[neighbor] or tentative_g_score < g_score[neighbor] then
-- Check if the neighbor is already in the open set
local neighbor_in_open_set = false
local open_set_items = open_set:GetItems()
for i = 1, open_set:Size() do
if open_set_items[i][1] == neighbor then
neighbor_in_open_set = true
break
end
end
if not neighbor_in_open_set then
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
open_set:Add({neighbor, tentative_g_score + heuristic(neighbor)})
elseif tentative_g_score < g_score[neighbor] then
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
end
end
end
end
return nil -- No path found
end
return a_star_search(start, goal)
end
--Get neighbouring tiles function
TileModule.Neighbours = function(tileName:string, diagonal:boolean)
local neighbours = {}
local pos = grid[tileName].Hitbox.Position
local directions = {
{x=1,y=0},
{x=-1,y=0},
{x=0,y=1},
{x=0, y=-1}
}
local diagonals = {
{x=1,y=1},
{x=-1,y=1},
{x=1, y=-1},
{x=-1, y=-1}
}
for i, direction in ipairs(directions) do
local search = grid:FindFirstChild(TileModule.GridPositon(Vector3.new(pos.X + direction.x*6.4, 0, pos.Z + direction.y*6.4)))
if search and search:GetAttribute('traversable') then
table.insert(neighbours, search.Name)
end
end
if diagonal then
for i, direction in ipairs(diagonals) do
local search = grid:FindFirstChild(TileModule.GridPositon(Vector3.new(pos.X + direction.x*6.4, 0, pos.Z + direction.y*6.4)))
if search and search:GetAttribute('traversable') then
table.insert(neighbours, search.Name)
end
end
end
print('Neighbors of tile: '..tileName)
for _, i in neighbours do
print(i)
end
return neighbours
end