next »

[William Broom]

Since it's pretty much certain that the next competition will be about Procedurally Generated Content, I thought I'd make a thread to discuss the technical aspects of such. I noticed several people said they wanted to see the competition go ahead, but couldn't participate themselves because they weren't good enough. I probably have much less experience than those people, but I still want to try 
So I'll start off by asking a question of my own, and if anyone else has questions they can post those too.


I figure the best way to do procedural content would be to have the player type in a name and then use that as the seed. That way they can play the same level over and over without having to remember a string of numbers. I thought up a method of doing this but I haven't tested it. Will it work, at least in theory?

1. Extract each character individually from the seed word.
2. Convert each character into its ASCI code. (At least in Game Maker, this seems to be the easiest way to convert letters into numbers).
3. Multiply all the ASCI codes together to make one big number.
4. Work out how many variables you need to generate the level/character/AI/whatever else you're generating procedurally. Each variable is based on digits of the number, so it should either range from 0-9, 00-99, and so on. If you want it to be a simple on/off switch, then you can make 0-4 = ON and 5-9 = OFF.
The game I have planned is quite simple and should only require 22 variables, but I might put that up to 30, so that if I need more later on, I don't have to make major changes to the code.
5. Check to see if your seed number has enough digits - in this case, 30.
6. If not, square the seed number and check again. Keep checking until you have 30 or more digits.
7. Once you have enough digits, break the number up again, into single digits or double digits depending on how precise your variables are.
8. Use the variables you've generated in the procedures to generate the content.

Like I said, I don't have much experience, so I need advice on whether this will work or not.

[mewse]

Well, I can't tell you about GameMaker, but the usual approach for this sort of scheme is to convert the user-entered string into a number (this is sometimes referred to as "hashing" the string).  And your method would work just fine.

And your proposed method would work, yes.  But there's a much easier way than that to do it. 

Basically, you just want to seed your random number generator using the number that you worked out above.  In C/C++, this is done using the 'srand()' function.  There will presumably be something similar in GameMaker and other software.  Anyhow, once you've seeded the random number generator, you can just use random numbers to set your "procedural" variables.

In C, it would look like this:

int value = CalculateHashOfUserEnteredString( userString );
srand( value );
int numberOfEnemies = rand();
int enemyMaxHealth = rand();
int enemySpeed = rand();


In the above code sample, if the user provided the same 'userString' value in two separate runs of the game, then you would get the same values for "numberOfEnemies", "enemyMaxHealth", and "enemySpeed" in those two runs, while different values of the userString would give different values for those variables.

Effectively, by seeding the random number generator off of a user string, random numbers automatically give you your procedural content. 


