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:

[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.

[William Broom]

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)

I'm glad to hear that because I haven't a clue what mjau is talking about. As far as I'm concerned, Xor is the king of Xor Castle and Mersenne Twister is his Overdrive attack.

[Zaphos]

I'm glad to hear that because I haven't a clue what mjau is talking about. As far as I'm concerned, Xor is the king of Xor Castle and Mersenne Twister is his Overdrive attack.

XOR just means 'exclusive or'.

[mjau]

Yeah, don't worry about it too much.  If anyone understood my post though, good for you .  (That hashing code I quoted has been released as public domain by its author btw, so it's free for anyone to use.)

Just for the hell of it though, xor is exclusive or.  It works on the individual bits of a number.  Bits are how numbers are represented internally in the computer.  They're "binary digits", each one can have a value of just 0 or 1 in stead of the usual ten choices of 0-9 we have in the number system we use normally, which is called the decimal system.  When you put several bits together you can make larger numbers called binary numbers with just the 0 and 1s, for example 101010 in binary is the same as 42 in decimal.  The decimal system is base 10, since it has ten digits:  To get the value of 42, you take the first digit, 4, and multiply it by 10, and then you add 2, getting, well, 42.  The binary system is base 2 (only two possible values for each bit), so you multiply by twos in stead.  10 is 1 * 2 + 0 = 2, 101010 is 1 * (2*2*2*2*2) + 0 * (2*2*2*2) + 1 * (2*2*2) + 0 * (2*2) + 1 * 2 + 0, or 1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 0 = 42.  You can do the same thing to convert from other bases.

So anyway, xor works on the bits of a number individually.  If it gets two equal bits as input, the resulting bit is 0, and if it gets two different bits as input, the resulting bit is 1.  For example, 101010 xor 000111 = 101101.  Bit shift operations also work on bits, but not individually.  They shift the bits up and down.  101010 << 1 (shift up 1 bit) is 1010100 (84, or 42*2), 101010 >> 1 is 10101 (21, or 42/2).

[Melly]

I just found out about what rinku said with GM7 allowing you to seed the random number generator.

This should make this compo much more manageable. :D

[Wilson Saunders]

Along the lines of using random numbers to make game content: I have made a game called "Ransack the Xmass Ninja" that randomly generates game maps. The download is here: http://www.monkeydev.com/Ransack/index.htm

The algorithm to generate the map works like this:
1) A map size is specified by the user which makes a 2 dimensional integer array populated with all 0's, except for the border which is populated with all 2's. (fyi 0's indicate traversable space, 1's indicate traversable space with a different ground texture in this case water, and 2's indicate non traversable wall).
2) The computer then picks a random x and a y integer that lies within the width and height of the array.
3) The computer also picks a segment file from the maps folder. This Segment file contains a 10x10 chunk of map that looks naturally formed, but was really hard coded by me ahead of time.
4) The computer inserts the chunk of map into the main map at the random x and y coordinates chosen. The insert is done like this:
4a) The 10x10 map segment is iterated by an x and a y iterator.
4b) Each value from the file is compared to the map array at point (xrand+xiter, yrand+yiter).
4c) If the value of the file at (xiter,iter) is greater than the map value at(xrand+xiter, yrand+yiter), the map value is changed. Otherwise the map value stays the same. In simpler terms if there is no wall we make one, but we do not remove existing walls.
5) Steps 2-4 are repeated until the map is done. The number of times repeated will depend on how big the map is. I advise you to use trial and error on specific map sizes. Just change the number of iterations until it looks right.
6) Place the level entrance and exit randomly in the map.
6a) select a random point for the level entrance
6b) if that point lies inside a wall (map array value == 2) pick a new point.
6c) select a random point for a the level exit
6d) it that point lies inside a wall or is too close to the level entrance pick a new point.
7) We must now validate the map to make sure the user is not dead ended from the level exit.
7a) Make a temporary boolean array the size of the integer map array.
7b) Set all values of the array to false.
7c) Use the recursive flood fill algorithm to find out which map points can be reached.
7ca(sorry I don't know how else to properly list this step)) start the recursive function at the map entrance.
7cb) Set the boolean array value at the current position to true to indicate we can reach this point from the start location.
7cc) If the point to the left of the current position (x-1,y) is not a wall and not already visited (the boolean array of that location shows false), call the recursive function at step 7cb only using (x-1,y) as the current position.
7cd) do the same check and call of the recursive function for positions (x+1,y) (x,y-1), and (x,y+1).
7d) When step 7c runs out of places to check the boolean array will represent all places in the map the user can legitimately reach.
7e) If the percentage of reachable space is less than 1/3 the total map space we have generated an un interesting map and should probably start all over from step 2. Don't worry the computer doesn't mind repetitive tasks.
7f) If the exit point is not within reachable space you will have to relocate it, or generate a new map.

There you go, pseudo code for generating random maze like dungeons. In all honesty Diablo inspired me to make this. I know my random generator does not hold a candle to theirs, but I like to think we were working off the same principles. If you want to see my poorly commented source code look here:
http://xmashack.bafsoft.com/2006/downloads
for Ransack by Wilson Saunders.