I’ve been pretty busy with life recently and it’s been taking up a lot of my spare time. This means that the Proc-Gen in GMS series has slowed down a little bit. So I figured I’d take a little time to explain the process of making the entries because I think it’s both informative about the actual process of working on PCG and also lets everyone know why there might be gaps between some entries (and is much quicker than an actual entry =P).
So far, I’ve been doing fairly “rote” entries explaining basic algorithms. While this is super important groundwork, it doesn’t take too much effort (well, actually, it does take a lot of effort to produce the entry, but it’s more on the side of making any graphical additions I might need, thinking about the best ways to break down algorithms, writing/editing, etc, not actual work on making the thing itself function). The last entry (#7: To Perturb A Room) is a somewhat unorthodox generation method. Most map generation techniques can basically be broken down into a grid of things. This has many benefits, but the big drawback is there on the tin…It’s a grid. You can try various ways to obfuscate the “grid-like” appearance of the map, but it’s always going to be there in one form or another.
Room perturbation doesn’t suffer from this drawback (or at least, it doesn’t suffer as much as others might). This is because of the free form way in which the generated rooms move to their final positions. You can have all sorts of crazy positioning, such as a room that is below two other rooms in the y axis, but also exactly in the middle of those rooms on the x axis. This sort of thing isn’t super common in the usual generators, which is cool as it can give some more interesting map layouts but also comes with it’s own drawbacks.
Because of the free form positioning of the rooms, I can’t directly reference a grid to figure out what rooms should potentially be connected to what other rooms (for instance, in a direct grid generation, you would connect the cells together), which means I have to get creative. So let’s go through the process of experimentation I’ve done so far and where I’m thinking of going next.
First of all, I tried the simplest approach. Loop through the rooms array and connect each room to the next room in the array using an A* generated path. A point to keep in mind with doing it this way is that it guarantees the start room will be connected to the end room without having to do any checks (if every room is connected to another room, there will be a path between any two rooms). This “works” but it’s not very pretty, because rooms next to each in the room array are almost guaranteed not to be next to each other on the map. They are randomly positioned. So there’s lots of weird overlap and it generally doesn’t look great. There’s also only one entry and one exit to each room. That’s fine, we’re experimenting and trying to find whatever techniques will make the map we are imagining in our head.
So my next thought process was to see what it would look like if I connected each room to all the other rooms. This might sound crazy (and it was) but as I’ve said and will say again, experimentation is the key to PCG. This method also guarantees a path between the start and end while also making sure there’s multiple entries and exits to each room. Who knows what interesting things this might generate. We have to try it to find out. Of course, it ended up not looking great either. Another point I would like to make is that even if things end up badly with what you are trying, it’s always super useful to actually go ahead and do it without second guessing yourself. It gives you a visual reference for whatever you are trying and you never know when, some time in the future, you might hit a problem that will be solved by exactly the crazy stupid generator you tested sometime in the past.
Ok, attempts 1 and 2 are duds. I’ve got to start thinking outside the box. This is where we get into theoretical territory as I haven’t had time to test these ideas out. But here’s where I’m headed next. I’m going to try a flood fill algorithm heading out from the center point of each room. That flood fill will find the four nearest rooms and mark them as “connected” to the room doing the flood fill. Then I’ll run A* to generate the corridors for each room to the rooms it should be connected to. I’m hoping this will avoid a little bit of the chaos of when the rooms are trying to connect to other rooms across the map. I’m anticipating the possibility of this method generating connective maps that don’t have a path from the starting room to the end room, so I’ll have to put in some tests (mainly, I will run A* from the starting room, with the goal being the end room and see if it manages to get there, if it doesn’t, I can either try to come up with some way to connect the non-connected parts, or I could discard the map as a whole and generate a new one until there is a connected path).
Another problem that I was considering which I might try to fix is that sometimes the A* algorithm runs a corridor directly alongside a room for the entirety of it’s wall. Depending on what aesthetics you are looking for, this may or may not be what you want. If I decide that no, I do not want it to happen, what I’ll do is create a “heat map” for the generator. I’ll run a floodfill outwards from each center point of the rooms and mark each consecutive cell moving out from the center points to a value which I will increment. I’ll then find the highest value on the heat map and use it to invert all the other numbers in the heat map. Basically, it will populate the heat map in such a way that the lowest values are the furthest distance from each room, with the closer you get to a room, the higher the value the cell will be in the heat map. This means that I can use the values in the heat map as the cost for the A* algorithm and the A* will naturally try to move towards the most open spaces between rooms, which should cut down on the number of times it runs directly alongside room walls.
So once I get some more spare time (probably in a week or two from now is when I’m guessing), I’ll implement what I discussed above and see how that works out. All of this is a good example of the iterative process of procedurally generating maps and gives some insight into why procedural generation isn’t a silver bullet to content creation. Sure, once you’ve got the generator running you can make a lot of content quickly, but getting the generator to the point where you are satisfied with it can take up as much or more time than creating the maps by hand (if I wanted to just place the rooms and corridors by hand, I would be done in an afternoon, rather than weeks later still running through ideas). This is why you always need to consider your reasons for using PCG compared to using more traditional design techniques and make sure you are using PCG for the right reasons.
Till next time, peace.
RefresherTowel Games 