Um engarrafamento 2D

17

O modelo de tráfego Biham-Middleton-Levine é um autômato celular de auto-organização que os modelos simplificados de trânsito.

Consiste em vários carros representados por pontos em uma treliça com uma posição inicial aleatória, onde cada carro pode ser de dois tipos: aqueles que apenas se movem para baixo (mostrados em azul neste artigo) e aqueles que apenas se movem em direção à direita (mostrada em vermelho neste artigo). Os dois tipos de carros se revezam para se mover. Durante cada turno, todos os carros do tipo correspondente avançam um passo se não forem bloqueados por outro carro.

Sua tarefa é visualizar esse modelo como uma animação. Aqui estão algumas boas demonstrações.

insira a descrição da imagem aqui

Entrada

Um número de ponto flutuante entre 0 e 1 representando densidade e dois números inteiros representando a altura e a largura da grade exibidas. Suponha que as entradas sejam válidas e que os parâmetros para uma função ou leitura da entrada do usuário estejam corretos.

Exemplo: 0.38 144 89(corresponde à imagem acima)

Resultado

Uma grade, pelo menos 80x80, que exibe a animação desse modelo em execução. No início, os carros são colocados aleatoriamente na grade até que a grade atinja a densidade de entrada, com meio vermelho e meio azul (ou seja, densidade vezes o número total de quadrados da grade, arredondados da maneira que você desejar). A densidade deve ser esse valor, o que significa que você não pode preencher cada célula com densidade como uma probabilidade. Para cada etapa, um tipo de carro se move para baixo ou para a direita, contornando se ultrapassarem a borda. O tipo de carro que se move alterna cada etapa. Para tornar a animação visível, deve haver pelo menos 10 ms entre cada etapa.

Regras

  • Os carros podem ter qualquer cor ou símbolo, desde que sejam distinguíveis entre si e com o plano de fundo, e cada tipo de carro tenha a mesma cor ou símbolo.

  • Console e saída gráfica são permitidos. Para a saída do console, qualquer símbolo imprimível é bom, mas a saída deve ser como uma grade de caracteres.

  • Especifique que tipo de saída você produziu se não tiver uma captura de tela ou gif.

  • A simulação deve ser executada para sempre.

A saída é um pouco complexa, portanto, se você tiver alguma dúvida, comente.

qwr
fonte
Alguma restrição sobre quão lenta ou rapidamente a animação deve ser executada?
Xnor
Talvez valha a pena especificar que o tipo de carro que se move alterna cada passo.
Greg Martin
@ xnor Eu estava pensando em pelo menos 5 ou 10 ms por loop, mas não tenho certeza se isso seria difícil de medir.
Qd #
3
A densidade significa que a densidade deve ser esse valor ou apenas que cada pixel tem uma probabilidade d de ser preenchida? Além disso, temos que atribuir a cor dos carros aleatoriamente ou não? Se aleatoriamente, novamente tudo bem se eles tiverem 50-50 de chance de serem de qualquer cor?
JD
11
@JarkoDubbeldam A densidade tem que ser esse valor. Eles têm uma chance de 50 a 50 de cada cor. No entanto, eu respondi tarde, então as respostas podem ser diferentes. Os carros podem se mover para cima ou para a esquerda.
Qd #

Respostas:

5

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()
  }
}

Função que recebe 3 argumentos: dcomo densidade e dimensões x,y. qé o número de carros em cada cor. mé a matriz com carros, que é preenchida inicialmente tomando um tipo aleatório do número de carros e espaços vazios. Os carros são 1ou -1, o espaço vazio é 0.

fé uma função que move os carros uma linha, olhando para os carros codificados como 1. Ele verifica se o carro pode se mover verificando 1s seguidos por 0. Costumamos applycorrer fem todas as linhas ou colunas, dependendo de quais carros.

flida com o movimento dos 1carros, para mover os -1carros, transpomos a matriz, seguindo a direção do movimento, multiplicando a matriz por -1, para que os -1carros se tornem 1carros, e vv e a matriz resultante é transformada novamente.

Isso é usado imagepara criar a plotagem, usando três cores padrão para os três valores. Usa o animationpacote para manipular as animações usando as opções padrão, que são 1 fps.

0.38, 144, 89:

Link para GIF

0.2, 144, 89:

Link para GIF

0.53, 144, 89:

Link para GIF

JAD
fonte
Sua animação parece muito legal - que densidade você usou? Parece que a coisa toda ficou preso muito rapidamente com um monte de espaço vazio
QWR
@qwr que realmente era algo que estava me incomodando. No meu programa, a coisa toda atola em densidades mais baixas do que no exemplo que você vinculou. Não me lembro dos parâmetros exatos usados ​​para o enredo, mas poderia muito bem ser o 0.38 144 89do exemplo.
JD
Brincando com grades quadradas, obtive uma densidade de 0,35 para encravar jasondavies.com/bml/#0.35/100/100, mas é quase sempre uma linha grossa de 45deg em vez de finas linhas diagonais. Desde suas linhas olhar mais vertical Acho que alguma coisa com os dois tipos de carros está fora
QWR
Eu vejo o problema agora. Cara só pode avançar se não for bloqueado por outro carro. Assim, nos exemplos da Wikipedia, todos os carros em movimento têm um espaço na frente deles. Mas na sua animação os carros se movem como uma linha. Interessante.
Qd #
Ah, isso faria isso.
29416 JAD
5

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]])&

A saída é uma dinâmica Image. O fundo é verde claro e os carros são pretos ou magenta, dependendo da direção.

Explicação

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

Crie o quadro inicial:

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

Defina icomo 2. Crie um Listde {0, 2}, cujo comprimento seja piso (densidade * largura * altura / 2) (dividido por dois porque {0, 2}é comprimento-2).

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

Remodelar o 2-D resultante List(2 x algo) em 1-D List(comprimento = largura * altura). Almofada 1se não houver valores suficientes.

RandomSample@ ...

(Pseudo-) classifica aleatoriamente o resultado.

... ~Partition~#2

Partição que resulta em comprimento (largura).

b= ...

Armazene isso em b .


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

Crie um Dynamic Image:

i=-i;

Vire o sinal de i.

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

Aplique o autômato celular com 193973693pesos de regra e vizinhos {{0, 0, 0}, {3, 9, 1}, {0, 0, 0}}para btranspor. Conjuntob igual a isso.

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

Se ifor positivo, deixe em bpaz. Caso contrário, transponha o b( 2-existe porque eu joguei CellularAutomatonum pouco). Essencialmente, isso transpõeb todas as outras iterações (para desfazer a transposição)

Colorize[ ... ]

Converta a matriz em um colorido Image .

Dynamic@ ...

Faça a expressão Dynamic. ou seja, as funções acima são executadas repetidamente.

Resultado

Aqui está uma saída de amostra (entradas :) 0.35, 192, 108para 2000 quadros (ampliada 2x).

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

JungHwan Min
fonte
Huh, usar o built-in é mais longo do que não usá-lo ?!
Adám 18/01/19
3

Dyalog APL , 190 108 115 112 bytes

Solução

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

TryAPL online (ligeiramente modificado devido a restrições online):

  1. Conjunto ⎕IO←0, definir a função S , e, em seguida, definir e exibir um aleatória 38% 14 × 29 grelha, L .

  2. Faça um movimento para baixo.

  3. Faça um movimento para a direita.

  4. Vá para o passo 2.

    Tráfego
    Animação do algoritmo anterior, que não garantiu densidade.

Explicação

