Seeding random numbers to store a randomly-generated video game level

[djr33]

This is just something I'm wondering about, after playing a particular video game on my iPhone.

In short, the game has only one level, but randomizes it each time (this is true of a number of games I imagine). So think of it as any kind of racing/running/whatever game, and as you go through it, unlike, say, one of the Mario games, the world is different around you each time so it's always new, even though there's only "one level" or just one environment.

It's fairly clear what the variables are-- every 30 seconds or so the background/environment changes to something new; obstacles appear in random places (and in harder places as you get farther in the level); extra characters run around in random places; and extra power-ups and so forth can be found at random times, with random values.

Easy enough. It's just set to random, basically a complicated version of any dice-rolling or card-shuffling game.

But it's not quite that simple. What I noticed the other day was that if I clicked "restart" instead of dying and exiting or just quitting the game, then I would restart the exact same level [actually, I'm not 100% certain that nothing is still variable, but most relevant things are exactly the same].

So there are technically two ways to do this:
1. Somehow store the level as a whole, already generated. This is impossible, because there are infinitely many variations that might occur (it's never exactly the same thing twice). It's remotely possible that it is stored throughout each race so that you can restart it and it remembers all of the randomly generated values, but that seems like a waste of energy on the part of the programmer and too much memory to use.

Therefore, I think it's much more likely that it's option 2:
2. It is generated "randomly", but not truly randomly. Instead, I think every race begins with generating a random seed number (perhaps from the time of day, milliseconds, or whatever is easiest). Then this value is stored. And everything is generated from it.

So what I want to ask is the following: would that work?
Is it possible to store a single seed number (randomly generated itself) and then exactly replicate an otherwise completely random level? That seems really interesting to me.

Likewise, you could use this for a website-- randomly show several ads, several embedded blog posts, and a few images of the day. Every time you reload the page you get something new. But, if you happen to do something (use some special URL, store a cookie, whatever) you could store a single seed number that would then generate exactly the same thing.

In other words, but using a non-random, seeded random algorithm, you can actually store a huge amount of information in a single integer.

Another purpose could be the following: generate hundreds of thousands of levels randomly. Some are bad (too hard, even impossible to win, or just too boring and easy, or even have weird bugs in them), then manually filter through them to find the ones that are actually decent-- store all of those seed values into an array somewhere, then whenever starting the same you could pick one of those stored seed values randomly, thereby generating a "random" environment but also only using the good ones. So you wouldn't need to perfect the random generating algorithm, just check that all of the, say, 100 combinations you have are allowed.

Of course at the same time it would be almost impossible to predict or design a seed number to do what you want.


What do you think? Is this something that's established? I haven't thought about it before, but I find it very interesting.



[Note: in case anyone isn't familiar with the term [i]seed as I'm using it, I'll explain quickly: when a computer generates a "random" number, it doesn't actually do anything random. It takes some value, such as the time of day, then uses that to "seed" the random number process. For example, it might take the seed value, square it, apply some kind of distortion algorithm (I've used MD5 in the past), and then base decisions on that. So nothing is really random if you set the seed number the same each time. If you manually set it to, for example, "1" then you'll always have the same "random" results. If you automatically set it to something that changes like PHP's microtime() which gives decimal values after the time of day in seconds, that'll be a reliable way to probably have a different page each time you load it. But I'm wondering here if you could use this to your advantage to control what happens with your actually non-random algorithm.]

[james438]

Just a few passing thoughts, but if you wanted to use saved random numbers could you generate long list of randomly generated numbers and then save them and then move the pointer along that list as various levels are played. If you did this you would probably need to create a list of random numbers for each new player. That wouldn't be so bad if you did this in segments. This isn't all that good of an idea, but I am just musing.

I did come across seeding such as the following:


<?php
srand(3);
echo(rand(1, 10));
?>

I could not come up with an efficient way to move a pointer to a particular point in the list of numbers outside of running the third line in a predetermined number of loops to get to where you want, which is about as inefficient as you can get. I am wondering what the best way would be to manipulate the seed value in a semi-random way for each user and then store the pointer for the seed. Sadly, this problem brings us close to square one again.

Way back when I created a small game in qbasic when qbasic was new. In the game there were falling tiles from the ceiling of the first room. The tiles were set to fall from random positions on the ceiling, but no matter how many times I ran the game the tiles always fell in the same order. It was then that I first learned that random isn't as random as I thought.

[djr33]

I'm not really worried about how to track this. I'm just interested in whether the idea is coherent-- a single seed value that then is used in all random calculations (even perhaps modified for some such as with md5).

Way back when I created a small game in qbasic when qbasic was new. In the game there were falling tiles from the ceiling of the first room. The tiles were set to fall from random positions on the ceiling, but no matter how many times I ran the game the tiles always fell in the same order. It was then that I first learned that random isn't as random as I thought. Right. The seed value never changed. Therefore, in theory, if you had changed it as desired and then stored some of those seed values, you could choose which version to replay.

I think I might be missing something in how complicated this would be in terms of setting up a seed value for all random numbers (that is, they might all end up the same). But somehow, I'd imagine this could work.

Basically, the seed value acts as a sort of initial force upon the whole system that is the random settings. Then everything plays out, but you could easily recreate those events by using exactly the same input again.

[As for the rest of your post, I might have missed something, but I'm not sure I follow. Could you expand on that a bit?]


(In unrelated news, I have since determined that the game I was referring to doesn't do this, or at least not for all values. I'm only positive about one. That means it might just be that one in particular that was stored. But at least it gave me an interesting question to ask.)

[james438]

It is hard to explain, but I was musing out loud on how to create long lists of predetermined random numbers. pi is an example. If you use pi and then move the pointer along the number to generate new levels. Later when you stop all you have to do is save the pointer location say at the 27th decimal point or so and then start from there the next time the player starts again.

The problem with that is that across many users the start point will always be the same so you will need many numbers like pi. You could use seeded random numbers, but then how do you save where you left off? You could also just generate long lists of random numbers for each player. That would also allow the developer to save where the player was last at in a database. All of these methods would allow the game to recreate the level the player was on when he stopped playing the game.

I still might not be making myself clear though.

[djr33]

Ok, makes more sense.

I'm not interested in how these numbers are generated. Using pi, PHP's microtime(), or whatever is fine. That would all work. But then you would store that number and use it as the seed for everything else.

The purpose would be for users to overlap in what was randomly generated. That is, if you have a reason for them to have the same level.

So let's assume you generate a few random seed values like:
1234
294048
35903583
2934

Now, what that allows is that any of those can start a level with "random" values, but if you ever use them again, you'll get the same ones.

So you can create those random numbers however you'd like. But then in choosing to use one (as opposed to another) you're choosing a specific set of "random" outcomes based on it.


The next step would be to figure out how to store all of this, etc.

An important question I'm not sure about: Is a number like "1234" enough information to use as a random seed value? Would that be enough to get some variability in the different "random" parts of what is generated? Or would you instead need a much longer number (like you said, pi)?

One option would be to raise pi to a power. Then use whatever comes of that. Regardless, you could get enough numbers somehow. What I'm really trying to figure out is whether having a number (for now just assume we have exactly one seed value) would allow based on "randomly" generating everything in a level, for that level to be "randomly" generated in exactly the same way each time. If so, then all that's left to solve is how to create the seed values.

[Deadweight]

I'm not entirely sure which game you are playing but if it's a that contains distance and gets more difficult as you progress couldn't you do something like this:
have two different stages. Stage One and Stage Two. During stage one you is just the normal difficulty for a certain amount of distance. One you hit Stage Two then that Stage Two becomes Stage One and then a new Stage Two is generated (again for a certain distance). So it will generate the difficulty of the objects spawning etc...
I think that is what you are asking. If not let me know or if you dont understand what im trying to say.

[djr33]

It does change over distance and so forth. But that's not particularly relevant to this question.
What's interesting is that it's random each time (different positions of objects, different bonus things to find, different characters around), but that apparently you can restart that same level with all of those random settings retained.
So I'm just wondering if a single "seed value" (a number used to generate [pseudo]random numbers) would allow for that.

[Deadweight]

oh yeah prolly in a seed. Something like minecraft