设计二维世界的最佳解决方案--生命游戏

Question

我需要创建一个应用程序来模拟食肉动物与猎物的关系。我可以使用一些框架(例如。，但我想知道从头开始编写应用程序的问题。

对我来说，最大的问题是如何用食物、食肉动物和猎物来表示地图。

非常简单的模型

我在考虑二维数组，比如说Cell。单元格将具有布尔字段predator、food和prey以及相应的设置器和getter。食肉动物和被捕食者会在特定半径(视线范围)内四处游荡和观察细胞。如果捕食者发现猎物，它就会向它移动。如果被捕食者发现捕食者，它就会向相反的方向移动。不受干扰的猎物在找到食物来源之前一直在游荡。

Moving/Wandering

在本例中，动物被转到目的地。

   _ _ _ _ _ _      _ _ _ _ _ _                _ _ _ _ _ _
0 |_|_|_|_|_|_|    |_|_|_|_|_|_|              |_|_|_|_|_|_|
1 |_|A|_|_|_|_|    |_|_|_|_|_|_|              |_|_|_|_|_|_|
2 |_|_|x|x|_|_| -> |_|_|A|x|_|_|    . . .     |_|_|_|_|_|_|
3 |_|_|_|_|x|_|    |_|_|_|_|x|_|              |_|_|_|_|_|_|
4 |_|_|_|_|_|D|    |_|_|_|_|_|D|              |_|_|_|_|_|D|
   0 1 2 3 4 5

这一步消耗了5个移动，动物将有一定的速度(2移动/秒)。在每次移动中，一个单元格将predator设置为false，另一个单元格将其设置为true。通过编程，它将如下所示(当然会有方法moveTo(x,y))：

Animal animal = new Animal(1,1);
animal.setPosition(2,2);
animal.setPosition(3,2);
animal.setPosition(4,3);
animal.setPosition(5,4);

观测

样本捕食者观察的最大范围为3。我已经用x标记了观察细胞。观察只是简单的检查是否getPrey()返回true。

   _ _ _ _ _ _ _      _ _ _ _ _ _ _      _ _ _ _ _ _ _          
0 |_|_|_|_|_|_|_|    |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|      
1 |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|    |_|x|x|x|x|x|_|        
2 |_|_|_|x|_|_|_|    |_|_|x|x|x|_|_|    |_|x|x|x|x|x|_| 
3 |_|_|x|A|x|_|_| -> |_|x|x|A|x|x|_| -> |x|x|x|A|x|x|x|       
4 |_|_|_|x|_|_|_|    |_|_|x|x|x|_|_|    |_|x|x|x|x|x|_|
5 |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|    |_|x|x|x|x|x|_|
6 |_|_|_|_|_|_|_|    |_|_|_|_|_|_|_|    |_|_|_|x|_|_|_|
   0 1 2 3 4 5 6

最好的方法是观察周围区域的每一步(移动)，但这似乎是大量的计算(检查条件)。我现在说的对不对？

这是一种将大部分数据保存在二维数组中的好方法吗？如果有建设性的回答，我将不胜感激。

这只是一个示例。在未来，我想添加复制，情绪，智慧等。

谢谢。

编辑

我忘了提这个问题的规模。

我认为捕食者和猎物的数量将少于100只。但这只是猜测。地图的大小将是500×500，甚至更小。

Answer 1

要求最好的解决方案总是意味着不舒服的压力。为了正确回答这样的问题并真正给出最好的解决方案，我们需要在问题说明中给出一定程度的细节，这是很难理解的。呃..。在问答网站上传达信息。

但不仅仅是因为回答这个问题的困难，我建议首先将它建模为一个接口。假设您已经有了一个Cell接口，您可以将这个世界表示为

interface World {
    Cell get(int x, int y);
    int getSizeX();
    int getSizeY();
}

根据内存消耗和效率之间的权衡，您可以提供各种实现。对于“密集”(且非常高效)实现，可以使用数组：

class ArrayWorld implements World {
    private Cell cells[][] = ...

    @Override
    public Cell get(int x, int y) {
        return cells[x][y];
    }
    ...
}

对于“稀疏”实现(尽管效率稍低)，可以使用类似于

class MapWorld implements World {

    // Assuming a class "IntPair" which encapsulates
    // two int values, with proper implementation 
    // of hashCode and equals:
    private Map<IntPair, Cell> map = new HashMap<IntPair, Cell>();

    @Override
    public Cell get(int x, int y) {
        return map.get(new IntPair(x,y));
    }
    ...
}

这里最巧妙的一点是，您可以很容易地实现在此类元胞自动机中经常使用的世界属性:即具有“圆环”拓扑的世界，其中坐标在边界处“环绕”：

class TorusWorld implements World {
    private World delegate = ...

    @Override
    public Cell get(int x, int y) {
        int wrappedX = ((x % getSizeX()) + getSizeX()) % getSizeX();
        int wrappedY = ((y % getSizeY()) + getSizeY()) % getSizeY();
        return delegate.get(wrappedX, wrappedY);
    }
}

然后，这个"Torus世界“可以得到World接口的任何其他实现的支持。

但是:您还提到了一个Animal类，所以还不完全清楚您的Cell类应该是什么样子：Cell真的包含Animal吗？还是只有一组旗子显示细胞中是否含有食物、猎物或其他东西？细胞是否可能包含两种(例如食饵和食物，它们很可能不会相互作用)？在规范阶段，这些都是应该尽早回答的问题。

Answer 2

这实际上取决于矩阵的大小和它的稀疏性。但是单元模型应该是很好的，特别是当你可以随机访问坐标(x，y)并且不想有一个巨大的矩阵的时候。为了获得高效的代码，您可以查看“严肃的”生命游戏实现：

• What's an efficient implementation of Conway's Game of Life for low memory uses?
• Optimizing Conway's 'Game of Life'

问题主要是内存消耗与速度(嗯.如往常一样)。

你要找的是细胞自动机。从头开始做这些很有趣，也很有趣。

Answer 3

您的2d数组方法总是最简单的实现方法。预先考虑一下最大数组大小是多少。

如果你需要使用一个巨大的世界，混合着密集和稀疏的生活，那么有更好的选择，但它们都要复杂得多。

对于动态2d结构，可以查看四叉树，甚至可以将四叉树与2d数组方法混在一起。