檢查大網格上的放置重疊

我正在製作一個遊戲，您將通過連接器鏈接的建築物放置在矩形網格上。什麼都不能重疊。一旦他們在電網上，建築物和連接器就不能改變;他們可以隨時被銷燬。網格定義爲左下角爲（0,0）。檢查大網格上的放置重疊

建築是矩形，其中，每個邊緣可以是1 - 4個單元長;還有一個5x5的方塊。

連接器有一個起點和一個終點。它們不能重疊，並且有1個單位寬。他們可以直線前進編輯:(左，右，上下）並彎曲90度的任何地方。無限長度。

電網將理想是相當大的（200×200或更高），但是這意味着可以有成千上萬的這些對象和連接器。

當一個對象被建立，我需要檢查它是否與任何重疊。如果我製作一個網格位，它的尺寸會超過300x300。如果我列出所有對象的列表，我可以在一定範圍內搜索，但是如何處理連接器？

眼看作爲比特的2-d陣列是不可能的，我必須索引的所有建築物，並用X座標進行排序，然後通過y座標。我可以對連接器進行線性搜索，但這會非常乏味和痛苦。

有沒有人有建議？ P.S.我在C++中做這件事

2013-07-20 ithenoob

90kbits不是那麼大。目標平臺有哪些限制？你應該看看四叉樹。連接器可以表示爲一系列1xN矩形。 –

我想我一直在努力嘗試超優化內存開銷。現在你提到它，我可以使用一個數組。（因爲我喜歡思考極端情況）理論上來說，一個1000x1000的網格最能用數組表示還是檢測物體碰撞？順便說一句，quadtree會如何幫助？ – ithenoob

Quadtrees應該使查詢像'這個新形狀是否與任何現有形狀相交'。應該比窮舉線性搜索更好。 –

除了300x300不是很大，如果你真的想要你可以在一個字節內打包布爾值（但我不建議出於速度的原因），你可以檢查連接器是否相交具有一個簡單的功能：https://stackoverflow.com/a/565282/2436175

假設你已經檢查過你的新建築不與其他建築物相交，剩下要檢查的是你的新建築物（部分）的一側不與任何其他建築物你已經在位的連接器。

2013-07-20 20:34:05 Antonio

對不起，問題不明確。連接器平行於x和y軸，可以在網格上的任意點彎曲。 – ithenoob

@ithenoob然後你的交集函數變得非常簡單。您的連接器不是一個網段，而是由多個網段組成。當連接器與建築物的一側重疊時，您還必須決定如何處理。 – Antonio

我想用一個布爾數組會做的事情...... 除此之外，最簡單的方法，我覺得做沿所有連接器蠻力搜索是因爲他們理論上可以採取任何形狀的唯一途徑。 – ithenoob

回答