If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer programming

### Course: Computer programming>Unit 5

Lesson 2: Randomness

# Random walks

Before we go into the complexities of vectors and physics-based motion, let's think what it means for something to simply move around the screen. Let’s begin with one of the best-known and simplest simulations of motion—the random walk.
Imagine you are standing in the middle of a balance beam. Every ten seconds, you flip a coin. Heads, take a step forward. Tails, take a step backward. This is a random walk—a path defined as a series of random steps. Stepping off that balance beam and onto the floor, you could perform a random walk in two dimensions by flipping that same coin twice with the following results:
Flip 1Flip 2Result
TailsTailsStep backward.
Yes, this may seem like a particularly unsophisticated algorithm. Nevertheless, random walks can be used to model phenomena that occur in the real world, from the movements of molecules in a gas to the behavior of a gambler spending a day at the casino. As for us, we begin this topic by studying a random walk with three goals in mind.

### The Random Walker Object

Let's review a bit of object-oriented programming (OOP) first by building a `Walker` object. This will be only a cursory review. If you have never worked with OOP before, you should go through the section on Object-Oriented JavaScript.
An object in JavaScript is a data type that has both properties and functionality attached to it, via its prototype. We are looking to design a `Walker` object that both keeps track of its data (where it exists on the screen) and has the capability to perform certain actions (such as draw itself or take a step).
In order to create instances of `Walker`s, we need to define a `Walker` object. We'll use that object as the cookie cutter, and each new `Walker` instance are the cookies.
Let's begin by defining the `Walker` object type. The `Walker` only needs two pieces of data—a number for its x-location and one for its y-location. We'll set those in its constructor function, setting them to the center of the canvas.
``````var Walker = function() {
this.x = width/2;
this.y = height/2;
};``````
In addition to keeping track of its x and y, our `Walker` object will also have methods that we can call on it. The first will be a method that allows the object to display itself as a black dot. Remember that we add methods to an object in JavaScript by attaching them to the object's `prototype`.
``````Walker.prototype.display = function() {
stroke(0, 0, 0);
point(this.x, this.y);
};``````
The second method directs the `Walker` object to take a step. Now, this is where things get a bit more interesting. Remember that floor on which we were taking random steps? Well, now we can use our canvas in that same capacity. There are four possible steps. A step to the right can be simulated by incrementing `x` (`x++`); to the left by decrementing `x` (`x--`); forward by going down a pixel (`y++`); and backward by going up a pixel (`y--`). How do we pick from these four choices? Earlier we stated that we could flip two coins. In ProcessingJS, however, when we want to randomly choose from a list of options, we can pick a random number using `random()`.
``````Walker.prototype.walk = function() {
var choice = floor(random(4));
};``````
The above line of code picks a random floating point number between 0 and 4 and converts it to a whole number by using `floor()`, with a result of 0, 1, 2, or 3. Technically speaking, the highest number will never be 4.0, but rather 3.999999999 (with as many 9s as there are decimal places); since `floor()` returns the closest whole number that is lesser or equal, the highest result we can get is 3. Next, we take the appropriate step (left, right, up, or down) depending on which random number was picked.
``````Walker.prototype.walk = function() {
var choice = floor(random(4));
if (choice === 0) {
this.x++;
} else if (choice === 1) {
this.x--;
} else if (choice === 2) {
this.y++;
} else {
this.y--;
}
};``````
Now that we've written the class, it's time to make an actual `Walker` object in our program. Assuming we are looking to model a single random walk, we declare and initialize one global variable of type `Walker`, by calling the constructor function with the new operator.
``var w = new Walker();``
Now, to make the walker actually do something, we define the `draw()` function, and tell the walker to take a step and draw itself each time that's called:
``````draw = function() {
w.walk();
w.display();
};``````
Since we don't call `background()` in the draw function, we can see the trail of the random walk on our canvas:

### Improving the Random Walker

There are a couple improvements we could make to the random walker. For one, this walker’s step choices are limited to four options—up, down, left, and right. But any given pixel in the window has eight possible neighbors, and a ninth possibility is to stay in the same place.
To implement a `Walker` object that can step to any neighboring pixel (or stay put), we could pick a number between 0 and 8 (nine possible choices). However, a more efficient way to write the code would be to simply pick from three possible steps along the x-axis (-1, 0, or 1) and three possible steps along the y-axis.
``````Walker.prototype.walk = function() {
var stepx = floor(random(3))-1;
var stepy = floor(random(3))-1;
this.x += stepx;
this.y += stepy;
};``````
Taking this further, we could use a decimal for `x` and `y` instead and move according to an arbitrary random value between -1 and 1 - if our environment could actually display the difference between "2.2" and "2.4":
``````Walker.prototype.walk = function() {
var stepx = random(-1, 1);
var stepy = random(-1, 1);
this.x += stepx;
this.y += stepy;
};``````
All of these variations on the “traditional” random walk have one thing in common: at any moment in time, the probability that the `Walker` will choose to take a step in a given direction (or not move at all) is equal to the probability that the `Walker` will make any other given choice. In other words, if there are four possible steps, there is a 1 in 4 (or 25%) chance the `Walker` will take any given step. With nine possible steps, it’s a 1 in 9 (or 11.1%) chance.
Conveniently, this is how the `random()` function works. Its random number generator produces what is known as a “uniform” distribution of numbers. We can test this distribution with a program that counts each time a random number is picked and graphs it as the height of a rectangle:
Are the bars all the same height, after a few minutes of running? Probably not. Our sample size (i.e. the number of random numbers we’ve picked) is rather small and there are some occasional discrepancies, where certain numbers are picked more often. Over time, with a good random number generator, this would even out.
The random numbers we get from the `random()` function are not truly random; therefore they are known as “pseudo-random.” They are the result of a mathematical function that simulates randomness. This function would yield a pattern over time, but that time period is so long that for us, it’s just as good as pure randomness!
In the next section, we'll talk about different ways that we can create walkers with "tendencies" to walk in certain directions. Before you dive into that, there's a challenge that awaits you!

This "Natural Simulations" course is a derivative of "The Nature of Code" by Daniel Shiffman, used under a Creative Commons Attribution-NonCommercial 3.0 Unported License.