How would I go about making a maze - solving alghoritm

I am working on a game of mine, that takes places in a procedurally generated maze, I wanted to add a “story mode”. But that would involve making sure the generated layout is valid, it would be considered valid if accessing certain locations in the map (also random) was possible, let me Illustrate what I mean:

The red area would be where the player starts, and I want to find out if they can get to the green tiles, references to the tiles are stored in a table that contains arrays for each column, and each column array contains the tiles in that column, starting from 1 (left to right, bottom to top), so for this example, the tile at the bottom left corner could be accessed as Tiles[1][1], and the top right Tiles[16][16], with the first index being X and the second one Y.

In addition, I can also get the directions from which you can enter that tile, let´s say that a tile has the wall at the bottom, so you can enter from its X Position +1 or -1 and it´s Y position +1, Unless of course, those entrances are blocked by the tiles in those positions, but i can also check that, with the same info.

With this information, how could I go about making the alghoritm? I am not asking for someone to make the script for me, but rather to get help on how I should do it, because I am not sure where to start, all I have figured so far is that It probably will make use of recursive functions.

1 Like

There’s lots of information online, try searching. Look up breadth-first-search/depth-first-search.

But depending on the exact algorithm you’re using, it might be that it’s guaranteed to always make every place accessible anyway so no need to check.

3 Likes

You could make a path with Pathfinding Service and check if the generated path has any waypoints. If it has, it means the the player can get to the point.

1 Like

I think there’s also a better way of doing this using Pathfinding but I’m not very experienced in it.

1 Like

Yeah, that did the trick, now I just have to find a way to expedite the process because the maze is big and it takes a full 20 minutes or so. :sweat_smile:

After messing around for a bit I found a way to make it quicker, it’s now under 5 minutes. tysm :pray:

How big is your maze? O.O Even a pretty big maze, like 100x100, shouldn’t take more than a few seconds

Its a 64 x 64 maze actually, probably takes that much because I am not only using a wait() in-between investigating each tile’s neighboring tiles, but also pathfinding to 40 points in the maze.

Ah yeah having unnecessary waits slows it down obviously, and there are also more efficient ways than doing a completely separate pathfinding-run for each point although it gets a bit more complicated then. Feel free to post if you want help making it faster :slight_smile:

Ok, I am not the best at writing clean code though.

This is how I reach each node:

local function ColorModel(model , color) --Used for testing purposes
	for i , v in pairs(model:GetDescendants()) do
		if v:IsA("BasePart") then
			if not color then
				v.Color = Color3.new(0.0980392, 1, 0)
			else
			v.Color = color
			end
		end
	end
end

local function WrapAround(num) --Wrap around function because the maze wraps around itself
	if typeof(num) == "table" then
		local nums = {}
		for i , v in pairs(num) do	
			nums[i] = WrapAround(v)
		end
		return nums
	end
	
	if typeof(num) == "Vector2" then
		return Vector2.new(WrapAround(num.X) , WrapAround(num.Y))
	end
	
	if num < 1 then
		num += TilesLength
	elseif num > TilesLength then
		num -= TilesLength
	end
	return num
end

local function AbsoluteVector3(vector) --I used this to attempt to calculate the neearest tile taking the wrap around feature into account.
	return Vector3.new(math.abs(vector.X),math.abs(vector.Y),math.abs(vector.Z))
end


local function ComputeTile(Tile)
	local PathOptions = {}
	local currentPosition = Vector2.new((Tile.Tile:GetPivot().Position.X + (tiles.Size / 2)) / 16 , (Tile.Tile:GetPivot().Position.Z + (tiles.Size / 2)) / 16)
	local nodeReached = false
	
	ColorModel(Tile.Tile)

	for i , e  in pairs(Tile.Entrances) do --For each neighboring tile

		local targetTile = tileData[WrapAround(e.X)][WrapAround(e.Y)] --Check the tile in that entrance position
		
		if table.find(WrapAround(targetTile.Entrances) , currentPosition) then -- if you can enter this tile from the selected entrance tile then
			
			if game.CollectionService:HasTag(targetTile.Tile , "Node") then -- if the current tile is next to a node tile, that means it is a reachable node
				nodeReached = true
				ColorModel(targetTile.Tile)
				game.CollectionService:RemoveTag(targetTile.Tile , "Node")
				targetTile.Status = "Node"
				ColorModel(targetTile.Tile.RoomValue.Value)
			end
			
			
			if targetTile.Status == "New" or targetTile.Status == "Wall"then --Mark the tile as an untestedPath if it was not approached previously or deemed impassable
			ColorModel(targetTile.Tile , Color3.new(1, 0.415686, 0))
			targetTile.Status = "UntestedPath"
			table.insert(PathOptions , targetTile)
			end
			
		elseif targetTile.Status == "New" then --Wall status can only be granted if the tile hasn't been walked through before, it can be removed though
			ColorModel(targetTile.Tile , Color3.new(1, 0, 0))
			targetTile.Status = "Wall"
		end
		
			ColorModel(Tile.Tile , Color3.new(1, 1, 1)) --Mark the path as tested so it isn't in the nearby untested tiles list
			Tile.Status = "TestedPath"
	
	end
	
	return PathOptions , nodeReached --return nearby accessible tiles and wether a node was reached
end

local starterTile = tileData[31][30]
local nearbyTiles = {}
local Nodes = game.CollectionService:GetTagged("Node")
	
table.sort(Nodes, function(NodeA , NodeB) --Sort nodes by the nearest to the center
	return NodeA:GetPivot().Position.Magnitude < NodeB:GetPivot().Position.Magnitude
end) 
	
for i , v in pairs(ComputeTile(starterTile)) do --Compute the starting tile to get the first nearby rooms in the array
	table.insert(nearbyTiles , v)
end
	
repeat

	local NewTiles, reachedNode = ComputeTile(nearbyTiles[1]) --Compute the first nearby tile
	for i , v in pairs(NewTiles) do
		if not table.find(nearbyTiles , v ) then
			table.insert(nearbyTiles , v) --insert the tiles that weren't there previously
		end
	end
	
	for i , v in pairs(nearbyTiles) do
		if string.sub(v.Status,1,8) ~= "Untested" then
			table.remove(nearbyTiles , i)
		end
	end
	
	table.sort(nearbyTiles , function(tileA, tileB)
		return (AbsoluteVector3(Nodes[1]:GetPivot().Position) - AbsoluteVector3(tileA.Tile:GetPivot().Position)).Magnitude > (AbsoluteVector3(Nodes[1]:GetPivot().Position) - AbsoluteVector3(tileB.Tile:GetPivot().Position)).Magnitude
		end) --Sort the nearby tiles so that
		
	if reachedNode == true then
			table.remove(Nodes , 1) --Removed the reached node
			workspace.Step.Value += 1
		warn("Step " .. workspace.Step.Value)
	end
	wait()
until #Nodes == 0 or #nearbyTiles == 0

I put a wait after checking around each tile because otherwise I get a script timeout error.
Due to how I coded it, every node after the first just pathfinds from the UntestedTile closest to that node.

Instead of waiting after computing 1 tile, it might be better to compute 5 or 10 tiles at one time and then wait. It should be faster and still prevent the timeout error.

1 Like