• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Complex Skill Trees

MrDave

Member
GM Version: GMS 1.4 and GMS 2
Target Platform: ALL
Download:
GMS2: http://www.davetech.co.uk/files/complexskilltrees.yyz
GMS1.4: http://www.davetech.co.uk/files/complexskilltrees.gmz (by @Dev_Smithy)
Links: Interactive example and more: http://www.davetech.co.uk/gamemakercomplexskilltrees

Summary:
I wrote a little flexible system to have skill trees where you can have many skills branch off one skill and also re-join together (one to many and many to one relationships). I wanted to do it all with array structures because it was easy edit and maintain huge lists (much larger than the ones I have here)



It could be used for other things like overworld maps, dialogue trees, character progression, level selection etc.




Tutorial:
First lets understand the arrays:

Code:
skillname[0] = "Skill0"; // the name of the skill (isnt used)
skillimage[0] = 0;     // this is the image that should be used
skillneeds[0,0] = -1;    // What skills the player needs to unlock before they can get this one (-1 is always available)
skillx[0] = 230;        // x position of this skill on the screen
skilly[0] = 230;        // y position of this skill on the screen

skillname[1] = "Skill1";
skillimage[1] = 0;
skillneeds[1,0] = -1;    // -1 always available
skillx[1] = 370;
skilly[1] = 230;

skillname[2] = "Skill2";
skillimage[2] = 0;
skillneeds[2,0] = 0;    // Link to both skill 0 and skill 1
skillneeds[2,1] = 1;
skillx[2] = 300;
skilly[2] = 160
Those three arrays build this skill tree:

Notice how skill 0 and 1 don’t say they are connect to skill 2, They only point towards the skill start object. This is because skill 2 says it is connected to both 0 and 1. When connecting skills you only need to connect them in one direction, you DON’T need both skill 1 to point skill 2 AND skill 2 to point back to skill 1.



The Code:

obj_skillspawner – create:
This is the code that turns your array into individual skill objects, also pre caches where to draw the lines into an array.
Code:
for (i=0; i<array_length_1d(skillname); i++) // loop around for each skill
{

    var newskill = instance_create_layer(skillx[i], skilly[i],"Instances",obj_skill); // Create an object that will be this skill
    newskill.image_index = skillimage[i];
    newskill.skillname = skillname[i];
    newskill.skillid = i;

    show_debug_message("We have made skill " +string(skillname[i]))
  
    // ASSERT – at this point the object skill has been made
  
    with(newskill) { // we now want to pre record all the lines this skill is connected to so we dont have to work it out every time
  
        for (j=0; j<array_length_2d(other.skillneeds,other.i); j+=1) // loop around all the skills I connect to
        {
            skillneeds[j] = other.skillneeds[other.i,j]
            show_debug_message("Skill "+ string(newskill.skillname) + " needs " + string(skillneeds[j]))
          
            if (skillneeds[j] == -1) { // This skill is always available so draw a line to the central object
              
                status = 1;
                linetox[0] = obj_skillspawner.x;
                linetoy[0] = obj_skillspawner.y;
                needcount = 1;
              
            } else { // on the new skill record where its lines should be drawn so we don’t need to look it up every frame
              
                linetox[j] = other.skillx[skillneeds[j]];
                linetoy[j] = other.skilly[skillneeds[j]];
                
                needcount++
            };
        }
    }

};
obj_skill – create:
Initialise everything obj_skill will use but we will overwrite all of this.

Code:
image_speed = 0; //Just to stop the skill trying to animate

// Initialise some things we will overwrite in obj_skillspawner
skillname = 0;    // We don’t use this but this could be drawn next to or on mouse over to show the player the name of the skill
skillid = 0;    // this is the unique id of this skill
skillneeds = -1; // this will be an array holding the unique id of any skill requiered before getting this one
needcount = 0;    // this will basically hold array_length_1d(skillneeds) so we dont have to do it every frame

linetox[0] = 0;    // this will be an array of where to draw every line coming out of this skill
linetoy[0] = 0;

status = 0;    // 0 = unavailable, 1 = available, purchased = 2
obj_skill – Draw
Draw the lines

Code:
if (status == 0) { // set the colour of the line (black means they can unlock it, gray is still locked)
    draw_set_colour(c_gray)
} else {
    draw_set_colour(c_black) // I want all my lines black
}

