FREEWAY - Based on an article in Algorithm July/September 1992 (no. 3.3)
Computer Recreations by A. K. Dewdney
DISCLAIMER: What you see is what you get. This program is distributed "as
is". I make absolutely no promises about the results of executing this
program on your computer. I have no responsibility for anything that may
happen to you, your computer, or its surroundings, directly or indirectly, as
a result of running this program. I have run this program with no bad effects
on my PC and several others, ranging from a 8 mhz 80286 to a 50 mhz 80486 -
all had VGA displays. Borland Turbo C++ documentation says it should work on
an EGA display, I have not tested it. Use this program at your own risk.
IBM PC compatible with MS-DOS compatible operating system
it is known to work with DOS 3.3 and higher
EGA/VGA display - the program, via Borland Turbo C++ initgraph, checks
for 640x350 or better resolution, and at least 16 colors
Programming Environment: Borland Turbo C++
(used as "a better C", i.e. not object oriented)
A. K. Dewdney once wrote a very interesting column for the magazine
"Scientific American" called "Computer Recreations". Each month he would
describe a small interesting program. His columns frequently dealt with
fractals (e.g., the Mendelbrot set - FRACTINT is the definitive fractal
program, if you have *any* interest in fractals, get it) and cellular
automata (e.g. Conway's "game" of Life, or, my favorite, DEMON, which I
programmed - look for it on your favorite BBS). He collected a couple years
worth of articles into a book, "The Armchair Universe", which I have greatly
enjoyed. He has written a second book, whose name excapes me (I never
finished all the programs suggested in "The Armchair Universe"), which
appears to be more of the same.
A couple of years ago, Dewdney's column disappeared from "Scientific
American". About the same time, Dewdney started publishing a small magazine
called Algoriths, which also had a "Computer Recreations" columns. Algoriths
may be more accurately described as a pamphlet, the most recent issue only
has 32 pages.
In a recent issue, Mr. Dewdney described the mission of Algorithms as follows:
"Presently we see Algorithms as a recreational programming magazine. The only
problem with the word "recreational" is that to some people it implies a
certain triviality. In truth, we are about the joy of ultimate control -
making the computer do what you want, bringing to life within its universal
circuits the world of your choice. Algorithm therefore becomes the gateway not
only to computing (specifically programming) but to a myriad of intellectual
worlds at the cutting edge. Not for passive persons but active ones."
If you enjoy programming, or think you might enjoy programming, you will
likely enjoy Dewdney's magazine or books. The address to subscribe to
P.O. Box 29237, Westmount Postal Outlet
785 Wonderland Road
London, Ontario, CANADA N6K 1M6
Algoritms is published quarterly, annual subscription $19.95 US. If you
subscribe, mention my name (Richard Maurer). They don't know me from Adam but
there may be some sort of reward for bringing in new subscribers.
Note: I have hacked Mr. Dewdney's FREEWAY program almost beyond recognition.
His algorithms, like those he includes with all his articles, *were*
relatively simple - using nothing more complex than a couple of vectors
(single dimensional arrays). The structures, pointers to structures and
dynamic memory allocation in the attached source are all my "enhancements".
My only excuse is it "just sort of grew that way".
FREEWAY simulates two lanes of a freeway, both going in the same direction.
Your observation point is as if you were in a traffic helicopter. Your
helicopter is flying along, with traffic, at about 45 miles per hour. The
traffic is moving at speeds of 45 miles per hour up to about 75 miles per
Actually the program deals with feet per second, the slowest cars are going 0
(zero) feet per second (relative to you) and the fastest are going 40 feet
per second (again relative to you). Dewdney suggested in his column that the
relative speeds be -20 feet per second to +20 feet per second but I had
problems with the movement and passing algortihms with cars having negative
relative velocities. The algorithms seemed a lot easier with all the cars
going the same direction.
I made a couple of other changes from Dewdney's column, but they are evident
only if you have access to the column and look at my program.
Dewdney suggested the use of "beside" pointers to control lane changes -
"passing" and "returning" in the nomenclature of this simulation. In contrast
to his usual thorough algorithmic description, some of the "pointer chasing"
algorithms were "described only generically, and some [were] barely implied
[to be there]". He does say that "neighboring vehicles [can be located] by
conducting a search [of the other lane and] would be somewhat shorter and
easier to code that the present one". He than goes on to say that the
"pointer" algorithm is much faster. *I* never got the "beside" pointer
chasing to work correctly and my profiler says the bulk of the time is spent
in drawing to the screen anyway. As Dr. Pournelle, Byte magazine
columnist, says, my version is "fast enough".
Dewdney also suggested giving the user the ability to move the observation
point along the freeway. I simply show the entire freeway broken up into
several sections, which I refer to as windows.
You have control of several parameters in the simulation from the command line.
Usage is: FREEWAY [options]
Where the available options are:
/d simulation interval
/p carlengths clearance to pass
/r carlengths clearance to return
/t set how slow before passing
/w number of lanes on screen
/h prints a help screen
The defaults, shown below, work well, to my tastes, on my 16mhz 386 with
Video 7 (now Headland) FastWrite VGA card. If you have a materially faster or
slower machine (or are just very patient or very impatient) you may adjust
the "d" or "w" parameters to suit.
Notes:1) The options must be entered in lower-case - "/d" works, "/D" won't.
I am just getting into UNIX which is case sensitive, I still
haven't decided if that is a "good idea" or not, but the designers
of UNIX did not consult me.
2) The numeric parameter does *not* include the "<" and ">" shown
below. Also, do *not* put a space between the option and the
numeric parameter, "/r2" not "/r 2".
/dis simulation interval in milli-seconds, i.e. thousandths
of seconds. The default is 100 milli-seconds, 1/10 of a
second. Increasing this parameter speeds up the simulation
(with a penalty of some jerkiness), decreasing it slows down
/pis the clearance required to pass, in car lengths. Default is
1 car length. Increasing this parameter makes a car that has
come up behind a slower car, wait for a larger opening in the
adjacent lane before passing. It cannot be decreased below 1.
/ris the clearance required to return to the rightmost lane in
carlengths clearance. Default is 1 car length. Increasing this
parameter makes a car that has moved to the passing lane wait
for a larger opening in the adjacent lane before returning.
It cannot be decreased below 1. (I often set /r to 2, it
seems to make for a more realistic simulation.)
/tsets the cars' tolerance to follow a slower car. That is, a
car will follow another car moving within "tolerance" of its
desired speed, but will pass if the other car is not within
"tolerance" of its desired speed. Default is 7. Setting this
parameter larger means that a car only passes if the car on
which it has come up behind is moving (relatively) very
slowly; setting it smaller means a car will almost always
pass when it comes up behind a slower car.
/wsets the number of lanes on screen (and in the simulation).
Default is 4. Changing this parameter affects the length of
freeway simulated and shown on the screen. Minimum is 1, the
maximun is whatever your display can handle, each lane is 19
pixels high. Increasing this parameter slows the simulation,
decreasing this parameter speeds up the simulation. This is
probably the best way to compensate for slower CPU's - using
/d to speed up the simulation tends to make the display
somewhat jerky. It also give the faster CPU's more to watch.
I hope you enjoy playing with this program as much as I enjoyed writing it.
If you would wish to share a comment with me, I can be reached at:
U.S. MailRichard Maurer
P.O. Box 150949
Nashville, TN 37215-0949