书名:代码本色:用编程模拟自然系统
作者:Daniel Shiffman
译者:周晗彬
ISBN:978-7-115-36947-5
第6章目录
6.14 算法效率(为什么程序跑得这么慢)
- 群集行为看起来很不可思议,但它的运行速度会非常慢,群集中的元素越多,程序运行得越慢。
1、优化方法
- 如果我们把屏幕划分成一个个网格,把这2000个Boid对象分配到这些网格中。对于每个Boid对象,只需检查同一单元格内的其他元素。这种技术称为“网格空间分割”
2、如何用Processing实现这种算法?
- 可以用多个ArrayList实现,其中一个ArrayList用于保存所有的Boid对象,就像群集示例中做的。
ArrayList<Boid> boids; - 除了这个ArrayList,我们还在另一个二维ArrayList中存放了每个Boid对象引用。对网格中的每个单元格,都有一个对应的ArrayList用于保存此单元格内的元素。
ArrayList<Boid>[][] grid; - 在draw()函数中,每个Boid元素都需要根据位置将自己放入合适的单元格内。
int column = int(boid.x) resolution;
int row = int(boid.y) resolution;
grid[column][row].add(boid);
- 当Boid对象检查邻居元素时,只需检查某个单元格内的元素(实际上,为了处理好边界情况,我们还应该检查邻近的单元格)。
3、示例
示例代码6-10 网格空间分割(略)