在2D板上隨機生成實體以避免碰撞

Question

我正在嘗試製作一個蛇克隆，並且我希望蛇的寬度爲5左右像素，並以1像素爲增量移動。這意味着蛇可以比自己的一條蛇的寬度更近。當隨機產生食物時，這會變得複雜，這將是一個5x5像素的正方形。我需要/想要一種算法將隨機生成減少爲不包含蛇的5x5方塊。

問題的一部分是，由於食物是5x5，因此必須檢查食物中每個像素的碰撞檢測，看看蛇是否部分在食物中。這使我有兩個問題

問題

如何減少時隨機產生的食物的搜索空間？

我想過做一個四叉樹，細分空間，直到分區比我想放置的食物更小。我也考慮過使用awt的Rectangle，並確定食物的生成位置是否包含在組成玩家的矩形列表中。

我能想到的最佳解決方案是生成一個包含所有可能的矩形的二維數組，其左上角爲索引值。然後生成另一個二維數組，將每個像素映射到包含它的每個矩形，甚至只是起點，不需要整個矩形（每個矩形25個）。然後在每次移動之後，更新頭部和尾部的角點地圖，標記每個被佔用的映射矩形。然後使用映射的角陣進行更簡單的隨機搜索（將其減少到1x1像素的搜索空間）。

我試圖避免的主要問題是，當蛇填充可播放空間的90％時，任何基本的搜索失敗重複系統將花費大量的時間來完成，最壞的情況下，永遠不會生成食物廣場。

Answer 1

7個月後，我有一個解決方案。我還沒有測試過，因爲我仍然需要執行它。

我處理蛇體的方式是由左上角X，Y座標，寬度和高度定義的矩形列表。

我可以做的是創建一個8度樹開始整個板，然後將每個蛇部分放入樹中，左上角偏移蘋果的大小。當放置零件時，我可以根據4個角，4條邊和蛇的中心將板分成9個部分。忽略包含蛇的電路板部件以及尺寸爲< = 0的電路板部件，我可以將它們放入樹中。

由於蛇的部分已經調整爲蘋果的大小，非自用葉節點內的任何點都可以用來放置一個蘋果