生成迷宫的算法，请教各位！最好讲解详细一些！(300分)

生成迷宫的算法，请教各位！最好讲解详细一些！
我自己使用了取随机数的方法，但求得的迷宫十有八九走不通！欢迎指教！

没做过，不知道。
听课~
坐下来，老师们快来吧~~

关注

gz

想了一个晚上，已经有办法了——
向一片空地上随机性的投下“生长点”，从这些“生长点”产生随机增长的折线——也就是
迷宫的墙壁。这些墙壁可以在满足一定条件的情况下相互拼接，最终形成有且只有一条通路的
迷宫。一个理想的迷宫应该没有环路、没有不可能到达的空地，也就是说，迷宫中任意两个
空地之间有且只有一条通路。
Working...

先生成一个走得通的路线再在这条路线的周围添加路线并保证它们与原路线只有一处相交。
生成边框。完成了

以上的回答我觉得好像不是正解，请大家继续！非常感谢！

本人打算用OPENGL做个真正的迷宫游戏[]

同意programsky。
一个好的迷宫应该象creation-zy说的那样（果然是算法高手），而且要走过整个迷宫的
2/3以上的地面。如果太简单了，两点就一条直线也没有意思，呵呵，生长点的想法应该
可以达到很好的效果，生长点应该有足够多但不能太多，连起生长点形成通路，再生成
其它墙壁就是通路。但是其它的迷惑人的通路的算法不大好办。

如果一个迷宫满足我在上面所说的条件，那么墙壁和空地都是平等的——将一个理想的迷宫
进行“反相”操作后，仍然是一个理想的迷宫。

哈哈！终于摆平了！！！
算法思路：
在迷宫中随机撒下“种子点”，由这些种子点不断的生长、拼接，最终生成有且只有一条通路
的理想迷宫。
在生成过程中，采用了LastPoint和RepeatLastDir两个0..1的变量进行控制，可以生成不同
风格的迷宫——Perfect！
算法性能：在P4 1.6G上生成100*100的迷宫耗时6秒。
由于源代码太长，不便全部贴出，现将关键类文件的 Interface 部分贴出来。需要源代码的
富翁请发邮件到 creation_zy@sina.com，为了不增大本贴的长度，如果只是要代码的话请不要
跟贴，发mail即可，谢谢合作！