(Actually, I just did some research, and it looks like GameMaker doesn't allow you to seed its random number generator, so this approach may not work for GameMaker games, or may require a replacement random number generator.  Any GameMaker experts have experience with this?)

[William Broom]

Thanks for your help. Game Maker certainly does have a function to set the seed, I haven't tested it yet but it looks pretty easy to use.

[Farbs]

I tend to use procedural content generation in my games whenever it's easier to do something in code than it would be to do it by hand. In some cases stuff you'd usually hand build can be waaay easier to produce in a couple of lines of code. For example:

Level Design
Both Polychromatic Funk Monkey and Fishie Fishie made heavy use of procedural level building techniques. PCFM built its levels by seeding a big empty world with a few solid and funk tiles, then growing those into larger islands or blobs. FF used mathematical patterns for each of its levels, so it was far easier to hardcode each one than to build any kind of editor.

Character Animation
The character in PCFM is drawn simply as a series of rectangles, and uses different chunks of code to animate his facing direction, his eye direction, and his "bopping" animation. These all move smoothing and independently, whereas a data heavy approach would have required a large number of frames, and would have looked terrible as a I can't draw

Tile Dressing
In PCFM and some backgrounds for ROM CHECK FAIL I determine which images to use to display tiles at render time. This allowed me to create the pipes and bubbles in PCFM without hand editing anything, and then allowed the player to modify the tilemap during the game without breaking up the visuals. In RCF it simply allowed me to dress a basic tilemap in different ways (eg Pac Man's blue lines, Moon Patrol's ground/rock division).

I'm not sure if that helps anyone, but I figured someone might find it interesting.
Procedural content for the win!

[Paul Eres]

Game Maker 6 and below actually did not have a way to seed the random number generator, but Game Maker 7 did, due to numerous requests by people such as myself.

I wanted it mainly because many things in games are impossible or difficult without it.

One is creating "replays" in the way that RTS games like Starcraft allow you to save and watch a replay. They do that by saving the random number seed used for that session along with the player's keypresses. If you couldn't set the seed then the only other way to do it would be to record it as a video or don't use random numbers at all or something.

[Paul Eres]

Also, procedural content generation is a bit vague. For instance, I personally wouldn't count moving a character's eyes around through code (as Farbs mentioned) to be procedural content generation, but others might.

It can mean a lot more than just generating maps through code, even though traditionally that's what it's been associated with. You can generate pretty much anything through code, even story and dialogue (see: Storytron). It usually comes down to which way is easier and produces better results.

[Paul Eres]

For those interested in procedurally generated imagery, I found this today:

http://www.processing.org/

Example of it in action:

http://www.vimeo.com/935317/

[Melly]

You might wanna keep from triple-posting rinku. Just saying, it might bug some people.

[Paul Eres]

Hm? I don't see why, as long as each post adds something significant.

[Hideous]

Because there's an edit button.

[joshg]

Processing is definitely an excellent choice of language/IDE for doing procedural graphics.  The video you linked to was (probably) not rendered in real-time, but Processing is definitely used for real-time stuff as well.

[Paul Eres]

If I had just edited old posts, people who were watching this thread by email wouldn't have seen that the new content was posted.

And yes, Processing looks great, I'm probably going to try it out one of these days.

[mjau]

3. Multiply all the ASCI codes together to make one big number.

There's one big problem with that.  Since order doesn't matter for multiplication, any words with the same characters in a different order would come out with the same result.  Same goes for addition etc.  It'd be better to use a real hash function for hashing your string.  Here's a good/simple one for strings (from Wikipedia, also, Bob Jenkins has a website with lots of hash functions):

Code:

uint32_t jenkins_one_at_a_time_hash(unsigned char *key, size_t key_len)
{
    uint32_t hash = 0;
    size_t i;
 
    for (i = 0; i < key_len; i++) {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

(if you're not familiar with c, << is left-shift, >> is right-shift, ^= does a xor between the variable and the value and assigns the result)

Also, personally I'd use UTF-8 (or some sort of unicode) in stead of ASCII to support other languages than english in a consistent way

int value = CalculateHashOfUserEnteredString( userString );
srand( value );
int numberOfEnemies = rand();
int enemyMaxHealth = rand();
int enemySpeed = rand();

This also has a problem, but only if you're concerned about consistent results on multiple platforms.  Unfortunately different c libraries implement the random function in different ways, so while you'll get consistent results on one platform, you probably won't get the same results in Windows as in Linux or OS X with the same seed, for example.  Only way around that is to use some well-defined function in stead.. (should use existing code or at least existing algorithm though, it's hard to get random right)

[mewse]

All your comments are correct, mjau. 

I was intentionally making ease-of-implementation trade offs, to keep from intimidating folks who haven't done much serious coding before.

I didn't want to discourage new or early coders by insisting that people use real hash functions or implement the Mersenne Twister or anything.  Because honestly, these things really aren't essential for what we're doing here;  Those advanced algorithms are about a thousand times the work for only a 5% gain.  Yeah, if you're comfortable doing that sort of thing then they're worth doing.  But if not, you'll still get along just fine without them.


All you have to do is to seed the random number generator, and then use the random numbers as your data.  It's really just that simple.  (And I'm relieved to hear that GameMaker now supports seeding the RNG!  I must have been reading outdated forum posts when my research suggested that it didn't)

[dustin]

Those advanced algorithms are about a thousand times the work for only a 5% gain.

Well if your using game maker and you would have to code it in strange game maker language yourself (i don't actually know how strange it is don't hurt me) then I agree with you.  If you are coding in java or c/c++ or some other common language I would say it's hardly any more work to just use a library hashing function and it will increase your effectiveness.  But once again, yeah I would have no problem playing a game with a bad hashing function if the person didn't feel they could handle anything more complicated.