Time to add some new features; specifically it is time to add the monsters. Not just the critters described earlier, but real monsters. Those that set the tone of the game. Monsters you cannot fight and even cannot really see because they exude darkness themselves. Images like this inspires me…
Time to get to it! The simplest of these are monsters that just follow the walls of the cave. So it is time to down and get write some low level algorithms! Left hand search, should be simple, right?
Err, well, maybe. My gut feeling says that enemies should not just roam the entire map, but be confined to certain areas. This way they represent something to discover once you progress to that area.
Ok, so how to split up my dungeon into areas?
That’s not that easy, actually. I played with some ideas on paper, but they did not really seem to work. So how to procees? Well, I could just generate a batch of caves and manually decide what would constitute good areas for monsters. Even better: manually draw some patrol paths, and then see if there is a common formula that I could implement in code.
And this is where I love the fact that I invested some time in getting to know the Gimp, it was easy to play around with this stuf. This is what I ended up with:
So, I came up with the following rules:
– patroll routes do not cross acid
– patroll routes do not venture into narrow corridors
– patroll routes must have a certain minimum length
Ok, but how to find these routes? While thinking about corridors I thought about what defines a corridor? It is the distance of its floor tiles to the nearest wall tile. A corridor consists of floor tiles that are all connected directly to wall tiles. Good, I can use this. Let’s make a map of the dungeon that shows for each floor tile the distance to the wall tiles.
And because I’m a sucker for visualisation, I started with just showing the number of non-wall neighbours for each floor tile.
Now calculate the distance to the walls, and you get something more useful:
Ah, a pattern emerges: the “1” distance tiles are clearly the route the patrol will follow. Only the routes still contains small corridors? How to removed them? What if we state that corridor tiles are those tiles that do not have any neighbour of distance “2”. Let’s set the corridor tiles to distance “0” just to see them clearly.
Actually, looking at this picture shows that it is very easy to create a route. We can take any floor tile with distance “1” and just follow the adjacent distance “1” tiles until we end up back where we started. And voila presto!
Maybe it is more visual if we add a new set of tiles that indicate the direction that each step is taking.
Glorious! And it is not even the pathing algorithm that makes me smile so much, but the fact that I can visualize it like this! Now for a final check, let’s see how the generated path compare to my initial idea of what patrol routes should look like.
That seems to have worked out rather nicely :)