在某个特定区域随机生成位置的最有效方法？

Question

我正在开发 "greedy snake" 游戏。我正在使用一个二维数组来存储地图的每个 location/grid 的值：要么是蛋，要么是蛇体，要么是空的。鸡蛋需要在空白处生成。一种解决方案可能是：

while (new egg location overlaps snake body)
     Within the range of 2d array randomly generate an egg location

然而，当蛇变得很大并填满了地图的大部分区域时，生成新蛋的效率变得非常低，因为它必须检查二维数组的几乎每个元素。如何优化？

Answer 1

将蛇当前占据的所有空间作为输入，然后从剩余空间中检查。不会完全达到 O(1)，但会减少它需要通过的数组数量。

Answer 2

维护所有空方块的列表。每次你需要一个新的随机空方块时使用：

Collections.shuffle(list).get(0);

Answer 3

public Point generateRandomPoint(){
    Random rand = new Random();
    Point p;
    boolean goodPoint = false;
    //while the point selected is not empty
    while (goodPoint!=true){
        p= new Point(rand.nextInt(MAX_X),rand.nextInt(MAX_Y));
        //is the point empty
        goodPoint = array[p.x][p.y].equals("empty");
    }

    return p;
}

如果您使用它，那么它只会检查将生成蛋的 space。现在，因为它是随机的，它可能需要检查很多 spaces，但除非你的电路板有几千个，否则它应该几乎是即时的（<<50 毫秒）。

Answer 4

首先，我想说你的解决方案没有任何问题。你遇到的唯一问题是游戏后期（当大部分方格都被蛇占据时）你可能需要尝试很多次才能找到空的 space.

在这种情况下，OldCurmudgeon 的解决方案非常适合。然而，它有一个不同的问题。从一个大的空网格中维护一个空方块列表是浪费时间。

所以在游戏早期，您当前的解决方案更可取。但是游戏后期他们的解决方案更好。

所以我建议检查蛇的大小。如果蛇占不到网格的一半，请使用您当前的解决方案。只有当蛇占据了一半以上的网格时，才开始维护一个空方块列表。

在某个特定区域随机生成位置的最有效方法？

Most efficient method to randomly generate a location on some certain area?

java

optimization