New Maps Available!

I finally got the server to generate what I consider an acceptable quality map from the live game data. These maps show a rough outline of where areas are, with lines for roads, trails, and rivers, and area fill for water. I'm actually really proud of these - a year ago I wouldn't have really thought this possible.

This would pretty much have been impossible without all the mapping work that has been going on, but that mapping work couldn't have been done without previous versions of the mapper. Either way, things are looking pretty good these days.

You can find the new maps listed as 'trade route' maps on the main maps page:

http://www.alteraeon.com/maps

Or, see these links for individual map pages of Sloe, Kordan, and Archais.

Various updates

It's been a while since I posted, so I thought I would just drop a general overview of what's been going on in the last couple of weeks.

The largest major change, at least in terms of useful functionality, has been updates to the grouping code. I've been playing a lot, and I've noticed that putting together groups is a lot harder than it really should be. This is a social game, after all. Getting people together into fun, functional groups is part of the process.

After that are changes to the who listings. I quickly prototyped a 'who idle' command on request, but within about five minutes of first using it I was in love. I ended up adding a bunch of who list configuration switches; see 'set who' for options and status. You can now change from the default who display to idle time based, list short or long form, and enable or disable microlevels and titles. I haven't even gotten any complaints about it.

One big yet unobvious change had to do with the PRNG (pseudo random number generator) upon which the game is based. For quite some time now, I've been using a pretty fast lagged fibbonacci generator instead of a linear congruential. On a whim, I downloaded the diehard PRNG tests and tried them out. As expected, the old random number generator failed a lot of them horribly.

So, I ripped the old one out and put in a new one that does actually pass the tests. Other than monster lore sends changing, noone will ever notice - and I can rest slightly more assured that there's not hidden correlations lurking in my generator that are causing weird behavior.

Last on the list of big ticket things is, of course, mapper updates. We've got global area maps that are almost ready for general public display. I'd really like to have oceanography working first, so maybe I'll work on that a bit tonight.

All in all, a lot more getting done than I expected. It's been a good week.

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.

Sailing the seven seas

As a side effect of the ongoing mapping and world linearization project, I had a strange idea: why can't I hop in a boat and sail from the mainland to the islands?

The short answer is that in most muds, rooms have no absolute position data. Since this is no longer true for Alter Aeon, having long-distance boats suddenly seemed possible. So, I set aside a short period of time to do it.

It was nowhere near enough.

As a first step, I created boats and allowed some lookup of position to figure out where I could place them. This worked reasonably well.

For the second step, built a quick lookup function to go from boat position back to nearest room. This allows people to disembark.

Next, I had planned to simply use that lookup function to build maps, so that sailing around would have a functional map display. We can also use the map generator to construct blind descriptions, so that blind players can still see when land is near. This is where the problems began.

While we do in fact have positional data for rooms, the reverse lookup is quite a bit less trivial. In order to build maps, the lookup has to be quick and efficient. To complicate matters, the world grid moves around dynamically the rebuild time has to be short as well. There are also difficulties with a single room appearing in multiple places, and with multiple rooms vying for the same space.

I initially tried a rather complex space partitioning scheme, but after sleeping on it I realized I should just use a hash table. I implemented the various hash table routines in about an hour, and with around 3 hours total I have most of the corner cases cleaned up in the map.

Next, I pull up the anchors and see about doing some exploring.

The mapping saga continues

While in the dentist's office yesterday, I had a brainstorm regarding mapping: why not run a real-time simulated annealing algorithm to automatically generate the global coordinate grid? When I got home, I took a few hours to implement it, and last night I booted an initial version into the game.

These new position values don't currently do anything, as I'm still working out the bugs and looking for general problems. One thing that appears to cause quite a bit of trouble are nonlinear 'portal' links that bridge a large distance; another major problem are god/builder rooms that link to unusual locations for plot device reasons.

Flagging these troublesome exits isn't something we can currently do, but it's become clear that we will need to do so in order to make the grid coherent.

Finding the problem exits is also difficult, but it's made somewhat easier by an extension to one of our existing mapping routines. By calculating a 'stress energy' for the linkages in each room in the map, I can get a pretty graph showing where maximum grid distortion occurs. These points of maximum distortion usually occur near a positional anchor, which are used to set the position of continents or isolated zones.

However, once the map for a given area has stabilized, the maximum distortion points typically indicate one of the nonlinear links described above. Once the approximate location is known, finding and marking the link is substantially easier.

All in all, I think this is working well enough that we may be able to use it globally for all area placement. Over the next week or two I'll be generating some area and room maps based on this data, and we should be able to refresh the god area and room maps on the web pages soon.

