Heh, I made a maze generator in pure Lua (no ROBLOX API) not too long ago.
It also solves itself using A*
-------------------------------------------------------------------------------------------
-- Vector2
Vector2 = {}
local v2Meta = {}
local function isVector2(obj)
local success,hasValues = pcall(function ()
return obj.X + obj.Y + obj.magnitude
end)
return success
end
function v2Meta.__tostring(v2)
return v2.X..", "..v2.Y
end
function v2Meta.__eq(self,other)
return self.X == other.X and self.Y == other.Y
end
local v2Methods =
{
add = "+";
sub = "-";
mul = "*";
div = "/";
}
local v2Format = "return Vector2.new(%d%s%d,%d%s%d)"
for key,met in pairs(v2Methods) do
v2Meta["__"..key] = function (self,other)
if type(other) == "number" then
other = Vector2.new(other,other)
end
local x = self.X
local y = self.Y
local ox = other.X
local oy = other.Y
local result = v2Format:format(x,met,ox,y,met,oy)
return loadstring(result)()
end
end
function Vector2.new(x,y)
local x = tonumber(x) and x or 0
local y = tonumber(y) and y or 0
local vec =
{
X = x;
Y = y;
magnitude = math.sqrt(x^2+y^2);
}
if vec.magnitude ~= 1 and vec.magnitude ~= 0 then
vec.unit = Vector2.new(x/vec.magnitude,y/vec.magnitude)
else
vec.unit = vec
end
setmetatable(vec,v2Meta)
return vec
end
-------------------------------------------------------------------------------------------
-- Generate Random Maze
print("Generating Maze...")
local maze = {}
local width = 93
local height = 50
local cells = {}
if (width%2 == 0) then
print("\t| Warning: Maze Width should be an odd number.")
print("\t| Changing from ".. width .." to ".. width+1 ..".")
width = width + 1
end.
if (height%2 == 0) then
print("\t| Warning: Maze Height should be an odd number.")
print("\t| Changing from ".. height .." to ".. height+1 ..".")
height = height + 1
end
for x = 1,width do
cells[x] = {}
for y = 1,height do
cells[x][y] = "#"
end
end
local visited = {}
local function visitCell(x,y)
if not visited[x] then
visited[x] = {}
end
visited[x][y] = true
cells[x][y] = " "
end
local function didVisit(x,y)
return (visited[x] and visited[x][y])
end
local function inRange(pos)
if pos.X > 1 and pos.Y > 1 then
if pos.X < width and pos.Y < height then
return true
end
end
return false
end
local function getUnvisitedNeighbors(x,y)
local neighbors = {}
for ox = -1,1 do
for oy = -1,1 do
local isSame = (ox+oy==0)
local isDiag = (math.abs(ox)+math.abs(oy))==2
local cx = x+ox
local cy = y+oy
if not (isSame or isDiag) then
cx = x+(ox*2)
cy = y+(oy*2)
if cells[cx] and cells[cx][cy] and not didVisit(cx,cy) then
local pos = Vector2.new(cx,cy)
table.insert(neighbors,pos)
end
end
end
end
return neighbors
end
local activeIndex = 0
local backtrace = {}
local function depthSearch(currentCell)
local x,y = currentCell.X,currentCell.Y
visitCell(x,y)
local n = getUnvisitedNeighbors(x,y)
if #n > 0 then
activeIndex = activeIndex + 1
backtrace[activeIndex] = currentCell
local unvis = n[math.random(1,#n)]
-- break down wall
local wallBetween = currentCell + (unvis-currentCell)/2
local wx,wy = wallBetween.X,wallBetween.Y
visitCell(wx,wy)
depthSearch(unvis)
else
activeIndex = activeIndex - 1
if activeIndex > 0 then
depthSearch(backtrace[activeIndex])
end
end
end
local startPos = Vector2.new(2,2)
local endPos = Vector2.new(width-1,height)
cells[1][2] = "S"
cells[width-1][height] = "E"
cells[2][2] = " "
cells[width-1][height-1] = " "
depthSearch(Vector2.new(2,2))
for y = 1,height do
local s = ""
for x = 1,width do
s = s .. cells[x][y]
end
table.insert(maze,s)
end
---------------------------------------------------------------------------------------------
-- A* Maze Solver
print("Solving Maze...")
local data = {}
local startPos
local endPos
local abs = math.abs
local showBlocked = true
for y,row in pairs(maze) do
local x = 0
for char in row:gmatch(".") do
x = x + 1
if not data[x] then
data[x] = {}
end
if char == "S" then
startPos = Vector2.new(x,y)
data[x][y] = " "
elseif char == "E" then
endPos = Vector2.new(x,y)
data[x][y] = " "
else
data[x][y] = char
end
end
end
if not startPos then
error("FATAL ERROR: START POS NOT DEFINED IN MAZE",2)
end
if not endPos then
error("FATAL ERROR: END POS NOT DEFINED IN MAZE",2)
end
local function surroundingCells(x,y)
if y == nil then
-- hack
x,y = x.X,x.Y
end
local cells = {}
for ox = -1,1 do
for oy = -1,1 do
local cx = x+ox
local cy = y+oy
local isSame = (ox+oy) == 0
local isDiag = (abs(ox)+abs(oy)) == 2
if not (isSame or isDiag) then
local row = data[cx]
if row then
local cell = data[cx][cy]
if cell then
local data =
{
Coord = Vector2.new(cx,cy);
Cell = cell;
}
table.insert(cells,data)
end
end
end
end
end
local currentKey
return function ()
local key,value = next(cells,currentKey)
if key and value then
currentKey = key
return value.Coord,value.Cell
end
end
end
local function aStar(s,e)
local closedCache = {}
local closedList = {}
local function addToClosedList(pos)
closedList[#closedList+1] = pos
local x,y = pos.X,pos.Y
if not closedCache[x] then
closedCache[x] = {}
end
closedCache[x][y] = true
end
addToClosedList(s)
local function getOpenList(pos)
local openList = {}
for openPos,cell in surroundingCells(pos) do
if cell == " " or cell == "E" or cell == "S" then
if not closedCache[openPos.X] then
closedCache[openPos.X] = {}
end
if not closedCache[openPos.X][openPos.Y] then
openList[#openList+1] = openPos
end
end
end
return openList
end
local foundPath = false
while not foundPath do
local g = #closedList-1
local lastPos = closedList[g+1]
local openList = getOpenList(lastPos)
if #openList > 0 then
local lowestF,bestPos = math.huge,Vector2.new()
for _,pos in pairs(openList) do
local h = (endPos-pos).magnitude
if h == 0 then
addToClosedList(e)
foundPath = true
print("Path found!")
break
end
local f = g + h
if f < lowestF then
lowestF = f
bestPos = pos
end
end
if not foundPath then
addToClosedList(bestPos)
end
else
break
end
end
return foundPath,closedList
end
local findingPath = true
local function deepCopy(t)
local new = {}
for k,v in pairs(t) do
if type(v) == "table" then
new[k] = deepCopy(v)
else
new[k] = v
end
end
return new
end
local function printMaze(closedList,impossible)
print()
local dataCopy = deepCopy(data)
local startPos = closedList[1]
local endPos = closedList[#closedList]
for index,node in pairs(closedList) do
if startPos == node then
dataCopy[node.X][node.Y] = "S"
elseif endPos == node then
dataCopy[node.X][node.Y] = "E"
else
dataCopy[node.X][node.Y] = string.char(165)
end
end
local finalData = {}
local blockedNodes = 0
for y,row in pairs(dataCopy) do
for x,char in pairs(row) do
if not finalData[x] then
finalData[x] = {}
end
if char == "B" then
blockedNodes = blockedNodes + 1
char = ((showBlocked or impossible) and "/" or " ")
end
finalData[x][y] = char
end
end
for _,column in pairs(finalData) do
print(table.concat(column,""))
end
if not impossible then
print()
print("We had to block "..blockedNodes.." nodes to find a path")
print()
end
end
local function block(node)
data[node.X][node.Y] = "B"
end
local function checkIfImpossible()
for pos,cell in surroundingCells(startPos) do
if cell == " " then
return false
end
end
return true
end
local backIterates = 0
local function backIterateBlock(nodes)
while true do
local node = nodes[#nodes]
local openCells = 0
for pos,cell in surroundingCells(node) do
if cell == " " then
openCells = openCells + 1
end
end
if openCells ~= 1 then
backIterates = backIterates + 1
break
else
block(node)
table.remove(nodes,#nodes)
end
end
end
while true do
local foundPath,nodes = aStar(startPos,endPos)
if foundPath then
printMaze(nodes)
print("It required "..backIterates.." A* scans to solve.")
break
else
local isImpossible = checkIfImpossible()
if isImpossible then
print("IMPOSSIBLE TO SOLVE")
printMaze({},true)
break
else
backIterateBlock(nodes)
end
end
end
