参考：http://www.jb51.cc/article/p-ktsijnyd-xn.html

1.填充地图

2.挖空需要访问的所有点

3.设置起始点

4.开始访问

4.1获取当前点4个方向上的可访问且没有访问过的点

4.2随机选择其中一个点进行访问，并设置为当前访问点，将该点加入已访问列表，同时挖空2个点之间的所有点

4.3如果当前点各个方向上都没有可访问的点，那么从之前访问过的点里随机选取一个点作为当前访问点，并重复以上步骤

5.如果所有点都已被访问过，结束，随机地图完成

代码

--[[
随机迷宫地图生成类

--]]


local RandMazeMap = class("RandMazeMap")

RandMazeMap._instance = nil

RandMazeMap._tmx = nil
RandMazeMap._emptyId = nil
RandMazeMap._fullId = nil
RandMazeMap._mapSize = nil

RandMazeMap._curPos = nil
RandMazeMap._toVisit ={} -- 用于位置直接索引
RandMazeMap._toVisitList = {} -- 用于列表序号索引
RandMazeMap._visited = {} -- 用于索引记录已访问过的点的索引 主要是方便从已访问的里面取随机点用

function RandMazeMap.GetInstance()
    if RandMazeMap._instance == nil then
        RandMazeMap._instance = RandMazeMap.new()
    end

    return RandMazeMap._instance
end

function RandMazeMap.ReleaseInstance()
    if RandMazeMap._instance ~= nil then
        RandMazeMap._instance:Release()
        RandMazeMap._instance = nil
    end
end

-- 初始化 读取tmx 获取迷宫总大小
function RandMazeMap:Init(tmx,randomSeed)
    if randomSeed == nil then
        randomSeed = os.time()
    end
    
    math.randomseed(randomSeed)

    self._tmx = tmx
    self._emptyId = self._tmx:getLayer("Pass"):getTileGIDAt(cc.p(0,0))
    self._fullId = self._tmx:getLayer("NotPass"):getTileGIDAt(cc.p(0,0))
    self._mapSize = self._tmx:getMapSize()
end

-- 生成随机地图
function RandMazeMap:MakeRandMaze(toVisit,firstVisited)
    -- 生成开始
    -- 地图填满
    self:FillMap()
    -- 设置必须经过的点 置0
    self:SetToVisit(toVisit)
    -- 挖空需要访问的点
    self:VisitAll()
    -- 设置初始点
    self:SetFirstVisited(firstVisited)
    -- 制作访问图
    self:DoVisitAll()
    -- 生成完毕
end

function RandMazeMap:FillMap()
    for w=0,self._mapSize.width-1 do
        for h=0,self._mapSize.height-1 do
            self._tmx:getLayer("Pass"):setTileGID(self._emptyId,cc.p(w,h))
            self._tmx:getLayer("NotPass"):setTileGID(self._fullId,h))
        end
    end
end

function RandMazeMap:SetToVisit(toVisit)
    if toVisit == nil then -- 内部所有点都访问一遍
        self._toVisit = {}
        self._toVisitList = {}
        for w=0,self._mapSize.width-1 do
            for h=0,self._mapSize.height-1 do
                if w%2 == 1 and h%2 == 1 and w ~= self._mapSize.width-1 and h ~= self._mapSize.height-1 then
                    self:AddToVisit(w,h)
                end
            end
        end
    else
        -- self._toVisit = toVisit
    end
end

function RandMazeMap:AddToVisit(x,y)
    -- 检查位置合法性

    table.insert(self._toVisitList,cc.p(x,y))
    if self._toVisit[x] == nil then
        self._toVisit[x] = {}
    end
    self._toVisit[x][y] = {isVisited = false,index = #self._toVisitList}
end

function RandMazeMap:VisitAll()
    for k,v in pairs(self._toVisitList) do
        self:MakeHole(v)
    end
end

function RandMazeMap:MakeHole(pos)
    self._tmx:getLayer("NotPass"):setTileGID(0,pos)
end

function RandMazeMap:SetFirstVisited(firstVisited)
    self._visited = {}
    if firstVisited == nil then -- 没有指定 则随机选一个
        firstVisited = math.random(#self._toVisitList)
    end

    self:SetVisited(firstVisited)
end

function RandMazeMap:SetVisited(visitedIndex,isNewVisit)
    if isNewVisit == nil then
        isNewVisit = true
    end

    -- 检查位置合法性

    local curPos = self._curPos
    local visitedPos = self._toVisitList[visitedIndex]
    self._curPos = visitedPos
    self._toVisit[visitedPos.x][visitedPos.y].isVisited = true

    if not isNewVisit then -- 非新添加 直接跳过下面的操作
        return
    end

    -- 记录添加到已访问表中
    table.insert(self._visited,visitedIndex)

    -- 处理ui界面部分
    -- 2点中间的所有单元都挖空
    if curPos ~= nil then
        self:MakeLineHole(curPos,self._curPos)
    end
end

function RandMazeMap:MakeLineHole(posSt,posEd)
    local offset = cc.pSub(posSt,posEd)
    local holePos = posSt
    if offset.x < 0 then -- 向右
        for i=1,-offset.x do
            holePos = cc.pAdd(holePos,cc.p(1,0))
            self:MakeHole(holePos)
        end
    elseif offset.x > 0 then -- 向左
        for i=1,offset.x do
            holePos = cc.pAdd(holePos,cc.p(-1,0))
            self:MakeHole(holePos)
        end
    elseif offset.y < 0 then -- 向上
        for i=1,-offset.y do
            holePos = cc.pAdd(holePos,cc.p(0,1))
            self:MakeHole(holePos)
        end
    elseif offset.y > 0 then -- 向下
        for i=1,offset.y do
            holePos = cc.pAdd(holePos,-1))
            self:MakeHole(holePos)
        end
    end
end

function RandMazeMap:DoVisitAll()
    local dirOffset = {
        cc.p(-2,0),cc.p(2,-2),2)
    }
    while #self._visited < #self._toVisitList do
        -- 获取各个方向相邻的访问点
        local nearPoses = {}
        for i=1,#dirOffset do
            local newPos = cc.pAdd(self._curPos,dirOffset[i])
            -- 添加~=nil判断 防止访问边界外的无效单元
            if self._toVisit[newPos.x] ~= nil and self._toVisit[newPos.x][newPos.y] ~= nil and not self._toVisit[newPos.x][newPos.y].isVisited then
                table.insert(nearPoses,self._toVisit[newPos.x][newPos.y].index)
            end
        end
        if #nearPoses > 0 then -- 存在没有访问过的点
            -- 随机方向
            local index = math.random(#nearPoses)
            -- 设置当前访问点
            self:SetVisited(nearPoses[index])
        else -- 各方向都已访问 随机直接取已访问过的点作为当前点 并重新访问
            local index = math.random(#self._visited)
            visitedIndex = self._visited[index]
            self:SetVisited(visitedIndex,false)
        end
    end
end

return RandMazeMap