Random Walk Generator
Volume Number: 15
Issue Number: 11
Column Tag: Programming Techniques
A Random Walk Generator
by F.C. Kuechmann, Vancouver, WA
A CodeWarrior Pascal implementation of the "random
walk" decision simulation technique
Humans have seemingly always been fascinated by random phenomena. Randomness is a
pervasive component of our everyday lives. It characterizes the patterns of raindrops,
shape and location of clouds, traffic on the freeway. It describes the selection of
winning numbers in the lottery and day-to-day changes in the weather. The science of
chaos says that everything began in pure randomness and will end that way.
The computer provides a means for the systematic extended study of randomness and
pseudo-randomness that is impractical using simpler methods such as flipping coins
or rolling dice. A graphics-oriented computer and a simple algorithm such as a
two-dimensional random walk is ideal for the visual display and exploration of random
principles.
The random walk decision procedure, like the eight queens and knight's tour problems,
predates computers. In one college finite math textbook (Kemeny et. al. , 1962) it is
described in the context of an absorbing (i.e. terminating) Markov chain process
wherein, at each decision point, only the most recent decision is considered when
making the current one. Variations of the random walk method are currently used with
computers to simulate systems in the fields of physics, biology, chemistry, statistics,
marketing, population dynamics, and others. A bit of Internet prowling will unearth
information on many current applications. An Alta Vista search on the key "random
walk" generated 2988 hits, many of them redundant, but containing at least one hit for
most of the current applications of the method. Sourcecode for various
implementations is freely available on the net in languages ranging from Java to C to
Lisp.
Figure 1.A random walk.
The Random Walk Algorithm
In one of its simplest forms, a random walk is an absorbing Markov chain process with
three possible outcomes at each step. Each new step can be perpendicular to the
previous step (two of the possible outcomes) unless the absorbing state has been
reached (the third possible outcome) and no further moves are possible. Absent the
absorbing condition, if the previous step moved up or down, the current step must go
left or right. If the previous step moved left or right, the current one must move up or
down. A somewhat more complex variant adds a fourth possible outcom - continue in
the same direction as the previous step. If we go further and allow each step to be in
any direction regardless of the previous step, the process generates somewhat more
interesting graphic patterns.
An absorbing state is one in which no further steps are possible. For simulation
purposes in a college math class we might begin with a jolly drunk at his favorite
tavern departing for home. If and when he reaches home, jolly has achieved an
absorbing state. Additional absorbing states might be added in the form of policemen,
and the tavern itself might be an additional absorbing state - if jolly returns for
additional liquid nourishment.
Figure 2.Another random walk.
The Program
Conceptually, implementing a basic random walk is relatively simple. If we assume
that each step can be in any of four directions (North-South-East-West, or
up-down-left-right) regardless of the direction of the previous step, and that the
number of steps is infinite, we can describe the walk in pseudocode as follows
choose starting point
repeat
choose random direction 1-4
step in chosen direction
until forever
If we limit the permissible direction to one perpendicular to the previous direction,
for example, things get a bit more complicated because we need to keep track of the
direction of each step. One obvious method is with Boolean flag variables. The
pseudocode then might look like this
choose starting point
repeat
repeat
choose random direction 1-4
test flags for ok
until direction ok
set and clear flags to track direction
step in chosen direction
until forever
An interactive Mac program gets still more complex. There's little reason to impose
undue limits on the possible variations and variables in the walk. We easily can
provide for variable fixed or random step lengths, widths, colors and number of steps
per walk, as well as variable execution speed. I've allowed for as many variations and
possibilities as seem to produce graphically interesting results.
Creating steps
The main part of the program is shown in Listing 1 . After initializing the toolbox,
window, menus, global variables, etc, the program executes a loop that repeatedly
calls procedures that create new steps, check for events, etc., until the Boolean exit
variable ggDoneFlag is TRUE.
Listing 1.
RandomWalk
{Macintosh random walk program in CodeWarrior Pascal}
Program RandomWalk;
uses
Globals,Inits,Misc,StepStuff,GetReady;
{ Main RandomWalk }
begin
Initialize;
GetPen(ggThePoint);
Repeat
NewStep;
CheckEvents;
if ggDoneFlag then
Leave;
{get ready for another round if not quiting}
{and max step count}
if ggStepCount >= ggMaxSteps then
GetReadyForMore
{wait for 'go' button press if single-stepping}
else if ggStepWaitFlag then
begin
ggGoFlag := FALSE;
SetControlTitle(ggGoButtonHdl, 'Go');
CheckEvents;
end
else
Stall(ggStallVal);
Until ggDoneFlag;
end.
The main loop calls the NewStep procedure in Listing 2 for each new step. It first gets
a new random 1-10 pixel step width in the variable ggStepWid if the Boolean variable
ggRandomWidFlag is TRUE; otherwise the step width value remains that selected via
menu. The step width is then saved in the local variable stepWid so that it can be
restored if it is reduced later due to proximity to the right or bottom edge of the
window. Random step length 1-15 pixels and random color are selected next, if the
governing Boolean flags are TRUE. The details of random color selection are discussed
later in this article.
NewStep retrieves the saved pen position and calls the procedure GetDirection (Listing
3 ) to select a legal step direction, followed by a call to SetPenAndDeltas (Listing 7 )
to set pen width and height dimensions and the values of variables dX and dY . The pen
position must be saved after each step and restored before each new step because
clicking the mouse button sets the pen position. If the mouse click is inside the active
walking window that point becomes the new pen position; otherwise we test to see if a
button on the control panel at right. See the EventStuff source code for details.
For horizontal steps, the horizontal parameter for the toolbox PenSize call is 1, the
vertical parameter is that held in the global variable ggStepWid . For vertical steps,
the horizontal parameter equals ggStepWid , the vertical 1. The end position
co-ordinates after the newly-calculated step are obtained by adding X to dX and Y to dY .
We then check to see if the new position is outside the window. If it is, one of the four
wrap procedures is called. These procedures draw the step to the edge of the window,
then wrap around to the opposite edge of the window if the variable ggWrapFlag is
TRUE. If the new endpoint is not outside the window (which is most of the time) the
step is drawn in the NewStep procedure by calling the toolbox Line procedure. After a
bit of tidying up, the pen location is saved in the global Point variable ggThePoint
before exiting.
Listing 2.
NewStep
{ trace a step in the window,}
{ possibly random length, width and color. }
procedure NewStep;
var
dX, dY : integer;
X, Y, newX, newY, dir, stepWid : longint;
begin
Inc(ggStepCount);
UpdateStepCount;
{get new step width if random mode}
if ggRandomWidFlag then
begin
SetRandWid;
UpdateStepWidth;
end;
{save step width}
stepWid := ggStepWid;
{get new step size if random mode}
if ggRandSizeFlag then
begin
SetRandLen;
UpdateStepLen;
end;
{get random step color if random mode}
if ggRandomColorFlag then
SetRandColor
else
SetStepColor;
{save step color}
ggStepColors[ggStepCount] := ggFieldColor;
{fetch pen position}
with ggThePoint do
begin
X := h;
Y := v;
end;
{get random step direction}
GetDirection(dir, X, Y);
SetPenAndDeltas(dir, dX, dY);
MoveTo(X, Y);
{new XY pen co-ordinates after next step}
newX := X + dX;
newY := Y + dY;
{check for wrap-arounds}
if newY < ggMinY then
begin
DoTopWrap(Y, X, dX);
ggWrapDir[ggStepCount] := 1;
end
else if newX > (ggMaxX) then
begin
DoRightWrap(Y, X, dY);
ggWrapDir[ggStepCount] := 2;
end
else if newY > ggMaxY then
begin
DoBottomWrap(Y, X, dX);
ggWrapDir[ggStepCount] := 3;
end
else if newX < ggMinX then
begin
DoLeftWrap(Y, X, dY);
ggWrapDir[ggStepCount] := 4;
end
else
{no boundary problem; draw step here}
Line(dX, dY);
if not ggWrapFlag then
ggWrapDir[ggStepCount] := 0;
GetPen(ggThePoint);
with ggThePoint do
begin
X := h;
Y := v;
end;
MoveTo(X, Y);
GetPen(ggThePoint);
{save pen position for field redraw}
ggStepPositions[ggStepCount] := ggThePoint;