One of the aspects I have enjoyed immensively in pyherc is level generation. It’s no surprise then that I wanted to try a slightly different approach that I’m describing here. It’s not fully finished, but should be sufficiently ready for a blog posting
After lots and lots of dirty hacks and ugly workarounds, I got new partitioner working (and then cleaned to a degree). Now it is possible to have levels, where rooms don’t form uniform grid, but form more interesting shapes.
If you recall from previous blog posts, level generation is split into multiple steps. One of the very first ones is dividing the level into square sections that are randomly linked together. Rooms are then placed within those sections and linked together with corridors. Previously sections formed uniform grid that produced somewhat uninteresting results.
The new routine starts by dividing the level in two sections. The split is done randomly in either horizontal or in vertical line. Resulting two sections are then split into two and this is repeated until they are small enough. After that sections are randomly linked together and level generation proceeds as before.
The routine used to link sections together is simple. First a random section is chosen. Then one of the neighbours that has not been connected is selected and connected to. Same is repeated to the neighbour that we just connected to, thus building a chain of linked sections. When new connection is not possible, we check if there are any sections that have been linked and have unconnected neighbours. If one is found, a new path is built from it, otherwise the routine terminates.
Results are pretty good already. At later time, I’ll add more routines for partitioning level, which hopefully will make environment more interesting.
Recently I have been tinkering with level generation in order to accommodate new set of tiles and decided to write a post about the whole process.
The process starts with a brand new level that usually has been filled with solid wall. Level is then split into sections and sections are linked to each other to form the general shape of the level. In the picture below red and blue parts represents sections and green block is link between them.
After the general shape has been decided. Each section is visited in turn and a room is created within it. There is a separate array where we can give names to locations, like “room” or “corridor”. This will greatly simplify item and monster placement later on.
At this point room is also connected to each and every link that the section may have, forming a net of interconnected rooms. Results of this are shown in the next picture. Black represents solid wall and gray area is space that has been carved out to create rooms.
Since the shape is known, we can next add stairs that link the level to other levels, monsters and items. Thanks to the previous step, we can search location array and always place stairs inside of rooms and generally control how items and monsters are placed.
At this point the level is already playable, albeit really boring looking. Rest of the level generation concentrates on polishing it to look nicer. This is done with the help of decorators (not to be confused with Python decorators).
Decorator is an object, that takes a level alongside with some configuration and then changes the level to some degree. The first decorator we run will reason where there should be walls in the level (currently we have only solid rock that looks a bit too uniform). Essentially, it will search for boundaries of empty space and solid wall and place a new kind of tile there.
Second decorator will then step in and polish the detected walls further. It does this by reasoning which direction any given wall tile seems to be going and replaces it with a different tile. It would be easy to combine this step with the previous one and do the whole thing in a single pass. I wanted to keep them separate in case in the future I want to do something else with the walls than simply make them look nice.
Polishing the floor is similar process and done with yet another decorator. Because stairs have already been placed on the level, we can take them into account and make floor tiles to flow around them nicely.
Last decorator in this example will find suitable spots for torches and randomly select few of the spots to house torch. Essentially I want to place them on straight sections of wall, with free space on south of it.
After this, the level is ready to be conquered. Since the amount of decorators is not limited, it is possible to use same simple room shapes and change their theme and contents to create new rooms.
This week I finally got the level generation to the point that it can be used. It can handle generating layout of the level, placing items, monsters, stairs and linking level to previous one. As usual, there are still lots of things to tune and more functionality to add, but it’s just details.
Test driven development worked pretty well with the generator. Biggest problems I faced because the lack of higher level tests. Unit tests alone aren’t enough, but they need to be supported with higher level integration tests. Otherwise components work really well in isolation, but integrating them together can be tricky.
Now that level generator is more or less ready to be used, I can concentrate on the content for a chance. Plan is to start fleshing out notes I have about various monsters and pick one of them to be implemented first. This will probably require more actions, changes into rules and graphics before monster is done. Artificial intelligence will need lots of work too.