Matlab利用prim算法實現(xiàn)迷宮的生成
更新時間：2022年10月13日 15:12:16 作者：slandarer
普里姆算法（Prim算法），圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。本文將利用prim算法迷宮生成及其藝術(shù)渲染，感興趣的可以了解一下
最近比較忙更新頻率也慢了下來，今天帶來一個比較有趣的可視化，基于prim算法的迷宮生成并用距離生成圖片：
我通過各種向量化編程編寫了一個迷宮生成函數(shù)，由于代碼不是很短因此放在最后面展示代碼，以下展示如果將最前面的參數(shù)進行改變會有啥效果。
代碼使用
迷宮生成
迷宮生成就是用的非常簡單的prim算法，大體就是不斷的在已經(jīng)開過門的房間四周隨機選擇緊挨著的房間，直到所有房間被開過。我的代碼編寫是專門弄了五個矩陣，一個存已經(jīng)到過的房間，另外四個分別存上下左右打開過的圍墻。
如果代碼最前面的基礎(chǔ)信息設(shè)置為:
%?地圖基礎(chǔ)信息設(shè)置 mazeSize=[30,30]; SPos=[2,5]; showMap=true; showSurf=false;
就意味著繪制30x30個房間，從第二行第五個房間開始開門，展示迷宮但是不展示距離映射。
當(dāng)然設(shè)置其他大小和其他起點也可以：
映射圖
將到起點的距離映射為顏色，只需要將前面的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
多起點
值得一提的是，多個起點也是支持的?。?/p>
%?地圖基礎(chǔ)信息設(shè)置 mazeSize=[30,30]; SPos=[2,5;20,15]; showMap=true; showSurf=true;
依舊可以設(shè)置顏色和更大的地圖：
當(dāng)然不建議將大小設(shè)置為300x300以上,？？？什么玩意這么香？？？？嗷原來是我的電腦??！
完整代碼
function?primMaze
%?@author?:?slandarer
%?公眾號??:?slandarer隨筆
%?知乎????:?已由hikari更名slandarer
%?地圖基礎(chǔ)信息設(shè)置
mazeSize=[50,50];
SPos=[2,5];
showMap=true;
showSurf=true;
%?初始化可達迷宮及上下左右圍墻矩陣
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)走到過且周圍至少有一個門的房間
????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);
????%?隨機選擇一個當(dāng)前已經(jīng)走到過的房間
????tempInd=randi(size(acRow,1),[1,1]);
????tempRow=acRow(tempInd);
????tempCol=acCol(tempInd);
????%?刪掉地圖外房間位置和不可達房間位置
????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,:);
????%?隨機選擇下一個房間
????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
????%?用來顯示地迷宮的代碼
????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算法實現(xiàn)迷宮的生成的詳細(xì)內(nèi)容，更多關(guān)于Matlab prim算法生成迷宮的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了如何使用C語言開發(fā)一個簡單的俄羅斯方塊游戲,涵蓋了游戲設(shè)計、數(shù)據(jù)結(jié)構(gòu)、核心邏輯和實現(xiàn)步驟,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-12-12
Qt數(shù)據(jù)庫應(yīng)用之實現(xiàn)圖片轉(zhuǎn)pdf
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實現(xiàn)圖片轉(zhuǎn)pdf功能，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)或工作有一定參考價值，需要的可以了解一下2022-06-06
這篇文章主要為大家詳細(xì)介紹了C/C++如何實現(xiàn)跨文件共享全局變量,文中的示例代碼講解詳細(xì),具有一定的借鑒價值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01
C++實現(xiàn)字符串類型相互轉(zhuǎn)換的代碼示例
在C/C++編程中，字符串是非常基礎(chǔ)且常用的數(shù)據(jù)類型，但是由于不同的編程語言或標(biāo)準(zhǔn)庫可能采用不同的字符串類型，因此在不同的應(yīng)用場景下可能需要進行字符串類型的相互轉(zhuǎn)換，本文將介紹如何在C/C++中將char*，std::string，QString，CString/MFC?String相互轉(zhuǎn)換2023-06-06
Qt數(shù)據(jù)庫應(yīng)用之實現(xiàn)文件編碼格式識別
在做數(shù)據(jù)導(dǎo)入導(dǎo)出的過程中，如果應(yīng)用場景多了，相信各位都會遇到一個問題就是文件編碼的問題。本文將用Qt實現(xiàn)文件編碼格式識別，感興趣的可以了解一下2022-06-06
這篇文章主要為大家詳細(xì)介紹了如何使用Qt實現(xiàn)旋轉(zhuǎn)動畫效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-11-11
C 與 C++ 接口函數(shù)相互調(diào)用的實現(xiàn)
這篇文章主要介紹了C 與 C++ 接口函數(shù)相互調(diào)用的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
這篇文章主要介紹了C++實現(xiàn)字符串切割的兩種方法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
基于Qt實現(xiàn)駕?？颇靠荚囅到y(tǒng)的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何基于Qt實現(xiàn)駕?？颇靠荚囅到y(tǒng)，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Qt有一定幫助，需要的可以參考一下2022-07-07
C++自旋鎖是一種低層次的同步原語,用于保護共享資源的訪問,這篇文章主要為大家介紹了如何利用原子操作實現(xiàn)自旋鎖,感興趣的小伙伴可以了解下2023-09-09