有很多方法可以用程式生成有隨機性的場景
比方說這個開源專案，可以生成有隨機性的迷宮
效果不錯
不過有個問題。起點和終點在哪裡？
如果完全隨機，有可能起點和終點就在隔壁，探索起來很無趣。
那如果以第一個生成的房間為起點，以距離他最遠的房間為終點呢？
這樣如果起點是位於中央的房間，終點還是有可能在隔壁，如下圖：
那要怎麼辦?
印象中最常路竟是NP困難問題
NP困難是什麼？
反正就是很難就對了吧(？)
還不能放棄，先仔細看一下程式碼吧...
Generator2D.cs 第 55 行
| PlaceRooms(); Triangulate(); CreateHallways(); PathfindHallways(); |
如果該區域沒有和其他房間重疊，就生成新的房間。
每個房間的中心點座標可以視為一個節點(node)
Triangulate 使用某種演算法把節點以三角形的形式連結起來
老實說我沒看懂演算法的細節
總之他把所有的頂點連結成一張圖(graph)了
CreateHallways 產生最小生成樹(Minimum spanning tree)
最小生成樹的邊就是房間之間的走廊
樹耶，沒有迴圈的圖，好像有方向了...
然後我也忘記我怎麼查到的，使用兩次DFS可以找到樹的最長路徑
這個最長路徑並不是嚴格意義上空間的最長距離
而是經過最多節點的路徑
對玩家而言，經過最多節點(房間)才能抵達終點，可以讓遊戲的探索更有趣
成果如下
灰色=牆
綠色=房間
橘色=走廊
藍色=起點
紅色=終點
