Random Location Generation

In Deity Quest, locations are areas where you can explore, convert followers and collect treasure. If you haven't heard of Deity Quest yet, it's my newest project, and you can read the introduction post here: Introducing Deity Quest! - Indie DB . I wanted the locations to be randomly generated so that they would be different every time you played, and so that they could be very large without having to map them by hand. They need to be large so that there's plenty of space to explore, and because the respawn rate of followers is going to be very low. If the locations weren't large, you could run out of enemies to fight and have to wait for the respawn. I also needed the locations to be coherent, with some system of paths that guide you to important areas so that you don't get lost. You can also leave the paths to "bushwhack", and you may just find some interesting areas doing that.

An example randomly generated bog location.

The first and most important part of the location generation algorithm was to place the paths. Once a coherent and interesting network of paths is generated, the rest of the location generation is simple: place objects where they don't block the path or overlap (trees, bushes, etc), and vary the ground tiles so that they aren't uniform (by placing groups of tall grass, flowers, lakes, etc).

My path generation algorithm deals with trail heads, where each trail head has an x,y coordinate and an x,y directional tendency. It starts by placing two trail heads in the start location with opposing directions, and then iteratively selects a random trail head and moves it following the directional tendency (with some jitter). At every iteration, it also changes the directional tendency slightly in order to have a large scale bend in the path, and with some probability may branch off. If the path branches, it creates a new trail head at the same location, with the directional tendency rotated either 90 or -90 degrees. These branches will move away from the main path, and will meander and can branch themselves. This algorithm continues for a set number of iterations, and at the end, the list of trail heads tells us all of the ends of the path (which we can later use to add events and interesting areas there).

An zoomed out view of the roads generated by the above algorithm.

The road generation algorithm can also be used for rivers by tweaking the parameters and placing water tiles instead of road tiles. And if a river crosses a path, that's easy to fix by just placing a bridge tile there to ensure that you can follow the paths wherever they go. As long as the paths are unblocked in the subsequent object placement algorithms, the player is guaranteed to be able to access all of the areas the paths reach - but there is still plenty of "empty space" to explore!

The only other complex generation code is the hills (shown in the below field screenshot). Hills require a connected circuit of tiles, and only the straight edges can overlap roads by being replaced with stairs. The basic idea I had was to start from a square, then jitter the edges and ensure that the road never hits a "bend" tile. This turned out to be a lot harder than it sounds (it would intersect itself when it jittered), and I won't get into the details of it, but suffice to say that they work and add an interesting obstacle with only a few entrances/exits.

An example randomly generated field location.

Everything from here is simply setting the probability distributions for what objects and floor tiles are allowed in what locations. The forest has a high probability of placing a tree and places 5x the number of objects as field locations, but the field locations place several hills. This allows me to tweak some numbers and create a whole new location generation algorithm that creates interesting, coherent and new places to explore every time you start a new game. The locations are 256x256 tiles, but by breaking the location into chunks and only displaying visible chunks, the performance remains high, even on my 900 mhz eeepc and my android phone. The location generation runs pretty fast as well (less than a second on all test devices) and is conservative in memory usage (one integer per tile, each "layer" taking up one byte).

An example randomly generated forest location.

I still have to place events and start the battle system on touching enemy follower events (some of which will be placed randomly, some will be placed near trail heads, some even guarding treasure), but already you can click around and watch your followers pathfind throughout the randomly generated locations. Once I'm done with events, I'll start on dungeons, which are similar to locations except they are smaller, have a fixed start and end point (with a one-time powerful guarding party and treasure at the end), and you can only leave dungeons at the start, end or by loading from before the dungeon (losing all followers/exp you gained in the dungeon). I may also add some randomly placed puzzles in the dungeons.

Look forward to future updates on Deity Quest and my other projects!