I finally laid my hands on Donald Knuth’s The Art of Computer Programming (what a wonderful set of books!), and found a neat algorithm for generating random integers 0, 1, 2, … , n – 1, with probabilities p_0, p_1, … , p_(n-1).
I have written about generating random numbers (floats) with arbitrary distributions for one dimension and higher dimensions, and indeed that method can be adapted for generating integers with specific probabilities. However, the method described below is much more concise, and efficient (I would guess) for this special case. Moreover, it is also easy to adapt it to generate floats for continuous distributions.
Continue reading “Generating Random Integers With Arbitrary Probabilities”
A cellular automata system is one of the best demonstrations of emergence. If you do not know what cellular automata (CA) is, then you should go download Conway’s Game of Life immediately:
Conway’s Game of Life
Essentially, CA is a collection of state machines, updated in discrete time intervals. The next state of one of these depends on the current state as well as the states of neighbours. Usually, the state machines correspond to cells in a grid, and the neighbours of a cell are the cells connected to that cell. For a more detailed explanation, see the Wikipedia article.
Even simple update rules can lead to interesting behaviour: patterns that cannot be predicted from the rules except by running them. With suitable rules, CA can simulate many systems:
- Natural phenomena: weather, fire, plant growth, migration patterns, spread of disease.
- Socio-economic phenomena: urbanisation, segregation, construction and property development, traffic, spread of news.
Continue reading “Cellular Automata for Simulation in Games”
Random steering is often a useful for simulating interesting steering motion. In this post we look at components that make up a random steering toolkit. These can be combined in various ways to get agents to move in interesting ways.
You might want to have a look at Craig Reynolds’ Steering Behaviour for Autonomous Characters — the wander behaviour is what is essentially covered in this tutorial. The main difference is that we control the angle of movement directly, while Reynolds produce a steering force. This post only look at steering — we assume the forward speed is constant. All references to velocity or acceleration refers to angular velocity and angular acceleration.
Whenever I say “a random number”, I mean a uniformly distributed random floating point value between 0 and 1.
Continue reading “Random Steering – 7 Components for a Toolkit”
I am playing around with generating textures and decided to post some preliminary results. The algorithm used to create these images is simple to implement, but slow. Here is how it works:
1. Generate White Noise
Start off with white noise (grayscale only – colour is much too slow).
2. Blend with random neighbourhood pixels
Generate a new image from the old one. Every pixel in the new image is a blend between the corresponding pixel in the other image, and a randomly selected pixel in a square window around that pixel. Every point in that window can be selected with a probability that is defined in a square matrix.
This matrix determines how the texture will turn out; it is unfortunately a bit hard to guess how the texture will look given the matrix, in the general case, without some mathematical analysis.
Repeat the above step. The more you repeat, the smoother the result is. The images below were created by repeating the step 50 times. On my computer, generating a 128 by 128 tile takes about 10 minutes (Python implementation).
4. Convert Grayscale to RGB
Normalise the image, and map to a gradient.
Some example textures are shown above.
There are some things that I still want to investigate:
- Is there a way to significantly speed up the algorithm?
- Is there an intuitive way to linkthe matrix with the result?
- What are the effects of starting with something other than white noise?
The code is currently too messy to release. I have built it on top of the code that was released for the Quadtrees article, so that is a good starting point if you do not want to wait. Otherwise, keep an eye out, I should post some code soon.