A 2D Traffic Jam

Question

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.

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.

Answer 1

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

Answer 2

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:

0.2, 144, 89:

0.53, 144, 89:

Answer 3

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.

   
   ^{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.

Answer 4

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: