5 replies to this topic

[Reefpirate]

I've been trying to set up a procedural generation engine for the world in my WIP game, and I seem to have hit a bit of a mental road block. Everything was going fine until I came to the point where I realized I would like to tile my rooms nicely. Let me do a quick explanation of where I am and how I got there:

The world map for my game is a 2 dimensional grid, and I did some fractal/cellular automata type stuff to assign each grid cell a particular value that represents what type of cell it is. Each world cell can be water, land, slums, mid-slums, commercial district, docks, etc.

Now, each world cell is generated in a new room as the player enters the world map cell with his PC. Each world cell room, or 'world room' as I call them, is a 12x12 grid made up of cells that store indexes to other grids (i call them sub-floors) that store various objects and features in a particular order.

So we have:
world map = 32x32 grid of world rooms that can be water, land, slums, commercial districts, etc.
world room = 12x12 grid of indexes to grids associated with that world room type (water, land, city, etc)
sub-floor = 12x12 grid of usually walls, trash cans, treasure chests, etc. Each grid cell represents 32x32 pixels.

So what this lets me do is create a random world map, and then each different type of world map tile can be randomly generated in 12x12x32 chunks. So when my player walks into a 'slum' world map cell that is adjacent to water on its north side, I can put coastal sub-floors across the north side, and then choose randomly from the list of pre-made slum 'sub-floors' and place them in the world room grid and bingo, I get a randomly generated world room.

Now, the problem arises when I want to tile these rooms. I quickly realized that tiles cannot be quickly and easily stored in a grid like objects can. For each tile I want to lay down, I need about 9 different parameters that can be different in each case. So I have come up with a few different solutions and I have absolutely no idea which one is best:

1. Create a 'tile object' for each sub-floor, and create it in the top left corner of the sub-floor each time I place a sub-floor. This object draws the appropriate tiles in the appropriate places for that sub-floor in reference to the top-left corner.
2. Make a generic set of tiles for each world-room type, and just randomly select a tile to cover the whole sub-floor depending on which type of world room we're drawing at the moment. This to me sounds ugly and would not allow any customization for say a shack with a different floor in a particular sub-floor.
3. Scrap my sub-floor grid system altogether, and just make each sub-floor into a separate object. I will then have a list of 100+ objects that handle the drawing for each individual sub-floor, including objects and tiles. So each world-room will consist of a 12x12 grid of objects, which then place a bunch of other objects and tiles. This to me sounds like the most flexible approach, but then I have a gigantic list of objects and I'm worried if this will be inefficient or unwieldy in the resource browser trying to keep everything straight.

I hope somebody can understand any or all of this! Any other suggestions? I feel like I'm over-complicating this whole design somehow... I need some halp!

Thanks

[AndrewB]

I'd say go for the first approach. Mainly because it'd be simple to implement based on what you have already and I can't see why it wouldn't be customizable.

The last approach seems like an extreme option, but I've done things like that before.

[Rani_sputnik]

If you are doing random generation, play with the random_set_seed(seed) function. This is how I'd do it. I'm not sure if you're aware or not but each time you run game maker its sets the seed to a random value. The seed defines what numbers are gonna pop out of the random() function. If you used random_set_seed then generated a map, the map would come out the same every time.

"Cool story bro, how can this be applied?" Well...

Start by generating your world map as you said, assigning each grid cell an 'environment' value but also assign each a cell a 'seed' value using the randomize() function and random_get_seed()

//psuedo code

world_map  = ds_grid_create(32,32);
world_seed = ds_grid_create(32,32);

for (i=0; i<32; i+=1) for (j=0; j<32; j+=1)
{
  ds_grid_set(world_map,i,j, whatever);
  
  // randomize the current seed value
  randomize();
  // apply the seed value to this grid cell
  ds_grid_set(world_seed,i,j, random_get_seed());
}

// Do all the other stuff to make your map

Then when the player moves to a new world room you can generate it on the fly. Now this will obviously increase loading time for each area but it will save you a huge big hastle with data storage, and random generation can be done pretty quick if you just start by focussing on the areas immediately around the player then work slowly outwards.

