尋找符合幾個標準的2D地圖上的位置

作爲我的個人項目，我開發了一個用戶可以隨時加入的遊戲。我有一個平鋪的世界地圖，它是從一個簡單的位圖創建的，它的資源隨機位置遍佈整個地圖，除了海洋。尋找符合幾個標準的2D地圖上的位置

當一個玩家加入時，我想在一個地方創建自己的起始位置，這個地方至少有4個資源中的每個資源在1個區域內（圓圈還有一個直徑，我認爲是3-4個區塊），但沒有海洋瓷磚（Tile.Type！=「ocean」），並且不與屬於另一個玩家的字段衝突（Tile.Owner == null）。

地圖大小可以變化，目前它的大小是600x450，它被實現爲一個簡單的Array：Tile [] []，其Tile.Resource爲null或將Tile.Resource.Type作爲資源名稱的字符串（因爲它是可以通過明文文件進行配置，以適應任何我想放進去的景物，所以沒有內置的枚舉可能）。

我目前有一個簡單的循環遍歷每個可能的位置，檢查範圍中的每個字段並計算每個資源字段的數量，並丟棄它，如果其中沒有一個或者其中一個屬於某個玩家或者是一片海洋。

我寧願如果它發現一個隨機的位置，但那不是一個要求，單聲道兼容性是一個要求。

在C＃中實現算法的最佳方法是什麼？

編輯

玩家可以和將增加/變化和資源可以使用了，甚至有可能隨機出現的區域（=>「你的勘探者發現新的金礦」），以便預計算出來的職位可能會不起作用。

來源

2010-03-02 dbemerlin

您可能會考慮模擬退火......實施起來並不複雜。你有一套具有一定權重的標準，並在某個「溫度」下隨機「搖動」位置（溫度越高，位置可能隨機移動的半徑越大，距離它的上一個位置越遠），那麼當它「冷卻「你根據總權數衡量位置的價值，並減去消極的東西，比如產卵離他們死亡的地方太近，或者接近其他玩家等等，如果這個值不在一定範圍內，你降低溫度，但再次「搖動」位置，冷卻下來，檢查重量和總體值，重複，直到獲得可接受的解決方案。

模擬退火用於地圖製作，以最清晰的方式標記城市和特徵，同時保持在範圍內並使重疊最小化。由於這是一種啓發式方法，因此不能保證會有最佳解決方案，因此您不斷保持「降低溫度」並最終選擇最佳結果。

來源

2010-03-02 15:23:58

這聽起來很有趣，感謝指針。我會讀到這。 – dbemerlin 2010-03-02 16:30:43

實現這一點看起來很有趣，儘管它可能並不總能給出最好的結果，但結果應該足夠好。解決方案接受 – dbemerlin 2010-03-03 07:50:18

我自己用它來做標籤應用程序，但是我從某個遊戲AI編程文章中得到了這個想法。我不記得來源。乾杯! – 2010-03-03 13:24:59

不是循環遍歷所有的職位，爲什麼不循環所有的資源？您的資源可能會更少。然後選擇符合您的聚類標準的其中一組資源。

來源

2010-03-02 14:26:18 plinth

這可能會加快搜索速度，儘管我仍然需要計算周圍的位置，因爲玩家無法啓動資源圖塊。對於這個好主意，仍然是+1，我會這樣做，直到我得到更有效的回覆/想法。 – dbemerlin 2010-03-02 14:48:15

讓我們假設一旦你的地圖被創建，你不必經常創建一個新地圖。

只需添加以下到每個瓷磚，一旦計算它們生成地圖後：當你想獲得一個瓷磚，你可以做到這一點相當快一點

-int NrOceanTiles 
-int NrResourceA 
-int ...

現在：

IEnumerable<Tiles> goodTiles = tiles.Where(tile => tile.NrResourceA >= 1 && tile.NrResourceB >= 2); 
Tile goodTile = goodTiles.ElementAt(randomI);

來源

2010-03-02 14:34:29 Carra

請參閱我的編輯預先計算/預先定義的位置。對不起，不夠清楚。 – dbemerlin 2010-03-02 14:46:03

如果遊戲不是爲大量玩家設計的，大多數遊戲都會在地圖上實現「開始點」。您可以手動選擇它們並以某種方式記錄地圖中的位置，可能與您實施地圖資源的方式類似（即在該地點存在可拾取的項目，但在瓷磚地圖上方）。由於資源是隨機產生的，你可以不在開始點上產生資源（這可能是可見的或不可見的），或者根本不在產生資源的開始點產生一個玩家（或者在一個9格盒子來找到一個關閉的替代位置）。

當然，您會想要保存一組可能的起始位置並在資源創建和使用時更新它。

來源

2010-03-02 14:36:35

請參閱我的關於預先計算/預定義位置的編輯。對不起，不夠清楚。 – dbemerlin 2010-03-02 14:45:30

@dbemerlin：謝謝澄清。我已經更新了我的答案。 – 2010-03-02 14:52:45

預定義的數據仍然是最好的前進方向。

由於修改地圖大小和添加/丟失資源不會經常發生，只需在數據表發生更新時更新。也許您可以每天進行一次地圖/資源更改，並且每日更新數據庫中的所有內容。

通過這種方式，找到一個有效的位置將比您實現搜索周圍所有瓷磚的任何算法快得多。

來源

2010-03-02 14:51:32 Dave

這種情況下的主要問題是實時發生的玩家變化區域（類似於文明影響區域），玩家可以建立新的前哨/城市/村莊，這些新前哨/城市/村莊直接佔據他們周圍的區域。 Ofc現在正在考慮它，我可能能夠刪除新的區域和舊的預先計算的區域的交集......我將檢查它。對於好的建議事件+1，儘管我仍然希望更好/更容易。 – dbemerlin 2010-03-02 14:57:21

看起來你最好的選擇就是計算地圖生成的開放位置。你的起始位置計算功能可以選擇網格位置和大小或矩形拐角。

有一個免費位置和佔用位置的列表。玩家佔領領土？將範圍內的資源移動到佔用列表。玩家被無情壓碎？將範圍內的資源移動到空閒列表。資源被淘汰？刪除在「打開/佔用」列表中使用它的任何位置。資源添加？使用效果半徑重新計算以確定受影響的區域。當地圖區域展開時，只需在網格+效果半徑的新部分上運行初始計算並添加新位置即可。

然後，您只需設置事件並在某人加入時隨機選擇一個自由值。

來源

2010-03-02 15:27:18 Josiah

尋找符合幾個標準的2D地圖上的位置

回答

相關問題