Tráfico, cervezas y autómatas celulares

Mi amigo Descollante es probablemente la persona más cuadriculada que existe. Si quedas a una hora con él puedes estar seguro que estará en el lugar y hora acordado pase lo que pase, así que con toda segurdad, Descollante ya estaba esperándome. Yo no soy de los que suele llegar tarde, pero ¿qué podía hacer? estaba encerrado en un terrible caravana de esas impredecibles.
Había quedado con mi amigo para tomar unas cervezas y charlar sobre un nuevo proyecto que íbamos a emprender. Una aplicación que iba a revolucionar el mundo del software (evidentemente esto es sólo un sarcasmo, ya que todo quedará seguramente, en agua de borrajas, como todos los proyectos que emprendemos). El caso, es que allí estaba yo, una hora más tarde, saludando y sentándome junto a un Descollante con cara de malas pulgas y dos cervezas de ventaja.
Lo siento hombre, ni te imaginas la caravana que me ha pillado -le dije. Ya sabes... son imprevisibles. Nunca sabes cuando te va a pillar una.
¿imprevisibles? Que va hombre... El tráfico se comporta como un simple modelo estocástico -dijo Descollante con esa mirada que pone cuando está a punto de descubrir la Teoría de Todo.
Lo que quiero decir -continuó Descollante- es que podemos encontrar un modelo probabilístico para describirlo. ¿Recuerdas cuando el otro día hablábamos de el juego de la vida?


En ese mismo momento llegó la camarera con dos cervezas (la tercera para Descollante) y las dejó sobre la mesa junto con unos cacahuetes.
Sí, claro que lo recuerdo, pero ¿qué tiene que ver el juego de la vida con el tráfico?
Descollante sonrió de nuevo y me lanzó su típica mirada de superioridad.
El juego de la vida es un autómata celular, y en ellos el espacio, el tiempo y sus estados toman valores discretos, por lo que son muy eficientes para para implementar simulaciones en un ordenador.
Ya, pero en el juego de la vida no hay ningún proceso estocástico. Todo depende del estado inicial -dije, intentando demostrar que tenía el tema controlado.
Efectivamente -Dijo Descollante con cara de aprobación- Hay que añadir alguna variable probabilística, algo de caos al sistema, y por supuesto, una serie de reglas que rijan el cambio de estados.
Tengo que reconocer que la cosa empezaba a entusiasmarme, pero no sé si por la conversación en sí o porque yo ya estaba terminando la segunda cerveza. Curiosamente a Descollante no parecía afectarle su recién terminada cuarta jarra (en esta ocasión de cerveza negra).
Veamos, -continuó- en este caso nuestro autómata celular será de una sóla dimensión (es decir, lo podemos representar como un array de una dimensión). Vamos a asumir que sólo simulamos el tráfico de un carril para simplificar el modelo. Cada celda va a representar a un vehículo más cierta distancia de separación entre coches. Digamos que cada celda va representar un espacio de unos 7 u 8 metros.
Comenzó a garabatear en una servilleta y continuó explicándome que cada vehículo tenía un estado compuesto por su posición en la retícula del autómata y su velocidad. En este caso, la velocidad estaría limitada para todos los coches por igual, por lo que la velocidad de un coche estaría comprendida entre 0 (parado) y la velocidad máxima permitida. Seguidamente me habló del modelo Nagel-Schreckenberg, que según mi amigo, era de los modelos más simples ideados para simular el tráfico y que estaba compuesta por 4 sencillos pasos:

El primero de los pasos -dijo Descollante aún con un cacahuete en la boca- representa la tendencia de los conductores a ir lo más deprisa posible. Si un coche no ha alcanzado la velocidad máxima en el instante t incrementamos su velocidad en una unidad.

El segundo paso modela la interacción entre vehículos. Si hay un coche delante a una distancia d y la velocidad v del coche que estamos evaluando es mayor que d, entonces la velocidad del coche pasa a ser d en vez de v. Esto es, se procura mantener la distancia de seguridad para evitar el choque entre coches.

En el tercer paso añadimos un poco de caos. Tratamos de simular aquellos coches que de pronto, sin motivo aparente, frenan o bajan su velocidad. En este caso, con probabilidad p, el coche reducirá su velocidad en el instante t+1 en una unidad.

