3
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Milo Brandt
    Dec 29, 2017 at 16:51
  • $\begingroup$ @MiloBrandt Yes, but 1 place away and 3 places away are exactly the same thing, since vertex are in $\mathbb{Z}_4$. $\endgroup$
    – Sergio Enrique Yarza Acuña
    Dec 30, 2017 at 16:12
  • $\begingroup$ @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. $\endgroup$
    – Xander Henderson ♦
    Dec 30, 2017 at 16:28
  • $\begingroup$ @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. $\endgroup$
    – Sergio Enrique Yarza Acuña
    Dec 30, 2017 at 17:58
  • $\begingroup$ @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. $\endgroup$
    – Xander Henderson ♦
    Dec 30, 2017 at 20:03

2 Answers 2

Reset to default
3
$\begingroup$

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

  % Start with a white canvas.
  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):

enter image description here

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:

enter image description here

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.)

$\endgroup$
2
  • $\begingroup$ Hi, I'm upvoting but not selecting because you're not giving the complete answer. $\endgroup$
    – Sergio Enrique Yarza Acuña
    Dec 30, 2017 at 16:16
  • $\begingroup$ @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. $\endgroup$
    – Fabio Somenzi
    Dec 30, 2017 at 19:23
0
$\begingroup$

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.

result

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .