{"id":266,"date":"2021-05-21T07:00:09","date_gmt":"2021-05-21T12:00:09","guid":{"rendered":"https:\/\/wollen.org\/blog\/?p=266"},"modified":"2021-09-05T04:53:30","modified_gmt":"2021-09-05T09:53:30","slug":"chaos-games","status":"publish","type":"post","link":"https:\/\/wollen.org\/blog\/2021\/05\/chaos-games\/","title":{"rendered":"The 2020 Summer Chaos Games (in 2021)"},"content":{"rendered":"<blockquote>\n<p style=\"text-align: left;\">Chaos was the law of nature; Order was the dream of man.<\/p>\n<p style=\"text-align: center;\">\u2014Henry Adams<\/p>\n<\/blockquote>\n<hr \/>\n<p>Recently I watched a <em>Youtube<\/em> video from <a href=\"https:\/\/www.youtube.com\/channel\/UCoxcjq-8xIDTYp3uz647V5A\" target=\"_blank\" rel=\"noopener\">Numberphile<\/a> that piqued my interest. If you aren&#8217;t familiar with the channel, they produce a lot of short math videos with <em>the rest of us<\/em> in mind. This one was about <a href=\"https:\/\/en.wikipedia.org\/wiki\/Chaos_game\" target=\"_blank\" rel=\"noopener\">chaos games<\/a>. I encourage everyone to watch it.<\/p>\n<p style=\"text-align: center;\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/kbKtFN71Lfs\" width=\"560\" height=\"360\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><span style=\"display: inline-block; width: 0px; overflow: hidden; line-height: 0;\" data-mce-type=\"bookmark\" class=\"mce_SELRES_start\">\ufeff<\/span><\/iframe><\/p>\n<p>You can see several more complex examples on the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Chaos_game\" target=\"_blank\" rel=\"noopener\">Wikipedia page<\/a>. I&#8217;ll recreate a few of them at the end of this post.<\/p>\n<p>If you can&#8217;t watch the video I&#8217;ll do my best to summarize chaos games, although I don&#8217;t claim to be a mathematician:<\/p>\n<p>Start by marking <em>n<\/em> corners of a polygon\u2014maybe 3, 4, or 5\u2014and pick a random point inside the shape. I&#8217;ll call this the &#8220;cursor.&#8221; Select one of the corners at random and move the cursor halfway toward it. Draw a point at the new cursor position. Then select another corner and draw another point. Continue this random process thousands of times until gradually a striking, seemingly non-random pattern emerges.<\/p>\n<p>The video demonstrates a triangle with purely random movement\u2014probably the easiest game to demonstrate. However at one point, as the presenter is drawing points by hand, he says, &#8220;It&#8217;s possible that something interesting would happen if I could do this quick enough&#8230; Maybe we want a computer to do this.&#8221; I couldn&#8217;t agree more.<\/p>\n<hr \/>\n<p>Let&#8217;s automate the process with <em>Python<\/em>. I&#8217;ll implement a <code>Cursor<\/code> class to keep track of the points.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">class Cursor:\r\n\r\n    def __init__(self, starting_x, starting_y):\r\n        self.x = starting_x\r\n        self.y = starting_y\r\n        self.movement_history = [(self.x, self.y)]\r\n\r\n    def move(self, new_coords):\r\n        new_x, new_y = new_coords\r\n        self.x += (new_x - self.x) \/ 2\r\n        self.y += (new_y - self.y) \/ 2\r\n        self.movement_history.append((self.x, self.y))<\/pre>\n<p>Vertices (corners) are placed as seen below. Note that the shape doesn&#8217;t have to be a regular polygon. In fact I stretched it here to make the code less complicated. But getting close will make the output easier to recognize.<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/triangle_vertices.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-278 size-full\" src=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/triangle_vertices.png\" alt=\"\" width=\"640\" height=\"480\" srcset=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/triangle_vertices.png 640w, https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/triangle_vertices-300x225.png 300w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/a><\/p>\n<p>The initial position is set at <em>Vertex #1. <\/em>But as I mentioned above, it doesn&#8217;t have to be placed here. Any random point inside the triangle will do.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">cursor = Cursor(starting_x=0, starting_y=0)<\/pre>\n<p>The engine driving this simulation is a loop that selects a random vertex and passes its coordinates to the <code>cursor.move<\/code> method.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">vertex_dict = {1: (0, 0),\r\n               2: (10, 0),\r\n               3: (5, 8)}\r\n\r\nfor _ in range(10000):\r\n    r = randint(1, 3)\r\n    cursor.move(vertex_dict[r])<\/pre>\n<p>The choice of ten thousand iterations is entirely arbitrary. Play with this number and see how your output changes. Or better yet, take several snapshots and watch the pattern emerge.<\/p>\n<p>After recording thousands of coordinates, let&#8217;s plot the information stored in <code>cursor.movement_history<\/code>. All we need is a bare-bones <em>Matplotlib<\/em> plot.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">x, y = zip(*cursor.movement_history)\r\n\r\nfig, ax = plt.subplots()\r\n\r\nax.scatter(x, y, s=1)\r\n\r\nax.set_xticks(range(11))\r\nax.set_yticks(range(9))\r\nax.set_xlim(-1, 11)\r\nax.set_ylim(-0.8, 8.8)\r\n\r\nfig.tight_layout()\r\n\r\nplt.show()<\/pre>\n<p>And the result:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/3_sides-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-277 size-full\" src=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/3_sides-1.png\" alt=\"\" width=\"640\" height=\"480\" srcset=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/3_sides-1.png 640w, https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/3_sides-1-300x225.png 300w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/a><\/p>\n<p>Sure enough, it looks like something! You might recognize this pattern from a poster hanging on your high school math teacher&#8217;s wall. It&#8217;s known as the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Sierpi%C5%84ski_triangle\" target=\"_blank\" rel=\"noopener\">Sierpi\u0144ski triangle<\/a>.<\/p>\n<p>But the chaos games are far from over. You can add more vertices and additional rules to create more complex <a href=\"https:\/\/en.wikipedia.org\/wiki\/Fractal\" target=\"_blank\" rel=\"noopener\">fractals<\/a>.<\/p>\n<p>For example, lay out a four-sided polygon and include a rule that a vertex cannot be chosen twice in a row. You&#8217;ll end up with something like this:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-281 size-full\" src=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_1.png\" alt=\"\" width=\"640\" height=\"480\" srcset=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_1.png 640w, https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_1-300x225.png 300w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/a><\/p>\n<p>Or a rule that a chosen vertex can&#8217;t be diagonal from the previous one:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-283 size-full\" src=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_2.png\" alt=\"\" width=\"640\" height=\"480\" srcset=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_2.png 640w, https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/4_sides_2-300x225.png 300w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/a><\/p>\n<p>Step up to five-sided polygons and you can create even more complex patterns. Here&#8217;s a pentagon whose vertices can&#8217;t be selected twice in a row:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/5_sides-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-313 size-full\" src=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/5_sides-1.png\" alt=\"\" width=\"640\" height=\"480\" srcset=\"https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/5_sides-1.png 640w, https:\/\/wollen.org\/blog\/wp-content\/uploads\/2021\/05\/5_sides-1-300x225.png 300w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/a><\/p>\n<p>Although at this point my low-resolution <em>Matplotlib<\/em> plots don&#8217;t really do justice to the chaos games.<\/p>\n<p>I find it fascinating that these random\u2014<em>chaotic<\/em>\u2014algorithms can create such ordered designs.<\/p>\n<p>What would happen if you jumped some distance other than halfway? Experiment with your own rules and see what you can create.<\/p>\n<hr \/>\n<p><strong>Full code:<\/strong><\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">from random import randint\r\nimport matplotlib.pyplot as plt\r\n\r\n\r\nclass Cursor:\r\n\r\n    def __init__(self, starting_x, starting_y):\r\n        self.x = starting_x\r\n        self.y = starting_y\r\n        self.movement_history = [(self.x, self.y)]\r\n\r\n    def move(self, new_coords):\r\n        new_x, new_y = new_coords\r\n        self.x += (new_x - self.x) \/ 2\r\n        self.y += (new_y - self.y) \/ 2\r\n        self.movement_history.append((self.x, self.y))\r\n\r\n\r\ncursor = Cursor(0, 0)\r\n\r\nvertex_dict = {1: (0, 0),\r\n               2: (10, 0),\r\n               3: (5, 8)}\r\n\r\nfor _ in range(10000):\r\n    r = randint(1, 3)\r\n    cursor.move(vertex_dict[r])\r\n\r\nx, y = zip(*cursor.movement_history)\r\n\r\nfig, ax = plt.subplots()\r\n\r\nax.scatter(x, y, s=1)\r\n\r\nax.set_xticks(range(11))\r\nax.set_yticks(range(9))\r\nax.set_xlim(-1, 11)\r\nax.set_ylim(-0.8, 8.8)\r\n\r\nfig.tight_layout()\r\n\r\nplt.show()<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Chaos was the law of nature; Order was the dream of man. \u2014Henry Adams Recently I watched a Youtube video from Numberphile that piqued my interest. If you aren&#8217;t familiar with the channel, they produce a lot of short math<\/p>\n","protected":false},"author":1,"featured_media":733,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40,41],"tags":[43,45,48,44,47,24,46,49,25,42,50,51],"class_list":["post-266","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-math","category-probability","tag-chaos","tag-chaos-games","tag-fractals","tag-games","tag-math","tag-matplotlib","tag-plot","tag-polygon","tag-python","tag-random","tag-sierpinski","tag-triangle"],"_links":{"self":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts\/266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/comments?post=266"}],"version-history":[{"count":36,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts\/266\/revisions"}],"predecessor-version":[{"id":364,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts\/266\/revisions\/364"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/media\/733"}],"wp:attachment":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/media?parent=266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/categories?post=266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/tags?post=266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}