Por último, la velocidad v para el instante t+1 ha quedado determinada para cada coche y sólo nos resta aumentar la posición del coche en la retícula del autómata en v posiciones.

Todo me pareció bastante sencillo, a pesar de las cuatro cervezas que ya me había metido en el cuerpo. Así que mientras volvía a casa (en taxi, por supuesto) iba dándole vueltas a la cabeza intentando acordarme de por qué habíamos acabado hablando del tráfico en vez de hablar de nuestro proyecto.

Cuando llegué a casa no podía quitarme de la cabeza todo lo que me había contado Descollante, así que me senté ante el ordenador y a duras penas pude teclear el siguiente programa en Java antes de quedarme dormido sobre el teclado.



Código fuente:

1. import java.awt.*;
2. import javax.swing.*;
3.  
4. class Trafico extends JFrame {
5.        
6.     public Trafico() {  
7.         super("Trafico");
8.         setBounds(0,0,600,200);
9.         setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
10.         Container con=this.getContentPane();
11.         con.setBackground(Color.white);        
12.         GCanvas canvas=new GCanvas();    
13.         con.add(canvas);
14.         setVisible(true);
15.     }
16.     public static void main(String[] args) {
17.         new Trafico();
18.     }
19. }
20.  
21. class Coche {
22.     int pos;
23.     int velocidad;
24. }
25.  
26. class GCanvas extends Canvas implements Runnable {
27.     int TAM_CARRETERA=600;
28.     int VMAX=4; // velocidad máxima
29.     double prob_frenada = 0.5; // prob. de frenada.
30.     int tiempo_pausa=100;
31.     Coche[] carretera = new Coche[TAM_CARRETERA];
32.     Thread t;
33.     int velLlegada=4; // cadencia de llegada de coches
34.    
35.     public GCanvas() {
36.         t=new Thread(this);
37.         t.start();
38.     }
39.    
40.    
41.     public void paint(Graphics g) {
42.         // dibujar carretera   
43.         g.drawLine(0, 95, 600, 95);
44.         g.drawLine(0, 115, 600, 115);
45.         for (int i=0; i<TAM_CARRETERA; i++) {
46.             if (carretera[i] != null) {
47.                 g.fillRect(i, 100, 1, 10);     
48.             }
49.         }
50.     }
51.  
52.     @Override
53.     public void run() {
54.         int cont = velLlegada;
55.         do {
56.             // ¿Crear un coche?
57.             if (cont-- == 0) {
58.                 Coche nuevoCoche=new Coche();
59.                 nuevoCoche.velocidad=0;
60.                 nuevoCoche.pos=0;
61.                 carretera[0]=nuevoCoche;
62.                 cont = velLlegada;
63.             }
64.            
65.             // calcular desplazamientos
66.             for (int i=0; i<TAM_CARRETERA; i++) {
67.                 if (carretera[i] != null) {
68.                     // aceleración
69.                     if (carretera[i].velocidad<VMAX) {
70.                         carretera[i].velocidad++;
71.                     }
72.                    
73.                     // distancia seguridad
74.                     for (int j=1; j<carretera[i].velocidad; j++) {
75.                         if (i+j < TAM_CARRETERA) {
76.                             if (carretera[i+j] != null) {
77.                                 carretera[i].velocidad=j;
78.                                 break;
79.                             }
80.                         }
81.                     }
82.    
83.                     // probabilidad frenada
84.                     double p = Math.random();
85.                     if (p>prob_frenada) {
86.                         carretera[i].velocidad--;
87.                     }
88.                 }
89.             }
90.            
91.             // mover coches
92.             for (int j=TAM_CARRETERA-1; j>=0; j--) {
93.                 if (carretera[j] != null) {
94.                     Coche cocheTmp=carretera[j];
95.                     carretera[j]=null;
96.                     cocheTmp.pos += cocheTmp.velocidad;
97.                     if (cocheTmp.pos < TAM_CARRETERA-1) {
98.                         carretera[cocheTmp.pos]=cocheTmp;
99.                     }
100.                 }
101.             }
102.            
103.             repaint();
104.             try {
105.                 Thread.sleep(tiempo_pausa);
106.             } catch (InterruptedException e) {
107.                 e.printStackTrace();
108.             }
109.         } while (true);
110.     }
111. }