Devlog 1 - Poisson disc map generation

Hey all, Steel here from Railgun Games. This is my first time writing a devlog so bear with me.

I've been working on the game almost every day for the past week+ since the first version dropped here on itch. This latest version addresses some lag issues that were still occurring with the final boss (for now), the goblin warlord. Props have also been added to the level generation, so now there are rocks, barrels, pedestals, and tufts of grass that spawn in the levels to help break things up a bit and keep it interesting. Currently two of the rocks do not have shadows so apologies for the inconsistencies.

The main topic however is the title of this post - poisson disc map generation.

The map generation has actually gone through a ton of different phases internally since the beginning. Initially it was a bit like the puzzle in the Ruins of Alph in Pokemon Gold and Silver - you have a set of tiles and can rotate them and place them in a grid. Our tiles in this case were potential route directions - one entrance, a line, an L shape, a T shape, and a plus shape. You had to place them in a way that connected your starting position to the boss, and I wrote some really mind numbing code to check and ensure the route was valid (you could make it to the boss) upon submission before locking it in, which ended the tile placing phase. After that, you would be forced to go anywhere on the route that you made (if there were intersections, you could choose wherever, there just needed to be a valid connection), and encounters would start as soon as you entered the space with one. The idea here was to let the player plan a route freely before heading out, like an adventurer would if they were going to explore some ruins, plus a little gameification to keep it interesting. We also toyed with the idea of partial route submissions and rewarding the player with more route tiles upon completion of rooms, that way they didn't have to plan the whole thing at once (and could adapt if things were looking dire), and even randomly forcing some tiles on the map from the beginning so they had to work around them. The problem with this is that it both didn't look too great visually and was really tedious. You end up spending multiple minutes having to drag the tiles back and forth, the hitboxes on them were not great so it was sometimes tricky to pick the right one up, etc. So we scrapped that.

The next system we came up with was the one in the last build - you can move wherever you want in the grid and it draws the path under you wherever you've gone, and you have a set number of moves before you have to rest. This was way less tedious, didn't require any route validation, and easy to understand immediately, and as long as we gave the player the ability to rest whenever, there was no issue getting to wherever you needed. Eventually, there would be a time based mechanic punishing those who rested too much and were greedy about going to every time possible, but it remains to be implemented. The main issue with this generation though was that it was still pretty boring visually - lots of regular enemy combats could cluster up so you would see a ton of wolf heads next to each other and be forced to traverse them, potentially.

So, we decided to revamp it again, this time using poisson disc map generation. This way, instead of using a neat grid, it mixes things up by randomly generating points, keeping them at least a set distance away from each other (r) but also close enough to make a feasible path (2r). This effectively makes a donut of allowable space around each generated point where another point could be generated, and as more and more points are generated, the inner circles of the donuts start to overlap and disallow more of the space to have points, until we have generated all that we can. As it iterates through each point, it tries a set number of times k to generate a point at least r away and checks to see if it is valid (at least r away from all nearby points, but also within 2r of our chosen point). Once it is done with that point (successful in adding a new point or not), it removes the point from the list of potential points to branch off from. For more details on how it was done mathematically, the post linked earlier in this paragraph does a great job.

With this, now we don't need random blank spaces to make the path to the boss less tedious/laborious - instead we can generate something on every point since there are less steps to get to the boss now anyways. Of course this required changing everything about the code for generation, path selection, movement, and even level completion, which is why I worked on it nonstop the past week or so. I also added some visual upgrades to the map as a part of this. Because you need to be able to select a destination that could be in any direction instead of a cardinal direction, a cursor was added to the map screen. When the cursor is hovering over a valid destination, the icon will enlarge to indicate you have selected it and can travel there. Additionally, mountains and forests generate as part of the background for some icons instead of filler tiles for the map. In the future, this will affect spawn rates of various props in the levels, but for now is just a visual effect for the map. This will also be used to fully tile the background of the map as a visual to make the scenery feel more real. The map also draws lines to all valid destinations from your current position, so you don't have to guess which points are within 2r of you.

Fingers crossed there aren't any major bugs with the map generation or traversal. Next time we plan to add some more abilities for the player to use in combat (weapon arts), then fleshing out of abilities that can be bought in the game at the shop (altars). Thanks for reading!