Estimating a Continuous Distribution from a Sample Set

header_rand_dist2 It is sometimes necessary to find the distribution given a sample set from that distribution. If we do not know anything about the distribution, we cannot recover it exactly, so here we look at ways of finding a (discrete) approximation.

Continue reading “Estimating a Continuous Distribution from a Sample Set”

Generating Random Points from Arbitrary Distributions for 2D and Up

header_rand_dist

I have already covered how to generate random numbers from arbitrary distributions in the one-dimensional case. Here we look at a generalisation of that method that works for higher dimensions.

The basic trick, while easy to understand, is hard to put in words (without reverting to mathematical equations). For two dimensions, we divide the plane into slices. Each slice is a 1D distribution. We also calculate a distribution from summing the frequencies in each slice. The latter distribution gives us one coordinate, and the appropriate slice to use. The distribution of that slice then gives the second coordinate. All distributions are put into inverse accumulative response curves as was done to generate one-dimensional random numbers. (You should review that before implementing the 2D case).

In more dimensions, we also slice the space up into 1D distributions. Sums of these give us more distributions, which we can sum again, and again, until we reach a single distribution. This is used for the first coordinate, and to determine which distribution to use for the next coordinate. This goes on, until a 1D slice gives us the final coordinate. Again, all distributions are converted to inverse accumulative response curves.

If the above is unclear, I hope the detailed description below clears things up.

Continue reading “Generating Random Points from Arbitrary Distributions for 2D and Up”

Cellular Automata for Simulation in Games

header

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”

A simple texture algorithm – faster code and more results

header

Faster Code

A while back I wrote about a simple texture algorithm that I have been exploring. The Python implementation was very slow – so much, that I decided to implement it in C++ to see what performance gain I would get. Surprisingly, the C++ version is about 100 faster, if not more. I expected a decent increase, but what once took several hours can now be done in a minute!

Continue reading “A simple texture algorithm – faster code and more results”

Random Steering – 7 Components for a Toolkit

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”

Quadtrees

The code below implements some quadtree extensions, as discussed in another Dev.Mag tutorial about quadtrees (see Issue 27). The tutorial covers the following topics:

  • what to consider in choosing whether to use a quadtree or not;
  • tests to help you choose an appropriate threshold;
  • how to handle discrete data; and
  • some modifications to the basic algorithm.

Handling Discrete Data

When it comes to discrete data, the “average” of a number of pixels doesn’t make sense. However, we can give it meaning and still use it to get good approximations of the original data, as illustrated in the images below.

The original grid of discrete data. The grid contains integers from 0 to 4. Every integer is mapped to a colour in this image. (If this grid represented a tile map, every integer would be mapped to a different tile).
Here we allowed floating point numbers in the quadtree. Results of queries into the quadtree are rounded before mapping them to colours.
Here we used the floating point part of queries to bias a randomly selected integer. For example, a result of 1.25 will result in a 75% chance of yielding 2.
Here we use a quadtree with interpolation. The result is rounded before it is mapped.
Here we use a quadtree with interpolation, and use the floating point part of the number to bias a randomly selected tile, as above.

Download

Python Implementation

Download from: http://code-spot.co.za/python-image-code/ (See quadtree.py, quadtree_image.py, and quadtree_demo.py).

A Simple Procedural Texture Algorithm – More Results and Code

spots

In a previous post I explained a simple algorithm for generating textures. Below are some more examples of the kinds of textures that the algorithm can generate, as well as how the different parameters influence the result. You can also download the code.

Continue reading “A Simple Procedural Texture Algorithm – More Results and Code”

5 Tips for Prototyping Slow Algorithms

2054205239_334a519d0e

(Photo by  Darren Hester)

Some algorithms take a long time to return their results. Whether it is because the algorithm has to operate on a huge data set, or because it has combinatorial complexity; every time you run it you have to wait minutes or even hours for the thing to finish, making errors very expensive.

This post gives some advice on how to prototype slow algorithms with as little frustration as possible. We assume that this algorithm is being implemented experimentally – that is, you will tweak it and change it often before it is finished (it is not the kind of algorithm you type in straight from a text book). For example, I used the ideas outlined here while playing with the texture generating algorithm of the previous post.

Continue reading “5 Tips for Prototyping Slow Algorithms”

A Simple Procedural Texture Algorithm

texture

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.

3. Repeat

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.

texture1 texture2 texture7
texture4 texture6 texture3
texture8 texture9 texture10

Some example textures are shown above.

 

Questions

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?

Code

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.

Quadtrees

The quadtree is an important 2D data structure and forms the core of many spatial algorithms, including compression, collision detection, and stitching algorithms. Below you can download general purpose quadtree implementations in Java and Python.

The code accompanies the Quadtrees article in Dev.Mag. The tutorial explains how the implement a quadtree that can be use to store 2D data efficiently, lists what considerations there are in real-world applications, and gives some debugging tips.

Channels Compressed Simultaneously

bar bar_c
The original image (by smcgee). The image after being loaded into a quadtree.

Continue reading “Quadtrees”