生成迷宫使用DFS算法

这里是DFS算法 http://www.mazeworks.com/mazegen/mazetut/index.htm 生成迷宫使用DFS算法

创建CellStack（LIFO）伪代码来保存细胞位置的列表
组TotalCells =在网格
细胞的数目选择在小区随机并调用它CurrentCell
集VisitedCells = 1

而VisitedCells < TotalCells 找到CurrentCell的所有邻居有完整
所有的墙如果一个或多个发现选择一个随机
击倒它，CurrentCell之间的墙壁上CellStack
使新细胞CurrentCell

推CurrentCell位置加1 VisitedCells

其他

从CellStack弹出最近的单元格输入
使其成为CurrentCell

endIf ENDWHILE

我的Smalltalk代码

Maze>>initialize 
    |sampleCell width height n sample | 

super initialize. 
self borderWidth: 0. 
sampleCell := VisibleSquare new. 
width := sampleCell width. 
height := sampleCell height. 
self bounds: ([email protected] extent: ((width + n) @ (height + n)) + (2 * self borderWidth)). 
visitedcell :=0. 
cells := Matrix rows: 8 columns: 7 tabulate: [:i :j | self newCellAt: i at:j].

这是另一种方法。

Maze>>newCellAt:i at:j 
    |c| 
    celltotal:= 8*7. 
[(visitedcell< celltotal)] whileTrue: 
["Im stuck with selecting cells next to current cell to make it as 
Invisible square" 
"else do this" 
c := VisibleSquare new. 
origin := self innerBounds origin. 
self addMorphBack: c. 
c position: ((i - 1) * c width) @ ((j - 1) * c height) + origin. 
^ c

我有2班一个为Visiblesquare无非是红色广场等为Invisiblesquare这是空方 enter image description here

来源

2013-03-05 Irfan

那么，是什么问题？ – 2013-03-05 06:52:58

我认为你的问题在于采用rows:columns:tabulate:填写矩阵，因为你不使用算法中描述的深度优先方法（并且您似乎也在为每个单元再次循环;我没有真正按照它应该做的这个:(）从我的POV你应该：

填入矩阵中的initialize方法，将矩阵的所有方块设置为VisibleSquare的新实例（每个实例至少应保持其位置和/或对其邻居的引用，以便稍后可以请求单元的邻居）。
在initialize方法的末尾添加一个新行（如self arrangeWalls），该方法实现了本文所述的算法。

HTH

来源

2013-03-05 11:19:32

我认为你是对的，它使整个过程对我来说变得复杂了，我现在使用TiledMorph类很容易实现一个迷宫 – Irfan 2013-03-06 02:58:32

生成迷宫使用DFS算法

回答

相关问题