有哪些算法可以用来加速一些元胞自动机模拟？

Question

3

我正在编写一个基于ncurses的C.A.模拟器，用于模拟几乎任何使用Moore或Neumann邻域的C.A.。

使用当前的（硬编码和最明显的[运行状态函数]），模拟运行得很好；直到屏幕被填满了“on”（或其他活动）细胞。

所以我的问题是：是否有有效的算法来处理至少类似生命游戏规则？或者是世代，加权生命/世代...

谢谢。

- zaphnat

1

我最近写了一个在GPU上运行的CA，你可能想考虑一下。 - Martin

3个回答

1

我认为编写状态机不仅仅是算法设计问题，更多地是如何编写整洁且“无错误”的代码的问题。你可能正在寻找的是元胞自动机/状态图的实现。

你可以参考以下链接： http://www.state-machine.com/ // 不是巧合 http://www.boost.org/doc/libs/1_40_0/libs/statechart/doc/index.html 你还可以尝试使用无堆栈的Python http://stackless.com/ 来实现状态机或元胞自动机。这里有一个关于无堆栈实现工厂流程模拟的教程 http://members.verizon.net/olsongt/stackless/why_stackless.html#the-factory。

- Luka Rahne

我不想要通用状态机，也不是干净的代码，我真正想要的是优化细胞自动机模拟执行（更快）。 - zaphnat

那就写一个又长又丑的switch吧，或者最好还是用很多goto语句。我没有更好的想法。状态机不能使用通用算法进行优化。 - Luka Rahne

请仅返回翻译后的文本：告诉我关于Hashlife。我重申，我不想要通用状态机，而是针对某些常见的细胞自动机规则进行一些优化。 - zaphnat

1

你可以研究一下HashLife算法，并尝试将其概念应用到你正在处理的自动机上。

- Marc Müller

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Autoplectic · Accepted Answer

通常情况下，仅在上一个时间步骤中有活动的网格区域中运行更新操作是很好的。如果您为每个传递保留一个“我是否在此次更改？”的布尔格子阵列，则只需要更新与更改格子阵列中“打开”状态相邻半径内的单元格。