for (d=0; d<needcount; d++) // loop around all of the lines we have already cached and draw them
{
    draw_line_width(x,y,linetox[d],linetoy[d],2)
};
obj_skill – Draw End:
Draw the skills
Code:
switch (status)
{
    case 0: // Unavailable
        draw_sprite(spr_skills,10,x,y) // image_index 10 is a gray image of the skill so draw this if they cant buy the skill
    break;
    case 1: // Available
        draw_sprite(spr_skills,image_index,x,y) // they can buy the skill so draw it normally
    break;
    case 2:
        draw_sprite(spr_skills,image_index,x,y) // they have bought the skill so draw it normally but ontop draw a box that shows they own it
        draw_sprite(spr_available,0,x,y)
    break;
}
obj_skill – Left Click Released:
The player wants to buy this skill so check to see if they can buy this one and then check all the skills that link to this one to see if they should now be available.

Code:
if (status == 1) { // You can only buy this skill if it is available

    // add any code here for buying the skill, i.e. you might have to deduct money or skill points

    status = 2 // set this skill as being bought
  
    with(obj_skill) { // go through all skills and see if they should now be set to available
  
        // Set skills I link to as available
        for (i=0; i<needcount; i++) {
            if (skillneeds[i] == other.skillid) {
                if (status == 0) { // dont overwrite if they have already bought upgrade
                    status = 1 // This skill is next to me on the tree and is unavailable so make it available.
                }
            }
        };
      
        // Set skills that link to me as available
        for (i=0; i<other.needcount; i++) { // go backwards down the tree
            if (other.skillneeds[i] == skillid) {
                if (status == 0) { // dont overwrite if they have already bought upgrade
                    status = 1 // This skill is next to me on the tree and is unavailable so make it available.
                }
            }
        }

    }
  
    // add any code here to save the changes
  
}
 
Last edited:
C

Crysillion

Guest
Am I right to assume that this system doesn't allow for skill icons to be unique? It looks like the case system allows to show icons of a skill not being available, a skill being available, and a skill being learned, and it's all rather universal, so we couldn't have, say, one icon be a sword, another icon be an arrow, etc. with this system?
 

MrDave

Member
Am I right to assume that this system doesn't allow for skill icons to be unique? It looks like the case system allows to show icons of a skill not being available, a skill being available, and a skill being learned, and it's all rather universal, so we couldn't have, say, one icon be a sword, another icon be an arrow, etc. with this system?
You can have a different icon for each one, I'm just not an artist so only made 9 different colours. But I would expect you would have a unique image for each skill.
 
P

ph101

Guest
Hey. This is pretty cool. I thought you might be interested in my approach. I made a tech tree recently but I wanted to make a system where I didnt have to hard code what each skill needs/is connected to because I find that very fiddly if you need to change the tree.

So instead of arrays needing to be reference each other, I had a grid which basically stored the tree. Each cell could represent either a skill (an index vlue, that references another array storing whether the skill is unlocked, its name etc) or a connecting branch (horizontal or vertical, could be expanded to T junctions and corners). Then I defined the tree stucture in the grid.

Then I looped through the grid drawing the icon for each skill at its relative position in the grid (or branches). When it drew the icon, it checked in turn the 4 adjacent (up/down/left/right). If it was a branch it followed the branch to see if it was connected to another skill and checked if it was unlocked (by grabbing the index and checking master array). If so it meant current skill being drawn is available to be unlocked. This meant the draw script allowed said icon to be selected and unlocked.

Just thought I would share the concept here. The reason I preferred this route was I can restructure the tree just by changing the grid layout/where the braches are in a grid - literally physically matching the tree in a grid, and not needing to enter what each value of what each skill is connected to across multiple cells in the array - so it's very flexible.
 

MrDave

Member
Hey. This is pretty cool. I thought you might be interested in my approach. I made a tech tree recently but I wanted to make a system where I didnt have to hard code what each skill needs/is connected to because I find that very fiddly if you need to change the tree.
Sounds good, either works so whatever is best for you really.
 
N

number_09

Guest
Very impressive. I was curious about doing this in later projects, and the use of the array system is interesting. I look forward to reading through this in more detail.
 
E

Ephemeral

Guest
This is really cool. I've been looking for something like this, and the way you did the connections is clever.

Don't mind me, I'm just going to see if I can reinvent your entire system to not use objects...

First, the arrays... could be more elegant. I usually prefer nested arrays over 2d arrays...
Code:
/// @description node_create
/// @param name As a string.
/// @param sprite The sprite.
/// @param prereqs As an array of node_ids, a node_id or noone.
/// @param x
/// @param y

var name = argument0;
var sprite = argument1;
var prereq = argument2;
var sx = argument3;
var sy = argument4;

var node;
node[NAME] = name;
node[IMG] = sprite;
node[PRQ] = prereq;
node[X] = sx;
node[Y] = sy;

node[LINES] = noone;
node[STATUS] = nd.unavailable;

return node;
So that the Create Event of our one object looks like:
Code:
// List Nodes
skill[0] = node_create("Zero", spr_default, noone, 230, 230);
skill[1] = node_create("One", spr_default, noone, 370, 230);
skill[2] = node_create("Two", spr_default, [0, 1], 300, 160);

map_node_connections(skill);

// Let's do this entirely in GUI, why not.
x = view_wport[0] / 2;
y = view_hport[0] / 2;
Script:
Code:
/// @description map_node_connections
/// @param array_of_nodes

var all_nodes = argument0;

var node_count = array_length_1d(all_nodes);
for (var idx = 0; idx < node_count; idx += 1)
{
    // Get the Node Array Out of the All Array, Then Get the Prereq Array Out of the Node Array
    var node = all_nodes[idx];
    var required = node[PRQ];

    // Deal With the Possibility that there Isn't a Prereq Array
    if (required != noone)
    {
        if (!is_array(required)) required[0] = required;

        // For Each Entry in the Prereq Array, Save A Connection
        var connection;
        for (var req = 0; req < array_length_1d(required); req += 1)
        {
            var c_idx = required[req];
            var c_node = all_nodes[c_idx];
            connection[req] = [ node[X], node[Y], c_node[X], c_node[Y] ];
        }
        node[@ LINES] = connection;
    }
    else
    {
        // Connect to Originating Object and Set State to Available
        node[@ LINES] = [ node[X], node[Y], x, y ];
        node[@ STATUS] = nd.available;
    }
}
return node_count;
I'm not testing this as I go, so if anyone copy-pastes any of this, they get what they deserve.

Anyway that ought to set everything up. Now to draw the thing, in the Draw GUI Event, even.
Code:
// Draw the Lines
draw_all_node_lines(skill);
draw_self();
draw_all_nodes(skill);
Code:
/// @description draw_all_node_lines
/// @param array_of_nodes

var all_nodes = argument0;
var node_count = array_length_1d(all_nodes);

for (var idx = 0; idx < node_count; idx += 1)
{
    // Get the Arrays Out
    var node = all_nodes[idx];
    var connection = node[LINES];

    // Set Color
    if (node[STATUS] == nd.unavailable) draw_set_color(c_gray);
    if (node[STATUS] == nd.available) draw_set_color(c_black);
    if (node[STATUS] == nd.acquired) draw_set_color(c_white);

    // Loop Through Connections and Draw
    var connect_count = array_length_1d(connection);
    for (var cc = 0; cc < connect_count; cc += 1)
    {
        var coord = connection[cc];
        draw_line_width(coord[0], coord[1], coord[2], coord[3], 2);
    }
}
draw_set_color(c_white);
Code:
/// @description draw_all_nodes
/// @param array_of_nodes

var all_nodes = argument0;
var node_count = array_length_1d(all_nodes);

for (var idx = 0; idx < node_count; idx += 1)
{
    // Get the Array Out
    var node = all_nodes[idx];

    // Draw the Node
    draw_sprite(node[IMG], node[STATUS], node[X], node[Y]);
}
Now to make it interactive! Back to the Step Event.
Code:
node_index = node_get_mouseover(skill);
var right_mouse = mouse_check_button_released(mb_left);

if (node_index != noone) and (right_mouse)
{
    node_acquire(skill, node_index);
}
Code:
/// @description node_get_mouseover
/// @param array_of_nodes

var node_index = noone;
var all_nodes = argument0;
var node_count = array_length_1d(all_nodes);
var mcx = window_view_mouse_get_x(0);
var mcy = window_view_mouse_get_y(0);

