2
\$\begingroup\$

I have been thinking of implementing a system like Wolcen does for their skill tree, however I want to use it for level unlocks.

Nodes grouped in segments and multiple segments from a ring (see picture attached)

Each inner segment touches two of the next outer ring' segments, and when each ring is rotated, the nodes are able to be connected the newly rotated section.

A static model of this is simple using a tree structure, where each segment is a tree-node in the tree and each tree-node contains an array of skill-nodes.

How would one achieve a the shifting functionality?

1

EDIT:

Starting State:

      1             Level 1 
    /   \ 
   2     3          Level 2
 /     /   \
4     7     8       Level 3

Trying to Achieve:

      1             Level 1 
    /   \ 
   3     2          Level 2
 /     /   \
4     7     8       Level 3

in other words, the children should not be affected of the parent shifting position.

\$\endgroup\$
  • \$\begingroup\$ So.. what have you tried, what seems to be the problem? \$\endgroup\$ – Kromster Aug 5 at 9:36
  • \$\begingroup\$ @Kromster The probelem is that if you replace a node in the tree with another, you have to "shift" its siblings over one.So the problem is i dont know how to implement the shift. I have tried setting up a static model and replacing nodes, including its children. \$\endgroup\$ – Vince Aug 5 at 9:46
  • \$\begingroup\$ It depends on how your tree is stored, but generally, you have a parent node and a list of it childs. Then you just cut one child from one parent and append it to another. Siblings are usually calculated (through parent), not stored in a node. \$\endgroup\$ – Kromster Aug 5 at 9:48
  • \$\begingroup\$ @Kromster the problem is handling the replaced node's children.Also each segment overlaps with two segments a level up \$\endgroup\$ – Vince Aug 5 at 10:07
  • \$\begingroup\$ @Kromster, this describes it more clearly : geeksforgeeks.org/swap-nodes-binary-tree-every-kth-level \$\endgroup\$ – Vince Aug 5 at 10:34
1
\$\begingroup\$

Let's say you have two ordered lists of nodes that connect two rings. For this example:

  • list1 is the more inner ring with nodes a b d c
  • list2 is the more outer ring with nodes Q R S T

I'm going to refer to the nodes & edges between rings as 'spoke nodes & edges' and I'm going to assume that they line up in a one to one fashion. That means there will be the same number of spoke nodes connecting one ring to the next and each has exactly one spoke edge.

So maybe we have something like this:

Q-----R
|\   /|
| a-b |
| | | |
| d-c |
|/   \|
T-----S

To shift or rotate a ring, all you need to do is go through the spoke nodes of each list & shift the relevant connections:

rotateOuterRingBack(list1);

void rotateOuterRingBack(List<Nodes> list){
  Node tempSpokeNeighbor = list.get(0).getSpokeNeighbor();

  for(int a=0; a<list.size()-1; a++){
    Node currNode = list.get(a);
    Node nextNode = list.get((a+1)%list.size());
    Node currNode.setSpokeNeighbor(nextNode.getSpokeNeighbor));
    Node currNode.getSpokeNeighbor().setSpokeNeighbor(currNode);
  }
  Node lastNode = list.get(list.size()-1);
  Node lastNode.setSpokeNeighbor(tempSpokeNeighbor);
  Node lastNode.getSpokeNeighbor.setSpokeNeighbor(lastNode);
}

Applying this to the example given, the result would be:

R-----S
|\   /|
| a-b |
| | | |
| d-c |
|/   \|
Q-----T

Rotating in the opposite direction is similar, but requires traversing the list in the opposite direction.

This could be extended to handle ring to ring connections that aren't one to one - the basic idea remains the same, but the implementation gets more complex.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, this makes sense. I originally had an array of trees and didn't even cross my mind to connect them like this. \$\endgroup\$ – Vince Aug 6 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.