17
\$\begingroup\$

The Biham-Middleton-Levine traffic model is a self-organizing cellular automaton that models simplified traffic.

It consists of a number of cars represented by points on a lattice with a random starting position, where each car may be one of two types: those that only move downwards (shown as blue in this article), and those that only move towards the right (shown as red in this article). The two types of cars take turns to move. During each turn, all the cars for the corresponding type advance by one step if they are not blocked by another car.

Your task is to visualize this model as an animation. Here are some good demonstrations.

enter image description here

Input

A floating point number between 0 and 1 representing density, and two integers representing the displayed grid height and width. Assume inputs are valid, and parameters to a function or reading from user input are both fine.

Example: 0.38 144 89 (corresponds to image above)

Output

A grid, at least 80x80, that displays the animation of this model running. At the start, cars are randomly placed on the grid until the grid reaches the input density, with half red and half blue (that is density times total number of grid squares, rounded however you like). The density must be this value, which means you cannot fill each cell with density as a probability. For each step, one type of car either moves downwards or right, wrapping around if they go past the edge. The type of car that moves alternates each step. To make the animation viewable, there must be at least 10 ms between each step.

Rules

  • The cars can be any color or symbol as long as they are distinguishable from each other and the background, and each car type is the same color or symbol.

  • Console and graphical output are both allowed. For console output, any printable symbol is fine, but output must be as a grid of characters.

  • Please specify what kind of output you've produced if you don't have a screenshot or gif.

  • The simulation must run forever.

The output is a bit complex, so if you have any questions, please comment.

\$\endgroup\$
  • \$\begingroup\$ Any restrictions on how slowly or quickly the animation must run? \$\endgroup\$ – xnor Dec 27 '16 at 5:23
  • \$\begingroup\$ Perhaps it's worth specifying that the type of car that moves alternates each step. \$\endgroup\$ – Greg Martin Dec 27 '16 at 5:37
  • \$\begingroup\$ @xnor I was thinking at least 5 or 10 ms per loop, but I'm not really sure if that would be difficult to measure. \$\endgroup\$ – qwr Dec 27 '16 at 5:39
  • 3
    \$\begingroup\$ Does the density mean that the density has to be that value, or just that each pixel has a probability d to be filled? Also, do we have to assign the color of the cars randomly or not? If randomly, again is it ok if they just have a 50-50 chance of being either colour? \$\endgroup\$ – JAD Dec 27 '16 at 12:29
  • 1
    \$\begingroup\$ @JarkoDubbeldam The density has to be that value. They have a 50-50 chance of being each color. However I answered late so answers may be different. Cars can move up or left. \$\endgroup\$ – qwr Dec 27 '16 at 22:35
5
\$\begingroup\$

R, 350 338 293 291 273 268 264 bytes

function(d,x,y){f=function(w){v=length(w);for(j in which(w>0&!w[c(2:v,1)]))w[c(j,j%%v+1)]=0:1;w};m=matrix(sample(c(rep(1,q<-floor(d*y*x/2)),rep(-1,q),rep(0,x*y-2*q))),x);p=animation::ani.pause;o=image;a=apply;repeat{o(m<-t(a(m,1,f)));p();o(m<--1*a(-1*m,2,f));p()}}

Ungolfed:

function(d,x,y){
  q=floor(d*y*x/2)

  m=matrix(sample(c(rep(1,q),rep(-1,q),rep(0,x*y-2*q))),x)

  f=function(w){
    v=length(w)
    for(j in which(w>0&!w[c(2:v,1)])){
      w[c(j,j%%v+1)]=0:1
    }
    w
  }


  library(animation)
  repeat{
    m=t(apply(m,1,f))
    image(m)
    m=-1*apply(-1*t(m),2,f))
    ani.pause()
    image(m)  
    ani.pause()
  }
}

Function that takes 3 arguments: d as density, and dimensions x,y. q is the number of cars in each colour. m is the matrix with cars, which is initially filled by taking a random sort of the number of cars and empty spaces. Cars are either 1 or -1, empty space is 0.

