Solving the Problems of Azeroth

My Mage managed to ding level 56 last night, while thinning out the population of Un'goro Crater. As I systematically eliminated a variety of Pterodax, Ooze, and Dinos I realized that I was racking up requirements for no less than 4 quests simultaneously. It's not unusual to see the counters up for 1 or even 2 quests at a time, but...4?

Amazing.

I mentioned previously that I'm following a leveling guide, at least for the past few levels, and I am truly in awe of the person who put it together. It reminds me of something from my college days that I thought would never have a practical application. Let me explain.

One of my classes in the field of Operations Research involved methods of solving difficult problems. Perhaps the most difficult problem is the Traveling Salesman Problem. This is a classic problem that has been taught for many, many years. Here's how it goes:

A traveling salesman needs to make sales calls in 4 different cities. Given the distance between each city find the optimal (shortest) route which includes all cities only once and returns to the starting point.

At first glance this may not seem to be a difficult problem to solve, and in fact if you only have 4 cities you can probably look at a map and figure out the fastest route. But...if you add additional cities, say 10 or 20 or more, it then becomes much more difficult.

There are only two way to solve this problem. The brute force method involves computing each possible combination of paths in turn and then selecting the shortest one. The number of possible routes for 4 cities is 4! (4 factorial), which is 4x3x2x1 = 24 possible routes. This is certainly manageable, tedious with pencil and paper, but simple if you use a computer. As you increase the number of cities, however, it gets exponentially harder.

Number of Cities	Possible Routes
5	120
10	103,628,800
15	1,307,674,368,000

Using a computer, you could still use the brute force method, but even a computer takes a good long time to calculate and compare over a trillion possibilities.

The second way to approach the problem is by using some sort of heuristic method. This essentially means that you make a series of educated guesses as to a good route, then compare other possible routes to your guess to see if they are better or worse. There are several possible algorithms designed to tackle this, and using any one of them you will get a good answer, but you will never be able to prove that you have the best route since you didn't test all of the possibilities. Looking at the map to guess which route is best for the initial example of 4 cities was essentially an heuristic method, since you would be eliminating the obviously longer routes based on your innate perception of distance. Unfortunately once you increase the number of cities you quickly outstrip the capability of this common-sense approach.

The point of this little ramble is that creating a leveling guide is much like solving the traveling salesman problem. Each quest is like a city, but even more complicated, because there are not only locations for quests, but also varying degrees of travel difficulty, different modes of transport available to different classes of characters, and prerequisites. There can also be multiple requirements for each quest, and they can begin and end in different locations. In short, a huge number of variations which would make the brute force approach to solving the problem even more daunting. There are also several constraints which limit the possible routes to take in completing quests, such as quests available only to one faction, race, class, or profession. And of course the menu of possible quests changes as you progress through the levels with new ones popping up and old ones going gray.

I'm pretty sure that the guide's creator didn't use the brute force approach, since in addition to requiring a huge amount of time and computing resources to solve, it would also require an extensive database of quest information to be compiled and programmed. Therefore the guide must be the result of an heuristic solution, otherwise known as educated guessing confirmed by experience gained by leveling multiple characters. I'd go even further and guess that the convergence of 4 simultaneous quests was more of a happy coincidence than a planned outcome. If I were to try to create a guide, here's how I would proceed.

First, I would narrow down the possible quests by faction and level, and then use Thottbot to find the ones with the largest XP rewards. Then, I'd try to find those featuring common locations and try to group them together. Finally, I'd draw myself a map and try stringing them together in several different ways. Once I had a route that looked pretty good, I'd run a character through it making careful notes on locations, the collection of items, and the rewards gained.

This is certainly a very tedious and time consuming approach, made even worse by the fact that it takes a considerable amount of time to get the test characters to the right level in the first place. And of course there's no way to guarantee that I would find the best solution, in fact my route might only be mediocre. Bet even so, it would still be much better and faster than randomly wandering through quest-givers never knowing if there was a better way.

So, to those who have taken the time to create a leveling guide, my hat is off to you, and you have my thanks. There may in fact be a better and faster way to level a character than your way, but I doubt that we will ever know for sure.

For more information on the Traveling Salesman Problem click here.

Making it Real

My main being a Mage, I feel so sorry for the rest of you non-Mages. Really, I do. I've already published a list of the best Mage characteristics, and today I want to expand on one a little bit.

The first thing in my list of Mage-arific abilities had to do with travel. For you non-Mages, know this: we'll beat you back to the tavern every time. Beginning at level 20 Mages can learn spells which allow them to instantly travel from wherever they are to either Ironforge or Stormwind, just like using a Hearthstone. At level 30 Darnassus becomes available as well, and Exodar too, though I haven't bothered with that one yet, since you do have to show up in the city once in order to learn the spell. At higher levels Portal spells are added so you can take your friends along with you.

While these are certainly convenient time-savers, what made a big difference for me was the role play opportunities that opened up for my character. I am a casual player, and even though I have enjoyed RP events many a time I often resent the feeling of wasted time that builds up when things drag on seemingly without direction. Imagine how much more frustrating this could be if I had to walk/ride/fly from Darnassus to Stormwind to attend?

