Jump to content

  • Log In with Google      Sign In   
  • Create Account

Reversing a procedural generation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
31 replies to this topic

#1 Hawkblood   Members   -  Reputation: 723

Like
0Likes
Like

Posted 06 March 2014 - 02:24 PM

Procedurally generated data has a random seed and random values generated by the process. Here is an example of what I mean:

You have a row of windows you want to either be broken or unbroken. You set you seed and loop through the "windows" randomly assigning "broken" or "unbroken" to each according to the output of the random number generator.

This is simple and straight forward......

 

What if I wanted to do that in reverse? If I started with all the windows "unbroken" and I throw rocks randomly and broke a few of them. I would like to reverse the process until I get THE random seed that would result in generating the windows into that state.

 

I'm sure it CAN be done, but how?

 

This process could be very useful in games that have a huge amount of "object states". Like a planet with mineral deposits. If the player collects a certain amount of them, it would be silly for the player to be able to come back to the planet and get those deposits again. And saving the state of each mineral deposit on every planet in every solar system would be crazy!



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13309

Like
7Likes
Like

Posted 06 March 2014 - 02:40 PM

I don't see what your last paragraph has to do with the rest of the post. If the player collects a certain amount of mineral deposits, you better write that down somewhere so the next time you generate this planet you can remove the appropriate amount of mineral resources. The information of whatever the player has done to the environment can't be magically folded into a new seed for the PRNG, in particular because the seed is probably not long enough to encode all the possible things the player might have done to the planet.



#3 osmanb   Crossbones+   -  Reputation: 1569

Like
6Likes
Like

Posted 06 March 2014 - 04:48 PM

To put it another way: If my building has N windows, then I need N bits of information to store whether or not each one is broken. If I have a 32 bit random seed, I can generate 2^32 unique sequences. If I have 33 windows on my building, it's impossible to generate every possible combination (there are 2^33).



#4 Hawkblood   Members   -  Reputation: 723

Like
0Likes
Like

Posted 06 March 2014 - 04:54 PM

If I have a random seed of 12345 and with the process, the windows generate:

1,0,1,1,0,0,0,0

where 1=="broken" and 0=="unbroken"

 

Then every time I go to generate the windows with seed 12345 it will look exactly the same.

 

If I break a window:

1,0,1,1,0,1,0,0 then the seed 12345 won't generate this result.

 

There IS some seed that will generate 1,0,1,1,0,1,0,0..... I want to go from the result to the seed. It's not magic, it's logic I am not fully aware of.



#5 ProtectedMode   Members   -  Reputation: 1212

Like
5Likes
Like

Posted 06 March 2014 - 05:32 PM

It could probably be done. There are only a few problems wink.png :

  1. The seed has to be long enough to contain all the possible combinations, and that could be pretty long depending on the situation, as said previously.
  2. The code generating the environment needs to be known. This won't be a problem if you program it yourself for your game.
  3. You would probably need to do a brute-force "attack" to get the seed that would be used to generate that environment. This won't be a problem for small things, but for large chunks of data, this will take a lot of time.

The seed, as stated before, needs to be long enough to hold the data. Technically, you could make it as space-efficient as possible. But that few bytes of data really don't matter. It would be nice to have them, but having a readable format which is fast to read and write (see point three) is more important.



#6 SerialKicked   Members   -  Reputation: 576

Like
9Likes
Like

Posted 06 March 2014 - 05:34 PM

I'm new here but I know my way around procedural generation.

 

Going from a seed to a world is a one way operation only, as explained osmanb. Your example with windows is flawed, because in it, your seed is larger than all the possible states of the windows. If you're generating a whole world / universe / whatever out of a 32 bit (or 64 / 128 .. doesn't matter) seed, things won't work in reverse.

 

The point you seem to be missing is that a seed, whatever clever procedural worldgen you've written doesn't and can't store all possible states of your world. Otherwise the seed would need to be as big as the sum of all the possible combinations/states of this world (as it is in your example). In other words, it would be a savegame, not a seed.

 

