The map generation in Super Scrapped Robot is one of the first things we did for it and it didn't fundamentally change since the Jam Version. Before the Jam it was always a dream of mine to one day write a map generator. Some day before the Jam I stumbled upon an explanation of the map generation in Nuclear Throne (formerly known as Wasteland Kings) which stole the fear from me, that map generation has to be a complex beast that isn't easily tamed. But it's just a Random Walker, which is maybe one of the first things i programmed on my own when i learned processing several years ago. So let's see in detail how the map generation works in Super Scrapped Robot.
Random Walker
This works exactly like it is described in the vlambeer article. Make a big two dimensional array, start in the middle and randomly walk in one of four directions. Sometimes mark rooms in random sizes. With these two simple rules we already get some nice looking maps and have parameters to play with to change the look of the map.
A more organic map
The random walker generates some nice maps, but they look more like indoor map, with corridors and rooms. We wanted to make shattered planet fragments, so we need more planar maps. While researching for this project, i found a site about rogue likes which also has a section about the map generation. Especially this article about using a cellular automata to make cave like maps was interesting. And it's simple, just check if there are at least 5 floor tiles in the area surrounding the tile and then make the tile in question a floor tile or leave it as it is. The more we repeat this process, the smoother the map gets.
Detecting the main island
The smoothing process has one problem thou. Some areas get disconnected from another and thus aren't reachable for the player. My first attempt to solve this was to build bridges between the separated areas, but it didn't really worked and i was under time pressure so i searched for an alternative solution. I once started to write an Sprite Atlas Generator, which i never finished, but it contained code that could detect if pixels are connected and how big of an area they mark. I looked for the biggest island and scrapped the rest. If the island was not big enough, i would just start from scratch again.
Mark the land
This section is pretty specific to Super Scrapped Robot, but i'll explain it anyway.
Grass & Sand
We wanted the ground tile to have some sort of variation. One solution would be just placing tiles at random and then smooth them out. That would have given us some sort of patchwork distribution. To make things a little bit more interesting, we settled for the following: Make an altitude map, the more the tile is away from the border, the higher it is. The threshold should be pretty low, so we get nice areas and then we mark those areas [in turns] as grass or sand.
Water
When you generate a few maps you'll probably notice that there are holes in the map. While this is generally fine for scattered planet fragments, we still wanted some areas that look like a little lake. The way I did it is stupid, but simple. I used flood fill to mark the empty area around the map as empty and then search, tile by tile for any other areas that are not land. When one such tile is discovered a random value determines if that area should be flood filled with water or nothing.
Trees & Rocks
Trees grow on grass and rocks are on sand. Go over every one of those tiles and per random cancer there will be a rock or tree. The more trees or rocks are in the neighborhood, the higher the chance that a tree will grow or a rock exists.
Points of interest
For the jam I version I did some weird stuff here, so let's not look at that. The final game uses a [poison disc] map to distribute points evenly around the map. I generate a poison map for the whole area of the map and throw away those points that are not on a floor tile or collide with some other stuff. This could be better, narrow areas rarely get a point, but it's good enough. One could change the minimal distance of the poison map generation depending on the distance to the border, maybe that would look better. A lot of points ended up directly on the border, which looked not good in the game. Who would put their camp fire directly on the edge of an planet fragment? So those points just get moved away from the border.
Placing the player & make the map solvable
This is still based on the weird stuff I did in the jam version. We wanted to let the player start at an interesting point. But what is interesting and how determine that? I decided that interesting as a start position means to be closest to an edge. The player jumps or get thrown from fragment to fragment and landing close to an edge gives the feeling of almost missing it.
Now that we placed all that nice obstacles we need to make sure that the player will be able to reach all points of interest or the game is not winnable in some situations. I once wrote an A* implementation that I used for this. Just get the path from the player start position to each point, ignoring any obstacle and remove each obstacle that is in this path. Keep in mind that the implementation of A* is intentionally bad. I was hoping that the resulting path would be more interesting then a straight one.
Randomness
I wrote a post on pseudo randomness in the past, but to keep this article complete, let's talk a little bit about randomness. Javascript gives you the nice Math.random function, which produces random numbers between 0 and 1. Thats cool and all, but you sometimes want to repeat the same randomness again. I wanted this for the Challenge mode in Super Scrapped Robot. Each player plays the same random map each week. This would not be possible if computers would produce real random numbers. Instead they are just pseudo and itself generated by a function. One of such functions is the Xorshift. The start value defines the whole random number list, so setting that to the same value for each player gives each of them the same map.
Final map
Conclusion
The whole thing was fun to write and i really like what comes out of it. The code is maybe the ugliest code i've ever written, but it works and was maintainable till the end. And that is what matters, right?
I once tried to clean up the code and generalize it a bit. But unfortunately that attempt failed miserably. You can see it here and laugh a bit.
Have some fun playing the game and exploring what kind of maps this generator produces.