Wednesday, February 6, 2008

The World Model

I've been thinking a lot about my implementation of the world, and how everything will fit together. I haven't decided on it yet, so I figured I would take the chance to go through my thought process "out loud" so anyone can benefit from it. Hopefully a coherent post will come through, since none of what I'm about to say is premeditated.

Before I begin I'll discuss some terminology. For the sake of this post the world is the entire game, and internally this is a collection of maps. A map is a single screen within the game. A dungeon is any vertical series of maps, this would include a tower since it's just an inverted dungeon.

I'll start by describing my goal for the system. I decided early on that each map in the game will be randomly generated. Once a map is generated it doesn't get recreated. I want to describe my world in such a way that it can be created randomly but retain a general look. So how do I go about doing that?

Since my maps will be both outdoor and indoor this lends itself to some interesting issues, the first of which is interconnectivity. Stated more clearly, I need to be able to determine that each of my maps are connected to any adjacent maps. Any given map can have connections from the north, south, east, west, up, and down. This lends itself well to a three dimensional coordinate system. Maps connected vertically will only need to be connected from a minimum of one point, but they could be connected by more. Maps connected horizontally can be connected by any number of points, and for most outdoor maps these connections are on each point on the outside of the grid.

Each map can be described in a text file by a list of grid workers used to create it, and the parameters for those grid workers. The only other thing the maps need to know is what maps are adjacent to it. They need this information for several reasons. Firstly, they need to know what connections to create. Secondly, they need to know what the adjacent maps look like, because we want to preserve the look across boundaries. For instance, if we have a forest map that borders a desert we don't want a harsh cut from forest to desert once the character travels to the next map. We'll want to organically blend these together so it looks natural.

This can be handled in a few different ways. I can generate the entire world at once, but that would take a long time and be a lot of useless processing up front. Also, I can look at the adjacent maps and use their creation algorithms to bleed the two maps together. This is a lot more difficult than it sounds, but probably the best solution. The bleed algorithms will have to be pretty intelligent, or a wide view of the world will just end up looking like a bunch of rectangles loosely connected. I'll probably need something in addition to bleeding, like the ability to set percentages on a given map. For instance, 25% of the north and west will be desert, while the remainder will be forest. I feel this is a problem I'll be fighting with for awhile.

This system will allow me to create a relatively complex world that is still randomly generated. Each map on subsequent plays will look slightly different. I'm worried that this will be stale, and if that lends itself to be true I'll have to think of a different system. The only other thing I can think of is instead of defining individual maps I would define regions. A forest could be anywhere from 2 to 5 maps large. There is a dungeon somewhere within a 5 map radius of this point. Stuff like that. Only time will tell.

I think I've said all I can say on this topic for now (or want to). As always, any comments are welcome!


Enne Walker said...

I think you're right that doing the full-blown world generation up front is more expensive than necessary. However, it sounds having a cohesive world is pretty important for you.

Why not generate the world up front, but do it in a low resolution way that doesn't take as much time or processing? I'm picturing that you could use a grid, where each grid is a screen in the world. Then your world generator could make better transitions between something like forest and desert or even enforce that you have a screen of grassland between them.

It just seems more straightforward to write another generator than it does to try to tweak percentages.

Attrition said...

Following what Enne said, this post on Jice's page about the same topic (interpolating a detailed map from a generated mini-map -- but without the bleeding map style you mention)

ilostmyjob said...

I am not a programmer, or a mathematician, or anything that would be useful to this discussion. However, it seems like an iterative process during worldgen would be best.

Start with a _very_ simplified map, maybe an 16x16 grid or the like. Generate the terrain types for each square from a limited list of meta-types (Mountainous, Ocean, Desert, Swamp, Forest, Grassland, Jungle, etc) Run some sort of "cleanup" algorithm that swaps the values of adjacent squares or the like to try to get most of your land in one area and your water in the other. Then break each square in your 16x16 grid into its own 16x16 (or whatever) and start an iterative algorithm that uses a much larger list of terrain types and use that to blend between the various meta-types (either assuming that the central square is of the terrain meta-type, or better yet, that a random square in the smaller grid is).

I wish I could refer you to the appropriate resources for this - but again, I am not any of several things that would be useful here, I've just played a lot of games.