As a follow up to yesterday’s Power Calc article, which, in passing, mentioned state machines, I pose the following question to you:

How many states are there for a typical traffic signal controlling two perpendicular streets?

There’s three light colors – red, yellow, and green – so that means there must be three states right?

Or, could it be that since there are twelve lights – two streets, each street running in two directions, one set of three colored lights visible in each direction (2*2*3=12) – that there are twelve states?

Or, noting, that opposite directions always have the same colors at the same time, perhaps that should be six states?

The correct answer is, in fact…. four.

To see why this is so, allow me to list each of the possible states. First, though, let’s name the two streets that are controlled by the lights in question as Street A and Street B. ( Kind of minimalist, i know. )

Here are the states:

  1. When the lights are green for cars on street A, by necessity the lights are red for cars on street B.
  2. When the lights are yellow for cars on street A, the lights are still red for cars on street B.
  3. When the lights on street A change from yellow to red, the lights on street B now change from red to green.
  4. Finally, the lights on street B change from green to yellow, by necessity the lights are still red for cars on street A. The very next state, when lights are green on street A, but red on street B, loops to the first state again.

When I’ve discussed this before, the hardest part for people to distinguish are the second and fourth states. Since the combination of colors are the same ( yellow-red for street A; and later, red-yellow for street B ) shouldn’t they be considered the same state? The point, however, is that they occur at different times and they control different streets. There is different information needed to describe the two situations, and so they are two independent states.

Here’s a couple of tables that might help. First a synopsis of the light colors, then the behavior of the drivers.

Light colors Link to heading

Street A Street B
green red
yellow red
red green
red yellow

Legal / desired behavior Link to heading

With those colors, to completely describe the situation, we need all four rows. Each row is its own unique states. So four states in all.

Street A Street B
drive. stop; wait.
slow down; don’t enter the intersection. keep waiting.
stop; wait. drive!
keep waiting. slow down; don’t enter the intersection.

Texas behavior Link to heading

For reference sake, here in Texas, cars from both directions actually start to move through the intersection at the same time. Some even at high velocity.

Street A Street B
green: drive red: proceed if there’s no traffic.
yellow: speed up; achieve maximum velocity. red: start driving; cackle as pedestrians dive to safety.
red: coast. green: check cell for voice mail.
red: stop only if you have to; curse governmental control. yellow: adjust volume of radio.

I can’t tell you how many states that is. It gets a bit messy.

Traffic Light Localization Link to heading

Of course, in the real world – Texas or otherwise – things are a whole lot more complicated in practice. There are green light switching delays, pedestrian signals, turn arrows, turn-only lanes, and a whole host of other issues.

If you’re making a driving game, best to write it all out long hand, or perhaps even, depending on the number of situations involved, you might consider writing a mini-dsl for controlling the lights, or maybe even create some sort of tag based rule system so you can tack on as many signal components as you want and make them all auto-magically work together.

For my jabs at Texas drivers, driving in Turkey is much crazier. One contributing factor: the traffic lights in Istanbul have a special flashing white strobe that, just before your light turns green, begins to flash. The instant the strobe goes off, the honking starts. “Not driving yet?” they ask.

The language of car horns, at least, is international.