Remapping of cities

In the quest for linearity and mapping in the game, the answer for towns and cities is clear and obvious: all rooms are the same size. I remapped and expanded the main city in Alter Aeon today, which really cleared up a lot of conflicts and has left no rooms on top of each other. It maps clean, and it wasn't even a lot of work. Here's an example of the client map for the new version:



There's lots of roads, lots of places for shops and other stuff, and a few dead spots to allow for expansion. Most of the player comments have been positive, which is surprising - generally anything that messes up someone's directions causes all kinds of havoc.

This doesn't address the issue of how to handle large expanses of space though, for example forests and other linkage areas. You really don't get an idea of how big the world is until you put into perspective the relative size of cities.

Take for example, my home town. It's a small town of 5-10k people, and from the recent Google maps it's a little over a mile in diameter. Meanwhile, the state in which in which it's located is around 250 miles in diameter (except that its squarish.) Take a penny and tape it to your wall. That's the size difference, and that's just one state, not an entire continent. For a continent, tape a quarter to skyscraper.

I'd like to think Ralnoth in the game is probably about the same size. The currently expanded Ralnoth is about 12 rooms wide and 25 tall; let's say 15 for the sake of argument. Meanwhile, the entire game is perhaps 400 rooms across and tall, neglecting portals to islands and the like. This makes the entire Alter Aeon mainland around 30 miles in diameter.

We have entire mountain ranges, jungles, swamps, other cities, and the shores of two oceans on the mainland. All within 15 miles of the central city of Ralnoth. Starting to see the picture?

A more reasonable continent size is on the order of 500-1000 miles. Even for a 500 mile wide continent, the scale of Ralnoth would imply walking through a minimum of 7500 rooms to get from one side to the other. This is probably not reasonable from a gameplay standpoint, so we need to find a different approach.

The simplest and easiest is to simply define cities to be much larger than they are. If we declare Ralnoth to be ten miles across instead of 1, we end up with a much more reasonable room count. But in that case, even the smallest house represents half a square mile of land area.

A better approach seems to be to change the size of roads and paths, such that the desired distances can be achieved. This kills the dull/boring wilderness areas and gets people out into the world to do something interesting.

I think there's a couple of different ways to handle this. One is to have different sized rooms and render them as best you can. Perhaps using terrain or other flags you can automatically decide what rooms are what size.

But it seems to me that a far better and easier way is to separate large and small sized zones from each other. When you leave one, you end up in the other with a different set of maps. For example, leaving a town shows the town zooming to a small size relative to the forest you're walking in. So many games have done this in the past, that it's a trivially obvious feature. It also happens to be a very good candidate for my overall mapping problems.

I'll let you all know if it works out.

Maps and area layout

One of our players, Woem, mailed me a handful of area descriptions and maps a couple of days ago. I finally managed to get through my email, and have put them online here:

http://dentinmud.org/maps

They're the maps of the Aggerazzi Swamp, the Fire Plane, and the Ice Plane. They're hand drawn, but really well done.

This got me thinking about mapping in general. Muds are particularly difficult to map because of the ad-hoc room linkage and arbitrary room sizes, not to mention lack of sanity checks to detect overlapping rooms. I'd like to be able to do it anyway because people are so visual, but there are some problems.

One of the biggest problems is that building is already so restricted, in that we generally have cardinal directions, without any real ability to place slopes or other such three-dimensional constructs. Another really big problem is that we don't build rooms with any regard for size; rooms just are, and they hold whatever we need them to hold. Further, we can hook them up to anything else without regard for space constraints.

To top this all off, Alter Aeon has over 30k rooms that are -already built-, and over two thirds of those are in working, sane areas. Rebuilding those areas with some (as yet ill-defined) positional features is really out of the question in the short term.

This has brought me back to thinking about automatic determination of room sizes, or at least room positions within areas. Some of this can be done based on terrain types; most individual areas can be mapped pretty well using a simple combination of flags and terrain to give rough sizes. The real clobbering comes when you attempt to glue areas together.

So, assuming I can automatically place the rooms in individual areas, how do we place areas overall? It turns out that we happen to have positional information for most areas anyway, so all that remains is to tie the area coordinates to the room positions within each area. The game can then scan for room linkages where the areas are markedly disjoint, and log it as a typo or bug.

Ta-da! With that, we should be able to correlate the real room position with the real area positions, and while the hookups wont be perfect, it will give us a very good idea of where the worst disconnects are.

Hopefully I can get some time to try this out in the near future. It's probably a handful of hours to do it and get it right, then I can hand off the cleanup to some of the worldbuilders and let them straighten out the worst of it.