Randomness plays an important role in many games. Enemies appear randomly, or events occur at randomly spaced intervals. A relatively easy way to think of random events in a game is as a deck of note cards. The probability of a particular word being drawn is a function of the number of cards in the deck with that word on them, and the total number of cards in the deck.
This approach is called a discrete
In the case of circle the aardvark, I used a discrete distribution to determine whether an aardvark or an enemy spawned, and how long each character should remain on the screen before timing out and going away.
The game is written in Monkey X, but the code in this post is in Python.
You can find the Monkey X version here.
Read on for details
Background: Two kinds of people can spawn in the pickup trucks, Aardvarks (who you are supposed to cricle), or Otto von Bismarcks (who you are not supposed to circle). In early levels, there should be lots of aardvarks spawning and not very many Bismarcks. In later levels, most of the people who spawn should be Bismarck, and very few should be aardvarks.
Problem: We need a function that when called will return either "Aardvark" or "Bismarck". The probability of returning one or the other should not necessarily be equal, but should be controllable by the caller.
Approach: We'll create a class for discrete distributions. Conceptually, we can think of the class as a "deck" where we can any number of cards with different labels, and draw the cards randomly with replacement.
Items can be drawn from a discrete distribution in one of two different
ways: with replacement, or without replacement. If items are drawn with
replacement, then the probabilities are the same for every call (the
card is put back in the deck and the deck is reshuffled every time a
card is drawn). If items are drawn without replacement, then every time a
particular result is returned, the chances of drawing the same result on a
subsequent draw decrease (unless there is only one kind of item in the
set, in which case, the chances of drawing it remain 100%). In circle the aardvark, I only used the approach with replacement, but I'll give code for both here.
The first thing I like to do when writing a class or set of functions is to decide on an interface. Before I start worrying about which algorithms and data structures will the the best suited to the problem, I think it is important to define the problem as precisely as possible.
In this case, we'll take an object-oriented approach, and create a class called "Deck". The class will have only one public function: a constructor to instantiate new instances. Instances will have four public methods:
add, remove, draw, draw_with_replacement
The prototypes for the function and methods will be as follows:
add(value, count=1) #value is the label on the card. Count is the number of instances of the card to put into the deck.
remove(value, count=None) #value is the label on the card. Count is the number of instances of that value to remove from the deck. If count == None, then all instances of value will be removed.
draw() #returns a random value from the deck and removes one instance of that value from the deck.
draw_with_replacement() #returns a random value from the deck, but does not remove any values from the deck.
There are many different ways we could implement the above functions. The kind of data structure we use as the basis will largely depend on which operation we expect to use most frequently, and thus want to optimize for speed. Here are some possibilities:
The built-in list structure from python seems like the obvious choice, but because deleting items in the middle of a python list (what would be called an array in C) is a slow operation, some kind of linked might be better, especially for games using drawing without replacement. A third possibility would be to use a dictionary where keys are deck entries and values are the number of times that entry appears in the deck.
In most practical situations for games, the discrete distribution code will probably not be a speed bottleneck (you probably won't need to be calling it thousands of times per second), so it probably won't make a lot of difference which data structure you use.
For this implementation I'll use a dict as the underlying data structure because it makes the implementation simple (though not necessarily fast).
To test , paste the test code at the bottom of the file and run it from the command line.
The interfaces and test code will be the same regardless of the underlying data structure, so you can use this code as a framework for optimizing for some specific use. (Although optimization is probably not necessary in most cases).
Be sure to let me know if you find any bugs, or if you have questions, or think I'm doing something wrong!
This post is part of a series of posts about the code behind my game circle the aardvark in the back of the pickup truck.