Traffic flow simulation based on a simple cellular automaton

NaSchl.sql

-- Traffic flow simulation based on a simple cellular automaton
--
-- Based on a 1992 model by Kai Nagel and Michael Schreckenberg (NaSch),
-- also see:
-- http://www.christophschuette.com/blog/?p=50
-- http://www.thp.uni-koeln.de/~as/Mypage/traffic.html

-- Car model:
-- - ID:       c
-- - position: x
-- - velocity: v

-- Model update (time t → t+1):
-- (1) move:       xₜ   ← xₜ + vₜ
-- (2) accelerate: v    ← min(vₜ + 1, v_max)
-- (3) brake:      v    ← min(v, front.xₜ - xₜ - 1)  # front.xₜ: position of car immediately in front of us
-- (4) linger:     vₜ₊₁ ← if random() < linger then v ← max(0, v - 1) else v

-- To produce pure JSON output (psql ... -q | jq .)
\set quiet on
\pset border 0
\pset footer off
\pset tuples_only on
\timing off

-- # of iterations to simulate
\set iterations  100

-- NaSch model parameters
\set road_length 200  -- length of road (in cells), ⚠ circular road, wraps around
\set density     0.2  -- density of cars on road (0 < density ⩽ 1)
\set linger      0.15 -- probability of spontaneous/unforced braking
\set v_max       5    -- maximum velocity

-- (Initial) road representation
DROP TABLE IF EXISTS road;
CREATE TABLE road (
  car int, -- car ID
  x   int, -- position on road
  v   int  -- velocity
);

-- Populate road (initially: cars equi-distant, velocity 0)
INSERT INTO road(car, x, v)
  SELECT c AS car,
         floor((1 / :density) * c) AS x,
         0 AS v
  FROM   generate_series(0, floor(:road_length * :density) - 1) AS c;
--                          └────────────────────────────┘
--                              # of cars on the road

WITH RECURSIVE nasch(iter, c, x, v) AS (
  SELECT 0 AS iter, r.*
  FROM   road AS r

    UNION ALL

  (WITH nasch AS (TABLE nasch)
     SELECT n.iter + 1 AS iter,
            n.c,
            (n.x + n.v) % :road_length AS x,                                                       --   (1) move
            GREATEST(0,                                                                            --                               ⎤
                     LEAST(LEAST(n.v + 1, :v_max),                                                 -- ] (2) accelerate ⎤ (3) brake  ⎟  (4) linger
                           ((front.x + front.v) + :road_length - (n.x + n.v)) % :road_length - 1)  --                  ⎦            ⎟
                       - CASE WHEN random() < :linger THEN 1 ELSE 0 END) AS v                      --                               ⎦
     FROM   nasch AS n, nasch AS front
     WHERE  front.c = (n.c + 1)   % floor(:road_length * :density)
     AND    n.iter < :iterations -- └────────────────────────────┘
                                 -- # of cars on the road (wrap-around)
  )
)
-- ➊ JSON output (needed for JavaScript-based traffic-sim.html)
SELECT array_to_json(array_agg(row_to_json(n.*) ORDER BY n.iter, n.c)) AS traffic
FROM   nasch AS n;


-- -- ➋ Average speed per iteration
-- SELECT n.iter, AVG(n.v)
-- FROM   nasch AS n
-- GROUP BY n.iter
-- ORDER BY n.iter;

-- -- ➌ Complete output for debugging
-- TABLE nasch
-- ORDER BY iter, c;