When the Council of Magi was a functioning guild, I participated in 2-3 weekly RP events. Our back story included our base in Stormwind so almost all events were there. We used the Park for book readings, the Blue Recluse for social events, and the Dwarven Hall for guild meetings and formal events. In fact, one of the best parts of playing WoW during that time was how alive the cities - Stormwind in particular - felt to me. Since all of my guildies were also Mages, we would often cross paths in the Wizard's Sanctum, the tower in the Mage District that held the class trainers and the portal spell destination. No matter where we happened to be in our levelling progress, we'd all converge in Stormwind frantically trying to be on-time for these events. For Robing Ceremonies which we used to initiate new members I used my meager tailoring skills to provide crafted robes to the initiates. Naturally we never knew in advance exactly what type and quantity was needed, so I would run around gathering mats from the AH or friends at the last moment. Then I would stagger into the meeting hauling several large bags stuffed with robes and documents like the frazzled old geezer that I was. If I was in the mood I'd even provide some narrative in guild chat for the amusement of all. It was fun, and considering my limited play time it would have been nearly impossible were I not a Mage.

So, having easy access to Stormwind made the city feel alive and personal. Even though I've really cut back on the RP due to time restrictions, I still feel that Stormwind is my home. I know where the important NPC's are, and I remember their names. I have my favorite auctioneer. The picture next to my profile on this page is taken next to my mailbox.

One quiet afternoon the guild chat turned to all of the empty buildings in Ironforge, and how there didn't seem to be any in Stormwind. Of course several of us then had to scour the city looking for them, and I've made it a point to really explore from time to time ever since. Though we didn't find anything that we could call a house in Stormwind, there is an empty Inn in the Park that I must have walked past 100 times without seeing it. It's similar to all the other Stormwind Inns, even the jaunty music plays, but there's no inkeeper or bartender. The well in front of the Slaughtered Lamb is perfect for small meetings, like guild officers, as long as a passing Warlock doesn't ruin your fun. There's a ledge overlooking the Moonwell in the Park that's perfect for snapping that large group photo. There's a little corner off the ramp to the Gryphons that I fell into and had to Hearthstone out of.

One of the oft repeated suggestions for new features in WoW is the addition of guild halls and/or player owned buildings. These would be great, but people do manage pretty well anyway. I know of two guilds that use the Westbrook Garrison as their home base. Oddly, even though they're on the same server they never ran into each other once. The Council was briefly on a quest for an appropriate location for their secret library, and we were leaning toward a room downstairs in the Cathedral of Light that had several tables along with bookcases. Of course it didn't fit the lore very well to have it in the cathedral. We might have used the Mage tower in the way to Redridge Mountains if the guild had held together. That would have fit the lore.

Looking for something a little more private? One of our guildies discovered a place along the Deep Run Tram tunnel where we could jump off. There was plenty of room for a whole bunch of people, and you could walk down the tunnel from the station if you were careful of the tram. There were some drawbacks...it was pretty dark, requiring a video adjustment for visibility, and first time visitors were apt to ride by on the tram several times before leaping to their death.

One guild event, a sort of open-ended RP that went on too long, started out great. The best part was the location....a room in Northridge Abbey that included the Priest Trainer for newbies. We had about 15 characters seated on benches, with one or two standing up talking. Every few minutes a level 2 Priest would wander in and wonder what the hell was going on. I hope that seeing this group together made these new players think WoW was a really cool game.

To AoE or not to AoE

Surely anyone with a mild interest in Mage tactics and some spare time at work has read about AoE grinding. I had one experience with this Mage-only (except for Pallies sometimes I hear) ability. I was grinding turtles in Dustwallow Marsh when a fellow Mage - guildie of mine - showed up. We decided to team up and try out AoE on the local Murlock population. Being the noob that I am (and was then) my partner was in the driver's seat, I was just along for the ride and to try to learn something.

She was Frost and had read up on the how-to and where-to for AoE. There's a group of Murlocks down at the south end of the beach with no casters off by themselves behind a hill. I was Fire and didn't really know what to do, but the plan was for her to round up some mobs, Frost Nova them, and blink over next to me at max Blizzard range. Then we would both unleash Blizzard and hopefully kill them all before they reached us.

The first attempt, she rounded them up, Nova-ed them and Blinked over to me. We got off one full Blizzard each, then had to scatter. Some were dead but most were not. We Blinked off in separate directions, Blizzarding between us, until one or both of us were oom and dead. Since the plan must have been sound, we tried this several times with similar disappointing results. Eventually we gave up, but not before I learned the following valuable lessons:

• This partner mode AoE grinding may be viable, but never assume that your partner has a good understanding of the mechanics unless he/she can explain it back to you. My partner knew what she was doing, but I didn't, and therefore I was not able to help out as much as I could have otherwise. Being a noob and knowing it, I elected not to advertise my ignorance, and instead demonstrated it.
• Make sure the coast is clear (groan) before starting. Our location featured a couple of Coastrunners that ran in big circles around the whole camp. Until we learned to take them out separately they would show up at the wrong time and screw everything up.
• Fire Mages are not the best choice...with no Frost Shield or Ice Block I was toast if anything went wrong. Mana Shield was no substitute because it left me oom with no options.
• Anything that causes your carefully grouped mobs to spread out results in big trouble. It is important to pass over talents like Frostbite that could leave the mobs advancing at different speeds. In counterpoint to the famous saying, united they fall.
• Try to find a place close to a grave yard.

Since I've been following a levelling guide I'm quite pleased with my progress, so the temptation to further experiment with AoE has faded. Looking back, the initial attraction was due to abandoning the Mage quest chain in Dustwallow due to frustration, and questing really is more interesting I think. If I had been Frost along with my partner, I think we would have figured it out that day. Partner AoE might not be as lucrative as solo AoE, but it would still seem to be worthwhile if you could survive it.