Skip to content

Instantly share code, notes, and snippets.

@frietz58
Created July 17, 2022 18:15
Show Gist options
  • Save frietz58/239c84e2c24513138ed7dd5ae17a15cb to your computer and use it in GitHub Desktop.
Save frietz58/239c84e2c24513138ed7dd5ae17a15cb to your computer and use it in GitHub Desktop.
Fun with Cellular Automata
Display the source blob
Display the rendered blob
Raw
{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"id": "a8caebe8",
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"import matplotlib.colors\n",
"import numpy as np\n",
"import os\n",
"import random\n",
"from PIL import Image\n",
"import glob"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "09143fd0",
"metadata": {},
"outputs": [],
"source": [
"class CellularAutomaton:\n",
" \"\"\"\n",
" Class for an abstract cellular automaton. \n",
" For now assumes grid is always 2D and always uses moore neighborhood\n",
" \"\"\"\n",
" def __init__(self, grid_size, cmap, name, n_types=5):\n",
" self.grid_size = grid_size\n",
" self.state = np.random.randint(n_types, size=grid_size)\n",
" self.name = name\n",
" self.cmap = cmap\n",
" self.counter = 0\n",
" self.neighborhood = [ # moore neighborhood\n",
" (-1, -1), (-1, 0), (-1, 1),\n",
" (0, -1), (0, 1),\n",
" (1, -1), (1, 0), (1, 1)\n",
" ]\n",
" \n",
" @staticmethod\n",
" def make_gif(path, gif_duration=100, upscale=0, interpolation=Image.NEAREST):\n",
" frames = []\n",
" curr_dir = os.getcwd()\n",
" os.chdir(path)\n",
" imgs = glob.glob(\"*.png\")\n",
" for i in imgs:\n",
" new_frame = Image.open(i)\n",
" if upscale:\n",
" new_frame = new_frame.resize((new_frame.width * upscale, new_frame.height * upscale), interpolation)\n",
" frames.append(new_frame)\n",
"\n",
" # Save into a GIF that loops forever\n",
" frames[0].save('animation.gif', format='GIF',\n",
" append_images=frames[1:],\n",
" save_all=True,\n",
" duration=gif_duration, loop=0)\n",
" os.chdir(curr_dir)\n",
" \n",
" def save_state_img(self):\n",
" \"\"\"\n",
" Saves the current grid state as image \n",
" \"\"\"\n",
" if not os.path.exists(self.name):\n",
" os.makedirs(self.name)\n",
" \n",
" plt.imshow(self.state, cmap=self.cmap)\n",
" plt.axis('off')\n",
" plt.tick_params(\n",
" axis='both', \n",
" left='off', \n",
" top='off', \n",
" right='off', \n",
" bottom='off', \n",
" labelleft='off', \n",
" labeltop='off', \n",
" labelright='off', \n",
" labelbottom='off')\n",
" plt.savefig(f\"{self.name}/%05d\" % (self.counter) + \".png\", dpi=100, bbox_inches='tight', pad_inches=0.0)\n",
" plt.close()\n",
" \n",
" def update_state(self):\n",
" \"\"\"\n",
" Must be implemented by inheriting, concrete CA.\n",
" \"\"\"\n",
" pass\n",
" \n",
" def animate(self, steps=100):\n",
" \"\"\"\n",
" Repeatedly calls the update method and saves the resulting state images.\n",
" \"\"\"\n",
" self.save_state_img() # save initial state\n",
" self.counter += 1\n",
" \n",
" for i in range(steps):\n",
" cont = self.update_state()\n",
" self.save_state_img()\n",
" print(self.counter, end='\\r')\n",
" self.counter += 1\n",
" \n",
" if not cont:\n",
" break"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4e03bd60",
"metadata": {},
"outputs": [],
"source": [
"class RPSLS(CellularAutomaton):\n",
" \"\"\"\n",
" Rock-Paper-Scissor-Lizard-Spook CA, dynamics based on:\n",
" https://softologyblog.wordpress.com/2018/03/23/rock-paper-scissors-cellular-automata/\n",
" Cells fight for local dominance based on neighborhood. If more than @param thresh cells in neighborhood are of \n",
" same type, cell changes to that type. Small @param noise value is added to outcome of cell update.\n",
" \"\"\"\n",
" def __init__(self, grid_size, cmap, name, thresh=4, noise=2):\n",
" super().__init__(\n",
" grid_size=grid_size,\n",
" cmap=cmap,\n",
" name=name\n",
" )\n",
" self.loss_map = {\n",
" 0: (1, 4), # rock, loses to paper and spok...\n",
" 1: (2, 3), # paper\n",
" 2: (0, 4), # scissors\n",
" 3: (0, 2), # lizard\n",
" 4: (3, 1) # spok\n",
" }\n",
" self.thresh = thresh\n",
" self.noise = noise\n",
" \n",
" def fight(self, cell_val, neighbor_val):\n",
" \"\"\"\n",
" @param cell_val fights against neighbor_cal and determines outcome based on loss map.\n",
" We return outcome and type of neighbor in order to determine the most frequent neighbor.\n",
" \"\"\"\n",
" if neighbor_val in self.loss_map[cell_val]:\n",
" return 1, neighbor_val\n",
" else:\n",
" return 0, neighbor_val\n",
" \n",
" @staticmethod\n",
" def most_frequent(List):\n",
" \"\"\"\n",
" Helper, returns most frequent item in list.\n",
" \"\"\"\n",
" return max(set(List), key = List.count)\n",
" \n",
" def update_state(self):\n",
" \"\"\"\n",
" Updates the current cell based on dynamics describe here: \n",
" https://softologyblog.wordpress.com/2018/03/23/rock-paper-scissors-cellular-automata/\n",
" \"\"\"\n",
" new_state = np.zeros(self.state.shape)\n",
" for row_idx in range(new_state.shape[0]):\n",
" for col_idx in range(new_state.shape[1]):\n",
" cc = self.state[row_idx, col_idx] # get current cell value\n",
" loss_count = 0\n",
" winner_list = []\n",
" \n",
" for idx in self.neighborhood:\n",
" if row_idx + idx[0] in range(self.state.shape[0]) \\\n",
" and col_idx + idx[1] in range(self.state.shape[1]):\n",
" loss, winner = self.fight(cc, self.state[row_idx+idx[0], col_idx+idx[1]])\n",
" loss_count += loss\n",
" if loss:\n",
" # if cell lost against neighbor, add neighbor to list of winners\n",
" winner_list.append(winner)\n",
" \n",
" noise_val = 0\n",
" if self.noise is not None:\n",
" noise_val = random.randint(0, self.noise)\n",
" \n",
" if loss_count + noise_val > self.thresh: # if lost more than some threshold, change to winner\n",
" new_state[row_idx, col_idx] = self.most_frequent(winner_list)\n",
"\n",
" else:\n",
" new_state[row_idx, col_idx] = cc # otherwise cell states the same\n",
" \n",
" cont = True\n",
" if (self.state == new_state).all():\n",
" cont = False\n",
" print(\"Reached equilibrium!\")\n",
" \n",
" self.state = new_state\n",
" \n",
" return cont"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e8d6d3e0",
"metadata": {},
"outputs": [],
"source": [
"cmap = matplotlib.colors.LinearSegmentedColormap.from_list(\"\", [\"#A8DADC\", \"#457B9D\", \"#1D3557\",\"#E63946\", \"#F1FAEE\"])\n",
"ca = RPSLS((128, 128), cmap, \"rpsls\")\n",
"ca.animate(1000)\n",
"ca.make_gif(r\"rpsls\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0309d7ce",
"metadata": {},
"outputs": [],
"source": [
"# banner, this is takes a while..\n",
"# cmap = matplotlib.colors.LinearSegmentedColormap.from_list(\"\", [\"#A8DADC\", \"#457B9D\", \"#1D3557\",\"#E63946\", \"#F1FAEE\"])\n",
"# ca = RPSLS((150, 600), cmap, \"rpsls\")\n",
"# ca.animate(1000)\n",
"# ca.make_gif(r\"rpsls\", upscale=2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e16db10e",
"metadata": {},
"outputs": [],
"source": [
"class ForestFire(CellularAutomaton):\n",
" \"\"\"\n",
" Forest Fire Ca that updates state based on dynamics described here: \n",
" https://scipython.com/blog/the-forest-fire-model/\n",
" \"\"\"\n",
" def __init__(self, grid_size, cmap, name, fire_chance=0.0001, growth_chance=0.1):\n",
" super().__init__(\n",
" grid_size=grid_size,\n",
" cmap=cmap,\n",
" name=name,\n",
" n_types=2\n",
" )\n",
" self.fire_prob = fire_chance\n",
" self.growth_prob = growth_chance\n",
" \n",
" def update_state(self):\n",
" new_state = np.zeros(self.state.shape)\n",
" for row_idx in range(new_state.shape[0]):\n",
" for col_idx in range(new_state.shape[1]):\n",
" cc = self.state[row_idx, col_idx]\n",
" new_val = cc\n",
" if cc == 0:\n",
" # if cell is empty, apply growth chance\n",
" if np.random.uniform() < self.growth_prob:\n",
" new_val = 1\n",
" elif cc == 2:\n",
" # if cell is burning, cell becomes empty\n",
" new_val = 0\n",
" else:\n",
" # if cell is tree check whether it catches fire from neighbor\n",
" for idx in self.neighborhood:\n",
" if row_idx + idx[0] in range(self.state.shape[0]) \\\n",
" and col_idx + idx[1] in range(self.state.shape[1]):\n",
" if self.state[row_idx+idx[0], col_idx+idx[1]] == 2:\n",
" new_val = 2\n",
" break\n",
" \n",
" # if tree did no catch fire apply random fire chance (lightning strike)\n",
" if np.random.uniform() < self.fire_prob:\n",
" print(\"Lightning\", self.counter)\n",
" new_val = 2\n",
" \n",
" new_state[row_idx, col_idx] = new_val\n",
" \n",
" if self.counter == 20:\n",
" if not np.any(new_state==2):\n",
" new_state[10, 10] = 2\n",
" \n",
" cont = True\n",
" if (self.state == new_state).all():\n",
" print(\"Reached equilibrium!\")\n",
" \n",
" self.state = new_state\n",
" \n",
" return cont\n",
" \n",
" def save_state_img(self):\n",
" \"\"\"\n",
" Saves the current grid state as image, for the forest fire CA we do an additional step to assign colors\n",
" to certain values manually, because mpl's colormap produces undesired results given that the range of values of the\n",
" CA's state can vary...\n",
" \"\"\"\n",
" if not os.path.exists(self.name):\n",
" os.makedirs(self.name)\n",
" \n",
" fire = matplotlib.colors.to_rgb(\"#fcd514\")\n",
" ground = matplotlib.colors.to_rgb(\"#bc6c25\")\n",
" forest = matplotlib.colors.to_rgb(\"#1fd224\")\n",
" \n",
" data_3d = np.ndarray(shape=(self.state.shape[0], self.state.shape[1], 3))\n",
" for i in range(0, self.state.shape[0]):\n",
" for j in range(0, self.state.shape[1]):\n",
" if self.state[i][j] == 0:\n",
" data_3d[i][j] = ground\n",
" elif self.state[i][j] == 1:\n",
" data_3d[i][j] = forest\n",
" elif self.state[i][j] == 2:\n",
" data_3d[i][j] = fire\n",
" \n",
" plt.imshow(data_3d)\n",
" plt.axis('off')\n",
" plt.tick_params(\n",
" axis='both', \n",
" left='off', \n",
" top='off', \n",
" right='off', \n",
" bottom='off', \n",
" labelleft='off', \n",
" labeltop='off', \n",
" labelright='off', \n",
" labelbottom='off')\n",
" plt.savefig(f\"{self.name}/%05d\" % (self.counter) + \".png\", dpi=100, bbox_inches='tight', pad_inches=0.0)\n",
" plt.close()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0dd80d00",
"metadata": {
"scrolled": false
},
"outputs": [],
"source": [
"np.random.seed(101)\n",
"cmap = matplotlib.colors.LinearSegmentedColormap.from_list(\"\", [\"#78290f\", \"#688e26\", \"#bf0603\"])\n",
"ca = ForestFire((128, 128), cmap, \"forest\", fire_chance=0.0000025, growth_chance=0.01)\n",
"ca.animate(1000)\n",
"ca.make_gif(r\"forest\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e805e7a9",
"metadata": {},
"outputs": [],
"source": [
"class GameOfLife(CellularAutomaton):\n",
" \"\"\"\n",
" Conway's Game of Life CA, as described here:\n",
" https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life\n",
" \"\"\"\n",
" def __init__(self, grid_size, cmap, name, thresh=4, noise=2):\n",
" super().__init__(\n",
" grid_size=grid_size,\n",
" cmap=cmap,\n",
" name=name\n",
" )\n",
" \n",
" glider_idx = [\n",
" (-1, 0),\n",
" (0, 1),\n",
" (1, -1), (1, 0), (1, 1)\n",
" ]\n",
" \n",
" blinker_idx = [\n",
" (-1, 0),\n",
" (0, 0),\n",
" (1, 0)\n",
" ]\n",
" \n",
" gosper_idx = [\n",
" (5, 1), (5, 2), (6, 1), (6, 2), (5, 11), (6, 11), (7, 11), (4, 12), (3, 13), (3, 14), (8, 12), (9, 13),\n",
" (9, 14), (6, 15), (4, 16), (5, 17), (6, 17), (7, 17), (6, 18), (8, 16), (3, 21), (4, 21), (5, 21), (3, 22), \n",
" (4, 22), (5, 22), (2, 23), (6, 23), (1, 25), (2, 25), (6, 25), (7, 25), (3, 35), (4, 35), (3, 36), (4, 36),\n",
" ]\n",
" \n",
" beacon_idx = [\n",
" (1, 1), (2, 1), (1, 2), (4, 3), (3, 4), (4, 4),\n",
" ]\n",
" \n",
" # starting state is empty\n",
" self.state = np.zeros(grid_size)\n",
" \n",
" # we put a few gliders\n",
" for idx in ((10, 10), (20, 10), (30, 10)):\n",
" for gl_idx in glider_idx:\n",
" self.state[idx[0] + gl_idx[0], idx[1] + gl_idx[1]] = 1\n",
" \n",
" # a few blinkers\n",
" for idx in ((5, 5), (5, 123), (123, 5), (123, 123)):\n",
" for bl_idx in blinker_idx:\n",
" self.state[idx[0] + bl_idx[0], idx[1] + bl_idx[1]] = 1\n",
" \n",
" # a few beacons\n",
" for idx in ((15, 110), (15, 110), (110, 15), (110, 110)):\n",
" for bl_idx in beacon_idx:\n",
" self.state[idx[0] + bl_idx[0], idx[1] + bl_idx[1]] = 1\n",
" \n",
" # and a gosper canon\n",
" for g_idx in gosper_idx:\n",
" self.state[32 + g_idx[0], 30 + g_idx[1]] = 1\n",
"\n",
" def update_state(self):\n",
" new_state = np.zeros(self.state.shape)\n",
" for row_idx in range(new_state.shape[0]):\n",
" for col_idx in range(new_state.shape[1]):\n",
" cc = self.state[row_idx, col_idx] # get current cell value\n",
" new_val = cc\n",
" \n",
" alive_counter = 0\n",
" for idx in self.neighborhood:\n",
" if row_idx + idx[0] in range(self.state.shape[0]) \\\n",
" and col_idx + idx[1] in range(self.state.shape[1]):\n",
" if self.state[row_idx + idx[0], col_idx + idx[1]] == 1:\n",
" alive_counter += 1\n",
" \n",
" if cc == 1:\n",
" if alive_counter < 2:\n",
" new_val = 0 # cell dies, underpopulation\n",
" elif alive_counter == 2 or alive_counter == 3:\n",
" new_val = 1 # cell remains alive\n",
" elif alive_counter > 3:\n",
" new_val = 0 # cell dies, overpopulation\n",
" elif cc == 0:\n",
" if alive_counter == 3:\n",
" new_val = 1 # cell birth\n",
" \n",
" new_state[row_idx, col_idx] = new_val\n",
" \n",
" cont = True\n",
" if (self.state == new_state).all():\n",
" cont = False\n",
" print(\"Reached equilibrium!\")\n",
" \n",
" self.state = new_state\n",
" \n",
" return cont"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c943bb5d",
"metadata": {},
"outputs": [],
"source": [
"cmap = plt.get_cmap(\"binary_r\")\n",
"ca = GameOfLife((128, 128), cmap, \"GameOfLife\")\n",
"ca.animate(1000)\n",
"ca.make_gif(r\"GameOfLife\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ffc7183c",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.12"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment