This project was done in response to /r/proceduralgeneration December 2015 challenge, in which one should use procedural techniques to create a pirate treasure map. Since I don't have much experience in this field I wasn't initially planning to fully participate. I just wanted to see other's work and try to fiddle with that. But after few days of lurking and looking at the early map prototypes I just had an urge to try creating something on my own.

I have chosen libGDX framework to work with, because it was on my ToTry list and it can output the Java (language I usually use) project as HTML5 application. In the early stages I was mainly learning the framework and the workflow. I was lucky to find that one of the participant used this framework as well and I could you his code to learn, how to make an application window and color some pixels.

 Act 1: Generating Heightmap

The first challenge laid in making some shape, that could be called an island. I have seen plenty of threads about generating heightmaps with Perlin noise and expected this to be the popular choice here as well. I decided, therefore, to try something different and ended up thinking about some basic, trivial approaches. The idea, that I decided to elaborate on and implement, was to set a mountain top (local maximum) at a random coordinate on the map and then make the surrounding points a bit lower step-by-step. I was hoping, that with a bit of help from the random function, I could get nice slopes on the map and clean waterline borders.

The basic algorithm was:

  • Find points with height n,
  • Start moving in each of {W, N, S, E} direction from the points and on every step roll a dice. If the roll is bad, decrement the height counter.
  • If the height counter is higher then visited point's height, set it as point's new height. 
  • Stop when on zero height level or you hit the map border.
  • Repeat for points of height n-1.
(1) - initial heigtmap attempt
(1) - initial heigtmap attempt

The result did not meet the expectation. Generated islands had always the same square-rotated-by-45° shape and the shoreline was really rough. The random dice roll on each step was not enough to make an interesting land (I blame the Law of Big Numbers for that). I tried to bring some variety by spawning multiple initial mountain tops (Fig. 1), but the shape was still really blocky and artificial. I tried fine-tuning the dice roll probability and found out that 75% chance to decrease height works the best. Going for higher chance made it too much likely to drop quickly to water level and lowering the chance made the map filled with rather flat terrain. After I realize, that tweaking the numbers would not improve the situation, I tried to play with graphics, to try and make it look a bit better (Fig. 2).

(2) - more height controu lines
(2) - more height contour lines

I let the project be for a few days and came back with an idea, that would really improve the quality of heightmap. Abuse random function even more. The first step was to randomize the height of the initial mountain tops to be between 50%-100% of maximal height. Smaller starting points would be useless, since they would most likely be "overwritten" by higher mountain range pixels passing by, or it would create a tiny piece of land in the ocean. I also increased the dimensions of the map and number of initial points. 

Act 2 - Fixing the borders

The hightmaps were getting better, but there has still been a serious untackled problem with ocean shoreline -- the black ugly island border created by coloring points with height = 1. Especially the "pier" artifacts, the long straight 1px wide line stretching through the ocean (plenty of them in Fig. 3). I was trying to figure out some trick to make it nicer but I couldn't.

(3) - ocean shore line artifacts
(3) - ocean shore line artifacts

Because of the performance issues, I was looking for a way to reduce the complexity of code. I tried reducing the size of generated hightmap and started interpolating some of the pixels in final map. In my early attempts I created a lattice having interpolated values of every second column and row (1:4 ratio). That worked fine, helped me with performance a bit and also somehow smoothed the island shape. This led me to trying even sparser lattices. 

I interpolated the values using something like bilinear interpolation. On 5x5 grid with corners having original values, the missing values in the first and the last row/column are linearly interpolated. After that, values of horizontal and vertical linear interpolations are calculated for every cell in the center region of the grid. Higher value is used.

(4) - messed up island after heavy interpolation

(4) - messed up island after heavy interpolation. Straight lines near N and E border are due to bug in interpolation logic.

The initial attempts were not really promising (Fig 4).  I needed to issue several tweaks before the mass in the picture could be considered an island. First I realized, that having all the ocean points have value 0, while using integer values for height, breaks interpolation near water. I fixed this by changing the water level to a positive integer. This way the ocean floor isn't actually flat. I also changed the generator logic a bit. I have added possibility to lower the current height multiple times while standing on one spot (rolling the dice until the requirement is met, reducing height for every failed roll). I also added an additional random roll determining how much the height will be lowered. The last change was to force initial points to be in the center region. This was mainly to dodge interpolation bug, which makes weird lines near S and E borders. The generator have been creating islands like Fig 5 since then. In the end interpolation still couldn't fix the shoreline.

(5) - island created from 1:25 interpolation after tweaks
(5) - island created from 1:25 interpolation after tweaks

After giving up on tweaking the interpolation algorithm, I started toying with cellular automaton logic. I used pretty simple automaton rule, that counts land cells in 3x3 grid, and if the number of land cells is lower than the threshold, I recolor the center cell to be a water cell instead. The recoloring is done in batch after every cell is passed. The automaton is stopped, when every land cell has more neighboring land cells than the threshold. I was initially hoping only to get rid of the "pier" border shapes, but the overall shape was improved by applying this logic (Fig 6). Later on I tried smoothing the contour lines as well, but I am not decided, whether the change made the relief nicer. The land looks a bit dull like that (Fig 11). 

(6) - shore line smoothed by cellular automaton
(6) - shore line smoothed by cellular automaton, small inland water bodies still present

The last issue to tackle was to deal with inland water bodies. I didn't really like the small water spots, that were mainly near the shoreline. I ran a flooding algorithm to find all the connected water bodies in the map and counted their area. Ocean is the only water body, that could be disconnected in some cases (landmass could divide the ocean by spreading outside of the window borders -- I don't calculate areas outside of the perspective). If the area of a water body is below the threshold, all pixels in the body are elevated to minimal land height. Larger areas are considered lakes and are colored with a different color to prevent them having the noisy shoreline effect.