f is a function that moves the cars one row, looking at cars coded as 1. It checks if the car can move by checking for 1s followed by 0. We use apply to run f on every row or column, depending on which cars.

f handles the moving of the 1 cars, to move the -1 cars, we transpose the matrix, chaninging the direction of movement, multiplying the matrix by -1, so the -1 cars become 1 cars, and v.v. and the resulting matrix is transformed again.

This uses image to create the plot, using 3 default colours for the three values. Uses the animation package to handle the animations using the default options, which is 1 fps.

0.38, 144, 89:

Link to GIF

0.2, 144, 89:

Link to GIF

0.53, 144, 89:

Link to GIF

\$\endgroup\$
  • \$\begingroup\$ Your animation looks really cool - what density did you use? Seems like the whole thing got jammed pretty quickly with a lot of empty space \$\endgroup\$ – qwr Dec 29 '16 at 0:30
  • \$\begingroup\$ @qwr that actually was something that was bothering me. In my program the whole thing jams at lower densities than in the example you linked. I can't remember the exact parameters used for the plot though, but it could very well be the 0.38 144 89 from the example. \$\endgroup\$ – JAD Dec 29 '16 at 9:52
  • \$\begingroup\$ Playing around with square grids I got a density of 0.35 to jam jasondavies.com/bml/#0.35/100/100 but it is almost always one thick 45deg line instead of thin diagonal lines. Since your lines look more vertical I think something with the two types of cars is off \$\endgroup\$ – qwr Dec 29 '16 at 10:19
  • \$\begingroup\$ I see the problem now. Cara can only advance if they are not blocked by another car. So in the Wikipedia examples all moving cars have a space in front of them them. But in your animation the cars move as a line. Interesting. \$\endgroup\$ – qwr Dec 29 '16 at 10:21
  • \$\begingroup\$ Ah, that would do it. \$\endgroup\$ – JAD Dec 29 '16 at 10:28
5
\$\begingroup\$

Mathematica, 237 228 203 198 181 bytes

