Zeno Rogue<p>Every tile in a hyperbolic tiling is randomly colored red or blue. How far should we move to find a specific pattern (a shape constructed out of tiles, with specific colors)?</p><p>The distance is usually proportional to \(n\), the number of tiles in the pattern -- this is because at a given location the pattern appears with probability \( 1/2^n \), and there are \(\Theta(c^d)\) possible locations in distance d.</p><p>So, for example, HyperRogue normally displays 582 tiles, and for every specific coloring of these 582 tiles, it should be somewhere in about 742 steps (and all of them in about 753 steps). If we used symbols (26 letters + space) instead of colors and were looking for a specific message of 1000 characters, it should appear in radius 6000.</p><p>Problem: however, it is not clear how to find such a pattern (and whether it would be still true for a given pseudorandom generator). What it the most elegant coloring algorithm with similar properties but where requested patterns can be found by following some procedure? (If you do not know how hyperbolic geometry works, might be easier to think about binary trees)</p><p><a href="https://mathstodon.xyz/tags/NonEuclideanGeometry" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NonEuclideanGeometry</span></a> <a href="https://mathstodon.xyz/tags/NonEuclidean" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NonEuclidean</span></a> <a href="https://mathstodon.xyz/tags/HyperbolicGeometry" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>HyperbolicGeometry</span></a> <a href="https://mathstodon.xyz/tags/HyperRogue" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>HyperRogue</span></a> <a href="https://mathstodon.xyz/tags/roguelike" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>roguelike</span></a> <a href="https://mathstodon.xyz/tags/procgen" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>procgen</span></a></p>