S←{defina a função direta S (explicada aqui da direita para a esquerda):

÷4 recíproco de 4 (0,25)

⎕DL aguarde alguns segundos (retorna o tempo decorrido real)

⍵⊣ descartar isso em favor de ⍵ (o argumento certo; a grade)

⎕← saída que

 transpor

⍉⍣⍺ transponha novamente se ⍺ (o argumento da esquerda; 0 = baixo, 1 = direita)

( aplique o trem de funções (explicado aqui da esquerda para a direita):

  ,⍨ o argumento anexado a si mesmo

  , anexado a

   em si

)

 dividir matriz em lista de listas

( regex de pesquisa (explicado aqui da esquerda para a direita):

  ⍺⊃ escolha uma das duas seguintes com base em ⍺ (0 = para baixo / primeiro, 1 = para direita / segundo)

  '(↓+) ' '(→+) ' seqüências de seta para baixo e esquerda, seguidas por um espaço

)⎕R' \1' substitua por um espaço seguido pela sequência encontrada

 misturar lista de listas em matriz

 transpor

d[⍺]↓ solte as linhas "altura" se ⍺ (argumento à esquerda) for 0 (para baixo) ou as linhas "largura" se ⍺ for 1 (à direita)

d[⍺]↑ então pegue tantas linhas

 passagem (serve como separador)

⍉⍣⍺ transpõe se ⍺ (o argumento da esquerda; 0 = baixo, 1 = direita)

}


' ↓→'[ indexe a string com (explicada aqui da direita para a esquerda):

 entrada numérica (dimensões)

d← atribuir isso a d

×/ multiplique as dimensões (encontra contagem de células)

c← atribua isso a c

⎕× multiplique isso com entrada numérica (a densidade)

 arredondar para baixo

1 2⍴⍨ repetir ciclicamente um e dois até esse comprimento

c↑ estenda isso até o comprimento c , preenchendo com zeros

d⍴ use d (as dimensões) para remodelar

{ aplique esta função anônima a isso (explicada aqui da esquerda para a direita):

  ⍵[ o argumento correto (a lista de zeros, uns e dois) indexados por

   ?⍨ os índices embaralhados até

   ⍴⍵ o comprimento do argumento

  ]

}

]

{ aplique a seguinte função anônima (explicada da direita para a esquerda):

0S⍵ aplique S com 0 (para baixo) como argumento à esquerda e a grade como argumento à direita

1S com isso como argumento certo, aplique S com 1 (direito) como argumento esquerdo

}⍣≡ até que duas iterações sucessivas sejam idênticas (um engarrafamento)

Notas

  1. Requer ⎕IO←0, que é padrão em muitos sistemas.

  2. Solicita (altura, largura) e, em seguida, densidade.

  3. Não usa nenhum autômato interno.

  4. Usa suporte a regex interno.

  5. Pára se houver um engarrafamento (nenhum carro pode se mover).

  6. Produz matrizes de caracteres onde representa carros se movendo para a direita, representa carros se movendo para baixo e espaços são estradas vazias.

  7. Como acima, ele envia para a sessão em 4 Hz, mas a frequência pode ser ajustada alterando ÷4; por exemplo, ÷3é 3 Hz e .3é ³⁄₁₀ Hz.

  8. É mais fácil ver o que está acontecendo se for executado ]Box on -s=max -f=onprimeiro.

  9. A distribuição necessária agora está garantida e os dois tipos de carros ocorrem exatamente em 50 a 50, exceto o arredondamento.

Adão
fonte
Sua geração inicial de placa não garante uma placa com densidade de entrada. Eu acho que a escolha do OP é permitir isso ou não.
JungHwan Min
Ah, o @JarkoDubbeldam já perguntou isso.
JungHwan Min
@JungHwanMin Como assim? Seja a densidade d. Cada posição recebe um valor entre 0 e 1. Se entre 0 e ᵈ⁄ᵈ, torna-se a ,. Se entre ᵈ⁄₂ ed se tornar a . Se entre d e 1, ele permanecerá vazio.
Adám
Bem, um caso extremo seria: toda posição de alguma forma obtém o valor 0(porque elas são (pseudo) - geradas aleatoriamente (pseudo) - independentemente; muito improváveis, mas possíveis). Então seu quadro está cheio de s.
JungHwan Min
@JungHwanMin Ah, entendo o que você quer dizer.
Adám
1

Java (624 bytes + 18 bytes para 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){}}
    }

Cenário:

insira a descrição da imagem aqui

Urna de polvo mágico
fonte
Não conhece java, mas vermelho, azul e branco são os nomes mais curtos para as cores que você pode usar? (talvez cinza é uma opção, salvando um byte vs branco)
JAD
A imagem parece mostrar o mesmo problema que o que eu descrevi aqui codegolf.stackexchange.com/questions/104742/a-2d-traffic-jam/...
QWR