(b=RandomSample@ArrayReshape[Table[{0,i=2},##/2],{1##2},1]~Partition~#2;Dynamic@Colorize[i=-i;b=CellularAutomaton[{193973693,{3,{a=0{,,},{3,9,1},a}},{1,1}},b];If[i>0,b,2-b]])&

The output is a dynamic Image. The background is light green, and the cars are black or magenta, depending on their direction.

Explanation

b=RandomSample@ArrayReshape[Table[{i=1,2},##/2],{1##2},1]~Partition~#2

Create the initial board:

Table[{0,i=2},##/2]

Set i to 2. Create a List of {0, 2}, whose length is floor(density * width * height / 2) (divided by two because {0, 2} is length-2).

ArrayReshape[ ... ,{1##2},1]

Reshape the resulting 2-D List (2 x something) into 1-D List (length = width * height). Pad 1 if there aren't enough values.

RandomSample@ ...

(Pseudo-)randomly sort the result.

... ~Partition~#2

Partition that result into length (width).

b= ...

Store that in b.


Dynamic@Colorize[i=-i;b=CellularAutomaton[{193973693,{3,{a=0{,,},{3,9,1},a}},{1,1}},b];If[i>0,b,2-b]]

Create a Dynamic Image:

i=-i;

Flip the sign of i.

b=CellularAutomaton[{193973693,{3,{a=0{,,},{3,9,1},a}},{1,1}},b]

Apply the cellular automaton with rule 193973693 and neighbor weights {{0, 0, 0}, {3, 9, 1}, {0, 0, 0}} to b transposed. Set b equal to that.

If[i>0,b,2-b]

If i is positive, leave b alone. If not, transpose the b (2- is there because I golfed the CellularAutomaton a bit). Essentially, this transposes b every other iteration (to undo the transposition)

Colorize[ ... ]

Convert the array into a colorful Image.

Dynamic@ ...

Make the expression Dynamic. i.e. the above functions are run repeatedly.

Output

Here's a sample output (inputs: 0.35, 192, 108) for 2000 frames (magnified 2x).

https://i.imgur.com/zmSyRut.mp4

\$\endgroup\$
  • \$\begingroup\$ Huh, using the built-in is longer than not using it?! \$\endgroup\$ – Adám Jan 18 '17 at 16:05
3
\$\begingroup\$

Dyalog APL, 190 108 115 112 bytes

Solution

S←{⍉⍣⍺⊢d[⍺]↑d[⍺]↓⍉↑(⍺⊃'(↓+) ' '(→+) ')⎕R' \1'↓(,⍨,⊢)⍉⍣⍺⍉⎕←⍵⊣⎕DL÷4}
{1S 0S⍵}⍣≡' ↓→'[d⍴{⍵[?⍨⍴⍵]}c↑1 2⍴⍨⌊⎕×c←×/d←⎕]

TryAPL online (slightly modified because of online restrictions):

  1. Set ⎕IO←0, define the function S, and then define and display a random 38% 14×29 grid, G.

  2. Make one move down.

  3. Make one move to the right.

  4. Go to step 2.

    Traffic
    Animation of previous algorithm, which did not guarantee density.

Explanation

S←{ define the direct function S (explained here from right to left):

÷4 reciprocal of 4 (0.25)

⎕DL wait that many seconds (returns actual elapsed time)

⍵⊣ discard that in favour of ⍵ (the right argument; the grid)

⎕← output that

 transpose

⍉⍣⍺ transpose back again if ⍺ (the left argument; 0=down, 1=right)

( apply the function train (explained here from left to right):

  ,⍨ the argument appended to itself

  , appended to

   itself

)

 split matrix into list of lists

( search regex (explained here from left to right):

  ⍺⊃ pick one of the following two based on ⍺ (0=down/first, 1=right/second)

  '(↓+) ' '(→+) ' down and left arrow sequences followed by a space

)⎕R' \1' replace with a space followed by the found sequence

 mix list of lists into matrix

 transpose

d[⍺]↓ drop "height" rows if ⍺ (left argument) is 0 (down) or "width" rows if ⍺ is 1 (right)

d[⍺]↑ then take that many rows

 pass through (serves as separator)

⍉⍣⍺ transpose if ⍺ (the left argument; 0=down, 1=right)

}


' ↓→'[ index the string with (explained here from right to left):

 numeric input (dimensions)

d← assign that to d

×/ multiply the dimensions (finds count of cells)

c← assign that to c

⎕× multiply that with numeric input (the density)

 round down

1 2⍴⍨ cyclically repeat one and two until that length

c↑ extend that until length c, padding with zeros

d⍴ use d (the dimensions) to reshape

{ apply this anonymous function to that (explained here from left to right):

  ⍵[ the right argument (the list of zeros, ones, and twos) indexed by

   ?⍨ the shuffled indices up to

   ⍴⍵ the length of the argument

  ]

}

]

{ apply the following anonymous function (explained from right to left):

0S⍵ apply S with 0 (down) as left argument and the grid as right argument

1S with that as right argument, apply S with 1 (right) as left argument

}⍣≡ until two successive iterations are identical (a traffic jam)

Notes

  1. Requires ⎕IO←0, which is default on many systems.

  2. Prompts for (height,width), and then for density.

  3. Does not use any built-in automaton.

  4. Does use built-in regex support.

  5. Stops if there is a traffic jam (no car can move).

  6. Outputs character matrices where represents cars moving right, represents cars moving down, and spaces are empty roads.

  7. As above, it outputs to the session at 4 Hz, but frequency can be adjusted by changing ÷4; e.g ÷3 is 3 Hz and .3 is ³⁄₁₀ Hz.

  8. It is easier to see what is going on if executing ]Box on -s=max -f=on first.

  9. The required distribution is now guaranteed, and the two types of cars occur in exactly 50-50, save for rounding.

\$\endgroup\$
  • \$\begingroup\$ Your initial board generation does not guarantee a board that has the input density. I guess it's OP's choice whether to allow that or not. \$\endgroup\$ – JungHwan Min Dec 27 '16 at 16:02
  • \$\begingroup\$ Oh, @JarkoDubbeldam asked that already. \$\endgroup\$ – JungHwan Min Dec 27 '16 at 16:03
  • \$\begingroup\$ @JungHwanMin How so? Let the density be d. Every position gets a value between 0 and 1. If between 0 and ᵈ⁄₂ it becomes a ,. If between ᵈ⁄₂ and d it becomes a . If between d and 1 it stays empty. \$\endgroup\$ – Adám Dec 27 '16 at 17:15
  • \$\begingroup\$ Well, an extreme case would be: every position somehow gets the value 0 (because they're (pseudo)-randomly generated (pseudo)-independently; very improbable but possible). Then your board is full of s. \$\endgroup\$ – JungHwan Min Dec 27 '16 at 17:19
  • \$\begingroup\$ @JungHwanMin Ah, I see what you mean. \$\endgroup\$ – Adám Dec 27 '16 at 17:25
1
\$\begingroup\$

Java (624 Bytes + 18 Bytes for Java.awt.* = 642 Bytes)

static void k(double b,final int c,final int d){final int[][]a=new int[c+1][d+1];int i=0,j;for(;i<c;i++){for(j=0;j<d;j++){a[i][j]=Math.random()<b?Math.random()<0.5?1:2:0;}}Frame e=new Frame(){public void paint(Graphics g){setVisible(1>0);int i=0,j;for(;i<c;i++){for(j=0;j<d;j++){g.setColor(a[i][j]==2?Color.BLUE:a[i][j]==1?Color.RED:Color.WHITE);g.drawLine(i,j,i,j);}}for(i=c-1;i>=0;i--){for(j=d-1;j>=0;j--){if(a[i][j]==1&&a[i][(j+1)%d]==0){a[i][(j+1)%d]=1;a[i][j]=0;}else if(a[i][j]>1&&a[(i+1)%c][j]==0){a[(i+1)%c][j]=2;a[i][j]=0;}}}}};e.show();while(1>0){e.setSize(c,d+i++%2);try{Thread.sleep(400L);}catch(Exception f){}}}

Ungolfed:

static void k(double b,final int c,final int d){
        final int[][]a=new int[c+1][d+1];
        int i=0,j;
        for(;i<c;i++) {
            for(j=0;j<d;j++) {
                a[i][j]=Math.random()<b?Math.random()<0.5?1:2:0;
            }
        }

        Frame e=new Frame(){
            public void paint(Graphics g){
                setVisible(1>0);
                int i=0,j;
                for(;i<c;i++) {
                    for(j=0;j<d;j++) {
                        g.setColor(a[i][j]==2?Color.BLUE:a[i][j]==1?Color.RED:Color.WHITE);
                        g.drawLine(i,j,i,j);
                    }
                }
                for(i=c-1;i>=0;i--) {
                    for(j=d-1;j>=0;j--) {
                        if(a[i][j]==1&&a[i][(j+1)%d]==0){
                            a[i][(j+1)%d]=1;a[i][j]=0;
                        }else if(a[i][j]>1&&a[(i+1)%c][j]==0){
                            a[(i+1)%c][j]=2;a[i][j]=0;
                        }
                    }
                }
            }
        };
        e.show();
        while(1>0){e.setSize(c,d+i++%2);try{Thread.sleep(400L);}catch(Exception f){}}
    }

Picture:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Not familiar with java, but are red, blue and white the shortest names for colours you can use? (maybe grey is an option, saving one byte vs white) \$\endgroup\$ – JAD Dec 27 '16 at 22:43
  • \$\begingroup\$ The screenshot appears to show the same problem as what I described here codegolf.stackexchange.com/questions/104742/a-2d-traffic-jam/… \$\endgroup\$ – qwr Dec 29 '16 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.