1. Hey! Guest! The 35th GMC Jam will take place between November 28th, 12:00 UTC - December 2nd, 12:00 UTC. Why not join in! Click here to find out more!
    Dismiss Notice

GML Creating custom Data Structures with simple OOP

Discussion in 'Tutorials' started by ECEngineering, Jun 24, 2017.

  1. ECEngineering

    ECEngineering Member

    Joined:
    Oct 14, 2016
    Posts:
    7
    GM Version: GM:S 1.4, but should work on any version if readjusted.
    Target Platform: Windows / All
    Download: here

    Built-in data structures are still more efficient than this method. It's purpose is to let you create your own custom data structures that do not exist in GameMaker.

    This tutorial should help you create your own data structures with ease. As an example, I will be creating my own custom list. If you are not familiar with the term, OOP stands for Object Oriented Programming.

    First thing you will have to do is create two scripts. One will create an instance of a "class", and the other one will delete it.

    Setting everything up

    First, let's create a "new" script that will create an instance of our class/object:

    Script: new
    Code:
    ///new(class name)
    var tmp = instance_create(0,0,argument0);
    instance_deactivate_object(tmp);
    return tmp;
    
    What this will do is create and instance of the object sent as the argument, then it will deactivate it to not waste our processing power and finally, return the reference to it.

    This way of creating objects is incredibly optimized as it only takes up memory. I've tested it by creating 100000 objects this way and it didn't affect performance at all.

    Now, let's write the "delete" script that will free our instance from the memory once we don't need it anymore.

    Script: delete
    Code:
    ///delete(obj)
    var object = argument0;
    instance_activate_object(object);
    with(object) instance_destroy();
    
    Before we can use "instance_destroy" function to delete the instance, we must first activate it because you can't access deactivated instances by using "with".

    Now, we have everything that we need to work with OOP, so we can begin creating our own data structures!

    Creating data structures

    Before we start creating our own data structures, I want to address a few things. It is possible to have something similar to class-functions, but in order to do that, you would have to activate the instance, call all the functions that you want to call, and then deactivate it again. As this usually looks very "ugly", I will be doing it the same way YoYoGames did it. We will create scripts that will take the reference of the instance as an argument in the similar manner as the built-in GM:S data structure functions do (ds_list_size(id)).

    First thing we'll have to do is create two objects. We'll call them "cls_node" and "cls_list". The image below ilustrates the concept of lists.

    [​IMG]
    The list consists of a chain of nodes that have two fields. One field holds their value, while the other one is holding the reference to the next node in the chain.

    We can now write this code in the create event of the "cls_node":

    cls_node Create Event:
    Code:
    data = undefined;
    next = undefined;
    
    The "data" variable will hold data, while the "next" variable will hold the reference to the next node in the chain.

    That's it for the "cls_node" object. Now, we will be working on our "cls_list" object. If you take a look at the image above again, you will notice that there is something called "head" pointing to the first node in the list. That "head" is the list (well, at least the minimum you need in order to create it). In order to optimize our list, beside this "head" field in the list, we will add two more fields. First one will be "tail" which will always point on the last element so we don't have to iterate through the whole list when adding new values to it's top, and the second one will be "length" which will hold the length of the list so we don't have to iterate and count each time the request for it's size has been sent. We will put this in "cls_list" create event:

    cls_list Create Event:
    Code:
    head = undefined;
    tail = undefined;
    length = 0;
    
    As I already said earlier, the "head" variable will hold the reference of the first node in the list, the "tail" variable will hold the reference of the last node in the list and the "length" variable will hold the current list size.

    The last thing we'll have to do is create some functions for our list. As I already said, you can create in-class functions and call them directly from the object by activating it and using "with" to call the function, but we will not be doing it because it is not convenient.

    I will give you examples on some functions but not all of them as this is not the tutorial on lists in particular, but on creating your own data structures in general.

    Script: list_size
    Code:
    ///list_size(id)
    return argument0.length;
    
    This function will simply return the size of the list by reading the variable

    Script: list_add
    Code:
    ///list_add(id, value)
    var list = argument0;
    var n = new(cls_node); //create a new node
    n.data = argument1; //write data to it
    
    //if the list is not empty, set the last element to point to this one (as it will become the tail now)
    if(list.length>0)
        list.tail.next = n;
    
    list.tail = n; //our new node will now become the tail
    
    //if the list is emty, this will be the first element - the head
    if(list.length==0)
        list.head = n;
    
    //increase the list length variable
    list.length++;
    
    This function will add values to the end of the list by creating a new node, setting our old tail's next value to be this node, and nominating it as the new tail.

    Script: list_find_value
    Code:
    ///list_find_value(id, index)
    var list = argument0;
    var index = argument1;
    
    if(list.length > index){ //if index is inside the list
        //iterating through nodes to get to the desired one
        var tmp = list.head;
        for(var i = 0; i < index; i++)
            tmp = tmp.next;
        return tmp.data; //returning the node data
    }else show_message("List Error: Index is outside of the list");
    
    This function will iterate through nodes until it reaches the requested one. After that, it returns it's data.

    Script: list_insert
    Code:
    ///list_insert(id, position, value)
    var list = argument0;
    var position = argument1;
    var value = argument2;
    
    if(position<list.length){
        var tmp = list.head;
        for(var i = 0; i < position-1; i++) //iterate until reaching the previous node
            tmp = tmp.next;
        var n = new(cls_node);
        n.data = value;
        n.next = tmp.next; //set the next value to the node currently occupying this index
        tmp.next = n; //set the next value of the previous node to our new one
        list.length++;
    }else if(position==list.length) //if inserting to the end, call the add function
        list_add(list,data);
    else show_message("List Error: Index is outside of the list");
    
    This function will iterate until reaching the node with the "position-1" index, then create a new node, set it's next value to the node currently occupying it's index and set the next value of the previous node to this new one.

    Script: list_free
    Code:
    ///list_free(id)
    var list = argument0;
    
    var iterator = list.head;
    var tmp = iterator;
    //iterates through all nodes and deletes each one
    for(var i = 0; i < list.length; i++){
        iterator = iterator.next;
        delete(tmp);
        tmp = iterator;
    }
    //deletes the list
    delete(list);
    
    This function will iterate through all nodes, deleting each one of them. In the end it deletes the list itself.

    Using our Data Structures in game

    We can now use these data structures from anywhere in the code. Here is the example of how you may use this in your game:

    Code:
    var list = new(cls_list);
    
    show_message(list_size(list));
    
    for(var i = 0; i < 10; i++)
        list_add(list,i+5);
     
    show_message(list_size(list));
    
    var s = "";
    for(var i = 0; i < list_size(list); i++)
        s+=string(list_find_value(list,i))+" ";
    show_message(s);
    
    list_insert(list,5,1000);
    
    var s = "";
    for(var i = 0; i < list_size(list); i++)
        s+=string(list_find_value(list,i))+" ";
    show_message(s);
    
    list_free(list);
    

    Making our Data Structures persistent:

    You may notice that ticking the "persistent" box in the object editor isn't enough to make our structures persistent. GameMaker:Studio does not allow deactivated instances to move through rooms even though they are persistent. To solve this, you will have to activate them before moving to the next room and then deactivate them in the next one again.
    For some reason, activating these instances in the "room end" event didn't work for me (I might have made a mistake somewhere), but it does work if you activate them before you call the "room_goto" or any other function that moves the game to another room or restarts it. After you go to the next room, you can deactivate these instances again in the "room start" event.


    Thanks for reading, you can download this project by clicking the link at the top of this thread. I hope you find this useful :)
    ~ECEngineering
     
    Last edited: Jun 28, 2017
    Guest likes this.
  2. Threef

    Threef Guest

    Well I'm just going to ask you what are advantages of this over using ds_list or other structures?
    1. You are using more memory than data structures.
    2. You've said that 100000 did not make performance slowdown, but you clearly didn't tried this many instance activation/deactivation at once
    3. 100000 is just a bit over 300 x 300 grid which isn't that big
    4. How can you save this data between game sessions without saving whole game state (that shouldn't be used because it cannot be controlled)
    5. What about deactivation and activation other objects in rooms?
     
  3. Guest

    Guest Guest

    That's very educational. Can you give some examples of data structures not in GMS2 that would be useful? People often say that GML does not have various things that other languages like C# do, but, as a non-programmer, it's hard to visualize what those things would be useful for. Kind of a Plato's Cave situation.
     
  4. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,459
    This is actually pretty educational indeed. However, The performance may be a little poor due to the large amount of memory allocation this will require.
    I suggest you use arrays instead. Its a bit more work, but here is my tutorial on the matter.
    By combining what @ECEngineering wrote, and using arrays over instances, you should achieve very good performance.

    I would also like to point out that as it stands, you tutorial is not truely OOP, but just using Structures. (not that it takes anything away from its value, GJ)
     
  5. ECEngineering

    ECEngineering Member

    Joined:
    Oct 14, 2016
    Posts:
    7
    1,2,3.
    This is not meant to replace built in data structures, but to allow you to write your own custom ones instead. I used lists as an example, could have used anything else really. But yeah, this is not something that should be used on data structures that will hold too much data as it is not super efficient.
    4. I don't see the problem in saving something like this, as long as you write your own custom saving system (which most of people do).
    5. I don't see how this impacts other objects. I've not used deactivation and activation functions on anything besides on the instances that are part of the data structure.

    Also, thanks for pointing these things out, I will add this to my post so it doesn't cause confusion.
     
    Last edited: Jun 25, 2017
  6. ECEngineering

    ECEngineering Member

    Joined:
    Oct 14, 2016
    Posts:
    7
    One example could be graphs. You can use it to create all kinds of graphs - Tries, Binary trees, Directed and Undirected graphs and many more things. I have used this method to create an inventory system. Using arrays instead can usually give you more performance but some data structures may be much harder to create that way. There are also some cases where using this method will actually be more efficient than using arrays.
     
  7. ECEngineering

    ECEngineering Member

    Joined:
    Oct 14, 2016
    Posts:
    7
    Most of things you say are right, but I don't think that you are right when you say that these are Structures and not Classes. Structures can't form "cycles". For example:
    Code:
    struct Node{
        int data;
        Node next;
    };
    
    This code would not work because it forms a cycle - it has the element of type Node. Structure size must always be constant.


    Code:
    class Node{
        int data;
        Node next;
    };
    
    This code does work.
     
    Last edited: Jun 25, 2017
  8. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,459
    True. But what you would be doing isn't
    Code:
    struct Node {
     int data;
     Node next;
    }
    
    but
    Code:
    struct Node {
      int data;
      Node* next;
    }
    
    See, its really a pointer. not a value. (even in your code above)/

    Anyhow, the real difference between structs and Classes is that Classes have methods.
    In you example, you don't really show the use of methods. you do show functions but those are not exactly the same.

    I was just being a little pedantic though. Its some good stuff you have here.
     
  9. ECEngineering

    ECEngineering Member

    Joined:
    Oct 14, 2016
    Posts:
    7
    Structures can have methods too so this is not the main difference between them. Also, these are references and not pointers. I think that GM:S allows the use of pointers only on some very specific occasions and using pointers works very differently than using references. I tried doing some research on the matter but I can't find much information on how GameMaker objects work. I am pretty sure that objects are classes (As that is how most of people create their "objects" in non-GML languages), but you can never be sure.
    As you already said, it doesn't matter really, the most important thing is that it works.
     
  10. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,459
    They can have method pointers. A little different but they are close enough.
    They are pretty similar. GMS never really uses pointers. Instead you have indices and references only for arrays.

    Game maker instances work with indices. When you call instance_create, you get an index back. It's pretty close to a pointer, but instead of marking a point in memory, it makes a point in an internal array of some sorts.

    Most of the time it doesn't matter to make the distinction but it can come in handy.
     
  11. Yal

    Yal GMC Memer GMC Elder

    Joined:
    Jun 20, 2016
    Posts:
    3,864
    The main issue that can arise is that you can't tell WHAT an index points to (or if it's just an integer), so there's some things you just can't do. Then again, if you're passing data around without really knowing what's stored in it and haphazardly interpreting it, you're not exactly writing stable code to begin with :p

    There's definitely a bunch of valid use-cases for when you'd want to pass multiple types of data to something, though.
     
  12. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,459
    That's why I build structs with arrays, and put their types at index 0.
    Even have a tool to build them, along with getters and setters, inheritance and type checking. Some thing I would not imagine doing without it.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice