Transcript random
Random numbers Why random numbers? • A random number is one of the easiest way to make a decision in a game • The player may see it as random, or try to guess the reasoning behind your choice! • Sometimes, games mix logical AI with some randomness to introduce surprises and reduce predictability • Later we can see how randomness may be shaped The m-sequence • The maximum length binary sequence may be generated in hardware or in machine code • It is made from shift-registers and exclusive-or function(s) • On a clock event, a shift register will transfer its input to its output and hold it there until the next clock pulse The m-sequence • An exclusive-or function will output a binary one if its inputs are different. • If presented with two ones or two zeroes, the output will be zero (this is called modulo-two addition) • Now let’s see a circuit: The m-sequence (copy this down) a3 a2 b3 (8) b2 (4) a1 b1 (2) a0 b0 (1) The m-sequence • We start off by “seeding” the circuit with all ones on the outputs of the single-bit memories. • The input of the exclusive-or gate has two ones on it, so the output is zero. • The output of the circuit is 1+2+4+8 = 15 • On the next clock pulse, inputs become outputs. Output b3 becomes zero. Circuit output becomes 1+2+4+0 = 7 The m-sequence • Easy exercise: • Please work out the 15 numbers in the sequence, until it starts to repeat. • Then work out what would happen if we stupidly seed it with all zeroes and start it off. • (5 mins) The m-sequence • Now you know what we’re talking about, let’s talk about it.... • It goes through every possible number except 0. • The sequence is (2n -1) long. Here we have 4 shift-registers, 24-1 = 15. So with only 16 shift registers we can have a sequence of 216-1 = 65535. It’s extremely efficient The m-sequence • Balance property: All numbers (except zero) occur only once. • The probability of any number (except zero) is the same. • Statistically it is smoother than a really random function. • This is the mechanism used in most random number generation in calculators and languages The m-sequence • The sequence is fixed – these are not random numbers, they are pseudorandom numbers. • The generator is sometimes run until interrupted by an external event (e.g. me pressing a key), making the next number unpredictable. • If we always seed using the same number, the sequence will always be the same (e.g. for debugging) • Many languages seed using the system clock Random numbers in high level languages • “C” has: • rand() – Produces a random integer • srand() – Sets up a seed for rand() • The ANSI C standard only states that rand() is a random number generator which generates integers in the range [0,RAND_MAX] inclusive, with RAND_MAX being a value defined in stdlib.h, and RAND_MAX being at least 32767 (= 215 – 1). Random numbers in high level languages • Dice – a bad algorithm: seed = time(NULL); srand(seed); i = (rand() % 6) + 1; // // // // % 6 means modulo 6, ie the remainder when the number is divided by 6. This is not the best way Random numbers in high level languages • Dice – a better algorithm: seed = time(NULL); srand(seed); x := ((rand()/(RAND_MAX+1)); y := (x * 6) + 1; i = int(y); // // // // x y i I is a float between 0 and 0.999 is a float between 1 and 5.999 is the dice output could have done this in one line Random numbers in high level languages • Many languages have a floating point random() function, which returns a value between 0 and 1. • In C we can produce one by: r = ((double)rand() / ((double)(RAND_MAX)+(double)(1))); • Let us assume that we have such a function. Exercise - Probability Densities • I throw a coin three times. What is the chance of: • Three heads? • Two heads and a tail? Probability Densities Probability Coins 3 2+1 1+2 3 M-Sequence Number/Enumeration Decisions using random numbers • The Boxer: • The boxer can use a Jab (j), an Uppercut (u), a Cross (c) or a Hook (h) • In this first example, we want all to be equally likely: The Boxer x := int(4*Random()); SELECT CASE (x) CASE (0) move := “j” CASE (1) move := “u” CASE (2) move := “c” CASE default move := “h” END SELECT The Boxer • In real life a boxer would use a jab far more often than any other move • So we assign our probability space accordingly. for r being a random number in the range 0-1.0: – 0... 0.4 means Jab – 0.4... 0.6 means uppercut – 0.6... 0.8 means cross – 0.8... 1.0 means hook The Boxer • What have we just done? • We’ve used a random number generator to “decide” on an AI opponent’s next move. • We’ve adjusted the probabilities so that the choice of move is more realistic. Star Field Generation • In Elite, there was a 2-D star-field • The field was based on an N x N grid • Whether there was a star in a cell or not was decided by a seeded random number generator Star := 0; IF (random() < 0.1 THEN Star := 1; Star Field Generation • Why was the random number seeded? • Well, the BBC Microcomputer only had 32k of memory. • Since the generator was seeded, it produced the same result every time it ran • So we didn’t need to store the star map in memory – we just ran the procedure. • A similar seeded procedure decided on the planets around the stars Terrain • We need to generate terrain for a landscape in which our hero is to fight • We don’t especially want to specify and remember the whole world – it’s easier if we can generate it on the fly, like our star map • There are a number of ways of doing this Terrain • A crude way: FOR each square in the grid Height = max_height * random() • Unfortunately, this produces a totally unrealistic landscape – the world wasn’t made that way! Terrain • The random grid could be cleaned up by constraining the maximum height difference between neighbouring cells • Since the top and left cells are filled in first, this results in ridges running diagonally top left – to – bottom right • Nevertheless, it sort-of works Terrain • In the PARTICLE DEPOSITION method, grains are dropped onto random points on the grid • The coordinates of the drop point are decided by running the random number generator twice. • There is a preset maximum height difference between cells • If the landing of a grain causes the height difference to a neighbouring cell to exceed the maximum, the higher grain “rolls” into the lower cell. • Having rolled, the algorithm assesses whether it still needs to roll one more cell, and does this if necessary Terrain • A simple algorithm is to use the star-field algorithm to allocate the positions of hills. • The hills have a standard height, width and shape • The shape is usually a raised cosine function • The height at any point is the sum of the heights contributed by any overlapping hill(s) Terrain Overlapping hills Background Sound • Background game music (extra-diegetic music) is usually looped because we don’t know how long the scene will last. • However, soundscapes cannot be looped for long. After a while you can predict the arrival of the cockerel’s crow (again!) • (Your best bet with a looped soundscape is to make it complicated and long) Background Sound • A better solution is the GRANULAR SOUND SYNTHESIS technique, where sound effects are added at random with a certain probability. • Sound effects may be randomly altered also: pitch and playback speed may be altered to hide the fact that they have the same source. Chip Music Percussion • When there is a game sound chip (Gameboy), percussion is often generated using filtered white noise. • Digital white noise is a random sequence of numbers. • This is usually generated on-chip using an M-sequence generator programmed into the hardware.