# Chaos game to get specific fractal

In the Wikipedia page for Chaos Game, you can see this fractal, which is the result of the rule:

A point inside a square repeatedly jumps half of the distance towards a randomly chosen vertex, but the currently chosen vertex cannot be 1 or 3 places, respectively away from the two previously chosen vertices.

However, that is unlikely since the rule implies that all the point will do is to get closer to vertex 1 or 3 (or 2 or 4), so that the image after some iterations would be a line joining both vertices.

Can you give a rule that produces the desired fractal?

• I think you may have misinterpreted that (very confusing) sentence; it's not that the next vertex must not be $1$ or $3$ places away from the current vertex, but that it cannot be $1$ place away from the current vertex, or $3$ places away from the previous vertex. This rule doesn't force it to get stuck on a diagonal. Dec 29, 2017 at 16:51
• @MiloBrandt Yes, but 1 place away and 3 places away are exactly the same thing, since vertex are in $\mathbb{Z}_4$. Dec 30, 2017 at 16:12
• @SergioEnriqueYarzaAcuña Not if you consider orientation. For example, 3 is one place away from 2, but three places away from 4. Thus if the last two vertices were $(1,4)$, then the next vertex cannot be 4 (as this would be 3 places away from 1), and it cannot be 1 (as this would be one place away from 4). Either of the other two remaining vertices are allowed. Dec 30, 2017 at 16:28
• @XanderHenderson If you check the rest of rules in the Wikipedia page, you'll see that whenever orientation is relevant, it is specified. However, if you consider orientation, you get the bottom-right figure in the first four for Fabio's partial answer. Dec 30, 2017 at 17:58
• @SergioEnriqueYarzaAcuña If you look at the talk portion of the Wikipedia page, it is clear that noone really understands what that image is. The description of the image is inchoate, whether or not orientation matters. Dec 30, 2017 at 20:03

Partial answer. I wrote the following MATLAB function to produce those pretty pictures:

function chaosGame(forbidden, mode, side, points)
% CHAOSGAME play a chaos game
%
% https://en.wikipedia.org/wiki/Chaos_game
%
% A point inside a square repeatedly jumps half the distance
% towards a randomly chosen vertex, but the currently chosen
% vertex must obey the constraint specified by forbidden and
% mode.
%
% - forbidden is a row vector with values from {0,1,2,3,NaN}.
% - mode is either 'all' or 'any'
%
% If forbidden(k) is m, then the current vertex should not be
% m places away (counterclockwise) from the one chosen k
% turns before.  If forbidden(k) is NaN, the vertex chosen
% k turns before imposes no constraint.
%
% If mode is 'all' all constraints specified by forbidden must
% be satisfied.  If mode is 'any' at least one constraint must
% be satisfied.  Using NaN with 'any' gives an unconstrained
% choice.

if nargin < 1 || isempty(forbidden)
forbidden = [1 3];
end
if nargin < 2 || isempty(mode)
mode = 'all';
end
if nargin < 3 || isempty(side)
side = 1000;
end
if nargin < 4 || isempty(points)
points = fix(side.^2);
end

switch mode
case {'all'}
compareall = true;
case {'any'}
compareall = false;
otherwise
error('mode should be either all or any')
end

canvas = ones(side);
% List vertices from top left counterclockwise.
vertices = [1 1; 1 side; side side; side 1];
% Past vertex indices (which are in {0,1,2,3}) are initially
% invalid (-1) so that the first vertex choice is free.
past = -ones(size(forbidden));
% Pick random starting point inside the canvas.
p = side * rand(1,2);
canvas(fix(p(1)), fix(p(2))) = 0;

for n = 1:points
while 1
pick = randi([0 3]);
d = mod(pick + forbidden, 4);
if compareall
validchoice = all(d ~= past);
else
validchoice = any(d ~= past);
end
if validchoice
past = [pick past(1:end-1)];
break
end
end
vert = vertices(pick+1,:);
p = (vert + p) / 2;
canvas(fix(p(1)), fix(p(2))) = 0;
end
imshow(canvas,'InitialMagnification','fit')
end


This is what I got for forbidden set to $0$, $1$, $2$, and $[1,3]$ (from top to bottom, and from left to right):

I'm not sure the $[1,3]$ picture is what you describe, but it's definitely not the one on the Wikipedia page. The 'any' mode also produces some nice graphs:

As one would expect, there are more black points, but we are still far from the desired result.

(Note: the function also works with Octave (except for an inessential warning) but is much slower.)

• Hi, I'm upvoting but not selecting because you're not giving the complete answer. Dec 30, 2017 at 16:16
• @SergioEnriqueYarzaAcuña Agreed: not selecting is the right thing to do. BTW, the "talk" section of the Wikipedia page records another case of someone who could not reproduce the $[1,3]$ fractal. At this point, my script also deals with general regular polygons, and the same problem occurs with the pentagonal graphs: it reproduces the one with the simple $[0]$ constraint, but not the one with the $[1,4]$ constraint. Dec 30, 2017 at 19:23

Dividing the image into 8×8 squares like a chessboard, we see that the two middle squares on each side are empty. That means each of the following triples of consecutive vertex moves must be disallowed:

↖↖↙, ↖↖↗, ↗↗↖, ↗↗↘, ↘↘↗, ↘↘↙, ↙↙↘, ↙↙↖.

In other words: “if the two previously chosen vertices were the same, then the currently chosen vertex cannot be 1 or 3 places away”.

Indeed, that rule reproduces the given picture perfectly.