random_set_seed(ds_grid_get(world_seed, current_worldRoomX, current_worldRoomY);

// generate the room

Hope this helps
Rani

EDIT: Ooooooh forgot something big. If your character is able to make changes to a scene, for example he can move a box around or something, make sure you have a list for each room and store all the changes in it. Theres two ways to do this, scripts (ie. You have a script move_box(from,to)) or with strings ("box.x = 14") then when you generate the room, flip through the list and simply call execute_string. Sound snazzy? it is

PS: This method reduces saved games file-size too! (usually)

Edited by Rani_sputnik, 15 May 2011 - 05:55 AM.

[Reefpirate]

@AndrewB: Thanks dude! I originally wanted to do the tiles-only objects, but I've now gone ahead and just made the sub-floors into objects. This opened up a whole new avenue of thought for me. Instead of a sub-floor being just a static 12x12 grid of objects, I can now put little scripts and random elements into each sub-floor upon creation. So now I can have a 'random junk' sub-floor that will randomly place certain objects and each one will be a bit different.

Also, I can do sub-sub-floors... or sub-sub-sub-floors! Ie. I can write a 'small-shack' objects that lays down the walls and tiles for a small shack, and then call this object from within a sub-floor object to have different placements for the shacks, etc.

@Rani: It sounds like you were involved in that other procedural generation topic in this forum I comprehend the saving of the seeds to recreate random levels without having to store them in memory, and that truly is an ingenious idea! However, I think with my design it would be a little cumbersome just because almost all of my objects can be destroyed. Also, the NPCs and enemies, etc. have to be persistent as well.

So when a player enters a world room where he hasn't been before, I have Game Maker create a new blank room and then do the procedural generation. I then set the room to persistent, and instead of saving the seed like you do in your example, I just save the room ID and return to it if the player returns. I was a bit worried about several rooms (hundreds possibly) being stored in memory, but it turns out that they don't take a whole lot of memory. My game hasn't gone over approx 55 MB of RAM usage so far. And, correct me if I'm wrong, but GM's built in save/load system works quite well with persistent rooms, doesn't it?

Feel free to let me know if I'm way off in my assumptions some how...

[Rani_sputnik]

Fair enough Good to see you are putting a good deal of thought in. (Cool game in ur sig btw) I never knew you could make rooms persistent, there you go I learnt something new today. In terms of saving and loading... er I wouldn't use them, or if you are gonna use them, test them thoroughly before you do because there is a lot of stuff that they don't save as far as I know, data structures especially (though they're the obvious example cause they're in the manual as not being savable)

I think it's just because I'm a control freak but I like knowing exactly what is going into a save file, and if you don't it can be really hard to find bugs later on. I guess I'm just one of those 'bad experience' customers but yeah, that's my advice.

Rani

[Reefpirate]

@Rani:

Thanks for the input! I might send you a PM or two about saving games like this, if that's alright with you. I actually haven't put much thought into the saves yet, seeing as I'm already drowning in other issues to solve at the moment. I think I'm in a little over my head with this project (the game in my sig is what I started this topic for too), but I'm far from giving up! But if you could share some tips on saving games, I think that could also help me out with a 'sub-floor' editor, which is something I'd really like to implement.

To get back on topic though, I've found that this style of procedural generation is really quite flexible. I originally thought it was a 'hack' way of doing it, a cheap way to get out of doing some 'real' procedural generation algorithms. But it turns out that it's quite complex and has quite a bit of potential.

I originally got the idea from an article I read about X-COM, and how they did their random levels. It's the same sort of idea here, but with quite a few more layers of complexity. You take a basic environment type, and then you shuffle up the random pieces of terrain you have made for that environment type, and then you stick em all together when you need to make a level. One thing I would sure like to know, however, is how they made their cities, or Terror maps work. They had streets and stuff, and rather than tackling how to make realistic streets at run-time, I've just skipped over them altogether and figured my game takes place in a 'post-street' world