Below is a simple pathfinding module that works in 3D space. It was made using the A* pathfinding algorithm, which I have adapted into this module.
Disclaimer: This module is not perfect, it has only been posted here for lack of a better one. It does work and it is functional, but a better solution is likely possible and perhaps even exists somewhere. If you have any feedback for this module, please leave a reply below!
How it works
This module was made using the algorithm explained in this article:
Introduction to A* Pathfinding | Kodeco
How to use
Step 1
Retrieve the module and initialize a new pathfinder object
local pathmodule = require(game.workspace.pathfinder)
local pathfinder = pathmodule.new()
Step 2
execute the pathfinder function
local myPath = pathfinder:genPath(startPos, goalPos, resolution, size, filtered, useStaticTerrain)
Parameters
woah! that function just had a lot of arguments!
The arguments are as follows:
-
Start Position
The position from which your path will begin -
End position
The position in which your path should end -
Resolution
The pathfinder divides the world around it into a 3D grid, and tests the individual voxels to see if there is anything in the way. The size of these voxels will affect how accurate this detection will be, but also how long it will take for the pathfinder to establish a path. Bigger resolution = fast and inaccurate, small resolution = expensive and accurate. -
Test size
This parameter defaults to be the same size as resolution, but can be modified if needed. This parameter allows for the pathfinder to test an area smaller or bigger than the given resolution, allowing the pathfinder to fit through smaller gaps and maintain the same resolution (or prevent it from fitting through bigger ones). Pathing between waypoints is verified via raycast, so this shouldn’t allow for paths to occur through walls. While this does make the pathfinding footprint smaller, it is still not perfect as it still has to align itself to the grid. Use of this parameter is not recommended, but provided as needed. -
Filtered
This parameter accepts an array of instances. Any instances included in this array will not be considered in the pathfinding operation. Useful for preventing the pathfinder from trying to pathfind around itself -
useStaticTerrain
Boolean parameter. When enabled, the code will save terrain voxels to a table each time they are queried, so that they do not need to be tested again the next time that voxel is interacted with by the pathfinder. Can help performance over server lifetime, but use is not advised if any terrain is modified during runtime.
Only the start position and end position parameters are required for the pathfinder to function.
Source code
--object initialization
Pathfinder = {}
Pathfinder.__index = Pathfinder
function Pathfinder.new() return setmetatable({}, Pathfinder) end
--constants
DEFAULT_RESOLUTION = 20
DIRECTIONS = {
Vector3.yAxis,
-Vector3.yAxis,
Vector3.xAxis,
-Vector3.xAxis,
Vector3.zAxis,
-Vector3.zAxis,
}
--for static terrain
local discoveredTerrainVoxels = {}
--fills a voxel with a part, for debug purposes
function DEBUG_FILLVOXEL(pos, size)
local part = Instance.new("Part")
part.Anchored = true
part.Position = pos
part.Size = Vector3.new(size, size, size)
part.CanCollide = false
part.CanQuery = false
part.CanTouch = false
part.Transparency = .9
part.Material = Enum.Material.Neon
part.Color = Color3.new(math.random(1,100)/100,math.random(1,100)/100,math.random(1,100)/100)
part.Parent = game.Workspace
return part
end
function GridVector(pos, resolution)
return Vector3.new(math.round(pos.X/resolution)*resolution, math.round(pos.Y/resolution)*resolution, math.round(pos.Z/resolution)*resolution )
end
--checks for both terrain and part collisions in area
local colCount = 0
function checkCollision(pos, size, params, ignoreWater, useStaticTerrain)
--smooth out performance cost
if colCount > 25 then
task.wait()
colCount = 0
else
colCount+=1
end
--static check
local terrainEmpty = nil
if useStaticTerrain then
--check that this recorded voxel has been recorded for this size
local entry = discoveredTerrainVoxels[pos][size]
if entry then
terrainEmpty = true
if entry.full then return true end
if entry.water and not ignoreWater then return true end
end
end
--part check
local parts = workspace:GetPartBoundsInBox(CFrame.new(pos), Vector3.new(size, size, size), params)
--part found, return true
if #parts > 0 then
return true
end
--terrain check
if not terrainEmpty then
--read the terrain
local regionsize = Vector3.new(size, size, size)/2
local mat, occ = workspace.Terrain:ReadVoxels(Region3.new(pos - regionsize, pos + regionsize), 4)
local foundMaterials = {}
local readsize = mat.Size
for x = 1, readsize.X, 1 do
for y = 1, readsize.Y, 1 do
for z = 1, readsize.Z, 1 do
foundMaterials[#foundMaterials+1] = mat[x][y][z].Name
end
end
end
--detect solid and liquid terrain
local full = false
local water = false
for _, i in pairs(foundMaterials) do
if i == "Air" then continue end
if i == "Water" then
water = true
else
full = true
end
end
--insert into discovered table if static terrain is enabled. documents sizes of checks used on this voxel
if useStaticTerrain then
local entry = discoveredTerrainVoxels[pos]
if entry then
discoveredTerrainVoxels[pos][size] = {
full = full,
water = water
}
else
entry = {}
entry[size] = {
full = full,
water = water,
}
discoveredTerrainVoxels[pos] = entry
end
end
if water and not ignoreWater then return true end
if full then return true end
end
return false
end
--removes unnecessary waypoints from path
function cullPath(path, ignoreWater)
local newPath = {path[1]}
local previous = path[1]
local goal = path[#path]
local params = RaycastParams.new()
params.IgnoreWater = ignoreWater
for x, i in pairs(path) do
--skip first index
if x <= 1 then continue end
--raycast between the last added waypoint and the current waypoint
local results = workspace:Raycast(previous, (i - previous).Unit * (i-previous).Magnitude, params)
--insert the previous waypoint if a collision is found
if results then
table.insert(newPath, path[x-1])
previous = path[x-1]
end
--insert the final waypoint into the path
if i == goal then
newPath[#newPath+1] = goal
end
end
return newPath
end
-- generate a path from point A to point B
function Pathfinder:genPath(start: Vector3, goal: Vector3, resolution: number, testSize: number, filtered: {}, useStaticTerrain: boolean)
local open = {}
local closed = {}
local path = nil
resolution = math.max( resolution or DEFAULT_RESOLUTION, .1)
testSize = math.max( testSize or resolution, .1 )
start = GridVector(start, resolution)
goal = GridVector(goal, resolution)
local rayParams = RaycastParams.new()
local overParams = OverlapParams.new()
rayParams.FilterType = Enum.RaycastFilterType.Exclude
rayParams.FilterDescendantsInstances = filtered
overParams.FilterType = Enum.RaycastFilterType.Exclude
overParams.FilterDescendantsInstances = filtered
local function algorithm()
--find S
local lowestScore = math.huge
local S = nil
for v, i in pairs(open) do
if (i.G + i.H) < lowestScore then
S = v
lowestScore = i.G + i.H
end
end
--move to closed
local Sdata = open[S]
open[S] = nil
closed[S] = Sdata
--process adjacent tiles
for _, i in pairs(DIRECTIONS) do
local dir = i * resolution
local tile = S + dir
--check goal
if tile == goal then
path = {}
local currentTile = S
table.insert(path, 1, tile)
while currentTile do
table.insert(path, 1, currentTile)
currentTile = closed[currentTile].P
end
return
end
--ignore if closed
if closed[tile] then continue end
--add to open if not already there
if not open[tile] then
--collision check (collision removes voxel from consideration)
local found = checkCollision(tile, testSize, overParams, true, useStaticTerrain)
if found then closed[tile] = true continue end
--sight check (lack of sight prevents source voxel from pathing to this voxel)
local raycast = workspace:Raycast(S, dir, rayParams)
if raycast and raycast.Material ~= Enum.Material.Water then continue end
--insert tile if no collision is found
open[tile] = {
G = Sdata.G + resolution,
H = (tile - goal).Magnitude,
P = S
}
continue
end
--already in open list
local sDist = Sdata.G + resolution
local prevDist = open[tile].G
if sDist < prevDist then
open[tile] = {
G = Sdata.G + resolution,
H = (tile - goal).Magnitude,
P = S
}
end
end
return
end
open[start] = {
G = 0,
H = (start - goal).Magnitude
}
local run = true
while run do
run = false
algorithm()
if path ~= nil then break end
for _, i in pairs(open) do
run = true
break
end
end
--cull path
if path then
path = cullPath(path, true)
end
return path
end
return Pathfinder
Credit: @TrippTrapp84 for programming assistance