Quick, think of a number between 1 and X. Random Numbers

2-1-2018

Where we last left off at enemy AI, I had chosen a randomize type routine to make random decisions for the enemy to chase you.

The first decision would be for the enemy to do nothing. Another decision it would make is to pursue you on the X axis, another would be to use the Y axis and a final decision would be to use both axis.

Then we discovered a problem using the randomizing routine. We tried to reformulate and still had issues. Then, we went into troubleshooting, then we went into optimization.

I thought I had resolved the problem, but the problem is that I am simply running out of memory. I still want to have the same number of screens and I would still like to have sound effects, so I am trying my best to optimize and squeeze everything in.

And, if you ask if I am compressing the maps and graphics, Yes, I am compressing them. I am using ZX7 by Einar Saukas, it’s all prebuilt into FASE, so there is nothing extra to do when you run the batch file, compression is part of the entire build.

Back to randomizing.

One of the things our little game does is make a decision based on a random number. We roll the dice and the result of the roll is based on what lands on the table.

We want to be memory friendly with our Randomizer, yet we also want the darn thing to work well.

So, let’s explore together, shall we?

Starting off, our free size is 12959 bytes free. This is without any type of randomization, meaning I took out of the code all types of fake randomizes and pseudo-randomizes. The enemies do nothing but sit there.

Let’s try a fake randomize routine. This technique I read about in a blog. It’s a quick hack to provide a steady stream of different numbers that aren’t really random. You can then place a modulo function to place the numbers in the range you want to use.The technique was written and used by Jon Cauldwell.

Just FYI the % is a modulus or modulo operator, it’s the dividend or remainder. If set it will return a max value of the number set behind it, so %5 is from 0 to 5.

It gives a steady stream of numbers that really aren’t random, but good enough for a game, reading the first 8192 bytes of the Spectrum ROM. The article is found here.

http://chuntey.arjunnair.in/?tag=random

Let’s try implementing that.

We will want to make sure that we have the Standard Library in place, and include it in our code. I’m pretty sure we did that already.

#include //standard library

In our globals, we need to place.

unsigned int romCounter;//randomize function
unsigned char randomNumber;

in our reading level code, we need to initialize the variable.

if (isLevelRead == 0)
{
     romCounter = 0;
}

In our enemyai function

romCounter ++;//randomize function
if (romCounter > 8192) romCounter = 0;//randomize function
randomNumber = bpeek (romCounter);//randomize function
decision = ((unsigned char)randomNumber%4) + 1;

So now, our counter will set to 0 on reading the level and every time the enemyAI code is read, we will step up 1 number. If the romCounter is larger than 8192, we reset the counter to 0 and start all over again.

The randomNumber variable reads the ROM with a PEEK command in the position of our counter.

Finally, our decision is based on a Modulo function which makes the number between 0 and 4. However, since our range is between 1 and 5, we add 1 to the results. We now have a steady stream of non-random numbers. They appear to be random in the way the enemies move, but the numbers are extremely predictable because they are based on the ROM numbers. Let’s compile and test.

Voila, the enemies seem to move in a random fashion. The code when compiled shows 12903 bytes free. So, there is a 56-byte cost to this function.

Let’s reset all back to where we started and try another routine.

There is, of course, a randomizer built into Z88DK, this is found in the standard library, which we need anyway, so let’s try it out.

decision = (unsigned int)(((long)(4) * rand()) / (long)(RAND_MAX));

Now our code shows at 12764 bytes free, so a cost of 192 bytes for that randomizer.

So deciding to research other randomization techniques on the internet, I found there was a whole field of study behind randomization. All of it interesting and some of it quite complex. A programmer by the name of George Marsaglia came up with a number of Pseudo Random Number Generators (or PRNG).

These can be found at

http://www.ciphersbyritter.com/NEWS4/RANDC.HTM#369B5E30.65A55FD1@stat.fsu.edu

He showed a number of different ways to generate them using C macros, so let’s give 2 of them a trial.

The first is a very commonly generator called Multiply with Carry.

To program it, we need to declare 2 static short variables in our globals.

static unsigned short z = 47;
static unsigned short w = 43;

The number generator is called via a series of macros.

#define znew (z=255*(z&256)+(z>>4))
#define wnew (w=254*(w&253)+(w>>4))
#define MWC  ((znew<<4)+wnew )

Finally, in the enemy movement, it’s all called with a simple command.

decision = (MWC %4) + 1;

When we compile, we find that the memory usage shows 12884 bytes free, so our cost of this function is 75 bytes, 177 bytes shorter than the standard built in randomizer. Pretty nice.

Next, let’s explore another PRTG, XOR Shift.

In our globals, we define.

static unsigned short jz,jsr=5;//used in randomizer can be any 8 bit number

We need to define a macro.

#define SHR3 (jz=jsr, jsr^=(jsr5), jsr^=(jsr<<3),jz+jsr)

and call the macro within the function

decision = (SHR3 % 4);

On compiling, we find 12885 bytes free, we shaved off 1 byte for a high quality random number generator, very nice, our cost is 74 bytes. It’s hard to ask for more than that, it’s only 18 bytes larger than the non randomized technique employed by Jon Cauldwell.

Just to give a reference to where I found the 8 bit version of this technique,
http://www.arklyffe.com/main/2010/08/29/xorshift-pseudorandom-number-generator/

is where the shift and understanding of the function came to play.

In the end, this is what I am deciding to go with, it’s compact, easy to use and takes up very little memory, and generates a decent random sequence.

Advertisements

Author: andydansby

I'm a hobbyist coder working with the ZX Spectrum. Living in New York state near the Syracuse area. I grew up in Virgina. The first computer my parents bought for me was a Timex Sinclair 2068.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s