unit Maze;
interface
uses
Graphics, ExtCtrls, Classes, SysUtils;
const
CriticalWallID=256;
//临界墙壁ID——两个ID均小于等于它的墙壁不能合并
type
PWord=^Word;
TBooleanPointerFunc=function (Pointer):Boolean;
TSupList=class(TList)
private
FValidCount: Integer;
function GetValidCount: Integer;
public
property ValidCount:Integer read GetValidCount;
procedure SoftDelete(const DelIndex:Integer);
procedure SoftUndelete(const UndelIndex:Integer);
procedure SoftDeleteByValue(const Pointer);
procedure SoftUndeleteByValue(const Pointer);
function AddValid(Item: Pointer): Integer;
function AddInvalid(Item: Pointer): Integer;
function AutoSoftDel(Func:TBooleanPointerFunc):Integer;
procedure Jion(SList: TSupList);
procedure DisposeList;
procedure FreeList;
procedure Clear;
override;
constructor Create;
end;
TWordPoint=Record
X,Y:Word;
end;
TMaze=class;
TMazeWall=class
private
FMaze: TMaze;
SelfID: Integer;
FPointList: TSupList;
FLastPoint: TWordPoint;
FLastDirection: Byte;
function GetLen: Integer;
function GetExpCount: Integer;
public
property Len:Integer read GetLen;
property ExpandableCount:Integer read GetExpCount;
property LastPoint:TWordPoint read FLastPoint;
property LastDirection:Byte read FLastDirection;
procedure AddPoint(const P: TWordPoint);
procedure DelPoint(const P: TWordPoint);
procedure Jion(Wall: TMazeWall);
procedure Growth;
function GetPoint(const Index: Word):TWordPoint;
constructor Create(OwnerMaze: TMaze;
ID: Integer);
destructor Destroy;
override;
end;
TPreDefineMazeUnit=(muNotDef,muEmpty,muWall);
MazeUnitRec=Record
Kind:Byte;
//0: Empty 1: Wall
WallID:Integer;
FreeDirNum:Byte;
Age:Word;
//越小表示生成的越早
PreDef:TPreDefineMazeUnit;
//预设单元
end;
TMaze=class
private
FData:array of array of MazeUnitRec;
FSpaceCount: Cardinal;
FTotalCount: Cardinal;
FWallCount: Cardinal;
FWidth: Cardinal;
FHeight: Cardinal;
FWallList: TList;
FFreeSeekCount: Integer;
FAge: Word;
FWallID: Integer;
FWallCountBeforeCritical: Word;
FStop: Boolean;
procedure SetHeight(const Value: Cardinal);
procedure SetWidth(const Value: Cardinal);
function GetHeight: Cardinal;
function GetWidth: Cardinal;
procedure AllocateSpace;
procedure FreeSpace;
function CanMake:Boolean;
function GetANewWallID:Integer;
procedure SetMazeUnit(P:TWordPoint;Empty_Wall:Boolean;WallID:Integer);
procedure PrepareWallID;
procedure MakeNewSeek;
procedure RefreshFreeDirNumRound(const P: TWordPoint);
function CanJion(x1,y1,x2,y2:Cardinal):Boolean;
public
RepeatLastDir:Single;
LastPoint:Single;
property Width:Cardinal read GetWidth write SetWidth;
property Height:Cardinal read GetHeight write SetHeight;
property TotalCount:Cardinal read FTotalCount;
property SpaceCount:Cardinal read FSpaceCount;
property WallCount:Cardinal read FWallCount;
procedure Clear;
function NewWall(StartPoint:TWordPoint):TMazeWall;
procedure Generate;
procedure MakeDefaultWall;
procedure Stop;
procedure SetElement(x,y:Cardinal;Empty_Wall:Boolean);
procedure Draw(Image:TImage;
WallWidth: Integer;
WallColor,BlankColor,OutsideColor:TColor;
ShiftX,ShiftY:Integer);
function SaveToFile(const FileName:String):Boolean;
function SaveToBitMap(const FileName:String):Boolean;
function LoadFromFile(const FileName:String):Boolean;
function LoadFromBitMap(const FileName:String):Boolean;
function IsValidWallPoint(P:TWordPoint):Boolean;
function IsValidEmptyPoint(P:TWordPoint):Boolean;
function CanWrite(P:TWordPoint):Boolean;
function WallByID(const WallID: Integer):TMazeWall;
constructor Create;
destructor Destroy;
override;
end;

