CosmosUI is an open source interface modification of World of Warcraft. Many of the CosmosUI additions were later implemented by Blizzard on the default interface.

I had been doing Warcraft III map making for more than a year when World of Warcraft has been leaked. This was really exciting to hack into the game and being able to modify it. Since I had no real programming knowledge at the time, I could not help people making a server for the game. However, I found the interface in XML and Lua really interesting and spent some time tweaking it.

There was nothing real to do in the sandbox servers at the time, I spent some time programming MiniGames (TicTacToe, Connect 4) in the interface. I have been remarked by Thott (thottbot.com) that gave me a Beta key in order to work on the open source interface modification project he took part: CosmosUI.

I have been working on CosmosUI during the whole beta and these are my notable additions.

QuestMinion

During the Beta of World of Warcraft, the only way to see your quest progression was to open the quest log and search for the quest you were doing. I made an addon that would show a summary of the quest you wanted in a small movable box located under the minimap by default, read about it on Guided Hacking Forum.

Since I did not want to maintain a standalone version people started making addons with this concept. The most successful is MonkeyQuest downloaded 1 million times. Blizzard added later a Quest Tracker functionality to the World of Warcraft default interface that is a nearly exact copy of QuestMinion. The game Warhammer Online made the same choice for its interface.

Quest Minion

Quest Minion

World of Warcraft

World of Warcraft

Warhammer Online

Warhammer Online

Addonification

At the beginning, CosmosUI was just modifications of the World of Warcraft interface files. This was good for small modifications but once CosmosUI grew, we had to make some tricky diff every time a World of Warcraft patch was released. CosmosUI was the only interface modification at the time, so people would be without interface for about 12-24 hours while we were merging everything.

I found a solution to this problem. Instead of modifying the actual code, we can hook the specified function and put our custom code in another file of our own.

local thefunction_backup = thefunction
thefunction = function (args)
  -- Do what we want before
  thefunction_backup(args)
  -- Do what we want after
end

I first moved my modifications out of the Blizzard code and everyone started to do so. Then a few weeks later Blizzard implemented an addon manager into the game. With the preliminary work we did, it was really easy to transform CosmosUI into an addon without any file dependency.

Localization

When I started working on CosmosUI, it was only available in English. Since I am French, I wanted my fellows to be able to use it in their native language.

CosmosUI being a compilation of multiple addons, I first started to make a translation template and applied it to my own addons. Then I put all the strings of all the CosmosUI addons into their respective English translation file. And finally, I formed a translation team composed of French and German people.

Once everything was translated, I started to advertise CosmosUI in the French community and made the technical support.

Sky - Communication Library

In order to make my MiniGames multiplayer, i had to transfert data between the two players. The only way at the time to achieve it was by text messages. However, they are visible to the user. My work on Sky was to automatically join a channel, hide all messages from this channel, make it invisible to the user and finally intercept the incoming messages.

Since channels were only available with command lines, they weren't used that much and their internal API was really buggy. Most of the job was to find workarounds for these bugs. Sometimes channels weren't saved across sessions, they would be joined there but not listed or not joinable at all. For more information you can read the description on WoWWiki

Quote

Christopher was one of our top contributors on the Cosmos project, overseeing both community relationships in the French community as well as developing several mods within the community. The most revolutionary of these was the Quest Helper addon, which became so infamous and popular that Blizzard added it into their base UI. Christopher was a major contributor to the project's culture, content and community. It would not have been the success it was without his direct contribution and passionate commitment.” April 27, 2009 -- Alexander Brazie, Cosmos UI Team Leader. (LinkedIn)

MMO-Champion is the biggest news website of World of Warcraft. The main page is viewed millions times a month and was done with old school tables. As a result, it was really slow to load but worse, all the content had to be loaded before being displayed.

The first thing I did was to rewrite the whole main page template using clean and valid HTML + CSS. The goal was to make it compatible up to IE6. The rendering was so much pixel perfect that nobody noticed a change when we pushed it live.

The main challenge was to rewrite the menu. Previously, the menu was using several images that were cut in order to make it easy to implement it in CSS. However, it was a torture to add another menu. The new one is now using a single image that is basically a screenshot of the rendered menu.

In order to save bandwidth, if the browser is supporting HTML5, instead of storing the menu state in a cookie, it is saved under the new localStorage feature.

Cineartistes.com

Cineartistes.com

Philippe Pelletier has been gathering information of people working on the cinema industry for years as a hobby. He realized that people could be interested in his work and he could share it over the internet.

