All Alchementalogs
Table of Contents
Where We Stand
In the last devlog, we tackled the problem of adding flavour to the map in a way that makes sense. Now, let’s do a little bit of refactoring of some of the previous code to fix up some small details and also get things setup nicely for the next devlog.
So when we last left off the map generation, we had basic rooms setup, with corridors that connected them and a final pass that guaranteed connectivity between all rooms. We also did some work on flavour, but we won’t be focusing on that in this entry. No, instead we’ll be taking a look at what changes I’ve made to the already existing codebase. Refactoring and rejiggering code is an important step as you progress along the programming journey. It helps keep things clean, it tightens existing stuff and it lets you insert little quality of life changes. Let’s get into it.
Centering Ourselves
There’s a few things I wasn’t a fan of when it came to the existing implementation of the map generation. The biggest problem initially was the way the corridors were being connected. We would pick a random spot in a region and connect it to a random spot in the region that had the nearest “center” to it. How was I determining the centers? Well, I basically pretended the rooms were rectangular in shape by taking the top-left-most cell and the bottom-right-most cell and projecting that into a rectangle. The center of that rectangle was what I called the “center” of the room.
There’s a big problem with this though and that’s that our rooms are most definitely not rectangular, at least most of them. This meant the center point often landed on a cell that was totally outside of the room, which didn’t make much sense.
The pink border is the actual general shape of the room, the blue border is completing the “imagined rectangle” I was building based off the top-left and bottom-right of the room, and the green is where the “center” is placed based off that imagined rectangle…Clearly it’s not in the right place to be the center of the room.
I spent a little while thinking about this problem and doing some research. I found a few different methods for calculating the center of the polygonal shape of the rooms, with the most prominent being to build a “straight skeleton of a polygon”. However, this was complicated and also relatively slow. I didn’t want to spend the time I would need to figure out how to do it while also not being sure if it was a good enough solution anyway.
So I sat and thought and thought and sat. And then it came to me…Why yes…Yes!…I would flood fill!
Hahaha, indeed, yet again flood fill is the answer! However, this would be a specialised type of flood fill.
To begin with, I would find the border cells of the region; a relatively simple procedure. I would just do a pass through each region before drilling any corridors, and mark any solid wall sections next to an open floor section as “bordering” the region.
These borders would all then get added to a priority queue for the flood fill with the priority being the current distance they have travelled from where they started (in this case, they would all get priority 0, as they are 0 cells from where they each start). I would then keep track of the distance traveled as the flood fill moved through each cell, storing the minimum distance to get to each cell in the room from the border in an array. This is really called Dijkstra’s algorithm (or Uniform Cost Search) and you can learn more about it here: Dijkstra’s Algorithm.
Here’s the code, if you’re interested:
var _queue = ds_priority_create();
var dist_map = array_create(map_width*map_height,undefined);
var _region_id = _region.region_id;
for (var j=0;j<_region.border_number;j++) {
ds_priority_add(_queue,_region.border_list[j],0);
var pos = _region.border_list[j];
var current_key = pos[X]+pos[Y]*map_width;
dist_map[current_key] = 0;
}
Above, we set up the priority queue as _queue, create the dist_map array where we will store the lowest distance found for each cell and we grab the region_id of the current region (which I have been calling rooms in this devlog) that is being processed (this is all inside a loop that cycles through all the regions). Then we loop through all the border cells I have stored for that region and add them to the priority queue, marking each border cell as 0 cost in the dist_map. Now we’ll begin the Dijkstra’s loop.
while (ds_priority_size(_queue) > 0) {
var pos = ds_priority_delete_min(_queue);
var cx = pos[X];
var cy = pos[Y];
var current_key = cx+cy*map_width;
var l = 1;
for (var k=0;k<4;k++) {
var d = k*90;
var nx = cx+lengthdir_x(l,d);
var ny = cy+lengthdir_y(l,d);
if (nx < 1 || nx >= map_width-1 || ny < 1 || ny >= map_height-1 || floor_map[nx][ny] != _region_id) {
continue;
}
if (cell_floor_map[nx][ny] != SOLID) {
var next_key = nx+ny*map_width;
var _dist = 1+dist_map[current_key];
if (is_undefined(dist_map[next_key])) {
ds_priority_add(_queue,[nx,ny],_dist);
dist_map[next_key] = _dist;
}
else {
if (_dist < dist_map[next_key]) {
dist_map[next_key] = _dist;
ds_priority_add(_queue,[nx,ny],_dist);
}
}
}
}
}
First, we grab whatever is the lowest priority (or the cell stored in the priority queue that has had the lowest number of “jumps” from the starting point) and then delete that entry from the priority queue. Since everything in the queue is a border cell and thus has a priority of 0, this essentially picks a random border cell to begin with.
Then we check the cells all around the current cell. If the neighbouring cell we are checking is outside the map or outside the region, we’ll ignore it with a continue, otherwise we check to see if it’s a wall or floor cell (SOLID is wall).
If it’s a floor cell, we add one to the distance that has currently been traveled (stored in dist_map[current_key]), which equates to a “jump”. Then we see if the neigbour cell has been visited or not (if the is_undefined() check returns true, we know it hasn’t been visited, otherwise if it returns false, we know it has).
If it hasn’t been visited, we can just go ahead and plop whatever the current distance traveled has been into it, otherwise, we check to see if the distance that has already been stored in it is greater than the distance we have currently traveled. If the current distance is less than the previously stored distance, we update the dist_map and add that cell back into the priority queue with a priority of the current distance.
Then we repeat this process until no more cells are being added to the priority queue and all the existing cells that have been added have been checked and deleted.
What this ends up doing is giving a nice “cost” map, where the cells closest to the border have the lowest cost and the cells furthest from the border have the highest cost. Why is this useful? Well, I can use the highest cost cell (or randomly pick from the highest cost cells, if there’s more than one with the same cost) and this will be the “gravitational center” of the region. The center of the largest section of the region in other words. Here’s a picture to show what I mean.
The bright orange cells are the border cells. In previous images, the number inside the rooms was the region id, but here, each cell inside the region shows the number of cell-sized jumps that have to be taken to get to it from the closest border cell, or the “cost” of movement to get there. We can see that the highest number of jumps needed in this room is 4, so the cell marked as 4 is considered the center.
Obviously, this isn’t the exact center of the room, in fact, it’s kind of better that the center is in the largest section, but Dijkstra’s is a relatively quick process and it forces the game to ignore any long arms that branch out of a room while also forcing the center to always be inside of the room itself. I could optimise the centering a little bit more by removing the border cells that are surrounded by room cells (I consider those tiles to be pillars and you can see quite a few of them in the above picture), but eh, I haven’t done it yet and I doubt it will make much of a difference to the final product. Something to keep in mind anyway.
So, we’ve now got some more sensible centers for the rooms. Let’s have a look at the actual pathfinding for the corridors.
A Link in the Chain
Previously, I was simply picking the nearest “other room” center to whatever room was being processed and drilling a hole through any walls on an A* path to that “other room” center. It worked ok, but sometimes it would snake through a thin arm of a third region (or even a fourth or fifth) on it’s way to the room with the closest center, and this led to connected corridors that the rooms didn’t know about.
This was not good. I wanted each room to know exactly what other rooms were directly accessible from it. What this meant is that I had to add another check to the corridor creation.
As the path from one room to the next was made, I would keep track of the last region id the path had visited. If the path crossed into a new room, I would check that new room against whatever room the path was heading to.
If they were the same, no worries, the corridor was directly connecting the two rooms with nothing in between them.
However, if the new room wasn’t either the starting room or the ending room of the path, I knew that I had just cut through an extra room.
At this point, I’d stop making the original path briefly, grab the center of the new room that had just been cut into and do an A* path from the new room’s center to the point on the original path that had just cut into the new room. I would then add the new room to the “connected” list of the most recent room that had been passed through previously and continue on with the original path.
This process would repeat each time a new room was encountered that wasn’t part of this connection chain already. This gave me a lot more information about the connectivity of the rooms and also meant that there were more branching corridors (although invisibly so, as I forced the corridors connecting these “intermediary” rooms to not cut through any walls), which made the future A* pathing run quicker. This is because corridors have the lowest cost in my A* algorithm, so A* prefers to travel down them, which means it checks less cells overall as it moves towards its goal (as long as an existing corridor is heading roughly in the direction of the goal).
Another, smaller tweak that I made was that originally I was simply cutting through the walls and letting the rooms know they were connected. Now I’m storing the cells that make up that corridor between the centers of the connected rooms. I don’t have a specific reason for this yet, but as an example of how it could be useful in the future:
Let’s say I wanted to do some pathfinding from one random room to another, I can now use the “connected list” for each room as “cells” in an A* search and I would already have a pre-defined path between the rooms (the corridor). This would dramatically cut down on search times, as instead of having to search through each cell in each room (potentially tens of thousands of cells to search on a large map), I can simply search room by room and use the corridors connecting them (making the search size max out at however many rooms there are, so like 30 to 50 cells to search on a large map), up until I’m actually in the room the thing I’m pathfinding to is in, where I would then need to start doing a cell by cell pathfind. So, potentially useful, but unused as of yet.
Well, that’s about it on the refactoring for now. Next time we’ll be looking into how to find where doors should be and adding some interactivity and excitement to the rooms.
RefresherTowel, away!
RefresherTowel Games 