
Two pages from my sketchbook, as I puzzle out nonlinear level layout possibilities for L4D.
Left 4 Dead is a well polished, mostly traditional FPS experience with a notable innovation: the Director.
Valve designers found that no matter how cleverly zombies were placed, players would quickly begin to anticipate them on repeat playthroughs. So they developed an ingenious system to handle the zombies.
The AI "Director" controls most of the zombie mobs placement and modulate their strength in lieu of traditional designer placement. This makes for wildly variable experiences in terms of enemy encounters, density, and where the Survivors make their defensive stands/when they decide to run.
But on the heels of the L4D SDK's release, my thoughts return to how this governing principle might be more completely extended through the experience--namely the level design.
My own experience of the excellent co-operative L4D experience was that I enjoyed it, but felt not much prompting to replay it because I had experienced the whole "ride".
Despite being a superior specimen thereof, it's still of the linear "funhouse" style FPS experience. I creep around the next corner of an expertly crafted environment, but my friends and I have no say as to where we're headed, which seems contrary to the spirit of a "surviving a zombie apocalypse" game.
Just as the Director unmoors zombie placement from direct designer control, what if the level layout were (to a smaller degree) unpredictable? What if alongside semi-random obstacles and dead-ends, the players had to fight but also actively navigate to freedom?
Arguably this is counter or more complex than Valve might deem desireable or saleable, especially for a game so well designed for perfect casual 30-45 minute play sessions. But for players who have invested enough time in the game and want a more challenging but also more varied experience, I think the idea has merit. Certainly worth further inquiry.
The initial plan is for the player start to be in the dead center of the map, with roughly four main paths radiating outward, like a pinwheel. In addition to these four main trunk lines, there would be interconnecting spokes. This gives players four possible paths with out-bound linear paths, but also lateral movement by way of the spokes.

The "pinwheel" design sketch. The paths are in a roughly square configuration to minimize lateral travel time between main trunk lines. In a finished layout, the actual player-paths would be more s-curved and kinked.
Instead of simply choosing one of four paths--in which multiple playthroughs would very likely expose one to be the easiest path and become preferential to players--there is a degree of chaos introduced by semi-random blockages or dead ends that would appear at various points along these paths and spokes.
This plan is far from a "sandbox" approach, but would ideally allow for complexity by way of multilinearity.
Further updates as I refine and implement a test case with the L4D SDK.
UPDATE: Multilinear layouts are not supported by Left 4 Dead.

Screenshot from test level. It shows that despite the test level having two safe rooms, the escape_route--how the Director and AI reckons player progress through the level--can only route to one of them, not both.
The bright spot here--other than providing a nice way for me to familiarize with L4D's AI/navigational architecture--is that I successfully predicted a design issue with a multilinear path.
Above I wrote that the trouble with multiple routes is that players would likely adapt to one preferential route quickly, without something like semi-randomizing dead-ends or blockages.
After writing the above update I downloaded the SDK and starting working with it. Then I remembered that I hadn't played the L4D commentary mode, and so I played that.
In it, one of the developers (Mike Booth maybe?) mentions trying an early non-linear city block level, and that the trouble was in fact that experienced players quickly found a preferred route (and that bickering about which route to take taxed teamwork).
Now, I don't think this would be as much of a problem if different routes actually provided vastly different endpoints--such as heading north means the suburbs, west means the slums, east meant the industrial outskirts and south meant the forest--but at this stage that's pure conjecture.
L4D is a particular sort of game and a very good one for the design elements chosen. I'll have to wait for another opportunity to experiment with the kind of level structure as outlined above; in the meantime I'm still quite piqued at building a L4D map/campaign.