Saturday, November 28, 2009

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.

Wednesday, November 25, 2009

An Example of Mob IACT Programming

[Reposted from the Alter Aeon Forums.]

An 'iact' is a type of interactive procedure that is used to make mobs perform actions. You can do some pretty complicated stuff with them, including interactive (hence the name) discussions, intelligent quest triggering, and the like. As examples, Thantos responds to Dentin's name, and the fire giants in the fire plane will give up quite a bit of history of the area if you just sit down and talk to them about it.

As common as these are, there's a lot of confusion about how iacts work. Most of this seems to stem from the fact that iacts are a form of finite state machine, and most people aren't used to thinking in state machine terms.

As an example, let's consider a mob that would unpack and wield weapons when fighting, then stop using and put them away when not fighting. This seems like an ideal example to demonstrate a simple state machine iact, as well as give an introduction to how iacts work.

The general idea is that the mob in question, let's call him Bob, has a weapon and a backpack. When Bob is in combat, the weapon should be out of the backpack and wielded, so Bob can defend himself. When Bob is not fighting, the weapon should be stored in the backpack, which Bob should be wearing.

The easiest way to do this is via four states in a state machine:

1) Not fighting. In this state, you wait for fighting to begin.
2) Start fighting. In this state, Bob is fighting, and should unpack his weapon and wield it.
3) Fighting. Bob is fighting for his life, and may need to retrieve his weapon if disarmed.
4) Stop fighting. Bob is no longer fighting, and should disarm and repack his weapon.

Here's a diagram of the four states, with the arrows being transitions between the states. Each block contains the name of an iact procedure, and in smaller text the iact code for that procedure:



Click on the image for a larger version.

As various things happen to Bob, he moves from one state to another. Most of his time will be spent waiting for fighting to start. When fighting does start, he'll quickly get out and wield his weapon in the 'start_fighting' procedure, then he'll transition to the 'fighting' procedure. While 'fighting', he'll continuously try to rewield his weapon if he's disarmed. When fighting stops, he'll transition to 'stop_fighting', which will unwield the weapon and put it away. Then he'll go back to 'not_fighting' and wait for another battle to begin.

Sunday, November 22, 2009

I'm a deadbeat

I was looking at the list of big-ticket/high priority items on my whiteboard, and it occurred to me that a lot of them are half done.

Not the good kind of half done, where it's a huge project and a lot of pieces are in and functional.

The bad kind of done where infrastructure is in place and working, but it's not doing anything valid in the game context.

A good example of this is the recent boat code. This largely works, and probably only needs a couple of hours to get it in god-level beta test. Instead, it's sitting there in the code base, largely complete but unconnected.

How about clan wars? I spent time adding a lot of infrastructure for this, then never hooked it up. It also probably doesn't need more than a few hours to get it in beta test.

Classes are a bigger picture. I have more structure reworks to do, but I have been avoiding them. This one is a bit more understandable, because the project is so large - but this isn't exactly a huge piece of the puzzle.

Part of the reason for this is because I'm constantly 'firefighting' instead of doing new development. I'm always fixing minor bugs, heading off social/political issues, trying to manage things and people. I'm starting to think it would perhaps be better for all involved if I simply stayed invisible most of the time. I used to do that a lot, for exactly this reason, but for some reason fell out of the habit.

Another part of the reason is that the detail work isn't any fun. It's painstaking and precise, and there's always negative feedback from players to look forward to. Nevertheless, leaving a heap of half-finished projects on the queue isn't helping anything either.

No pain no gain, perhaps.

Friday, November 20, 2009

Halloween Havoc

I finally got the event report up for Halloween Havoc! You can see the report on the Alter Aeon System Events page.

This event was special for me in that nearly all of it was run by, well, not me. I was present for some of it, but I actually got to log in and play a mortal for a while. For the most dangerous (in terms of administration) part, the pk arena, Morpheus handled it, with some help from the gods Taran and Draak.

This is a very good thing, and it should teach me a lesson: delegate. We have gods that are capable of running, handling, and managing system events. Let them do it.

I like this plan.

There are also plans for thanksgiving and christmas-time events in the near future.

Tuesday, November 17, 2009

Web Page Updates

Yesterday, I spent far too much time working on changes to the Alter Aeon web site. I spent some time hacking down the menu so that there were fewer items that are better organized; I also managed to switch over the layout to a more standard looking block based design. Along with this came a number of other minor updates and improvements.

It never ceases to amaze me that you can work on a web site, get to the point where you've done the best you can, then come back a month later and improve it even more. For me, it's like my creativity is tapped out - I have to take a break to let new ideas percolate in. I think part of it might also be that I have to get used to a new design or layout before I can compare it against something else.

Regardless, of the half dozen or so people I asked, their opinions were an almost universal 'much better' for the new version. Here's to hoping that this 'much better' translates into a higher conversion into newbies!

For a look at the new layout, here's a link to the Alter Aeon Web Site.

Tuesday, November 10, 2009

Software Reuse

There is an old saying in the nootropic (mental-performance enhancing drug) community:

"The guys in the 60's had this truly brilliant idea of using drugs to expand conciousness and improve thinking. Unfortunately, all they had at the time was LSD." [Just to ensure proper context, this is said without sarcasm. It really was a good idea, however LSD turned out to be a complete flop in achieving this goal.]

I've recently been doing some work that involved C++ templates, so allow me to reword this for modern usage:

"The c++ guys in the 90's had this truly brilliant idea of direct language support for generic code and module reuse. Unfortunately, all they had at the time was c++ templates."

Saturday, November 7, 2009

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.