203 lines
7.4 KiB
Lua
203 lines
7.4 KiB
Lua
-- Copyright 2016 rnd
|
|
|
|
-- This program is free software: you can redistribute it and/or modify
|
|
-- it under the terms of the GNU General Public License as published by
|
|
-- the Free Software Foundation, either version 3 of the License, or
|
|
-- (at your option) any later version.
|
|
|
|
-- This program is distributed in the hope that it will be useful,
|
|
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
-- GNU General Public License for more details.
|
|
|
|
-- You should have received a copy of the GNU General Public License
|
|
-- along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
|
|
|
|
----------------------------------------------------------------------------------------------------------
|
|
-- maze generation
|
|
-- http://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search, recursive backtracker
|
|
-- representation of node coordinate (row,coloumn)=(i,j) -> (i-1)*n+j, i=1..n, j=1...m
|
|
-- representation of walls: below node k --> k, left of node k --> k+m.n
|
|
|
|
-- good overview of maze generation algorithms using javascript/html5
|
|
-- http://www.jamisbuck.org/presentations/rubyconf2011/index.html#recursive-backtracker
|
|
|
|
-- helper functions
|
|
--stack in lua
|
|
local stack={};
|
|
function stack.push(s,e) s[#s+1]=e end
|
|
function stack.pop(s) local r = s[#s];s[#s]=nil;return r end
|
|
--function table2string(s) local r = ""; for i,v in pairs(s) do r = r.. " ["..i.."]=".. v ; end return r end
|
|
|
|
function maze_deep_first_search(m,n,start,seed) -- returns a table of strings representing line renders
|
|
|
|
local steps,maxsteps; steps= 0; maxsteps = 999999;
|
|
local maze = {}
|
|
maze.m = m; maze.n = n;
|
|
maze.unvisited = {};maze.stack = {}; maze.walls = {};
|
|
maze.free = maze.m*maze.n;
|
|
local i,j,k
|
|
local nb,wall -- unvisited neighbbors, walls
|
|
|
|
--init structures
|
|
for i=1,maze.m do
|
|
for j =1,maze.n do
|
|
k=(i-1)*maze.n+j;maze.unvisited[k]=true -- initially all cells unvisited
|
|
maze.walls[k]=true;maze.walls[k+maze.n*maze.m]=true; -- walls are there
|
|
end
|
|
end
|
|
|
|
math.randomseed(seed)
|
|
maze.current = start
|
|
maze.unvisited [ maze.current ] = false;
|
|
maze.free = maze.free-1; maze.stack[1+#maze.stack] = maze.current
|
|
|
|
while maze.free>0 and steps<maxsteps do -- main loop
|
|
steps=steps+1
|
|
-- check current node neighbors
|
|
k=maze.current
|
|
j = k % maze.n;i=math.ceil(k/maze.n); -- get coords back from index
|
|
if j==0 then j = maze.n end
|
|
--print("coords current node "..k .. " = " .. i .. " " ..j)
|
|
|
|
nb={};wall={}-- check unvisited neighbors & wall removals
|
|
|
|
if i>1 then -- down
|
|
k=(i-2)*maze.n+j; if maze.unvisited[k] then wall[#wall+1]=k+maze.n;nb[#nb+1]=k end
|
|
end
|
|
if i<maze.m then -- up
|
|
k=(i)*maze.n+j; if maze.unvisited[k] then wall[#wall+1]=k;nb[#nb+1]=k end
|
|
end
|
|
if j<maze.n then --right
|
|
k=(i-1)*maze.n+j+1; if maze.unvisited[k] then wall[#wall+1]=k+maze.n*maze.m; nb[#nb+1]=k end
|
|
end
|
|
if j>1 then --left
|
|
k=(i-1)*maze.n+j-1; if maze.unvisited[k] then wall[#wall+1]=k+1+maze.n*maze.m;nb[#nb+1]=k end
|
|
end
|
|
|
|
--print(" unvisited neighbors " .. table2string(nb))
|
|
if (#nb)>0 then -- if unvisited neighbors, choose random one as next current node
|
|
stack.push(maze.stack,maze.current) -- remember previous current node
|
|
k=math.random(#nb); -- pick random unvisited neighbor
|
|
maze.walls[wall[k]]=false; -- remove wall
|
|
--print(" removed wall ".. wall[k])
|
|
k=nb[k];
|
|
maze.current = k; -- new current cell
|
|
maze.unvisited[k]=false; maze.free = maze.free-1 -- one less unvisited
|
|
--print("new explore " .. k);
|
|
|
|
elseif (#maze.stack)~=0 then -- no unvisited neighbors, backtrack using stack
|
|
|
|
maze.current = stack.pop(maze.stack)
|
|
--print("backtrack to "..maze.current)
|
|
|
|
else -- even stack is empty, just pick random unvisited cell
|
|
k = math.random(maze.free); j=1;
|
|
for i =1,maze.m*maze.n do
|
|
if maze.unvisited[i] then
|
|
if j==k then k=i; break end -- pick node
|
|
j=j+1
|
|
end
|
|
end
|
|
--print(" stack empty, random pick " ..k)
|
|
maze.current=k;maze.unvisited[k]=false; maze.free = maze.free -1;
|
|
end
|
|
end -- of do
|
|
|
|
-- render maze with chars, row by row
|
|
maze.ret = {};
|
|
local hor;local vert;
|
|
local wall = "1"
|
|
|
|
for i=1,maze.m do
|
|
hor="";vert="";
|
|
k= (i-1)*maze.n;
|
|
-- horizontal
|
|
for j = 1, maze.n do
|
|
k=k+1;
|
|
-- if maze.walls[k+maze.n*maze.m] then vert=vert.."X." else vert=vert.. "0." end
|
|
-- if maze.walls[k] then hor=hor.."XX" else hor=hor.."X0" end
|
|
if maze.walls[k+maze.n*maze.m] then vert=vert..wall.."0" else vert=vert.. "00" end
|
|
if maze.walls[k] then hor=hor..wall..wall else hor=hor..wall.."0" end
|
|
end
|
|
maze.ret[1+#maze.ret]=hor..wall;maze.ret[1+#maze.ret]=vert..wall;
|
|
end
|
|
maze.ret[1+#maze.ret] = string.rep(wall,2*maze.n+1)
|
|
return maze.ret
|
|
end
|
|
|
|
-- RUN PROGRAM
|
|
-- local maze=maze_deep_first_search(10,30,1,2015)
|
|
--for _,v in pairs(maze) do print(v) end
|
|
|
|
|
|
|
|
minetest.register_chatcommand("maze", {
|
|
description = "/maze (optional m,n,start,seed) generates maze at players position, directed towards positive x,z axix",
|
|
privs = {kick = true},
|
|
func = function(name, param)
|
|
local m,n,start, seed
|
|
if param == "" then m=10;n=10;start=1;seed=1 else
|
|
local words = {}; local word
|
|
for word in param:gmatch("%w+") do words[1+#words]= word end
|
|
if words[1]~=nil then m = tonumber(words[1]) else m = 10 end
|
|
if words[2]~=nil then n = tonumber(words[2]) else n = 10 end
|
|
if words[3]~=nil then start = tonumber(words[3]) else start = 1 end
|
|
if words[4]~=nil then seed = tonumber(words[4]) else seed = 1 end
|
|
end
|
|
if m*n>1000000 then minetest.chat_send_player(name, "limit maze size to 1000000 cells") return end
|
|
local player = minetest.env:get_player_by_name(name); if player==nil then return end
|
|
local pos = player:getpos();local p
|
|
local maze=maze_deep_first_search(m,n,start,seed) -- m,n,start,seed
|
|
local i,j,k;local p = {x=pos.x,y=pos.y,z=pos.z};
|
|
--render
|
|
for i,v in pairs(maze) do
|
|
p.x = pos.x+i
|
|
for k = 1,string.len(v) do
|
|
p.z=pos.z+k
|
|
if string.sub(v,k,k)=="1" then
|
|
minetest.set_node(p,{name="basic_layout:stone_maze"})
|
|
else minetest.set_node(p,{name="air"})
|
|
end
|
|
end
|
|
end
|
|
|
|
|
|
end,
|
|
})
|
|
|
|
minetest.register_node("basic_layout:glass_maze", {
|
|
description = "maze_glass",
|
|
drawtype = "glasslike_framed_optional",
|
|
tiles = {"maze_glass.png"},
|
|
inventory_image = minetest.inventorycube("maze_glass.png"),
|
|
paramtype = "light",
|
|
sunlight_propagates = true,
|
|
is_ground_content = false,
|
|
groups = {immortal = 1,disable_jump=1},
|
|
sounds = default.node_sound_glass_defaults(),
|
|
})
|
|
|
|
minetest.register_node("basic_layout:stone_maze", {
|
|
description = "maze_wall",
|
|
tiles = {"default_brick.png"},
|
|
is_ground_content = true,
|
|
groups = {immortal = 1,disable_jump=1},
|
|
legacy_mineral = true,
|
|
sounds = default.node_sound_stone_defaults(),
|
|
on_rightclick = function(pos, node, player, itemstack, pointed_thing)
|
|
local name = player:get_player_name(); if name == nil then return end
|
|
if minetest.is_protected(pos, name) then
|
|
return
|
|
end
|
|
local player_inv = player:get_inventory()
|
|
if player_inv:room_for_item("main", {"basic_layout:stone_maze"}) then
|
|
player_inv:add_item("main", "basic_layout:stone_maze")
|
|
minetest.remove_node(pos) -- remove bones
|
|
end
|
|
|
|
end
|
|
})
|
|
|
|
|