• entries
    16
  • comments
    19
  • views
    16818

Planning: Map Generation

Sign in to follow this  
omnomnom

1071 views

To recap: you start in the south of the game world and the objective is to reach a location in the far North. To get there you must pass through unique zones with different challenges: a desert zone, a dense forest zone, an icy mountains zone, a swamp zone, etc. Each zone is harder than the last - both in terms of the monsters in it and the environmental dangers. Here's a rough diagram of the world map and the different zones that must be crossed:

mapzv.png

The zones themselves and the order they occur in the map will be fixed in every replay of the game, but the contents of each zone - the placement or rivers, monsters, trees, etc will be different each time to increase re-playability.

The North/South dimension of the map is figured out, but the East/West options are open:

  • Thin map. The player is prevented from traveling very far east or west. This will seem somewhat unrealistic but will increase the challenge. The thin map limits the paths a player can take North and will force the player to sometimes *have* to pass that difficult monster/obstacle.
  • Wide map. Width of map still limited but the player has more choice of paths to take North. This means the player can avoid tough challenges, retreat and take another route North. A wider map also increases the explorable content of a zone.
  • Infinitely Wide Map. The player can travel infinitely east or west. Map generation would have to be on-the-fly. No "unrealistic" physical barriers.
  • Looping Map. If the player travels far to the East they eventually come back to where they started. Advantages: No physical barrier to east and west is required and the map can be pre-generated. The big disadvantage here is that a looping map is harder to implement and lots of edge case (literally) testing must be done to avoid catastrophic bugs.

    I'll probably avoid the exotic "infinite" and "looping" solutions and just make a limited width map of configurable width. I can always change this later right? Lets see what the gameplay is like before deciding this.

    Plains Zone

    Each zone has very different content. The desert zone for example won't have rivers, while the forest zone will have occasional rivers and a lot of trees. The lake zone will have loads and loads and loads of water and perhaps a few islands. It makes sense for there to be a separate generator for each zone, so I have decided to focus on the generator for the plains zone to begin with.

    What is in the plains zone? The plains zone is where the player starts. It is meant to be the easiest zone. Here's an image depicting my initial idea of what plains zone will look like:

    map2z.png

    • Lots of grass with clusters of trees.
    • East/West rivers with occasional bridges or fjords to cross them.
    • Small lakes/ponds.
    • Large rock outcrops containing caves.
    • Villages or huts (not sure if they will be inhabited).
    • In this zone there would be a lot of food/water available and other resources.
    • The above image is only a small amount of the zone's height extent. The actual zone would go on much further south/north than the above image. It would take the player many game days to cross a zone.
    • In the South of the zone the monsters would not be very threatening (small wild dogs, foxes). Further North some of the caves might have a defensive bear in them and there might be the odd wolf about during the night. Even further North there would be large dangerous bears roaming about during the day and packs of wolves at night.

      Constraints

      Take a look at this map and imagine it was procedurally generated:

      unwinnable.png

      There's no route North. The player must cross the river, but there are no crossing points and the player has no boat. A wider map reduces the chance of such an obstruction happening. A longer zone increases the chance. In any case the game map generator must never create cases like this.

      There are three solutions I thought about for guaranteeing a zone will be passable:

      1. The generating algorithm has the responsibility not to create impassible output. This is quite hard and it is prone to error. I don't want to have to (ie can't) mathematically prove an algorithm won't create impassible output.
      2. Test each zone the generating algorithm produces. If it's impassible then chuck it out and generate a new one. This solution works, but in dense zones there could potentially be a lot of chucking out and processing time spent testing maps.
      3. After generating the map, trace one or more random North/South paths through it. Either go round obstacles or destroy them.

      I'll probably go with solution #3. It guarantees a path through the map and doesn't require an exhaustive test. Here is an example of 2 guaranteed paths being created through the map:

      winnable.png

      This is adequate for the plains zone where the obstacles are sparse. In the remote chance of an obstructive barrier as above the player can easily hunt east and west for the path through. For more denser zones (eg thick forests) this solution will not be adequate as it will lead to the creation of Mazes with numerous Dead Ends and only a few solutions which are frustratingly hard to find. The player may have to backtrack miles back South to get back to the right path. If they have to do that the game has failed.

      The solution for denser zones will probably be to divide the zone into a grid and make sure each neighboring grid tile has a short connecting path. Ie to trace paths horizontally as well as vertically.

      Pre-Generating vs Generating On-The-Fly

      The main benefit of on-the-fly generation is to support infinite maps. I have decided not to have infinite maps so the only remaining benefit of on-the-fly generation is to reduce pre-generation time at the start of the game. However that's not really a big deal. It's a once-only task which takes a relatively short amount of time compared to how long you will be playing in that world. The disadvantage of generating the map on the fly is that the map generation algorithm gets more complicated.

      So I will stick with pre-generation for now. I am actually a fan of world generation at the start of the game. It makes it seem like something cool is being made for you to play. The generation at the start of Dwarf Fortress where it creates the world and it's history is pretty cool.

      Also weirdly I like the idea that the game world exists in it's entirety. Far far to the North there are already structures set in stone. There might be a terrible monster on the map somewhere. There's something cool about being able to (in the debugger at least) ask where that monster is. In contrast knowing that the world is being randomly built as I travel makes it seem less real. Although from the point of view of the player it makes no difference of course.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now