WW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WW WW WW WW WW
WW WWWWWW WWWWWW WWWWWWWWWWWWWW WW WWWWWW WW WWWWWWWWWW WWWWWWWWWWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW WW
WW WWWWWWWWWW WWWWWWWWWW WWWWWWWWWWWWWW WW WWWWWW WWWWWW WW WW WWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WWWWWW WW WW WWWWWW WW WWWWWW WW WW WW WWWWWW WWWWWW WW WWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WW WWWWWWWWWW WW WWWWWWWWWWWWWW WW WW WWWWWW WW WWWWWW WW WW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WW WW WWWWWWWWWW WWWWWW WWWWWW WW WWWWWW WWWWWW WWWWWWWWWW WW WW
WW WW WW WW WW WW WW WW WW WW
WW WWWWWW WW WWWWWWWWWW WWWWWWWWWWWWWW WW WWWWWWWWWW WWWWWWWWWW WW WW WW
WW WW WW WW WW WW WW WW WW WW WW
WW WWWWWWWWWW WW WW WWWWWW WWWWWWWWWWWWWWWWWW WWWWWW WWWWWWWWWWWWWW WW WW
WW WW WW WW WW WW WW WW WW
WWWWWW WWWWWWWWWW WWWWWW WWWWWWWWWWWWWWWWWWWWWW WW WW WWWWWWWWWWWWWWWWWW WW
WW WW WW WW WW WW WW WW WW WW
WW WW WWWWWWWWWWWWWWWWWW WWWWWWWWWW WWWWWW WWWWWW WW WWWWWW WWWWWWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WW WWWWWW WWWWWW WWWWWW WW WW WWWWWWWWWW WW WW WWWWWWWWWW WW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WWWWWW WWWWWW WWWWWW WW WW WW WW WWWWWWWWWW WWWWWWWWWW WW WW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WWWWWWWWWW WWWWWWWWWWWWWW WW WW WW WW WWWWWW WWWWWW WWWWWW WW WW WW
WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WWWWWW WWWWWW WWWWWWWWWWWWWW WWWWWW WWWWWW WWWWWWWWWW WW WW WWWWWW
WW WW WW WW WW WW WW WW
WW WWWWWWWWWW WWWWWW WWWWWW WWWWWWWWWWWWWWWWWW WWWWWW WWWWWW WW WWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WWWWWWWWWW WW WWWWWWWWWW WWWWWWWWWWWWWW WW WW WW WW WW WW WW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WWWWWW WW WW WW WWWWWW WW WW WW WW WW WW WWWWWW WWWWWW WWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW WW WW WW WW
WW WW WW WWWWWWWWWW WW WW WWWWWW WW WW WWWWWW WWWWWWWWWWWWWW WWWWWW WW
WW WW WW WW WW WW WW WW WW WW WW
WW WW WW WWWWWWWWWWWWWW WWWWWWWWWW WW WWWWWWWWWW WWWWWWWWWW WWWWWW WWWWWW
WW WW WW WW WW WW WW WW WW WW WW
WW WW WW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WW WWWWWWWWWW WWWWWW WWWWWWWWWW WW
WW WW WW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WW

生成的迷宫样图，请看：
http://images.sonicalbum.com/upload_028/myphotos/creation_zy_Maze.gif
http://images.sonicalbum.com/upload_028/myphotos/creation_zy_Maze1.gif
http://images.sonicalbum.com/upload_028/myphotos/creation_zy_Maze2.gif
唉！便宜无好货呀！ 上面的图片链接可能变动的，如果发现不能看，请将upload_028中
后面的数字加减一二试一试（比如今天（8月9日）就便成了 .../upload_029/...）

总算找到了一个能用的主页空间，大家可以到下面这个页面去下载源代码：
http://www24.brinkster.com/creationzy/myprg.htm

