我正在一個60 * 60的場上玩蛇遊戲（Linux中的Nibbles），四個蛇爭奪一個隨機放置的蘋果。如何找到距離最近的點時，我們之間有一些塊！ （在2D 2D中 - 貪吃蛇遊戲）
我實現了我和A *（A星）Snake算法的運動。
我的問題是這樣的：當我不是最靠近蘋果的蛇時，我不想去拿蘋果，因爲我得到它的機會比至少有一條蛇低，所以我想要尋找一個地方，我希望在下一個地方，一個蘋果生成，然後我會是最接近的那個蘋果蛇。我的意思是我正在尋找一個最接近潛在位置的最大數量的地方。
請建議任何好方法或任何算法，可以幫助我找到這個地方。
這是遊戲的圖像。紅點是蛇的頭。
我測試了一些辦法，最後我決定用這種方式：
我認爲最好的辦法是讓大小爲一個二維數組：60 * 60，那麼的每個節點（X）數組，計算字段中有多少個節點（可步行！）（不是塊），是這個節點（x）最接近的。
那麼答案將是最大金額，然後我設置這個節點的目標。但由於我必須在不到0.1秒的時間內找到下一步並做這項工作，所以有4個循環的大小：60，（60^4），當我找到它時，A *算法也會運行，這項工作永遠不會在不到0.1秒內完成。因此，由於Snake不能沿對角線移動，並且它只是向上，向下，向右，向左移動，所以我決定不檢查所有節點，因爲在每個週期（0.1秒）內，我只能移動1單位，我決定檢查只有4個節點（上，下，左，右），並移動到一個節點，它的數量是最大。
現在它的工作差不多吧。 ;）
如果你是最接近蘋果，你應該走得到它，但如果你是遠離蘋果你最好的機會是走在地圖的中間，你會發現戰略，如何佔據中間的地圖。
您可以將您的地圖四個變焦（順時針），左上，右上，右下和左下角（1,2,3,4）。我們檢查兩條蛇之間的距離：如果蘋果當前處於縮放1（假設中心爲平均）並且您處於地圖中心，則對手可以放大1,2,3,4（再次假定它位於此中心位置以更簡單的方式縮小平均值）如果在縮放1中，如果縮放比例爲2或4，則它有更好的機會（1-0），距離爲sqrt（2）/ 2，對手距離爲1，因此距離您最近，最後如果你的對手在縮放3，你的距離是sqrt（2）/ 2，你的對手距離是sqrt（2），所以在3個情況下你有更好的機會。
但是因爲你的形狀有一些塊，你應該計算在其他方式的中心位置，事實上，在網格的每個點計算出所有其他點的距離。這將需要60^2 * 60^2這可以快速完成。並找到總量最小的細胞（你可以選擇最好的10個細胞），這些細胞可以成爲你的中心，每次你應該從一箇中心移動到另一箇中心（除非你離蘋果最近或者你的蛇吃蘋果，中心）。
再次，這不是要求什麼。如果左邊有一個競爭對手，那麼最好的地方就在他們的右邊。這使得你比前兩欄中的任何蘋果的競爭對手都有優勢。你的解決方案不如此。 – 2012-03-26 15:32:10
對不起 - 在這裏看到我的其他評論。如果你編輯這個答案（任何東西，只是爲了解決stackoverflow的限制），我會刪除downvote。 – 2012-03-26 15:41:45
@andrewcooke，我會編輯我的答案。 – 2012-03-26 20:11:18
既然你已經實現了A *，你生成地圖後，您可以使用A *創建每個單元映射值的基礎上，從每個單元的總成本參觀其他各小區一個。如果您在放置塊之後生成此圖，那麼您的加權圖將說明它們的存在。
要生成此，從我的頭頂，我會說，你可以從每個細胞開始，並指定了它可以在一個回合中訪問的每個小區的一個點。例如，角落中的單元格將獲得兩個點用於第一個移動，因爲它只能訪問另外兩個單元格。第二回合會得到5點，因爲它可以通過兩次移動來接近5個單元格。重複，直到你訪問所有其他廣場，然後你有該廣場的得分。
從這一點來說，如果蘋果似乎和你的蛇是不是最接近它，你的蛇可以前往最高的加權單元，您已預先計算。
編輯：請參閱下面的評論以獲得更有利的解決方案。
不是要求什麼，但是，是嗎？要求什麼取決於其他蛇的位置。 – 2012-03-26 15:30:56
@andrewcooke他正在尋找最接近所有其他地方的地方。如果他不是最接近當前的蘋果，那麼他希望領先，因爲預計會更快。 – 2012-03-26 15:35:55
我不這麼認爲。我認爲最好的地方比任何其他的蛇更接近更多的地方。如果其他蛇更近，靠近很多地方是毫無意義的。 – 2012-03-26 15:39:21
最接近的位置的最大數量爲中心，其他人都表示。比其他蛇更接近最大數量的地點是一個非常不同的和更難的問題。在那種情況下，我會讓每隻蛇的頭部看到誰控制了最多的方格。這是基礎分數。接下來，當我繪製一張空白圖時，我會在地圖上隨機設置一組點，並選擇以最高分作爲目的地的點。如果你有處理能力，你可以嘗試網格上的每一點，並選擇最好的K.G.建議，但這可能會相當激烈。
真正的考驗是，當你發現你的觀點，找出在未來需要走多遠，你到那裏，並運行一些AI爲其他蛇類，看看他們是否會攔截你。你開始進入像國際象棋這樣的大片。 :)
+1從蛇的頭部測量A *。這包含了安德魯庫克的一些關於優化你的對手的目標區域的問題，以及賽義德阿米里的一些分區想法。我想看看這個算法的視頻正在運行！ – 2012-03-27 00:11:05
似乎是一個很好的解決方案，但我沒有考慮解決方案錯誤，如果您認爲這比其他答案更好，可以將其標記爲答案。 – 2012-04-02 22:44:39