for (var idx = 0; idx < node_count; idx += 1)
{
    var node = all_nodes[idx];
    var sprite = node[IMG];

    var left = node[X] - sprite_get_xoffset(sprite);
    var right = left + sprite_get_width(sprite);
    var top = node[Y] - sprite_get_yoffset(sprite);
    var bottom = top + sprite_get_height(sprite);

    if (mcx > left) and (mcx < right) and (mcy > top) and (mcy < bottom)
    {
        node_index = idx;
        break;
    }
}
return node_index;
Code:
/// @description node_acquire
/// @param array_of_nodes
/// @param node_index

var all_nodes = argument0;
var node_index = argument1;
var node_count = array_length_1d(all_nodes);

// Prevent Out of Bounds Error
if (node_index >= array_length_1d(all_nodes)) return false;

// Check if the Node is Available and Acquire It If It Is
var node = all_nodes[node_index];
if (node[STATUS] == nd.available)
{
    node[@ STATUS] = nd.acquired;
}
else
{
    return false;
}

// Update All Unavailable Nodes
for (var idx = 0; idx < node_count; idx += 1)
{
    var c_node = all_nodes[idx];
    if (c_node[STATUS] == nd.unavailable)
    {
        var required = c_node[PRQ];
        if (!is_array(required)) required[0] = required;

        // If All Required Nodes are Acquired, Change Status to Available
        var r_count = array_length_1d(required);
        var update = true;
        for (var req = 0; req < r_count; req += 1)
        {
            var r_idx = required[req];
            var r_node = all_nodes[r_idx];
            if !(r_node[STATUS] == nd.acquired) update = false;
        }
        if (update) c_node[@ STATUS] = nd.available;
    }
}
return true;
I think that does it, but I probably lost track of something somewhere in there... I wrote this all in one go right here in the forum post box without even opening GMS2, so yeah.
 
H

hajfajv

Guest
hey

this is pretty cool for a complete newb to have fun with, I just want to add that you get a few syntax errors in gm2 if you use the code that's in the original post - the link works fine :)
 
N

Nejc Podlipnik

Guest
Hey, great guide thank you!
What if I wanted this tree to follow the view of the player? I can draw the tree on GUI layer but the clickable objects stay on original position.
 

tlorgeree

Member
This is really cool. I've been looking for something like this, and the way you did the connections is clever.

Don't mind me, I'm just going to see if I can reinvent your entire system to not use objects...
This was amazing, just the solution I was looking for! I know it has been a couple years so I tweaked it a bit to GMS 2.3 and changed window_view_mouse_get_x() and window_view_mouse_get_y() to device_mouse_x_to_gui() and device_mouse_y_to_gui() in the Node_Get_Mouseover() function. Please forgive variable changes I made for consistency with the rest of my project... Otherwise it was perfect!



Obj_Skill_Tree_Generated:
Create:
GML:
/// @desc Initialize Nodes
//starting node example
skill[0] = Node_Create("Initial", spr_Starting_Node, noone, x, y, ACQUIRED);
// prereq node array example
skill_node_prereqs[0] = skill[0];
//peripheral node example
skill[1] = Node_Create("Peripheral", spr_Peripheral_node, skill_node_prereqs,  x + 25,  y + 25,  AVAILABLE);  // +25 was just to test gui drawing, can be any value



Map_Node_Connections(skill);


x = view_wport[0] / 2;
y = view_hport[0] / 2;
Step:
Same as before

Draw GUI:
Same as before


Script: Skill_Tree_Functions
GML:
//Some macros for readability
#macro NAME 0
#macro SPR 1
#macro X 2
#macro Y 3
#macro LINES 4
#macro STATUS 5
#macro PRQ 6 //prerequisites
#macro UNAVAILABLE 0
#macro AVAILABLE 1
#macro ACQUIRED 2

function Node_Create(name, sprite, prereq, _x, _y, status){
    var node;
 
    node[NAME] = name;
    node[SPR] = sprite;
    node[X] = _x;
    node[Y] = _y;
    node[PRQ] = prereq;

    node[LINES] = prereq;
    node[STATUS] = status;
 
    return node;

}