The first poster told you the correct way to do things and that's also why savegames of procedurally generated games (at least those in which the terrain can be altered) only goes bigger as time goes on. They regenerate the fresh world out of the seed, and then add the changes made by the player. And it's usually not as time consuming or memory wasting as you seem to think.


Edited by SerialKicked, 06 March 2014 - 05:42 PM.


#7 Servant of the Lord   Crossbones+   -  Reputation: 19507

Like
8Likes
Like

Posted 06 March 2014 - 06:00 PM

This process could be very useful in games that have a huge amount of "object states". Like a planet with mineral deposits. If the player collects a certain amount of them, it would be silly for the player to be able to come back to the planet and get those deposits again. And saving the state of each mineral deposit on every planet in every solar system would be crazy!

 

What if there are twenty thousand mineral deposits on a single planet?


[save seed]
[save 1 bit for each deposit]
 
Total size: 20,000 bits = 2.5kb - less than a single 32x32 bitmap.

 
But what if you need more details, what if you need alot more information, for an infinite number of planets?
Sadly, there is no magic compression algorithm. sad.png Videogames have to work with their limitations.
 
Procedural generation works awesome for generation, but any changes have to be saved using conventional means (including normal compression methods) and re-applied to the re-generated result.


It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#8 Hawkblood   Members   -  Reputation: 723

Like
-2Likes
Like

Posted 06 March 2014 - 06:25 PM

This is a SUPER SIMPLE random number generator:

int RNSeed=12345;
int randomnum(void){
	RNSeed=abs(RNSeed*8786545643)%987654321;
	return RNSeed;
}

With this initial seed, the first time it's called it results in 770159010, and the second time it results in 808599291.

This will happen EVERY time I start with 12345. The problem with reversing the calculation is the modulus of 987654321. Any seed value greater than that number will be some value that can't be found and therefore the previous seed us unknown. The solution would involve a random number generator that can be reversed-- I don't know how to make that (or if it can be made at all).

 

All of you are either think I don't know how random generators work or you are missing my point entirely.



#9 JTippetts   Moderators   -  Reputation: 8490

Like
13Likes
Like

Posted 06 March 2014 - 06:56 PM

This is a SUPER SIMPLE random number generator:

int RNSeed=12345;
int randomnum(void){
	RNSeed=abs(RNSeed*8786545643)%987654321;
	return RNSeed;
}

With this initial seed, the first time it's called it results in 770159010, and the second time it results in 808599291.
This will happen EVERY time I start with 12345. The problem with reversing the calculation is the modulus of 987654321. Any seed value greater than that number will be some value that can't be found and therefore the previous seed us unknown. The solution would involve a random number generator that can be reversed-- I don't know how to make that (or if it can be made at all).
 
All of you are either think I don't know how random generators work or you are missing my point entirely.


They're trying to explain to you that what you ask is impossible for anything non-trivial. Find another way.

Edit: to further clarify, pseudo-random generators CAN be reverse engineered. That is part of what people do when attempting to crack cryptographic schemes. If you can reverse-engineer the generator you can crack the encryption. It's a very difficult task. Some classes of PRNGs are much easier than others. And the greater the period, the more difficult it can be. What you are asking for is to reverse-engineer a PRNG of such an enormous period (for any non-trivial game state) that you could literally burn billions of hours of computing time trying to reverse it.

I understand what you are trying to achieve. If you COULD somehow magically come up with the seed required to represent any given game state, then you can reduce the workload of saving the world. However, the act of coming up with that seed would be such a Herculean effort of engineering and time, that it's just not feasible. You CERTAINLY won't be saving yourself any time; quite the opposite, actually.

Edited by JTippetts, 06 March 2014 - 07:03 PM.


#10 Mona2000   Members   -  Reputation: 596

Like
4Likes
Like

Posted 06 March 2014 - 07:22 PM

You have 2 windows and a 1 bit seed. 0 is both windows broken, 1 is both windows intact. You want a seed that leads to only 1 broken window... there isn't one. Now think larger scale and you'll understand why you can't do what you want to do.



#11 Álvaro   Crossbones+   -  Reputation: 13309

Like
3Likes
Like

Posted 06 March 2014 - 07:26 PM