The website Cineartistes.com is a database of biographies and filmographies of actors, film directors. Some of them contains a gallery of photographies and film covers. There is a section dedicated to awards (Oscars, Césars ...).

There are two points that make the project unique:
Content is parsed from a Word Document. Philippe Pelletier had thousands of already written Word documents when he asked me to create the website. What he has to do is copy & paste from Word to a textbox. The parser analyzes the text and automatically adds italic, bold and color for filmographies.

Names in biographies are automatically linkified. In order to have a smooth navigation in the site, artists names in the biographies are transformed into links. This is working retroactively and without any special markup for the content manager.

Conference Delphi

Conference Delphi

Together with Alban Perillat-Merceroz, we organized a one-hour presentation of the programming langage Delphi followed by 3 hours of exercises. The objective was to introduce Delphi to the students in order for them to be able to start working on their year project.

Students had no more than two months experience of programming with Caml, a functional (opposite of imperative) language. The first part of the presentation was a comparison between the two paradigms and how to move from interpreted to compiled code. Then, a brief explanation of the various structures of the languages and how to organize files around the project has been explained.

Even if the conference was not mandatory and took place a friday 9pm, there were about 200 students attending. They have been split into two room and attended the presentation made by Alban and myself. Right after, they moved to the computer rooms and started working on the exercises.

The exercises focused on very basic things like function definition, for, while and structures for the most advanced. We formed a team of 15 people helping everyone out. Overall, this has been a success. You can download the Presentation Slides (Powerpoint 2007), Exercises subject (PDF) and Correction (ZIP).

A school project was to find the shortest path in a dungeon graph. You start with an amount of hit points, and each edge gives or removes hit points. You have to find the path from two points going through the minimum of edges (no matter their value) alive (hp > 0 all along the path). The difficulty here is that you have to go a finite amount of time through absorbing cycle to complete interesting graphs. Here is the full subject.

Example dungeon graph

Example: dungeon graph

Example: You start with 10 hp. The shortest path is [1, 2], [3, 4, 2] * 492, [3, 5]. You notice that you have to loop a huge number of time on the [3, 4, 2] cycle that gives you 1 hp per run.

The common solutions were either a custom Breadth First Search or Dijkstra algorithm along with a heuristic. It is easy to write, always gives the shortest path and have space for improvement. However, it has a major flaw: it doesn't scale well with high values. Instead of 500, put 50 000 000 and it will run forever.

My approach is to detect the cycles and find the best cycle organization. In this example, you would notice that [3, 4, 2] is a cycle that takes 3 edges and gives 1 hp. You come to this cycle with 9 hp, you need to pass with 501 hp so you need to take this cycle (501 - 9) = 492 times.

Finding Atomic Paths & Cycles

Definition

