0

我正在对捕食者、猎物和食物(根据条件在地形上生长的植物和生物死亡时释放的肉)进行进化模拟。他们每个人都占据一个(x,y)位置。

目前,每个生物都有几只对红色、绿色和蓝色通道敏感的“眼睛”,当一个生物或一块食物在它们的视线范围内时,眼睛会做出反应,向它们的神经网络发送一个输入,取决于他们看到的物体的颜色、相对角度以及与生物的距离。

我现在正在做的是遍历所有植物、肉块和生物,并检查它们是否在生物的观察距离内。如果该条件为真,则计算网络的输入。

问题是与生物的观看距离(通常在 150 到 300 个“单位”之间)相比,世界是巨大的(大约 10,000*10,000 个“单位”)。最重要的是,植物数量可能会根据地形条件而变得非常高(最多几千个),以及所有其他生物和肉块。

因此,我通常最终会为每个生物执行一个大规模循环,这确实会减慢模拟速度,而检查的大多数生物和食物块完全不相关(距离太远)。

我要求的是某种方法或算法,可以减少在每个循环中检查距离的点数,限制被检查点的距离,或其他一些技术。

PS:我考虑过将模拟划分为不同的“区域”,所以如果一个生物在一个区域中,它只会检查该特定区域中的其他点(食物和其他生物)。但是,由于它们不断移动,如果它们位于区域的边缘,则会使它们的视野非常不准确。我还通过检查距离^2(不做sqrt)稍微提高了速度,并且只有当它小于viewing_distance^2时才计算它。

4

2 回答 2

1

将世界划分为多个区域。如果区域宽度略大于最大观看距离,您最多只需要检查 4 个区域。

使用四叉树或 kd-tree 的缺点是需要不断更新结构。但它可能会更好,做一些分析。

于 2013-08-04T21:26:26.477 回答
0

四叉树结构可用于几何表示: http ://en.wikipedia.org/wiki/Quadtree

这完全取决于您需要多少效率。区域答案还有一个问题,如果你的生物靠近区域的边界,你最终可能会扫描 4 个区域。

于 2013-08-05T08:50:47.620 回答