You can design a PRNG that is easily reversible, by using just about any private-key cryptographic method (any block cipher would do).

Or you can just perform a sequence of reversible operations on sets of 64 bits, like
* multiply by an odd constant
* add a constant
* XOR with a constant
* rotate the bits (e.g., `seed = (seed << 24) ^ (seed >> 40);')

A long enough sequence of these operations will hash the seed into being completely unrecognizable, and that can be used as a PRNG. The inverses of these operations are relatively straight-forward, and that allows you to reverse the process and compute the seed from a result.

However, I think we all understood your situation perfectly well and you should re-read what we posted.

#12 Hawkblood   Members   -  Reputation: 723

Like
0Likes
Like

Posted 06 March 2014 - 08:12 PM


You can design a PRNG that is easily reversible, by using just about any private-key cryptographic method (any block cipher would do).

Now that's positive thinking!

 

 

I thank you all for responding. After serious consideration, I think you may be right about one thing: the random number generator wouldn't have calculations that would repeat numbers. This means even if I had some linear values, I couldn't have all 0's or all 1's or any number. Otherwise it wouldn't be a PRNG.... The game state should have the ability to have any valid state for all parameters.

 

+1 to all......



#13 Bacterius   Crossbones+   -  Reputation: 8828

Like
14Likes
Like

Posted 06 March 2014 - 09:15 PM

The fallacy is in believing that every possible world state has a corresponding 32-bit seed. Those seeds only produce an infinitesimal subset of all possible world states, and so "almost all" world states do not correspond to any small seed. If you study one-way functions you will see that the reason you can go "one way" from a small seed to a huge interesting world is that the procedural algorithm has inherent structure which makes it easy to encode those particular worlds in a small seed (because that's how you defined it, e.g. place a planet here, scatter some rocks there) but doing the opposite is not something we know how to do efficiently, because once you change the world so that it no longer falls in that set of "simple" worlds, the structure is broken and you need a new procedural algorithm. Needless to say, this kind of analysis is impossible to do because of the amount of variables involved in describing an average world.

 

And either way, you would not save anything, by a simple information-theoretic argument: you might save a little for some worlds, and you might lose a little for others, but on average, the seed would have to contain as much information as the entire world state, and would therefore be more or less the same size as a typical save file (but you get encoding/decoding time as well). It is a fun idea, but unfortunately it doesn't work.

 

As an example, suppose my "world" is a single integer. Suppose I have a seed from 0 to 31, that my world states range from "1" to "around 4 billion", and I define my procedural algorithm as P : x -> 2^x. Then I can reach a bunch of interesting worlds, like world "1", "4", "32768", "1024", etc... but ultimately I can only reach 32 of them through my procedural algorithm. Now suppose I pick world "1024", but then my character moves a rock, and the world state is changed to "1025". Oops! There is no seed that works to generate this world.

 

So I can try a couple things: I could say that you need to subtract 1 before saving the seed, and then adding back 1 again when loading the world. So now the seed for this world is (10, 1), such that 1025 - 1 = 2^10. Looks good, until you realise that on average that offset won't be 1 but might be a large number with no specific properties, so now your seed has been bumped up to around 37 bits (instead of 5 bits like it was before, from 0 to 31) which is actually larger than necessary since 32 bits are sufficient to encode all possible worlds.

 

Or I could just say that, hey, 1025 is not a power of two, but there's still an x such that 2^x = 1025, which is approximately 10.0014. So let's store that instead, it's just a number. Great! But then you realise that you need space to store those decimal digits, and since the states range from 1 to 4 billion approximately, it turns out you'll need approximately 11 digits of precision to represent everything (the exact amount varying somewhat randomly depending on the state), which comes out to a 32-bit seed at least, and you're back to square one.

 

At this point it's probably obvious - there is no encoding that will work like you want it to, and in practice the best approach is to store the initial seed to get most of the world up and then only save player actions in the traditional way (and occasionally wiping player actions when it's been too long or he's gone too far away from that point such that going back would take long enough so that plants regrow/rock formations are created again/etc...).


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#14 Stainless   Members   -  Reputation: 934

Like
1Likes
Like

Posted 07 March 2014 - 06:13 AM

How about this.

 

Generate random locations for all mineral deposits every time you visit a planet.

 

When a player visits a planet, typically they will land at a location and collect all the minerals within range of their ship.

 

So work out a region that has been mined out. Store the region in the save game.

 

Next time you come to the planet, generate all the minerals again and compare each one to the mined region.

 

When you leave the planet, rationalise the region list. I.E. if two regions are contiguous, merge them into a single region.

 

Eventually you will end up with a single region, the whole planet.

 

The save game storage would not be a major problem then, and a simple point / region intersection test will not slow down the game very much.



#15 TheComet   Members   -  Reputation: 1568

Like
1Likes
Like

Posted 07 March 2014 - 08:41 AM

Yet another example is MineCraft. The world is generated by a 32-bit seed, yet it is infinitely large (theoretically). Obviously, you can't reverse that back into a seed, as explained above.

 

I would like to point out that early versions of MineCraft used to save the differences between the original world generated by the seed and the modified world edited by the player. Alas, the longer the world existed and the more you mined, the larger the save-files became and the longer it took to apply the differences whenever you loaded the world.

 

I recommend saving absolute states and not relative states. You can optimize it in many ways, one way is only saving the sub-sections that are different than what was generated by the seed.


YOUR_OPINION >/dev/null


#16 Hawkblood   Members   -  Reputation: 723

Like
1Likes
Like

Posted 07 March 2014 - 11:12 AM


At this point it's probably obvious - there is no encoding that will work like you want it to

That's correct.....

 

To everyone: I've moved away from the idea of using a seed as a save state.

 

Perhaps I should start a new post on saving the state of a galactic sized game.....

Any ideas on minimizing the save game size for really huge games?



#17 JTippetts   Moderators   -  Reputation: 8490

Like
4Likes
Like

Posted 07 March 2014 - 11:34 AM

If a certain amount of time has passed since anyone visited a given planet/system/galaxy, you can probably prune the save data for it from the save file. Hand-wave it away as enough time has passed that the things that were done have been erased by natural processes. This pruning can be done whenever the save file is accessed to keep it lean. 

 

Compress as much as you can. If something is either there or not there, figure out some way of storing it as a single bit if possible, rather than as, say, a bool

 

Use a binary format rather than a text-based one. Text formats are for human-readable content and can vastly inflate file size.

 

If you are doing voxel world generation, look into storage schemes for large amounts of array data, such as run-length encoding schemes used for TGA files. Research lossless image compression to get ideas for how you can compress your array data.



#18 Hawkblood   Members   -  Reputation: 723

Like
0Likes
Like

Posted 07 March 2014 - 02:20 PM

That sounds interesting. How about storing save data as data for an image like .png? The data would look like a picture (noise), but it would utilize the image's compression..... Don't know if that's what you were getting to, but it made me think of it anyway.

 

Some values will be actual bites and some will be stored/read as bites but actually have 8 yes/no values..... Sounds like a good way to encrypt it too-- don't know if anyone is using this method.



#19 phil_t   Crossbones+   -  Reputation: 3913

Like
0Likes
Like

Posted 07 March 2014 - 02:43 PM


How about storing save data as data for an image like .png? The data would look like a picture (noise), but it would utilize the image's compression..... Don't know if that's what you were getting to, but it made me think of it anyway.

 

Yeah, that might make sense if you were using a library that had png support and for some reason weren't able to use some other 3rd party compression library.

 

I don't know the details of png compression, but I wouldn't be surprised if it made some assumptions about what a typical image looks like (e.g. smooth gradients from pixel to pixel, etc...). Basically, it assumes the data is an image, and will probably compress that better than arbitrary data.

 

The point being, if you know something about your data, you can probably choose a compression scheme that will work better with it.



#20 Hawkblood   Members   -  Reputation: 723

Like
0Likes
Like

Posted 07 March 2014 - 07:45 PM

I don't know a lot about data compression. I've never written anything that used it. Image files are compressed on the disk (except .bmp). I was simply implying I could use something that already had support through DirectX.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS