快捷導(dǎo)航

Matlab利用prim算法實(shí)現(xiàn)迷宮的生成

更新時(shí)間：2022年10月13日 15:12:16 作者：slandarer

普里姆算法（Prim算法），圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹(shù)。本文將利用prim算法迷宮生成及其藝術(shù)渲染，感興趣的可以了解一下

代碼使用

迷宮生成

迷宮生成就是用的非常簡(jiǎn)單的prim算法，大體就是不斷的在已經(jīng)開(kāi)過(guò)門的房間四周隨機(jī)選擇緊挨著的房間，直到所有房間被開(kāi)過(guò)。我的代碼編寫是專門弄了五個(gè)矩陣，一個(gè)存已經(jīng)到過(guò)的房間，另外四個(gè)分別存上下左右打開(kāi)過(guò)的圍墻。

如果代碼最前面的基礎(chǔ)信息設(shè)置為:

%?地圖基礎(chǔ)信息設(shè)置
mazeSize=[30,30];
SPos=[2,5];
showMap=true;
showSurf=false;

就意味著繪制30x30個(gè)房間，從第二行第五個(gè)房間開(kāi)始開(kāi)門，展示迷宮但是不展示距離映射。

當(dāng)然設(shè)置其他大小和其他起點(diǎn)也可以：

映射圖

將到起點(diǎn)的距離映射為顏色，只需要將前面的showSurf更改為true:

%?地圖基礎(chǔ)信息設(shè)置
mazeSize=[30,30];
SPos=[2,5];
showMap=true;
showSurf=true;

當(dāng)然如果設(shè)置的地圖較大，建議將showMap設(shè)置為false，不然繪制的太慢了：

mazeSize=[200,200];
SPos=[50,50];
showMap=false;
showSurf=true;

當(dāng)然如果把74多行的colormap改成其他顏色，比如pink、bone、turbo、colorcube：

當(dāng)然colormap可以自己設(shè)置的更復(fù)雜：

%?自定義色帶
if?1
Cmap=[89,214,179
140,181,195
177,156,206
241,189,239
215,193,244
178,199,253
140,189,234
145,166,229
106,85,202]./255;
Ci=1:size(Cmap,1);Cq=linspace(1,size(Cmap,1),300);
Cmap=[interp1(Ci,Cmap(:,1),Cq,'linear')',...
?????interp1(Ci,Cmap(:,2),Cq,'linear')',...
?????interp1(Ci,Cmap(:,3),Cq,'linear')'];
colormap(Cmap)
end

多起點(diǎn)

值得一提的是，多個(gè)起點(diǎn)也是支持的！！

%?地圖基礎(chǔ)信息設(shè)置
mazeSize=[30,30];
SPos=[2,5;20,15];
showMap=true;
showSurf=true;

依舊可以設(shè)置顏色和更大的地圖：

當(dāng)然不建議將大小設(shè)置為300x300以上,？？？什么玩意這么香？？？？嗷原來(lái)是我的電腦！！

完整代碼

function?primMaze
%?@author?:?slandarer
%?公眾號(hào)??:?slandarer隨筆
%?知乎????:?已由hikari更名slandarer

%?地圖基礎(chǔ)信息設(shè)置
mazeSize=[50,50];
SPos=[2,5];
showMap=true;
showSurf=true;

%?初始化可達(dá)迷宮及上下左右圍墻矩陣
mazeMat=ones(mazeSize);
mazeMat(sub2ind(mazeSize,SPos(:,1),SPos(:,2)))=0;
zerosMat=zeros(mazeSize);
disMat=zeros(mazeSize);
[UMat,DMat,LMat,RMat]=...
????deal(ones(mazeSize),ones(mazeSize),ones(mazeSize),ones(mazeSize));

if?showMap
????wallHdl=drawMap(UMat,DMat,LMat,RMat);
end

while?any(any(mazeMat))
????%?找到全部已經(jīng)走到過(guò)且周圍至少有一個(gè)門的房間
????UMazeMat=zerosMat;UMazeMat(2:end,:)=mazeMat(1:end-1,:);
????DMazeMat=zerosMat;DMazeMat(1:end-1,:)=mazeMat(2:end,:);
????LMazeMat=zerosMat;LMazeMat(:,2:end)=mazeMat(:,1:end-1);
????RMazeMat=zerosMat;RMazeMat(:,1:end-1)=mazeMat(:,2:end);
????maze4Mat=UMazeMat+DMazeMat+LMazeMat+RMazeMat;
????[acRow,acCol]=find(mazeMat==0&maze4Mat>0);
????%?隨機(jī)選擇一個(gè)當(dāng)前已經(jīng)走到過(guò)的房間
????tempInd=randi(size(acRow,1),[1,1]);
????tempRow=acRow(tempInd);
????tempCol=acCol(tempInd);
????%?刪掉地圖外房間位置和不可達(dá)房間位置
????nextPos=[tempRow,tempCol]+[-1,0;1,0;0,-1;0,1];
????nextPos(nextPos(:,1)<1,:)=[];
????nextPos(nextPos(:,2)<1,:)=[];
????nextPos(nextPos(:,1)>mazeSize(1),:)=[];
????nextPos(nextPos(:,2)>mazeSize(2),:)=[];
????nextBool=mazeMat(sub2ind(mazeSize,nextPos(:,1),nextPos(:,2)))>0;
????nextPos=nextPos(nextBool,:);
????%?隨機(jī)選擇下一個(gè)房間
????nextInd=randi(size(nextPos,1),[1,1]);
????nextRow=nextPos(nextInd,1);
????nextCol=nextPos(nextInd,2);
????mazeMat(nextRow,nextCol)=0;
????disMat(nextRow,nextCol)=disMat(tempRow,tempCol)+1;
????%?打破墻壁
????switch?true
????????case?isequal([nextRow,nextCol]-[tempRow,tempCol],[-1,0])
????????????UMat(tempRow,tempCol)=0;DMat(nextRow,nextCol)=0;
????????case?isequal([nextRow,nextCol]-[tempRow,tempCol],[1,0])
????????????DMat(tempRow,tempCol)=0;UMat(nextRow,nextCol)=0;
????????case?isequal([nextRow,nextCol]-[tempRow,tempCol],[0,-1])
????????????LMat(tempRow,tempCol)=0;RMat(nextRow,nextCol)=0;
????????case?isequal([nextRow,nextCol]-[tempRow,tempCol],[0,1])
????????????RMat(tempRow,tempCol)=0;LMat(nextRow,nextCol)=0;
????end
????%?用來(lái)顯示地迷宮的代碼
????if?showMap
????refreshMap(wallHdl,UMat,DMat,LMat,RMat)
????drawnow
????end
end
%?=========================================================================
%?繪制顏色映射圖
if?showSurf
sax=gca;hold?on
[sM,sN]=size(UMat);
sax.XLim=[0,sN]+.5;
sax.YLim=[0,sM]+.5;
sax.DataAspectRatio=[1,1,1];
surf(flipud(disMat),'EdgeColor','none')
colormap(pink)

%?自定義色帶
if?0
Cmap=[89,214,179
140,181,195
177,156,206
241,189,239
215,193,244
178,199,253
140,189,234
145,166,229
106,85,202]./255;
Ci=1:size(Cmap,1);Cq=linspace(1,size(Cmap,1),300);
Cmap=[interp1(Ci,Cmap(:,1),Cq,'linear')',...
?????interp1(Ci,Cmap(:,2),Cq,'linear')',...
?????interp1(Ci,Cmap(:,3),Cq,'linear')'];
colormap(Cmap)
end
end
%?=========================================================================
%?CODE:?test?drawMap
%?UMat(2,3)=0;
%?DMat(1,3)=0;
%?drawMap(UMat,DMat,LMat,RMat)
????function?wallHdl=drawMap(UMat,DMat,LMat,RMat)
????????ax=gca;hold?on
????????[M,N]=size(UMat);
????????ax.XLim=[0,N]+.5;
????????ax.YLim=[0,M]+.5;
????????ax.DataAspectRatio=[1,1,1];
????????%?繪制上方圍墻
????????[Y,X]=find(UMat);Y=M+1-Y;
????????X=[X.'+[.5;-.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[.5;.5];nan.*(ones(1,length(Y)))];
????????wallHdl{1}=plot(X(:),Y(:),'LineWidth',1,'Color','k');
????????%?繪制下方圍墻
????????[Y,X]=find(DMat);Y=M+1-Y;
????????X=[X.'+[.5;-.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[-.5;-.5];nan.*(ones(1,length(Y)))];
????????wallHdl{2}=plot(X(:),Y(:),'LineWidth',1,'Color','k');
????????%?繪制左側(cè)圍墻
????????[Y,X]=find(LMat);Y=M+1-Y;
????????X=[X.'+[-.5;-.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[.5;-.5];nan.*(ones(1,length(Y)))];
????????wallHdl{3}=plot(X(:),Y(:),'LineWidth',1,'Color','k');
????????%?繪制右側(cè)圍墻
????????[Y,X]=find(RMat);Y=M+1-Y;
????????X=[X.'+[.5;.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[.5;-.5];nan.*(ones(1,length(Y)))];
????????wallHdl{4}=plot(X(:),Y(:),'LineWidth',1,'Color','k');
????end
%?-------------------------------------------------------------------------
????function?refreshMap(wallHdl,UMat,DMat,LMat,RMat)
????????[M,~]=size(UMat);
????????%?繪制上方圍墻
????????[Y,X]=find(UMat);Y=M+1-Y;
????????X=[X.'+[.5;-.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[.5;.5];nan.*(ones(1,length(Y)))];
????????wallHdl{1}.XData=X(:);
????????wallHdl{1}.YData=Y(:);
????????%?繪制下方圍墻
????????[Y,X]=find(DMat);Y=M+1-Y;
????????X=[X.'+[.5;-.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[-.5;-.5];nan.*(ones(1,length(Y)))];
????????wallHdl{2}.XData=X(:);
????????wallHdl{2}.YData=Y(:);
????????%?繪制左側(cè)圍墻
????????[Y,X]=find(LMat);Y=M+1-Y;
????????X=[X.'+[-.5;-.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[.5;-.5];nan.*(ones(1,length(Y)))];
????????wallHdl{3}.XData=X(:);
????????wallHdl{3}.YData=Y(:);
????????%?繪制右側(cè)圍墻
????????[Y,X]=find(RMat);Y=M+1-Y;
????????X=[X.'+[.5;.5];nan.*(ones(1,length(X)))];
????????Y=[Y.'+[.5;-.5];nan.*(ones(1,length(Y)))];
????????wallHdl{4}.XData=X(:);
????????wallHdl{4}.YData=Y(:);
????end
end

以上就是Matlab利用prim算法實(shí)現(xiàn)迷宮的生成的詳細(xì)內(nèi)容，更多關(guān)于Matlab prim算法生成迷宮的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: