The first feature I want to talk about are the levels... well there are none, all of the maps will be generated as the player enters the dungeon/maze/crypt.
There are a few reasons why I won't be hand crafting each map. Time is one - if I want to finish this game in this decade I can't spend all my time designing levels. Random maps also let people play the same game multiple times, but there is a more important reason, although it may be important just for me - I'm making this game because I want to play it and unpredictable, random levels is the only way I won't know the layout of each map.
There will be some technical talk now, if you're not interested in how random level generation works, you might as well stop reading now.
This is not a new concept, rougelike games have been doing it for decades and there's a lot of material on this topic on the net, yet I think I may be doing something new here.
Most algorithms I've seen use the concept of rooms and corridors. You first put rooms in your map and then connect them with corridors until each room is somehow connected to all the other rooms. Some algorithms work by 'digging' tunnels and then expanding some of them into rooms using cellular automata or some other clever tricks.
In my approach there are no rooms, there are only equally sized tiles, rooms and corridors are emergent, they are created when tiles connect in the right way - and they can only connect in the right way.
But before we get to tiles, let's talk about grids. In my system the grid is needed only for checking if a new tile can be placed in a certain part of the map or is that place already occupied by some other tile. The grid could be triangular, but that's very limiting (you can only have 2 tile shapes - with one or with two connections), a hexagon grid is very interesting but a bit harder to make (there can be 5 types of a tile with 1 connection and there can be 1,2,3,4 or 5 connection - that's a lot of options!). A square grid will do just fine and it also fits the typical dungeon/maze shapes.
As I said all tiles have the same size, this makes it easy to put them in the grid, each tile takes up exactly one 'space'. Each tile also has exactly one way to connect to already placed tiles and can have multiple ways to connect future tiles (on a square grid tiles can have 3, 2 or 1 'out' connections arranged in a few different ways). Connections are part of the tile, if the tile is moved or rotated, the connections move and rotate with it.
The algorithm works as fallows:
0. If there are no tiles, place a tile, store its position in the grid.
1. Select a random connection and check in the grid if the location of the connection is free (if not, remove this connection, plug the hole if needed, and redo step #1)
2. Select a random tile and put it in the location of the selected connection, rotate the tile if needed.
3.Store the tile location in the grid, if there are still open connections go to step #1.
The downside of this algorithm is that it can produce closed loops before a level is big enough, but that can be fixed by replacing a tile in a corner by a tile with 3 open connections. If the algorithm made a closed loop it is guaranteed that there will be a tile with 1 connection in the leftmost column of the top row (and also every other corner of the map). The good news is that it's simple, every tile is reachable and you can control the shape of the level by giving weights to each tile type (more 3-connection tiles=more rooms, more 1-connection tiles where the 'in' and 'out' connections are opposite = more straight corridors, more 2-connection tiled = maze).
I'll post some examples later, when I have enough tile types ready.
No comments:
Post a Comment