Spatial Hashmap Memory Leak

Believe it or not, I actually managed to add a spatial hashmap (using global ds_lists), and it actually works perfectly!
...almost. There seems to be a pretty bad memory leak whenever my player object reads through the lists.

Here's how it works:
  1. Cells in the hashmap are just very large tiles for the sake of making my life easier (and it's less calculating so I think it should run faster too). My hashmap tile cells are 640*368.
  2. I have a persistent game controller object. When the level starts, the controller creates an array of ds_lists for every hashmap tile. Thankfully this works without issue.
    Code:
    var tile_id = layer_get_id("layerGridCollision");
    collisionGrid = layer_tilemap_get_id(tile_id);
    var width = tilemap_get_width(collisionGrid) - 1;
    var height = tilemap_get_height(collisionGrid) - 1;
    var endLoop = false;
    var i = width;
    var j = height;
    do{
        global.collisionList[i, j] = ds_list_create();
        show_debug_message(string(global.collisionList[@ i, j]) + " X: " + string(i) + " Y: " + string(j));
        switch (j = 0)
        {
            case true:
                if (i > 0)
                {
                    i -= 1;
                    j = height;
                }
                else endLoop = true;
                break;
            case false:
                j -= 1;
                break;
        }
    }until (endLoop = true);
    maxCells = width*height;
    gridExists = true;
  3. Objects have an array of hashmap cells. Here is how it is initialized:
    Code:
    var tile_id = layer_get_id("layerGridCollision");
    collisionGrid = layer_tilemap_get_id(tile_id);
    collisionGridWidth = tilemap_get_width(collisionGrid) - 1;
    collisionGridHeight = tilemap_get_height(collisionGrid) - 1;
    var endLoop = false;
    var i = collisionGridWidth;
    var j = collisionGridHeight;
    do{
        collisionCells[i, j] = false;
        if (j = 0)
        {
            if !(i = 0)
            {
                i -= 1;
                j = collisionGridHeight;
            }
            else endLoop = true;
        }
        else
            j -= 1;
    }until (endLoop = true);
  4. Each frame, objects go through a routine where they check which cells the edges of their bounding box overlap. If the object has moved enough where they are in different cells, then the object will loop through it's own array of collision cells and remove itself from each one. It will then place its id in the controller object's hashmap lists (one for each cell), and then store those cells' id's in it's own array. Unfortunately I've noticed the memory steadily but slowly go up when I disable the collision checking routine but leave these to run, so something is wrong here.
    Code:
    ///COLLISION CELLS ADD TO
    
    var collisionCell, collisionCellX, collisionCellY;
    var xLoop, yLoop;
    var x1BBoxTemp = bbox[@ 0, 0], y1BBoxTemp = bbox[@ 1, 0], x2BBoxTemp = bbox[@ 2, 0], y2BBoxTemp = bbox[@ 3, 0];
    var cellX1, cellY1, cellX2, cellY2, boxWidth, boxHeight;
    var tileLoop = true;
    var value = 0, list;
    
    #region //Creating Temporary BBox
        switch (wrapHorizontal)
        {
            case true:
                #region //if bbox stretches entirely across the room
                if ((x1BBoxTemp < 0) && !(x2BBoxTemp < room_width))
                {
                    x1BBoxTemp = 0;
                    x2BBoxTemp = room_width - 1;
                }
                #endregion
                #region //Otherwise wrap bbox boundaries
                else
                {
                    while (x1BBoxTemp < 0)
                        x1BBoxTemp += room_width;
                    while !(x1BBoxTemp < room_width)
                        x1BBoxTemp -= room_width;
                    
                    while (x2BBoxTemp < 0)
                        x2BBoxTemp += room_width;
                    while !(x2BBoxTemp < room_width)
                        x2BBoxTemp -= room_width;
                }
                break;
                #endregion
            case false:
                #region //constrain bbox boundaries within room
                    x1BBoxTemp = min(max(0, x1BBoxTemp), room_width - 1);
                    x2BBoxTemp = max(min(room_width - 1, x2BBoxTemp), 0);
                    break;
                #endregion
        }
        switch (wrapVertical)
        {
            case true:
                #region //if bbox stretches entirely across the room
                if ((y1BBoxTemp < 0) && !(y2BBoxTemp < room_height))
                {
                    y1BBoxTemp = 0;
                    y2BBoxTemp = room_height - 1;
                }
                #endregion
                #region //Otherwise wrap bbox boundaries
                else
                {
                    while (y1BBoxTemp < 0)
                        y1BBoxTemp += room_height;
                    while !(y1BBoxTemp < room_height)
                        y1BBoxTemp -= room_height;
                    
                    while (y2BBoxTemp < 0)
                        y2BBoxTemp += room_height;
                    while !(y2BBoxTemp < room_height)
                        y2BBoxTemp -= room_height;
                }
                break;
                #endregion
            case false:
                #region //Otherwise constrain bbox boundaries within room
                    y1BBoxTemp = min(max(0, y1BBoxTemp), room_height - 1);
                    y2BBoxTemp = max(min(room_height - 1, y2BBoxTemp), 0);
                    break;
                #endregion
        }
        cellX1 = tilemap_get_cell_x_at_pixel(collisionGrid, x1BBoxTemp, y1BBoxTemp);
        cellY1 = tilemap_get_cell_y_at_pixel(collisionGrid, x1BBoxTemp, y1BBoxTemp);
        cellX2 = tilemap_get_cell_x_at_pixel(collisionGrid, x2BBoxTemp, y2BBoxTemp);
        cellY2 = tilemap_get_cell_y_at_pixel(collisionGrid, x2BBoxTemp, y2BBoxTemp);
        switch ((cellX1 = bbox[@ 0, 1]) && (cellY1 = bbox[@ 1, 1])
        && (cellX2 = bbox[@ 2, 1]) && (cellY2 = bbox[@ 3, 1]))
        {
            case true:
                tileLoop = false;
                break;
            case false:
                bbox[@ 0, 1] = cellX1;
                bbox[@ 1, 1] = cellY1;
                bbox[@ 2, 1] = cellX2;
                bbox[@ 3, 1] = cellY2;
                break;
        }
    #endregion
    
    switch (tileLoop)
    {
        case true:
            scrCollisionListsRemoveFrom();
            #region //Add ID to new collision cells
            xLoop = cellX1;
            yLoop = cellY1;
            var cellLoop = true;
            do
            {
                list = global.collisionList[@ xLoop, yLoop];
                ds_list_add(list, id);
                collisionCells[@ xLoop, yLoop] = true;
                if (yLoop = cellY2)
                {
                    if (xLoop = cellX2)
                    {
                        cellLoop = false;
                    }
                    else
                    {
                        yLoop = cellY1;
                        xLoop += 1;
                    }
                }
                else yLoop += 1;
            }until cellLoop = false;
            #endregion
            break;
        case false:
            exit;
            break;
    }
    Code:
    ///COLLISION CELLS REMOVE FROM
    
    var xLoop = collisionGridWidth;
    var yLoop = collisionGridHeight;
    var cellLoop = true;
    var value = 0;
    var list;
    do
    {
        value = collisionCells[@ xLoop, yLoop];
        if (value = true)
        {
            list = global.collisionList[@ xLoop, yLoop];
            value = ds_list_find_index(list, id);
            ds_list_delete(list, value);
            collisionCells[@ xLoop, yLoop] = false;
        }
        switch (yLoop = 0)
        {
            case true:
                switch (xLoop = 0)
                {
                    case true:
                        cellLoop = false;
                        break;
                    case false:
                        yLoop = collisionGridHeight;
                        xLoop -= 1;
                        break;
                }
                break;
            case false:
                yLoop -= 1;
                break;
        }
    }until cellLoop = false;
  5. After all of that, the objects will check for collisions. They will only check for collisions with objects in the same cells instead of having to loop through every object, which is awesome. This is where the massive memory leak is though.
    Basically, the player object goes through it's own array of cell id's, and for each that returns true, it will find that respective ds_list and loop through it to check for collisions. Anything you see about vectors and platforms you can ignore since that's just what I'm using the hashmap to check for.
    Code:
    if (vectorCollisions = true)
    {
    #region //Vector Collisions
    if instance_exists(objVectorParent)
    {
        loop = true;
        var check;
        var list, listPos, listValue, listSize, objectIndex;
        var vector, vectorRecX1, vectorRecY1, vectorRecX2, vectorRecY2;
        var vectorX1, vectorY1, vectorX2, vectorY2;
        var xLoop = 0, yLoop = 0;
        
        #region //Loop through collision lists
        do
        {
            if (collisionCells[@ xLoop, yLoop] = true)
            {
                list = global.collisionList[@ xLoop, yLoop];
                listSize = ds_list_size(list);
                listPos = 0;
                #region //Iterate through list for vectors to collide with
                do
                {
                    listValue = list[| listPos];
                    switch (is_undefined(listValue))
                    {
                        case true:
                            break;
                        case false:
                            objectIndex = listValue.object_index;
                            switch (objectIndex)
                            {
                                case objVectorLineSingle:
                                #region
                                    vector = listValue;
                                    #region //Create Vector Bounding Rectangle
                                        vectorX1 = vector.x1;
                                        vectorY1 = vector.y1;
                                        vectorX2 = vector.x2;
                                        vectorY2 = vector.y2;
                                        vectorRecX1 = vector.bbox[@ 0, 0];
                                        vectorRecY1 = vector.bbox[@ 1, 0];
                                        vectorRecX2 = vector.bbox[@ 2, 0];
                                        vectorRecY2 = vector.bbox[@ 3, 0];
                                    #endregion
                                    #region //Collision Check
                                    switch ((groundIDMode = 2) && (groundID = vector))
                                    {
                                        case true:
                                        #region //If Already On the Vector
                                            slopeTemp = vector.slope;
                                            yIntercept = vectorY1 - (slopeTemp * vectorX1);
                                            slopeYPos = (slopeTemp*sensorGroundXTemp) + yIntercept;
                                            switch(point_in_rectangle(
                                            sensorGroundXTemp, sensorGroundYTemp,
                                            vectorRecX1, sensorGroundYTemp, vectorRecX2, sensorGroundYTemp))
                                            {
                                                case 0:
                                                    break;
                                                case 1:
                                                case 2:
                                                    if (adjustYPos > slopeYPos)
                                                        collision = true;
                                                    break;
                                            }
                                            break;
                                        #endregion
                                        case false:
                                        #region //Otherwise perform Rectangle Check
                                            switch (rectangle_in_rectangle(
                                            bbox[@ 0, 0], bbox[@ 1, 0], bbox[@ 2, 0], bbox[@ 3, 0],
                                            vectorRecX1, vectorRecY1, vectorRecX2, vectorRecY2))
                                            {
                                                case 0:
                                                    break;
                                                case 1:
                                                case 2:
                                                    slopeTemp = vector.slope;
                                                    yIntercept = vectorY1 - (slopeTemp * vectorX1);
                                                    slopeYPos = (slopeTemp*sensorGroundXTemp) + yIntercept;
                                                    switch(point_in_rectangle(x, sensorGroundYTemp,
                                                    x, slopeYPos, x, slopeYPos + sensorGroundY))
                                                    {
                                                        case true:
                                                            if (adjustYPos > slopeYPos)
                                                                collision = true;
                                                            break;
                                                        case false:
                                                            break;
                                                    }
                                            }
                                            break;
                                        #endregion
                                    }
                                    #endregion
                                    #region //Collision w/ Vector
                                        switch (collision)
                                        {
                                            case true:
                                                collision = false;
                                                adjustYPosSet = true;
                                                adjustYPos = slopeYPos;
                                                tempValues[@ 2] = vectorX1;
                                                tempValues[@ 3] = vectorY1;
                                                tempValues[@ 4] = vectorX2;
                                                tempValues[@ 5] = vectorY2;
                                                tempValues[@ 6] = point_direction(vectorX1, vectorY1, vectorX2, vectorY2);
                                                groundIDTemp = vector;
                                                groundIDModeTemp = 2;
                                                collisionFloor = true;
                                                break;
                                            case false:
                                                break;
                                        }
                                    #endregion
                                    break;
                                #endregion
                                case objVectorAABB:
                                #region
                                    vector = listValue;
                                    #region //Create Vector Bounding Rectangle
                                        vectorX1 = vector.x1;
                                        vectorY1 = vector.y1;
                                        vectorX2 = vector.x2;
                                        vectorY2 = vector.y2;
                                        vectorRecX1 = vector.bbox[@ 0, 0];
                                        vectorRecY1 = vector.bbox[@ 1, 0];
                                        vectorRecX2 = vector.bbox[@ 2, 0];
                                        vectorRecY2 = vector.bbox[@ 3, 0];
                                    #endregion
                                    break;
                                #endregion
                                default:
                                    break;
                            }
                            break;
                    }
                    listPos = listPos + 1;
                }until (listPos = listSize);
                #endregion
            }
            switch (yLoop = collisionGridHeight)
            {
                case true:
                    if (xLoop = collisionGridWidth)
                        loop = false;
                    else
                    {
                        xLoop += 1;
                        yLoop = 0;
                    }
                    break;
                case false:
                    yLoop += 1;
                    break;
            }
        }until (loop = false);
        #endregion
    }
    #endregion
    }
I have literally no idea how to fix this memory leak, it's pretty intense. If I had to guess it might be because I store the list id's in var's but I used accessors as much as I could so who knows. I am pretty new to ds_lists and such in general though. Would anyone potentially be able to help me figure this out?
 

Paskaler

Member
I'm going to look through all of the code you've posted properly to see if I can spot a memory leak, but, I'd first like to say is that GMS2 does this sort of thing internally by default and GMS 1.4 does it if you tick on Use Fast Collision System in Global Game Settings. So, unless you implemented this for learning purposes and such, you might not need it.

EDIT:

Are all of those ds_lists destroyed on level end from global.collisionList? They should be, using ds_list_destroy. Other than that, I don't see any dynamic stuff being created in any of the code snippets you posted. Just the one in the controller object where global.collisionList is initialized.
 
Last edited:
I'm going to look through all of the code you've posted properly to see if I can spot a memory leak, but, I'd first like to say is that GMS2 does this sort of thing internally by default and GMS 1.4 does it if you tick on Use Fast Collision System in Global Game Settings. So, unless you implemented this for learning purposes and such, you might not need it.

EDIT:

Are all of those ds_lists destroyed on level end from global.collisionList? They should be, using ds_list_destroy. Other than that, I don't see any dynamic stuff being created in any of the code snippets you posted. Just the one in the controller object where global.collisionList is initialized.
Thank you so much.
One thing I forgot to mention, I actually do destroy the lists when the room ends. This is different though, the memory leak happens during the collision checking loop.

Sadly I wish I could rely on default collisions, but my code’s set up to run everything in a specific order, I basically run every object’s user events in the order I want from the controller’s step event. It’s awesome for stuff like moving platforms, they work like a charm. Basically my player object loops through any moving platform objects, and whichever ones the player is colliding with will move the player’s intended height up to the top of the platform. Looping through every single moving platform when I could have a bunch in the room at once could be pretty cpu costly so it makes sense to add a spatial hashmap so you only need to check which ones are need you. It is a bit confusing but it’s good practice too!
 
Top