function Map_Node_Connections(node_library)
{
    var node_count = array_length(node_library);
 
    for (var i = 0; i < node_count; ++i)
    {
        // Get the Node Array Out of the All Array, Then Get the Prereq Array Out of the Node Array
        var node = node_library[i];
        var required = node[PRQ];
     
        // Deal With the Possibility that there Isn't a Prereq Array
        if (required != noone)
        {
       
            if (!is_array(required)) required[0] = required;

            // For Each Entry in the Prereq Array, Save A Connection
            var connection;
            for (var req = 0; req < array_length(required); ++req)
            {
                var c_x = required[req];
                var c_node;
             
                for (var find = 0; find < array_length(node_library); ++find)
                {
                    if (node_library[find] == c_x)
                    {
                        c_node = node_library[find];
                     
                    }
                 
                }
             
                connection[req] = [ node[X], node[Y], c_node[X], c_node[Y]];
             
            }
            node[@ LINES] = connection;
         
        }
        else
        {
            // Connect to Originating Object and Set State to Available
            node[@ LINES] = [ node[X], node[Y], x, y ];
            node[@ STATUS] = 1;
        }
    }
    return node_count;

}

function Draw_Node_Library_Connections(node_library)
{
    var node_count = array_length(node_library);
 
        for (var i_x = 0; i_x < node_count; ++i_x)
        {
            // Get the Arrays Out
            var node = node_library[i_x];
            var connection = node[LINES];
                 
            // Set Color
            if (node[STATUS] == UNAVAILABLE) draw_set_color(c_gray);
            if (node[STATUS] == AVAILABLE) draw_set_color(c_black);
            if (node[STATUS] == ACQUIRED) draw_set_color(c_white);

            // Loop Through Connections and Draw
            var connect_count = array_length(connection);
            if (is_array(connection[0]))
            {
                for (var cc = 0; cc < connect_count; ++cc)
                {
                 
                    var coord = connection[cc];
                    draw_line_width(coord[0], coord[1], coord[2], coord[3], 2);
                }
            }
            else draw_line_width(connection[0], connection[1], connection[2], connection[3], 2);
         
        }
        draw_set_color(c_white);
}

function Draw_Node_Library(node_library)
{
    var node_count = array_length(node_library);

    for (var i_x = 0; i_x < node_count; ++i_x)
    {
        // Get the Array Out
        var node = node_library[i_x];
        // Draw the Node
        draw_sprite(node[SPR], node[STATUS], node[X], node[Y]);
    }
}

function Node_Get_Mouseover(node_library)
{
    var node_index = noone;
    var node_count = array_length(node_library);

var mcx = device_mouse_x_to_gui(0);
var mcy = device_mouse_y_to_gui(0);

    for (var i_x = 0; i_x < node_count; ++i_x)
    {
        var node = node_library[i_x];
        var sprite = node[SPR];
     
        var left = node[X] - sprite_get_xoffset(sprite);
        var right = left + sprite_get_width(sprite);
        var top = node[Y] - sprite_get_yoffset(sprite);
        var bottom = top + sprite_get_height(sprite);

        if (mcx > left) && (mcx < right) && (mcy > top) && (mcy < bottom)
        {
            node_index = i_x;
         
            break;
        }
    }
    return node_index;
}



function Node_Acquire(node_library, node_index)
{
    var node_count = array_length(node_library);

    // Prevent Out of Bounds Error
    if (node_index >= node_count) return false;

    // Check if the Node is Available and Acquire It If It Is
    var node = node_library[node_index];
 
    if (node[STATUS] == AVAILABLE) //available
    {
        node[@ STATUS] = ACQUIRED; //acquired
    }
    else
    {
        return false;
    }

    // Update All Unavailable Nodes
    for (var i_x = 0; i_x < node_count; ++i_x)
    {
        var c_node = node_library[i_x];
     
        if (c_node[STATUS] == UNAVAILABLE) //unavailable
        {
            var required = c_node[PRQ];
            if (!is_array(required)) required[0] = required;

            // If All Required Nodes are Acquired, Change Status to Available
            var r_count = array_length(required);
            var update = true;
            for (var req = 0; req < r_count; ++req)
            {
                var r_i_x = required[req];
                var r_node = node_library[r_i_x];
                if !(r_node[STATUS] == ACQUIRED) update = false;
            }
            if (update) c_node[@ STATUS] = AVAILABLE;
        }
    }
    return true;
}
 

TheWaffle

Member
i love it, but could anyone please give an example how we would apply these skills to our player once purchased?
seems like just change state to ACQUIRED and just do what that would do .....
If it did double attack, then do double attack .... that part of the tree is on you :)
 
Top