Archive for eve online

Some Tools You May Need For P.I.

Posted in How To, OOC with tags , , , , on April 26, 2010 by yakshamash

Planetary interaction is coming, and needless to say I’m frigging pumped to planet spin!  Some of you may not feel the same way, but I know for a fact most of you will at-least Try P.I.  Its another thing to do, to profit from, and to master.  In eve online, mastering something is all about optimization.  Weather your an Industrialist working to make the most profit from the least amount of “stuff” or a Combat pilot finagling your fit to push out the most tank and dps your ship will allow, you are optimizing.  I have a feeling that this will stay constant in PI.  If you want to know how to optimize ANYTHING you talk to a computer scientist, lucky for you, I am one.  From what I have seen of PI, it will consist of points, connected by routes.  You show that to a computer scientist, chances are they will say “HEY thats a directed Graph!!!” and what do you know, we study graph theory.

Although I don’t know for sure if they will be of use, I’m pretty certain that these four algorithms will help you optimize your planetary networks, and they are something that you should at least familiarize your self with.

Some Terms To Know

  • Tree – An acyclic graph contained within a graph.
  • Acyclic – The only way back to a point you are coming from is to backtrack the same path you took to get there.

The first two algorithms are for finding the “minimum spanning tree.”  In simple terms, they find the tree within a graph that will hit all points, with the least amount of distance overall.


Complements of the fabled Wikipedia….

Image Description
Prim Algorithm 0.svg This is our original weighted graph. The numbers near the edges indicate their weight.
Prim Algorithm 1.svg Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
Prim Algorithm 2.svg The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the arc DF.
Prim Algorithm 3.svg The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
Prim Algorithm 4.svg In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the arc BE.
Prim Algorithm 5.svg Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the arc EC.
Prim Algorithm 6.svg Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight it and the arc EG.
Prim Algorithm 7.svg Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

Kruskals Algorithm

Another minimum spanning tree algorithm, and once again this table is complements of wikipedia.

Image Description
Prim Algorithm 0.svg This is our original graph. The numbers near the arcs indicate their weight. None of the arcs are highlighted.
Kruskal Algorithm 1.svg AD and CE are the shortest arcs, with length 5, and AD has been arbitrarily chosen, so it is highlighted.
Kruskal Algorithm 2.svg CE is now the shortest arc that does not form a cycle, with length 5, so it is highlighted as the second arc.
Kruskal Algorithm 3.svg The next arc, DF with length 6, is highlighted using much the same method.
Kruskal Algorithm 4.svg The next-shortest arcs are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The arc BD has been highlighted in red, because there already exists a path (in green) between B and D, so it would form a cycle (ABD) if it were chosen.
Kruskal Algorithm 5.svg The process continues to highlight the next-smallest arc, BE with length 7. Many more arcs are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD.
Kruskal Algorithm 6.svg Finally, the process finishes with the arc EG of length 9, and the minimum spanning tree is found.

Next we have an algorithm to solve the Shortest Path Tree – This is a tree that is created from a single point, and it connects all other points to it in the shortest way possible.

Dijkstra’s Algorithm –

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step-by-step.

  1. Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
  2. Mark all nodes as unvisited. Set initial node as current.
  3. For current node, consider all its unvisited neighbors and calculate their distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
  4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
  5. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next “current node” and continue from step 3.

Here is a image demonstrating Dijkstras

Now for my last and final algorithm we have one to solve the problem of Maximum Flow.  Its called several different things, but for low lets just call it the augmenting path algorithm.  This solves how to get the maximum amount of Stuff from one point to another, while visiting all points, with constraints on the amount of “Stuff that can flow through the tubes.”  This diagram is somewhat self explanatory, although a few things are worth noting.  the #,#+ or #,#- may seem a bit odd. The first number represents the amount of additional flow that can be brought from the source to that vertex.  The second number is the name of the vertex that flows into the one being labeled.  If this seems a bit unclear, spend a bit looking at the process worked out and see if you can get a feeling for it.

Well I hope this helps in some way, or at the very least introduced you to the wild and exciting world of graph theory.  Although some of these concepts may be a bit fuzzy to you, with a bit of practice and some critical thinking, you may be able to use them to set up your P.I. colonies for maximum efficiency.  If you need anything explained in more detail, or just cleared up in general feel free to leave a comment and I will get back to you as quickly as I can,

(p.s Watch this space, there may be a colony lay-0ut optimizer program in the works once Tyrannis is released)



Posted in Uncategorized with tags , , , , , , , , on December 24, 2009 by yakshamash

War is upon us… Cant reveal much… Its time to fuck up some can flippers!

[OOC] Happenings

Posted in OOC with tags , , , , , on December 7, 2009 by yakshamash

Some awsome things have been happening lately, and some not so awesome.
On the not so awesome side finals week is underway, and for a computer science student that means a week of zero sleep, many, many pots of coffee, and finger nails that are much shorter than usual.
Enough on that, time for some awesome!  First of all I just got a new position in my Corp(Royal Assassins Guild), Executive Mercenery Operations Officer, so now i’m right under my CEO! Second, I finally broke down and bought my dream mission ship, the apocalipse navy issue, my first faction ship and it’s everything I ever wanted. Last but not least I am now an official eve blogger! I just got the notice from CK and it’s really cool to see this URL in his posts on my Jesus phone via Capsuleer.
Well that’s about all for now, more after this week of hell is over, part 1.2 should be coming out soon.  Now all I need to do is figure out how a 5 stage pipeline effects the CPI of a single core processer, assuming no data hazards have occured…

[OOC] A Bit About Myself And This Blog

Posted in OOC with tags , , , , , , , on November 20, 2009 by yakshamash

I assume if you are reading this you may want to know something about me, and if you don’t, I’m going to tell you anyways.  I have been playing eve for almost two years, and I can honestly say it truly is a hobby for me.  I am an executive officer of a relatively small and mellow corp, which is part of a relatively small and mellow alliance.  We are currently in the process of recruiting and redirecting the way we operate.
In real life I am a theoretical computer science major at Coastal Carolina University in South Carolina.  I love my major and the field I am heading into, despite the fact that it robs me of sleep, social interaction, and EVE time.  I currently work as a web designer toiling away with HTML and PHP in Dreamweaver, while simultaneously designing the front end visuals in Photoshop and Illustrator.  Obviously in the next few weeks this blog will be getting a significant visual boost.  I don’t plan to be in web design for long, I will soon be moving towards software engineering and plan to break into the gaming industry, albeit an uphill battle.  Other than eve, work, and school, I spend my spare time surfing, boozing, and watching American football.

I plan to keep this blog mostly fiction oriented, but how it evolves may be another story.  I have the first section of my first story posted, and plan to have several installments.  If you have any suggestions or comments, please leave them, I welcome all statements, no matter what they say.

Just in case you wanted to know a bit about the man behind the story’s…