What we want to do is find all the possible paths going from point A to point B. Since there are cycles involved, you can't just go through and enumerate them all. Instead, you will have to find atomic path that doesn't loop and the smallest possible cycles (you don't want your cycle to repeat itself).

The first definition I took of an atomic path is a path that does not go through the same node twice. However, I found out that is was not taking all possibilities. After some reflexion, I figured out that nodes aren't important, however edges are! So an atomic path is a path that does not go through the same edge twice.

This definition is handy, it also works for cycles: an atomic cycle of point A is an atomic path that goes from point A and ends to point A.

Implementation

Atomic Paths A -> B

In order to get all the path starting from point A, we are going to traverse the graph recursively from the point A. While going through a child, we are going to make a link child -> parent in order to know all the edges we have already crossed. Before we go to that child, we must traverse that linked list and make sure the specified edge has not been already walked through.

When we arrive to the destination point, we can store the path we found.

Freeing the list

A problem occurs when you want to free the linked list. It is basically a tree chained in the reverse order. A solution would be to double-link that list and when all the atomic paths been found, free the tree from the starting point.

But a clever solution is to use a reference counting (inspired from Garbage Collection). Each time you add a link to a parent you adds one to its reference count. Then, when you arrive at the end of a path, you go backward and free while the reference count equals to 1. If it is higher, you just remove one and stop.

Atomic Cycle A

Looking for the atomic cycle of A is the same as looking for the atomic path from A to A. However there are several optimizations we can do. First, when we arrive at the destination point, we want to save the path only if the sum of the edges cost is negative: we only want to go through absorbing cycles.

As you have seen previously, the whole graph is being traversed when looking for an atomic path. Instead, we can limit the search area to the strongly connected component containing A. Finding these components requires a simple traverse of the graph with Tarjan's algorithm.

Combining Atomic Paths and Cycles

At this point, we have all the atomic paths that goes from A to B and all the atomic cycles of each node, left to us to organize everything to get the shortest path. From now on we are going to study how to find the best combination of atomic cycles in an atomic path.

In order to see the problem, we can use a digression. Imagine a plane that wants to cross a mountain. The only way to get up is to stay on hot air spot for a while. He has to chose the best combination of spots in order to go over each peak loosing as little time as possible.

Atomic Cycle Characteristics

Absorbing cycles can only be unlocked when moving through the path. In the example, the cycle [3, 4, 2] is only available after being on the node 2. So you have to have 1 hp to get to node 2 and 1 more hp to get to node 3 and then be able to get the -3 bonus. This highlights an important characteristic: minimum hp. Each cycle and node have a minimum hp to be visited.

We are now able to fully describe an atomic cycle with these four characteristics:

  • Entry point
  • Edge count
  • Cost (negative)
  • Mininum hp

Nodes to States

Atomic cycles have an inner minimum hp, hence, this is not possible to merge them with their entry point. We have to make a virtual state representing the possibility to walk that cycle. The condition of that state is having at least node minimum hp + cycle minimum hp. This way we can define a state minimum hp.

Example: Node to State

Example: Node to State

In the example, the third node has a minimum hp of 1 + 2 and the yellow cycle has a minimum hp of 1, so the resulting state has a minimum hp of 4.

Warning: This technique is subject to overlapping. I did not find an efficient way to handle this case so it can generate wrong result.

Greedy Combination

What we have now is a list of states, each one unlocking one or more cycles. We have to find the best combination of cycles.

We have first to define what is the best cycle. There can be two definitions based on the ratio hp / edge.

  • Global ratio: The one that gives the most hp per edge.
  • Local ratio: The one that goes from A to B with the less number of edges

We could be tempted to use the global ratio but this is not a good idea. Imagine you need to get 2 hp to go to the end. You don't want to use the cycle that gives you 1 billion hp for only 100 edges when there is a cycle that gives you 2 hp for 10 edges.

A simple algorithm to find a good solution is to take the cycle with the best local ratio available at state A enough times to go to state B, then repeat the same process with cycles available at state B to go to state C and so on.

This works great but is too much subject to local errors. Let say you have the two cycles of the previous example available at state A and you want to go to state Z that is 200 hp away with small steps between. You will always choose the cycle that gives you 2 hp for 10 edges and end up with 200 edges when you could have used the 1 billion hp for 100 edges in the first time.

A solution is to sophisticate the algorithm a little. Instead of doing [A -> B -> C -> D], we are going to do
[A -> B -> C -> D], [A -> C -> D], [A -> B -> D] and [A -> D] and see what's best. This is more processing but gives much better results.

Warning: This method does not give the best possible combination, only an approximation. Also, it does not handle cases were a combination of multiple cycles is better than a single cycle to go from one state to another.

Optimizations

Before attempting to compute an atomic path, take the cycle with the best global ratio available and see how many edges would be necessary to get to the end with that ratio. If that's superior to the already found shortest path, it is worthless to do it. This simple test should allow you to skip the majority of the paths.

When you are generating the states, you do not have to take care of cycles when there is a better one available before. A better cycle is a cycle that has less edges for the same amount of hp. This reduces the number of states, therefore by a great factor the number of combinations needed in the sophisticated algorithm.

Conclusion

Advantages

Complexity edge value independent

The main advantage of this method is that the complexity depends of the number of nodes and the density of the graph but is not affected by edge values. If you set the critical edge to be 50 or 50 000 000, this will give you the result in the same time. However, the time required increases faster with the number of nodes than the basic method.

Parallelizable code

To compensate, the code becomes parallelizable. During the first step, you can give each atomic path and cycle detection to different computers at the same time. Then, each path can be computed no matter the order.

Low memory output

The main problem with the basic method is memory allocation. For each node of the final and potential (to some extent) paths a memory chunk is allocated. When you are testing you usually do it with long paths and memory becomes really fast the limiting factor.

Disadvantages

Much more code

The resulting code is much bigger than the basic method. This means a longer development time, more bugs.

Not perfect result

The real problem are the edge cases when it does not return the shortest path or worse, when it gives an invalid path. The three problems are the overlapping issue when converting nodes to states, the greedy algorithm to find combinations and finally the single-only cycle to go from one state to another.

I don't know if all of them could be fixed without seriously affecting the complexity of the algorithm.

Is strongly depending of the size of the graph

Since the algorithm does a brute force of all possibilities, the complexity goes exponentially with the size of the graph. However, in the case of the project, we were told that only small (no more than 50 nodes) would be tested.