Rotmg Map Seeds

Back in 2010, I wrote a map generator in Flash. The authors of Realm of the Mad God used it to generate thirteen maps^[1] that shipped with the game. The authors don’t remember the map seeds they put into the map generator.

I’ve been curious what the map seeds were.

I told myself at the time that it would be a pain to recover the seeds. There are 2³² = 4 billion map seeds. It took 5 seconds to generate each map. That’d take 20 billion seconds, or around 630 years, to generate all the maps, each with 2²² = 4 million tiles.

 1  Point selection#

How can I speed this up?

1. Instead of generating all 4 million tiles per map seed, I can test a handful of tiles first, and skip the rest if those tiles don’t match.
2. Instead of using the full map generation (delaunay, flood fill, distance fields, and other algorithms) on those tiles, I can run only the first step, which marks which tiles are land and which are water.

The land vs water test uses one of four functions in the IslandShape class^[2]:

1. makeRadial() uses overlapping sine waves in polar coordinates.
2. makePerlin() uses Perlin Noise along with an island-shaping function.
3. makeSquare() fills the entire map. This is not used for RotMG maps.
4. makeBlob() uses my blob logo shape. This is used for World 12.

If the tile doesn’t match, does it mean I can rule out the map seed? No. The remaining steps can change whether it’s land or water, and Realm of the Mad God implemented further steps that I don’t have access to. All I can say is that if it doesn’t match, the map seed is less likely to be what I’m looking for.

If I test lots of points and most of them are matches, then that map seed is a candidate.

Not all points are equally useful. For example, the points at the corners of the map are always water. Testing them doesn’t rule out any map seeds. The points in the center of the map are usually land. Testing them rarely rules out a map seed.

I think most of the maps are using makePerlin() so I looked at that function:

return function (q:Point):Boolean {
    var c:Number = (perlin.getPixel(int((q.x+1)*128), int((q.y+1)*128)) & 0xff) / 255.0;
    return c > (0.3+0.3*q.length*q.length);
};

The value of c will be between 0.0 and 1.0. If it’s higher than the threshold, it will be land. If it’s lower, it will be water.

A high chance of mismatch is when the candidate map and an average map do not match. For example, if most maps have land at some (x,y), but the map we are looking for has water, then that’s a good (x,y) to put in the test set. Given the eleven generated maps, we can look for (x,y) points that don’t match the average map, and use those as ideal test points.

What is the coordinate system for the q:Point input? I found it here:

public function inside(p:Point):Boolean {
    return islandShape(new Point(2*(p.x/SIZE - 0.5), 2*(p.y/SIZE - 0.5)));
}

SIZE is the resolution of the image. So p.x/SIZE will range from 0.0 to 1.0. And (p.x/SIZE - 0.5) will range from -0.5 to +0.5. And 2*(p.x/SIZE - 0.5) will range from -1.0 to +1.0. That’s the range for q:Point.

I made a separate page to explore how to best select points. I initially made it interactive, thinking I’ll click on a few points on this blend of the eleven generated maps:

But then I decided I wanted to analyze the points. How often would the average map have Land or Water? The results matched my intuition:

But the maps we’re looking for aren’t the average map. I counted how often the point was different from average:

Those are the points that will give us the most information through testing.

I realized while thinking about this that the point selection is not the interesting problem. It’s a side quest. It’s a distraction. I suspect it won’t matter that much as long as I have a reasonable set of points. So I picked all of the grid points instead of trying to pick the best ones.

 2  Seed testing#

I tested these points, with roughly this code structure, and the Ruffle Flash Player emulator^[3]:

for seed from 0 to 2^32-1:
    generate the perlin noise map
    for point in test_points:
        for desired_map in target_worlds:
            check generated_map[point] == desired_map[point]

Turns out the bottleneck is per seed rather than per test point. That meant the time I spent trying to pick the “best” points was wasted!

I considered more ways to speed up the search:

1. For each seed, I’m using Flash’s Perlin noise function to generate all values in a 256✕256 grid. I don’t need that many. I could generate a lower resolution grid, and then test all of those points. → medium win
2. I could bypass Flash’s function and generate values only for a small set of test points. I don’t have access to Flash’s source code, but Ruffle has reverse engineered it, and I could look at their code^[4]. → didn’t try
3. Although there are 2³² seeds, the UI’s “Random” button picks from the first 100,000. I think it’s reasonable to think the Realm of the Mad God authors clicked “Random” repeatedly until they found a map they liked, instead of typing in seed values in the tiny input box. → big win

I also tested the radial function but got no matches at first. It’s because I had a bug — my original Flash code used true for land, but for some reason I had false for land in this project. I should have used the same convention to minimize the chance of bugs. After fixing this bug, I got some matches.

 3  Results#

Overall I think this was successful! I found map seeds that produce outputs that are similar to the Realm of the Mad God maps:

world	rotmg from realmeye[5]	seed	mapgen2 from my page[6]
1
2		perlin 20927-1
3		perlin 84542-1
4
5		perlin 30997-1
6
7		perlin 65166-1
8		perlin 7785-1
9		perlin 43671-1
10
11		perlin 59103-1
12		blob
13		radial, many

I didn’t find World 13 exactly, but I found several that are similar:

Why don’t any of the results match exactly?

1. The elevation function used in Realm of the Mad God is not exactly the same as what I used in mapgen2. Sometimes they’ll have shallow water where I have land. They also remove unconnected islands. I believe they also flatten out some of the ground to place buildings / quest sites.
2. The rivers and biomes depend on the map variant after the dash in the map seed. Try map seeds 20927-1 through 20927-9 to see how the island shape stays the same but the rivers and biomes change. I did not try to figure out which variant was used. They use my rivers but they have their own code for biomes.
3. I searched using a quick approximation instead of testing precisely, and it’s possible another output would be an even better match with a better comparison function.

Why didn’t I find all the seeds?

1. It’s possible they used some map seeds greater than 100,000. I only tested up to that point.
2. I had good luck with the Perlin island shape function and less luck with the Radial shape function.

This was both a fun and frustrating project. It has given me some ideas for future projects. For example, if I can construct a metric for “normal” then I can look for “abnormal” maps in my other map generator projects. In this project I defined normal to be a circular island shape, and then found outliers like these:

Another thing I could do is look for seeds that produce similar outputs. I found it was common with the Radial shape function, but there must be some for the Perlin shape function too. Look closely at World 2 and you’ll see it doesn’t quite match perlin 20927-1 in many places. Could it be that there’s a different seed that produces a very similar map with slightly different details? I don’t know.

This project made me stop thinking of map generation as seed → map and instead of as set of seeds → set of maps. There are papers about “expressive range generation” that explore this topic with procedural content generation.