Global mapping - a story of invention

When I first started this mapping project, my goals were grandiose. I had a vision of the dclient showing a very high level map with the location of cities and perhaps roads between them, updating a small amount in real time as you walked from place to place.

This large vision seemed so close, and yet so far - while easy in principle, the biggest issue was in generating the maps. Mud areas in general do not have to respect linearity. You can arbitrarily connect any room to any other room; in short, generating a cartesian, mappable layout becomes a builder constraint, not a tool constraint.

When faced with 20k rooms of previously built nonlinear content, the task seemed ridiculous and daunting. Initially, I tried piecemeal mapping: each area would have an internal, generated layout, and we'd try to move them around like puzzle pieces to get everything to fit. This didn't really work that well, but some new mapping tools were built and I was able to collect a lot more data.

The next idea was to try a form of annealing, where rooms would update their x/y/z coordinates based on what rooms they were connected to. This worked slightly better, in that it tended to smooth out big gaps and it forced areas to fit in places they didn't before. But it had the drawback of taking a very long time to settle, and it still didn't deal with nonlinearities.

Around this time, the idea of the big/small room distinction came about. Cities on maps are generally very small compared to the surrounding landscape; in Alter Aeon, this was definitely not true. The main city of Ralnoth was easily half as long as the Great Southern Road. I decided to declare cities, towns, buildings and other terrain as 'much smaller' than outdoor/wilderness/linkage areas.

This big/small transition appeared to work very well on the few initial areas I tried it on. Older areas required the most rework, but a lot of 'small' areas had limited linkage to their surroundings anyway, and the transition was easy. The southeast portion of the continent was hit the hardest, as it was designed on a unified grid. It had to be extensively retconned, but even that work happened quickly thanks to the dedication of Draak and Shadowfax.

As part of the big/small experiments, I extended the previously failed area map code to cross all zones, and used that to generate some cheesy room maps showing absolute and relative positions of everything. After a bit more work, I was able to show nonlinear linkages on the maps as well - and this is when things really started to get done. Seeing the problem spots, it was surprising how few of them there really were. We began to aggressively target those.

Meanwhile, the annealing/smoothing code was running in the background, continuously updating the 'real' positions of rooms, as opposed to where we thought they should be. The most recent advance was the realization that the 'perfect' and 'real' maps should be as close to each other as possible, and in fact the 'real' map should try to match the 'perfect' map. I made a few very minor changes to the algorithm, and the global map consistency (not to mention convergence speed) has increased greatly.

After all of this, I'm almost to the point where I can generate the high-level maps I originally wanted in the first place.

The lesson to take away is that invention happens in bursts and is often triggered by random things. Ideas are easy, but implementing them is hard; further, you never know which experiments are going to fail or succeed until you spend time on them. There were several dead ends along the way in this project, but each provided tooling or insight into new things to try.

Overall, if I had known the final form of things at the beginning, all of the code work could probably have been done in a couple of weeks, and all of the area work to follow in another month (with builder help of course). As it stands now, the mapping saga has been going on since the beginning of the year, with breakthroughs and advances from time to time.