加速元胞自动机
是否有可能通过某种算法或类似的东西来加速细胞自动机的速度？我正在使用 在 XNA 中实现康威的生命游戏，它工作得很好，但问题是，当我使用大于128x128 单元格它变得非常慢。
我不认为这与代码或 XNA 如何处理纹理和绘图有关，但事实是更新如此多的单元格（即评估每个单元格的邻居并基于此获取其新状态）它是一个 大量计算。
当然，理想的元胞自动机应该无限大，但实际上这是不可能做到的。但在我看来，128x128 太小了，无法实际看到系统的行为。
任何帮助将不胜感激！
Is it possible, with some sort of algorithm or something like that, to speed up a cellular automata? I'm using a Conway's Game of Life implementation made in XNA and it works perfectly, but the problem is that when I use a grid larger than 128x128 cells it becomes awfully slow.
I don't think is has to do with the code or how XNA handles textures and drawing, but the fact that updating so many cells (i.e. evaluating each of the cell's neighbors and based on that obtaining its new state) it's a lot of computation.
Of course, an ideal cellular automata should be infinitely large, but in reality that's impossible to do. But 128x128 is just too small to actually see how the system behaves, in my opinion.
Any help would be greatly appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Hashlife算法使用四叉树、哈希和记忆来压缩CA的时间和空间，从而大幅提高性能。查看 Golly 示例实现。
我仍在尝试自己解决这个问题，并寻找好的图书馆。
这里有很好的解释（带有示例代码）： http ://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478。
The Hashlife algorithm uses quad-trees, hashing, and memorization to compress the time and space of the CA for a massive increase in performance. Check out Golly for an example implementation.
I'm still trying to figure it out myself, and look for good libraries.
There's good explanation here (with example code): http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478.
如果您尝试一下多试几次，你就会知道时间都花在哪里了。
人们不应该猜测，但我的猜测基本上是所有时间都花在了渲染上。
邻居的评估可能看起来像很多代码，但很可能非常简单。
如果您有办法避免重新渲染未更改的单元格，那么可能会节省很多。
If you try this a few times, you'll see where the time goes.
One shouldn't guess, but my guess is essentially all the time goes into rendering.
The evaluation of neighbors may look like a lot of code, but chances are it's extremely simple.
If you have a way to avoid re-rendering cells that haven't changed, that might save a lot.
我建议使用 OpenGL 和 GLSL。通过这种方式，您可以消除从 CPU 到 GPU 的数据传输，并获得 10 倍或更多的加速。
I would recomend to use OpenGL and GLSL. This way you can eliminate the data transfer from cpu to gpu and gain a nice speedup of 10x or more.