算法思路：
两个主要运算对象：迷宫地图的二维矩阵以及迷宫的墙壁，它们分别由TMaze和TMazeWall
进行管理。而一个TMaze又可以包含若干个TMazeWall对象。
迷宫的单元(FData[][])的结构为:
MazeUnitRec=Record
Kind:Byte;
//0: Empty 1: Wall
WallID:Integer;
FreeDirNum:Byte;
Age:Word;
//越小表示生成的越早
PreDef:TPreDefineMazeUnit;
//预设单元
end;
其中，Kind表示是墙壁还是空白；WallID表示该格所在墙壁的ID号（如果是空白则为0）；
FreeDirNum表示该点可以“发展”的方向数（0..4）；Age表示该点被赋值为墙壁时整个迷宫
的“年龄”；PreDef表示该点是否被预设，如果被预设，则在生成迷宫的过程中该点的Kind
状态不能被改变。
本算法中地图上只有x,y座标都能被2整除的点才能成为生成墙壁的“种子点”，所以矩阵
的实际长度、宽度均为设定值的2倍+1。
生成迷宫的过程为：
1.生成迷宫的两个进出口以及位于左下、右上方的两个墙壁（WallID分别为1,2）；
TMaze.MakeDefaultWall
2.释放被已经合并了的墙壁；
TMaze.MakeDefaultWall
3.根据剩余的未被占用的墙壁种子点的数量以及当前的墙壁数生成新的墙壁；
TMaze.FreeJoinedWall
4.随机选择若干个墙壁进行生长（Growth）操作
TMazeWall(FWallList[n]).Growth
5.如果剩余的墙壁种子点的数量为0，且墙壁数量为2，则结束生成过程；否则转到过程2。
关键的Generate过程代码如下：
procedure TMaze.Generate;
var
i,n,OldSpaceCount,c:Cardinal;
OldJoinRand:Single;
begin
if FData=nil then
AllocateSpace;
FStop:=false;
OldJoinRand:=JoinRand;
Inc(FAge);
c:=0;
//防止死循环的计数器
while (not FStop) and ((FFreeSeekCount>0) or
(FWallList.Count>FWallCountBeforeCritical)) and not (c>=10000000)do
begin
FreeJoinedWall;
MakeNewSeek;
if FFreeSeekCount=0 then
JoinRand:=1;
//when there is no free space - you can just join
with FWallListdo
for i:=0 to Count-1do
begin
OldSpaceCount:=FSpaceCount;
if (Count>3) and (Random<0.99) then
n:=Random(Count-2)+2
else
n:=Random(Count);
TMazeWall(FWallList[n]).Growth;
if OldSpaceCount<>FSpaceCount then
Inc(FAge);
end;
Inc(c);
end;
JoinRand:=OldJoinRand;
end;

下一个核心算法就是墙壁的生长、拼接算法了。在介绍算法之前，我先对TMazeWall进行一些
必要的说明：
FPointList: TSupList;
用于存放属于迷宫的点的坐标（TWordPoint）。
为了实现特殊功能以及提高算法效率，我采用了继承自TList类的TSupList类。该类中的数据
虽然还是在同一个List数组中，但是被ValidCount分割为了两部分，前一部分存放“可生长”
点，后一部分存放“不可生长”点，这样人为分割之后，我就可以用Random进行快速的可生长
点的随机选择。之所以想到采用这个类，是受到了Aimingoo在
http://www.delphibbs.com/delphibbs/dispq.asp?lid=650664
中提出的高速成批操作TList元素方法的启发。我在此用一个类将“软删除”功能进行了封装，
极大的方便了编程。
墙壁的生长、拼接算法的基本思想如下：
一个点的“可生长”性可以由它的FreeDirNum确定。如果它的周围没有任何墙壁或者已经被
预定义的点，那么FreeDirNum应该为4；如果其中有的方向已经被“墙壁”占据，那么就要用
CanJoin函数进行可连接性判断。
CanJoin函数的思想为：如果两个点之中有一个为空白，并且没有被预设的空白，那么它们
就是可连接的；如果两个点都是墙壁，那么就要根据它们的WallID进行判断——如果两个点的
WallID相同，那么就是不可连接的——否则就会形成“墙壁环路”（原因请大家自行思考），
如果不同，那么只要其中一个的WallID大于CriticalWallID，那么他们就是可拼接的（注意到
整个迷宫至少要有两个墙壁，这两个墙壁肯定是不可拼接的——否则迷宫肯定走不通！）。
TMazeWall.Growth过程（即墙壁的生长过程）的步骤是：
1.随机选择一个可“生长”的点
2.对该点进行“生长”操作
3.更新迷宫的地图
具体代码为：
procedure TMazeWall.Growth;
var
wp,nwp:TWordPoint;
function TestDir(const d:Byte):Boolean;
begin
with wpdo
case d of
0: Result:=(y>0) and FMaze.CanJion(x,y,x,y-2);
1: Result:=(x<FMaze.FWidth-1) and FMaze.CanJion(x,y,x+2,y);
2: Result:=(y<FMaze.FHeight-1) and FMaze.CanJion(x,y,x,y+2);
3: Result:=(x>0) and FMaze.CanJion(x,y,x-2,y);
else
Result:=false;
end;
end;
function TestJoin:Boolean;
begin
Result:=true;
with nwpdo
if FMaze.FData[x][y].WallID>0 then
Result:=Random<=FMaze.JoinRand;
end;
var
i,dir,c:Integer;
begin
if SelfID<0 then
//删除标记
exit;
if (FLastPoint.X=$FFFF) or (Random>=FMaze.FLastPointRand) then
begin
i:=Random(FPointList.ValidCount);
wp:=TWordPoint(Self.FPointList);
end
else
begin
wp:=LastPoint;
if Random<=FMaze.FLastDirRand then
begin
if TestDir(FLastDirection) then
begin
nwp:=WPByDir2(wp,FLastDirection);
if not TestJoin then
exit;
AddPoint(WPByDir(wp,FLastDirection));
FLastPoint:=nwp;
AddPoint(FLastPoint);
exit;
end;
end;
end;
with wpdo
dir:=Random(FMaze.FData[x][y].FreeDirNum);
c:=0;
for i:=0 to 3do
begin
if TestDir(i) then
begin
if c=dir then
begin
nwp:=WPByDir2(wp,i);
if not TestJoin then
exit;
AddPoint(WPByDir(wp,i));
FLastPoint:=nwp;
AddPoint(FLastPoint);
FLastDirection:=i;
end;
Inc(c);
end;
end;
end;

