Implement map generation

[mminer]

This seems like it could be a gnarly task if we attempt to do it from scratch. My vote is to integrate an existing library. I found a few:

• libtcod: C++ library, but perhaps we could pull it in as a plugin
• RogueSharp: loosely based on libtcod; has field-of-view calculations which might be interesting for providing lighting (e.g. if the player holds a torch)
• GoRogue: also inspired by libtcod

[mminer]

It occurs to me that pulling in libtcod as a native plugin will prevent us from making WebGL builds, so let's scrap that option.

[bradkeys]

@mminer would it make sense to:

• Use a maze generation algorithm
• Have a validation method that confirms there is a clear path from start to finish (should always pass initially)
• Then randomly add some path-blocking element, check if validation fails, if so then make the blocking-element a non-optional thing that must be solved in the map, otherwise make it something optional, then except it from the validation and do this step again (repeated attempts depend on balance)

[bradkeys]

To make it more interesting, you could potentially create multiple mazes (ie. 4 would generate Tetris shapes) that connect to each other and self-manage their random elements. Connecting them might difficult but the generator I linked to above allows specifying the start, so it's likely doable and we would know exactly where these connections are, which may allow an opportunity for a mechanic (a special doorway, reward, enemy, difficulty bump, etc).

[mminer]

Hmm yeah, that approach might make sense.

On the pre-made library front, I tried RogueSharp and the maps it generates look good to my eyes. They're effectively a series of rectangles connected by hallways, but the results have a somewhat organic feel to them.

################################
################################
################################
##########.....#################
##########.#...#################
##########.############......###
##########.############......###
######.......................###
######.......##.......#......###
#########..####.......#......###
#########..####.......#......###
#########..####.......#......###
#########..#######.####......###
#########..#######.######.######
#########..#######.######.######
#########..#######.######.######
#########........#.######.######
#########..........####......###
#########........######......###
#########....................###
#########..############......###
#########..############......###
#########..############......###
#######........#################
#######........#################
#######........#################
#######........#################
#######........#################
#######........#################
#######........#################
################################
################################

To enforce hallways with doors, generating four smaller maps like you mention (or two side-by-side?) and carving a path through them seems like a good idea.

For monsters that you have to slay by first finding a chest with a weapon, we could do something similar:

1. Generate a 1-unit wide hallway
2. Randomly place a chest in an empty tile
3. Do a pathfinding check to see if the chest is reachable without passing through the monster
4. If it's not reachable, back to step 2; repeat until we know it's possible to get a weapon before reaching the monster

[mminer]

I connected RogueSharp to our tilemap. I think this might work nicely as our foundation.

[mminer]

I'm going to call this done. We have to do more work to fill the dungeons with obstacles and items, but we can consider the map generation itself finished (sans tweaking).