#skilltrees

Not been lazy, just messing around with lots of little things. Skill Tree UI is mostly sorted out, except for drag-drop for setting them into your active skill slots and ugly tooltips.

We see above the skill tree for the game Path of Exile.  The Problem that we are posed with is such. Given the Skill Tree above, what is the best path/nodes for maximum game play. 

Problem: The Skill Tree Problem

Input: Given a Skill Tree in the form of a graph G and k, the number of nodes you are allowed to select.

Output: Find the most OP Path.

This is rather simple for say a game like Borderlands 

Players are restricted by their level and have the option on building out three separate trees (although since they are all connected to a root node, it's basically one tree).

However, we see that this can scale up dramatically, as is the case of Path of Exile. In fact, the Skill Tree Problem is probably NP Complete since this can probably be reduced to the infamous Traveling Salesman Problem (Will attempt to prove this some other time or leave as an exercise to the reader =P)

How to Solve: NP complete problems are in the set of NP problems and the set of NP hard problems and are therefore difficult to solve.

In fact, NP stands for Non-deterministic Polynomial meaning this problem can be solved by a Non-deterministic Turing Machine in Polynomial Time. Usually, we approximate NP Complete problems through the use of dynamic programming and greedy algorithms. For practicality these approximations suffice.