2
\$\begingroup\$

I wish to build data structures such as trees, linked lists, graphs, stacks, queues, etc. in Game Maker. However, the concept of object in Game Maker Version 8.1 and older does not have a reliable concept of what a pointer is. They shift whenever something is deleted or instantiated, which is obviously bad if everything relies upon a construct of pointers. I think the motivation behind this is to avoid a dangling pointer error, but it makes objects practically useless.

The built in data structures found in the "ds_..." functions do not persist when saving and loading. They are simply unsaved altogether. This is also not very good in the long run as it could complex constructs to fall apart at random.

Therefore, this begs the question of how one can implement data structures in general that don't have this issue?

Due to recent updates in the engine's implementation of pointers in Game Maker Studio, the problem itself no longer exists as pointers do not need to shuffle to prevent dangling pointer exceptions (as was apparently the motivation behind that cough idiotic cough design choice). However, as objects in the language are somewhat bloated this question still serves as a way of asking for a memory-cheap solution to this problem.

Users of the original Game Maker software or people attempting to mod older games which feature code-based modding will still benefit from this post.

\$\endgroup\$
1
\$\begingroup\$

The solution is to use C-style dynamic memory allocation which is essentially the idea of a struct based programming language. In this sense memory within an array is allocated (for instance 5 indices) and those indices act as your individual node, list, graph or what-have-you. Pointers in this context will just be array indices.

Below are the scripts used to implement this (with titles in bold). The mm_init function sets up the allocator and should be ran once per object as this is a locally scoped allocator. A global one can also exist either by having one master object everything accesses or by changing the array variables to global. I personally feel that local scope will be better as a global variable might become subject to memory leaks when changing rooms.

Malloc is a function that allocates n indices.

Free is a function that deallocates a block returned by malloc. Pass it what was originally received (which is also the first indice in the memory block).

All of this will require one to write low-level structs to begin with and build their way up to a list or tree. However, I will point out that once nodes are implemented, lists and other things can just be simple manipulations of the node structs. I would recommend writing get and set scripts for all structs you choose to make. It will obscure the nature of the pointers and make it more like manipulation of ordinary structs like in C.


mm_init

HEAD_NODE = 0;
/*no need to align 0*/
HEAP_SPACE[HEAD_NODE] = 0;
LINKED_LIST_LENGTH = 0;
TAIL_NODE = HEAD_NODE;
return 0;

mm_malloc

newsize = argument[0] + (argument[0] mod 2);
freeP = HEAD_NODE;

if (mm_getLength(freeP) - newsize > 0 && !mm_getFree(freeP))
{
    mm_setFree(freeP,true);
    mm_insert(freeP, newsize);
    return freeP + 1;
}
while (mm_getNext(freeP) < TAIL_NODE)
{
    freeP=mm_getNext(freeP);
    if (mm_getLength(freeP) - newsize > 0 && !mm_getFree(freeP))
    {
        mm_setFree(freeP,true);
        mm_insert(freeP, newsize);
        return freeP + 1;
    }
}

p = TAIL_NODE; /*add to the heap and return the starting position*/
//p = mem_sbrk(newsize + 8); /*add to the heap and return the starting position*/
if (p == -1)
{
    return NULL;
} else
{
    HEAP_SPACE[p] = (newsize) + (1 << 31);
    HEAP_SPACE[mm_getNext(p) - 1] = newsize;
    if (LINKED_LIST_LENGTH == 0)
    {
        HEAD_NODE = p;
    }
    TAIL_NODE = mm_getNext(p);
    LINKED_LIST_LENGTH += 1;
    return (p + 1);
}

mm_free

/* adjust so that ptr points
 * to the node for this block
 */
p = argument[0] - 1;
HEAP_SPACE[p] = mm_getLength(p);

/*did the pointer originate from the heap*/
if (p > HEAD_NODE && p < TAIL_NODE)
{
    if (!mm_getFree(mm_getPrevious(p)))
    {
        /* the previous node
         * can be coalesced
         */
        mm_removeNode(p);
        p = mm_getPrevious(p);
    }

    if (!mm_getFree(mm_getNext(p)) && mm_getNext(p) <= TAIL_NODE)
    {
        /* the next node
         * can be coalesced
         */
        if (mm_getNext(p) == TAIL_NODE)
        {
            TAIL_NODE = p;
        }
        mm_removeNode(mm_getNext(p));
    }
}

mm_getNext

return (argument[0] + mm_getLength(argument[0]) + 2);

mm_getPrevious

return (argument[0] - mm_getLength(argument[0]-1) - 2);

mm_getLength

/*zero out the leftmost bit, reserved for the free value*/
return HEAP_SPACE[argument[0]] & (~(1 << 31));

mm_getFree

return ((HEAP_SPACE[argument[0]] & (1 << 31)) > 0);

mm_setLength

HEAP_SPACE[argument[0]] = argument[1] + (mm_getFree(argument[0]) << 31);
HEAP_SPACE[mm_getNext(argument[0]) - 1] = argument[1];

mm_setFree

HEAP_SPACE[argument[0]] = mm_getLength(argument[0]) + (argument[1] << 31);

mm_removeNode

mm_setLength(mm_getPrevious(argument[0]),mm_getLength(mm_getPrevious(argument[0]))+mm_getLength(argument[0])+2);
LINKED_LIST_LENGTH -= 1;
/*length is in terms of integer words*/

mm_insert

/* the node has to fit to avoid distorting
 * the linked list's heap property
 */
if (argument[1] + 2 < mm_getLength(argument[0]))
{
    node = argument[0] + argument[1] + 2;
    /*ensure the free field is 0*/
    HEAP_SPACE[node] = 0;
    mm_setLength(node,mm_getLength(argument[0])-argument[1]-2);
    mm_setLength(argument[0],argument[1]);
} else
{
    /* all blocks and nodes are 2 byte aligned, so a difference of one
     * would only exist in the case of a system flaw
     */
    HEAP_SPACE[argument[0]] = mm_getLength(argument[0]) + (1 << 31);
}
\$\endgroup\$

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.