随着生成过程的进行，“墙壁”们不可避免的要进行拼接操作。拼接的过程是：
1.判断哪个墙壁是“被合并”的——如果两者之中有一个的SelfID小于CriticalWallID，
那么另一个墙壁就是被合并方；如果两者的SelfID均大于CriticalWallID，那么总长度短的
就作为被合并方，以减小运算的复杂性；
2.将被合并方的所有元素添加到合并方的元素列表中（注意到有必要让两者的Valid部分
合并，所以采用了TSupList.Join方法）；
3.更新所有属于被合并方的点的WallID属性，将其设为合并方的SelfID；
4.刷新新列表所有点的FreeDirNum属性（TMaze.RefreshFreeDirNumRound过程）；
5.将被合并方的SelfID置为-1，即做上删除标记，让TMaze.FreeJoinedWall过程完成删除。
代码如下：
procedure TMazeWall.Jion(Wall: TMazeWall);
var
i,id:Integer;
W0,W1:TMazeWall;
//W0: the longer wall (or id <=CriticalWallID) --do
n't change
begin
if (SelfID<=CriticalWallID) or ((Wall.SelfID>CriticalWallID) and
(FPointList.Count>Wall.FPointList.Count)) then
begin
W0:=Self;
W1:=Wall;
end
else
begin
W0:=Wall;
W1:=Self;
end;
id:=W0.SelfID;
for i:=0 to W1.FPointList.Count-1do
//刷新所有的WallID属性
with TWordPoint(W1.FPointList)do
FMaze.FData[x][y].WallID:=id;
W0.FPointList.Jion(W1.FPointList);
for i:=0 to W1.FPointList.Count-1do
//刷新所有的FreeDirNum属性
FMaze.RefreshFreeDirNumRound(TWordPoint(W1.FPointList));
W1.SelfID:=-1;
//删除标记
end;

最后一个需要说明的地方就是更改TMaze地图上点的属性的TMaze.SetMazeUnit过程了。
它调用了RefreshFreeDirNumRound过程，由后者根据地图点更新前后的FreeDirNum数值自动
完成对相应墙壁的添加、删除点操作。
它们的代码如下：
procedure TMaze.SetMazeUnit(P: TWordPoint;
Empty_Wall: Boolean;
WallID: Integer);
var
x,y:Integer;
pmu:^MazeUnitRec;
begin
x:=P.X;
y:=P.Y;
pmu:=@FData[x][y];
if Empty_Wall then
begin
//空格
if pmu^.Kind=0 then
exit;
Inc(FSpaceCount);
pmu^.Kind:=0;
pmu^.WallID:=0;
if IsValidWallPoint(P) then
//增大自由种子数
begin
Inc(FFreeSeekCount);
RefreshFreeDirNumRound(P);
end;
end
else
begin
//墙壁
if pmu^.Kind=1 then
exit;
Dec(FSpaceCount);
pmu^.Kind:=1;
pmu^.WallID:=WallID;
pmu^.Age:=FAge;
if IsValidWallPoint(P) then
//减小自由种子数
begin
Dec(FFreeSeekCount);
RefreshFreeDirNumRound(P);
end;
end;
end;

procedure TMaze.RefreshFreeDirNumRound(const P: TWordPoint);
procedure RefreshOneDir(x,y:Word);
var
dir:Byte;
begin
dir:=0;
if x>0 then
if CanJion(x,y,x-2,y) then
Inc(dir);
if x<FWidth-1 then
if CanJion(x,y,x+2,y) then
Inc(dir);
if y>0 then
if CanJion(x,y,x,y-2) then
Inc(dir);
if y<FHeight-1 then
if CanJion(x,y,x,y+2) then
Inc(dir);
if FData[x][y].FreeDirNum>0 then
begin
if dir=0 then
WallByID(FData[x][y].WallID).FPointList.SoftDeleteByValue(
Pointer(WordPoint(x,y)));
end
else
if dir>0 then
WallByID(FData[x][y].WallID).FPointList.SoftUndeleteByValue(
Pointer(WordPoint(x,y)));
FData[x][y].FreeDirNum:=dir;
end;
var
x,y:Word;
begin
if IsValidWallPoint(P) then
begin
x:=P.X;
y:=P.Y;
RefreshOneDir(x,y);
if x>0 then
RefreshOneDir(x-2,y);
if y>0 then
RefreshOneDir(x,y-2);
if x<FWidth-1 then
RefreshOneDir(x+2,y);
if y<FHeight-1 then
RefreshOneDir(x,y+2);
end;
end;

强烈佩服中！

问题：
>>随便看看, 时间：2002-8-19 20:36:00, ID：1274407
...我想向你请教一下，算法应该是建立在数据结构的基础上吧，你在回答那个迷宫的算法
时用到了哪些数据结构？还有就是请你介绍几本关于算法的好书以及你自己学习算法的经验
好吗？
另外我刚开始学Delphi，我看到好像一些命名的前面都有个T，这代表什么意思？

回答：
也许是我在上面说的不到位，我在现针对数据结构进行简要说明：
地图：二维数组（FData:array of array of MazeUnitRec），每个元素与实际地图上的一个
图元相应。
墙壁列表：列表类型（FWallList: TList），用于管理迷宫中的所有墙壁。
墙壁（TMazeWall）：专用的列表类型（TSupList），列表的元素用于存放墙壁所包含的点的
(x,y)座标。
我看过的算法书不多，仔细看过的只有老师上过的清华大学出版社《数据结构》Pascal版。
我个人认为算法的书没有什么好坏之分，只要将基本的数据类型讲完即可。
写算法程序就像解数学或物理题一样，掌握几个必要的公式，然后就看你的思路是否灵活、
开阔了。我认为只要理科成绩过硬，达到算法过硬很容易；当然，如果理科成绩不好（这通常
意味着逻辑思维能力的欠缺）的话...就不适合写算法。
"T"是"Type"的缩写，表示该标识符是用于定义“类型”的，用于和普通变量相区别。比如，
你要定义一个“轿车”类和一个由该类生成的“轿车”变量，就应该用：
type
TCar=class
...
end;

var
Car:TCar;
...
这是Delphi约定俗成的习惯，大家都已经认可，同样的，C++中，用Class的缩写"C"作为前缀。

谢谢creation-zy！！非常佩服！虽然我也学过数据结构(可能跟你学的那本一样！)，但是
我却不知道怎么用！唉~~~~~~！

接受答案了.