Vjeux

Diablofans.com needed a bit of love. It is really gratifying to be able to visually improve a website by an order of magnitude just by changing some colors and fixing broken layout 🙂

Here are some of the changes I made:

Post
Poll
Blizzquote

For a school project, I have to implement Simulated Annealing meta heuristic.

Thanks to many open source web tools, I've been able to quickly do the project and have a pretty display. CoffeeScript, Raphael, Highcharts, Three.js, Twitter Bootstrap, jQuery and Web Workers.

2D Demo

You have a shuffled grid and you have to find the original grid. The only operation available is to swap 2 random elements. The cost function is the distance of the point with their original neighbors.

Click to view the 2D demo

3D Demo

On this one, we are given many functions and we have to find the global minimum. The challenge was to be able to display the evolution of the algorithm, as it traverses 200k points per second.

Click to view the 3D demo

CoffeeScript Sexyness

I've written the project in CoffeeScript and I don't regret it. I find myself writing code a lot faster because I have a lot less to type. Most of the Javascript syntax is either shortened (function to ->) or optional (parenthesis, curly brackets ...) in CoffeeScript. There are also handy features such as splats, generators ...

Destructuring Assignment

worker.onmessage = (data: [id, rest...]) ->
  switch id
    when 'update'
      [cost, temperature, accepted, tried, data, force] = rest

Trimmed JSON

chart = new Highcharts.Chart
  chart:
    renderTo: 'container'
  yAxis: [
    title:
      text: 'Cost'
  ]
  tooltip:
    formatter: ->
      this.series.name + ': ' + this.y

Report

Felix Abecassis wrote a report that explains everything 🙂 It's in French, sorry!

Download PDF

MMO-Champion is a World of Warcraft news website. When a new patch is released, we want to show what has changed in the game (Post Example). An english summary of each spell change is hand written, but we want to show the exact tooltip changes.

Generate Tooltips

First, we use the database application to generate the tooltips in HTML form.

Tokenize

We are not going to do a full HTML diff which is really difficult. Instead, the trick is to parse the HTML and extract only text nodes. We split them by space to generate a token stream.

Diff

Paul Butler SimpleDiff algorithm is used on the two token streams to label each token with old, new or both.

Combine

We parse the HTML again. This time we pretty-print the HTML while traversing it. As we parse text nodes, we add <ins> tags where we need to. We just make sure to group contiguous insertions.

Text Diff

We would also like to get a text-based diff we can insert in a Patch Note. We combine both token streams into one.

Chestguard of Nature's Fury
Binds when equipped
Chest
1669 Armor
+341+321 Intellect
+512 Stamina
Red Socket
Socket Bonus: +10 Haste Rating
Requires Level 85
Equip: Improves critical strike rating by 205.
Equip: Increases your mastery rating by 241.221.

Chestguard of Nature's Fury Binds when equipped Chest 1669 Armor +341+321 Intellect +512 Stamina Red Socket Socket Bonus: +10 Haste Rating Requires Level 85 Equip: Improves critical strike rating by 205. Equip: Increases your mastery rating by 241.221.

However, the result isn't that readable. There is too much noise. We want to show only the information that has changed! In order to do that, we are going to keep only the lines that contain changes.

+341+321 Intellect
Red Socket
Socket Bonus: +10 Haste Rating
Equip: Increases your mastery rating by 241.221.

+341+321 Intellect Red Socket Socket Bonus: +10 Haste Rating Equip: Increases your mastery rating by 241.221.

And it works a lot better 🙂

Conclusion

This approach is working really well with the World of Warcraft tooltips. After many patches and hundreds of changes, I haven't seen any weird behavior. They were common before using this technique. The only downside: non textual changes such as icons or colors will be completly ignored.

During the course "Introduction to Model Checking" by Alexandre Duret-Lutz we've been assigned to create a Binary Decision Diagram library. Contrary to most people, I've been writing mine in Javascript instead of C++. Overall it is running slower but by an acceptable factor (around x5).

Display

I've written a BDD display using the graph library called Dracula which is built on-top of RaphaëlJS. The API of the lib is really neat but there are only 2 available node layout algorithms and none of them really fit my needs. I'd love to have the ones available in GraphViz.

In order to enter a formula, I've written a small parser that accepts most common binary operations. The little dice gives you some random formula. Also, on the left, you have all the evaluations that satisfy your formula.

Use Case

Binary Decision Diagram are used in Boolean Satisfiability Problem and Model Checking. As a benchmark example, we use the BDD to solve the 8-Queens problem.

A version using web-workers is available. However, using more than one worker will be slower as the cost of communication (through JSON serialization) is really high (hundreds of thousands nodes). You can also try to use a random ordering for the variables, but beware, the execution time varies a lot (up to x100 for the fastest/slowest)!

Conclusion

It was a really fun project to do. You can view the sources and probably use them as a base if you ever need to use a BDD in your life 😛

Check out the updated World of Warcraft talent calculator I've been working on 🙂