使用Java幫助解決D＆D迷宮

我一直在閱讀一些已經發布在stackoverflow上的其他問題，並且我有點不知所措的搜索算法的數量。我不在尋找代碼和更多的頁面，這個頁面會覆蓋算法的背景，也可能是一些sudo代碼。我知道有像A *這樣的算法，但由於時間不夠，我不知道是否可以用這種算法來完成程序。迷宮是使用服務器程序生成的，解算器連接到服務器以便向更多的玩家發送命令。我無法訪問服務器程序中的方法。我必須解決一個被創造出來的迷宮，就像D迷宮一樣。下面是遊戲的基本概述：使用Java幫助解決D＆D迷宮

一個經典的d & d電腦遊戲由一個地牢（迷宮），在遊戲的目的是通過地牢，使一個人的方式，進入在迷宮的「入口」並退出其「出口」。爲了使的事情更具挑戰性，地牢的佈局並不知道先驗，並且有障礙物（殭屍，焦油坑和門）必須通過使用物體（票價，階梯和鍵）來克服沿途找到了。

我注意到，其他許多帖子都不必擔心障礙物完成迷宮，這是否會成爲修改算法以補償障礙物的主要問題？我想知道像右手規則這樣的東西是否可以解決迷宮問題，如果不是，那麼算法會盡可能簡單地解決迷宮問題（由於我必須儘快完成這個程序）。任何其他的鏈接都會很好，因爲我知道我必須在Objective-C中再次完成這個程序，並且我希望在這種情況發生時實現更強大的右手規則。謝謝你的幫助。

來源

2011-09-24 intelman

只是一個快速警告：右手規則不會總是解決這樣的迷宮。例如，如果你需要找到迷宮中間的東西，並且有一個島（中心島周圍的連續走廊），那麼你將永遠不會使用這個規則到達中心。 – nycdan

很好的簡單的迷宮，你基本上沿着一條路徑「走」，直到你到達十字路口。那時你記錄下你的所有選項。然後你選擇一個（使用你喜歡的任何啓發式方法，因爲你的右手技巧，你總是會「向右」）。一旦你記錄了這些選項，你就可以將它們放入堆棧。然後你繼續前進。

當你讀完一個死衚衕時，你要麼「回頭」，要麼只要彈出堆棧，選擇另一個選項並從那裏繼續。要走回頭路，你只需記錄堆棧中的每一步，然後開始解開堆棧，直到達到最後一個路口。

你可以簡單地繼續這樣做，注意怪物，例如你可以通過的東西，或者你錯過了一件物品，作爲「死衚衕」。然後，您可以在交叉口記錄這些可通過的死角，以便如果您回到交叉路口仍然在尋找出口，您可以檢查庫存中的「鑰匙」或「劍」或任何需要通過的鑰匙。當你回來時，檢查未開發路徑的選項，以及被可能失敗的東西阻塞的路徑。如果你有能擊敗怪物的物品，你可以重新找回那條路線，擊敗怪物並繼續。

我不記得這種技術是否適用於有周期的迷宮。它應該，因爲你應該始終能夠告訴你以前是否訪問過某個地點，在你身後留下一條「麪包屑」或者記錄你所看到的地點。

它當然不會告訴你最佳路徑或最佳得分路徑，只要你在它上面碰到它，它就會讓你到達出口。

當您發現交叉點時，您還可以將內部地牢表示爲內存中的連通圖，圖中的每個節點都是交集，並且每個節點之間的路徑長度（步數）爲圖中的轉換。您也可以將此圖中的障礙物表示爲節點。

所以，如果你遇到一個吸血鬼，這將是與在走廊的盡頭沒有出口的一個節點。之後，當你得到十字架和木樁時，你就會「知道」吸血鬼在哪裏，並且能夠將圖形回溯到吸血鬼（當然，假設它不移動）。

訣竅是真正建立這個圖，你去和使用股票圖的遍歷算法（其中有許多，而且他們並不難）導航從一個節點到另一個節點。

但遍歷一個簡單的迷宮，堆技術工作得很好。

附錄：

對於簡單的迷宮，單個堆疊應該是足夠的。我不知道你的地圖是如何佈局或如何定位它，等

但是你可以做的是每次移動時，只需將堆棧上的舉動。然後，當您想要回溯時，您會開始彈出堆棧並沿着相反的方向行進，直到您返回到十字路口，然後從那裏開始。

這簡直是一個「深度優先」搜索一棵樹，你不知道的還佈置的。但同樣重要的是，您還要以其他方式跟蹤您在哪裏。例如，如果您將迷宮表示爲大量地板和牆塊，則可以捕獲您在簡單列表中輸入的每個地板塊的座標。

這樣做的原因是，這樣如果在迷宮週期，你不想上，你已經走在空格「向前走」。顯然你需要這樣做時，回溯。但是當探索時，你需要知道你有沒有看到。你如何跟蹤這取決於你的地圖的數據結構。

考慮這個簡單的迷宮：

# ######## 
# ######## 
# # # # 
# # #### # 
# #a b# 
# # #### # 
# # # 
##### #### 
# c # 
# ########

你可以看到，你只需要在位置A，B和C推到堆棧中。如果你能以紀念樓你去過的地方，你的地圖看起來像這樣在第一個十字路口：

#.######## 
#.######## 
#.# # # 
#.# #### # 
#.#a b# 
#.#.#### # 
#. .# # 
##### #### 
# c # 
# ########

而且你堆看起來像：

{d,d,d,d,d,d,d,l,u}

對於7個起伏，一個離開，一個離開。

如果你不能標記地圖，你可以跟蹤座標。這完全取決於。

來源

2011-09-24 21:35:07

那麼只會有一個堆棧？如果我在死路一回，或者我在十字路口，我是否只會將積分推入堆棧？謝謝您的幫助。 – intelman

我個人會嘗試使用遞歸找到路徑。你可以有if語句來處理陷阱，還有什麼不與return語句一起來告訴你路徑。

public static int recursion(int x, int y) { 
    if (location == end) { 
     return 0; //found the end 
    } 
    if (deadEnd) { 
     //backtrack 
    } 
    if (trapName) { 
     //put whatever you need to do to get around it 
    } 
    if (x+1 <= edge) { 
     recursion(x+1,y); //Moves right 
    } 
    }

這是或多或少的僞代碼。希望它有幫助，但！

來源

2011-09-25 03:16:16 Aerophite

使用Java幫助解決D＆D迷宮

回答

相關問題