Act 3 - Path to the X

The next step was to generate the X mark, choose a landing site and find the route between the two. Logic for the X generation is trivial - random point from a square area enclosing random mountain top is chosen. If the point happens to be water, new point is randomized. 

Landing site is found by randomly selecting an ocean point and drawing horizontal and vertical line through the point. The first intersection with land from N, S, W and E direction is considered a candidate for landing point. If no candidate is found, new ocean pixel is randomized. Random point from the candidate list is chosen as the landing point. This should guarantee, that the landing point is reachable from open sea. It does not guarantee the point to be on the same land mass as the treasure though.

The pathfinding was a bit more complicated. Again, I wanted to try some simple algorithm and study the "correct" techniques from other contenders later. Initially I wanted to use some greedy algorithm, that would choose the direction of next step. I tried working with 4 and 8 directions, but the results were really ugly due to the number of directions limitation and the frequency of direction changes. I was searching for a way to make the turns smoother and ended up combining the Poisson disc and spline.

Poisson disc allowed me to consider different angles of next move without the need for evaluating every pixel in range. In the final version, Poisson spread distance is 5, maximal move distance in the path is 30, and only ~70 points needs to be evaluated in each step (circle with radius 30 has ~2800 pixels). The increase in step length also reduced the number of changes and the path looked much smoother. 

The metric for greedily finding the best move consisted of:

  1. Difference in distance to target between last situation and evaluated move 
  2. Difference in height between last situation and evaluated move
  3. Difference in distance between second to last situation and evaluated move

Component 1. should direct the path toward target. Component 2. should make the pathfinder more likely to stay on the same height level, or move to lower height (I am searching for path X->landing point). Component 3. was meant to prevent zig-zag patterns and make it harder to double back. Note, that the algorithm does not care about the pixels that needs to be traversed to get from last point to evaluated target.

The pathing was terrible and quite often resulted in deadlock, when several moves were repeated multiple times. The main culprit was actually the component 3, that I hoped to prevent this. The deadlock usually happened when greedy algorithm decided to move along the shore instead of moving through center of the island, because it seemed to lead towards target. The shoreline turned away from target after several steps and there was now a mountain range in between walker and the target. The algorithm gave a heavy malus to "moving back to crossroad" alternative and also to "climb up the mountain" alternative resulting in moving in small circle formed by lowland points.

(7) - pathing algorithm choosing the wrong direction at crossroad, but eventually recovering
(7) - pathing algorithm choosing the wrong direction at crossroad, but eventually recovering

I tried to solve the problem by discarding component 3. and making a rule to discard any point that has been already visited from search. The algorithm was able to eventually reach the target now (Fig 7), although there was still much to be desired. The malus for climbing up was still too big and the algorithm tried to desperately stay in lowlands. I tweaked it a bit to consider the ratios instead of differences in components 1. and 2. This means, that climbing from 16 to 17 (0.94) is actually less costly then from 1 to 2 (0.5) and turning away from target direction is more tolerated when far from target. I also added malus for moving in lowlands to prevent boring "lets go the shortest way to shore and then move along until we hit landing point" paths.

There were still problems with drunkard path segments, that was caused by algorithm trying out all the possible points in the area until it is forced to move through an undesirable point. I decided it is not worth trying to tweak the greedy algorithm any more and just post-processed the path. The path is traversed in reverse direction and if there is a possibility to move (point is in specified range) to a point with higher index, all the points in between are discarded. This method sometimes causes a sharp turn to appear in the final path (Fig 8), but it is still better, than the drunkard path segments.

"(9)
(9) - Post processed path with a sharp artifact

I was satisfied with this result. The last finishing touch was to make the dashed line. LibGDX has a neat tool to compute the points creating the spline from several reference points. The reference points were the ones found by pathfinding algorithm. Drawing the computed points made a nice solid line, but I yearned for a dashed line (Fig. 10), that seems to be a bit more popular on treasure maps. This was actually done by adjusting the number of computed points to depend on the number of reference points and rendering only points with indexes 0-100, 200-300 and so on. Length of the dashes should be similar in every generated map.

(10) - dashed line leading to treasure
(10) - dashed line leading to treasure
(11) - smoothing the contour lines with celular automaton
(11) - smoothing the contour lines with cellular automaton

Act 4 - compiling to JS/HTML5

During the development I tried to build HTML5 versions via GWT as well. Soon, I found out, that writing apps runnable on web this way is a different beast and one has to carefully optimize the code. An early prototype, that on desktop took ~10 secs to generate a map, needed ~5 minutes to finish as web app. Main issues were creating new objects way to often (inside a loop) and setting every pixel in the pixmap after every generation step (after all the points of height x has been processed). The first issue were dealt with by reusing the objects inside procedures. The second issue made me to only update pixels, that has been processed and they will not be changed for the rest of heightmap generation process. Filling up the pixmap with water color beforehand was also great time saver. After the tweaks the generation times changed to ~3 secs on desktop and ~7 secs on web.

I originally wanted to have the HTML5 version publicly available as well, but there has been an issue with converting a code from Poisson disc library, that I use for pathfinding. The library uses java.awt.geom.Point2D and the GWT compiler doesn't seem to able to get the source code of Point2D from Java suite and therefore is not able to convert it to javascript. I might write my own Poisson disc implementation in the future, that doesn't use Point2D, which would solve the issue. As of now, only an early prototype is available on web.