You can either use A* or dijkstra. I’ve used dijkstra in the past within roblox.
Here is a video: https://www.youtube.com/watch?v=EFg3u_E6eHU
I’ve got this from Github GitHub - matthewdeguzman/Maze-Generator-and-Path-Finder: Roblox game that generates random mazes from a given size and solves them using either a breadth-first search or Dijkstra's algorithm, I will place the code below:
local Dijkstra = {}
-- Gets services
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local RunService = game:GetService("RunService")
-- gets values
local values = ReplicatedStorage:WaitForChild("Values")
local clear = values:WaitForChild("Clear")
local finishClear = values:WaitForChild("FinishClear")
-- gets module scripts
local guiScripts = require(ReplicatedStorage:FindFirstChild("GUIScripts"))
local helper = require(ReplicatedStorage:WaitForChild("Helper"))
-- Begins Dijkstra's algorithm
-- grid: adjacency list of every wall and path block
-- start: starting position
-- endPos: end position
function Dijkstra.solve(grid, start, endPos, size)
-- removes any pathblocks if they previously existed
helper.removePaths()
-- creates a new model to hold the pathblocks
local pathBlocks = Instance.new("Model")
pathBlocks.Name = "PathBlocks"
pathBlocks.Parent = workspace
-- Constant to simulate an infinite value
local inf = 10000000
-- table that contains the visited path blocks
local vis = {}
-- table that holds the shortest distance from the starting point to every path block
local dist = {}
-- table the holds the current path
local prev = {}
-- Initializes an indexed priority queue
local ipq = require(game:GetService("ReplicatedStorage"):FindFirstChild("IndexedPriorityQueue"))
local queue = ipq.new(#grid)
queue:initialize()
-- Initializes all of the tables with default values
for i = 1, #grid do
table.insert(vis, false)
table.insert(dist, inf)
table.insert(prev, 0)
end
-- Initializes the distance from the starting node to be 0 and places it in the queue
dist[start] = 0
queue:insert(start, dist[start])
-- Begin's pathfinding andd the timer
guiScripts.activateTimer()
while not queue:isEmpty() do
-- Remove the pair with the smallest value from the queue
-- and assign variables to the key and the distance
local pair = queue:poll()
local index = pair[1]
local distance = pair[2]
-- set visited to true since we are now on the path block
vis[index] = true
-- If we've already found a better distance to the current path block
-- than the one that has been retrieved, we continue because it does not
-- hold the shortest path
if dist[index] < distance then
continue
end
-- we place a block down based on the index of the wall to
-- show we are exploring the path
-- this can be removed if you want to remove visualization
helper.placeBlock(index,size)
-- looks at all of the connected path blocks to the current path block
-- and determines if their distances can be improved
for i, value in ipairs(grid[index]) do
-- If we've already visited the neighbor than we're assuming
-- we've already found a better path and we finish the iteration
if vis[value] then continue end
-- retrive the new distance by adding the edge cost (will always be 1 because
-- this is an unweighted graph)
local newDist = dist[index] + 1
-- if the new distance is shorter than the previous distance
-- we will update it
if newDist < dist[value] then
prev[value] = index -- update prev to hold the shortest pathblock
dist[value] = newDist -- update dist to hold the shortest distance
-- if the path block hasn't been explored yet, then we will be
-- placing it in the queue
-- else we will be updating the distance of the path
if not queue:contains(value) then queue:insert(value, newDist)
else queue:decreaseKey(value, newDist) end
-- Runservice wait to get shorter wait time
RunService.Heartbeat:Wait()
end
end
-- If we've reached the end position than we can break out of the loop
-- because we've found the shortest path to the end position
if index == endPos then
-- ends the timer because we've found the end
guiScripts.stopTimer()
-- updates dijkstra's solve time
guiScripts.updateTime("Dijkstra")
break
end
-- if we want to clear the maze then we stop the timer and exit the script
if clear.Value then
finishClear.Value = true
return
end
end
-- Creates a path table that will be one plus the size of the shortest distance
-- and fills it with a default value
-- the variable at is the path block which connects to the end
local at = prev[endPos]
local i = dist[endPos] - 1
local path = table.create(dist[endPos]-1, -1)
helper.drawPath(i, prev[endPos], prev, table.create(i,-1),size)
end
return Dijkstra
Helper.lua
local helper = {}
-- Helper helper functions --
-- These functions were made helper functions because i needed to call them
-- within the module scripts and module scripts can't require them selves
-- given the placement number of a block and the size of the maze, it returns
-- the column and row number it was placed in
local function _unbox(position, d)
local a = {}
table.insert(a, math.ceil(position / d))
a[2] = position - (a[1] - 1) * d
return a
end
-- Given the x and z position of a block, it returns the x y and z coordinates
-- based on the size of the block
local function _getPos(x, y, z)
return {(x-1)*4, y, (z-1)*4}
end
-- opposite of the unbox function, given the row and column number of the block
-- it returns the placement number of the block given the maze's size
local function _box(y, x, size)
return x+(y-1)*size
end
-- Given a posiiton and size of the maze, it places a pathblock
function _placeBlock(position, d)
-- receives it's position
local pos = _unbox(position, d)
-- Creates part and places it in pathblock model
local part = Instance.new("Part")
part.Color = Color3.fromRGB(159, 161, 172)
part.Anchored = true
part.Size = Vector3.new(4,2,4)
part.Material = Enum.Material.Neon
part.Position = Vector3.new((pos[1]-1)*4, 4, (pos[2]-1)*4)
part.Parent = workspace:FindFirstChild("PathBlocks")
end
-- Functions
function helper.unbox(position, d)
return _unbox(position, d)
end
function helper.getPos(x, y, z)
return _getPos(x, y, z)
end
function helper.box(y, x, size)
return _box(y, x, size)
end
function helper.placeBlock(position, d)
_placeBlock(position, d)
end
-- Creates a block given certain perameters
function helper.createBlock(name, sz, mat, brkClr, pos, par)
local part = Instance.new("Part")
local p = _getPos(pos[1],pos[2],pos[3])
part.Name = tostring(name)
part.Size = Vector3.new(sz[1],sz[2],sz[3])
part.Material = mat
part.Color = Color3.fromRGB(brkClr[1],brkClr[2],brkClr[3])
part.Position = Vector3.new(p[1],p[2],p[3])
part.Anchored = true
part.Parent = par
end
-- Draws the path of the solved maze
-- i: the number of blocks needed to be placed
-- at: the placement number of the block that needs to be placed
-- prev: a table that holds the paths of how to get to certain blocks from the starting posiiton
-- size: size of the maze
function helper.drawPath(i, at, prev, path, size)
-- Gets the runservice of the game and the pathblocks model
local RunService = game:GetService("RunService")
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local values = ReplicatedStorage:FindFirstChild("Values")
local clear = values:FindFirstChild("Clear")
local finishClear = values:FindFirstChild("FinishClear")
local pathBlocks = workspace:FindFirstChild("PathBlocks")
-- reconstructs the path by continuously updating the connected paths
-- until at is equal to zero, which means that we've found the beginning
-- because we set it's path to be 0
while i >= 1 do
path[i] = at
at = prev[at]
-- stops early so it doesn't place a block on the start
if prev[at] == 0 then
break
end
i -= 1
end
-- get's the model we created called path blocks and clears all of it's children
pathBlocks:ClearAllChildren()
-- we then traverse the path and place a block on every path block we traverse
-- to outline the shortest path
for i, v in ipairs(path) do
-- If the user has decided to clear the maze, then we stop the function
if clear.Value then
finishClear.Value = true
return
end
_placeBlock(v,size)
-- optional wait that can be removed
RunService.Heartbeat:Wait()
end
-- once we've finished constructing the path, we turn it blue to indicate that
-- we've finished
for i, v in ipairs(pathBlocks:GetChildren()) do
v.Color = Color3.fromRGB(82, 124, 174)
end
end
-- Destroys a path if it exists
function helper.removePaths()
local path = workspace:FindFirstChild("PathBlocks")
if path ~= nil then path:Destroy() end
end
return helper
