GML Flow-Field Optimization

[lindens]

I've been developing a flow field for some time now and i'm running out of optimization ideas. Currently, it's just too slow for use in an actual game. I am using buffers, accessors, and making sure my scripts are as lightweight as possible. I already know about separating the map into several heat-maps but i want to be sure that generating the heat-map (in general) is as efficient as possible.

The data structures i use for the generation:

Spoiler: Create Event

grid_width  = room_width div cell_size;
grid_height = room_height div cell_size;
buffer_size = grid_width * grid_height; // 680 cells

heatmap   = buffer_create(buffer_size, buffer_fast, 1);  // used as a 1D array holding heatmap cell costs
heatmap_q = ds_queue_create();                           // used by the heatmap for breadth first search algo
flowfield = buffer_create(buffer_size, buffer_fast, 1);  // used as a 1D array holding flowfield directions

Initially i was using ds_grids instead of the buffer but apparently buffers are faster so i had to try it.
I only generate the entire flowfield when the player moves to another location in the grid.
I start by clearing the heat-map to zeroes, ignoring walls, which is actually very fast.

Then i make the heat-map using the breadth first search algorithm:

Spoiler: Heatmap

/// Calculates the heatmap using breadth first search algorithm
var target = argument0;                    // the center, or 0 cost position, of the heatmap
ds_queue_enqueue(heatmap_q, target);

while (ds_queue_size(heatmap_q) > 0) {
    var c_cell      = ds_queue_dequeue(heatmap_q);                // dequeue the next cell, make it the current cell
    var c_index     = (c_cell[@ 1] * grid_width) + c_cell[@ 0];   // convert 2d coordinate to index for buffer
    var c_cell_cost = buffer_peek(heatmap, c_index, buffer_u8);   // get the current cell's cost from the target
    var nb_list     = get_neighbours(c_cell[@ 0], c_cell[@ 1]);   // get adjacent cell coordinates (top, bot, left, right)
 
    // iterate through the neighbouring cells
    for (var i = 0; i <= 3; i++) {
     
        // convert the 2D neighbour coordinate into an index for buffer
        var nb_index = (nb_list[@ i, 1] * grid_width) + nb_list[@ i, 0];
     
        // if the neighbour's cell cost is 0 (meaning not a wall and not already assigned a value)
        if (buffer_peek(heatmap, nb_index, buffer_u8) == 0) {
         
            // set the current neighbour's cell to the current cell's cost + 1
            buffer_poke(heatmap, nb_index, buffer_u8, c_cell_cost + 1);
         
            // put the current neighbour's position (x, y) into the heatmap queue
            ds_queue_enqueue(heatmap_q, vec(nb_list[@ i, 0], nb_list[@ i, 1]));
        }
    }
}

// set target's position to 0 since it gets set to 2 for some reason
// (does not affect functionality, maybe performance very slightly)
var target_index = (target[@ 1] * grid_width) + target[@ 0];
buffer_poke(heatmap, target_index, buffer_u8, 0);

I will post my flow-field script if i get some replies. I just need someone to tell me if i'm doing something wrong yet
Ask if anything is unclear, or you would like to see a screenshot of my current implementation
I have referred to these many times to aid me if anyone is interested:
Goal-Based Vector Field Pathfinding
Flow Field Pathfinding
Amazing PDF on the subject (I will be attempting to implement some concepts from here)

 

[Simon Gust]

I would use the GPU to do this stuff. There is actually code for this I made in this thread if you are interested.
https://forum.yoyogames.com/index.php?threads/ideas-for-advanced-platformer-pathfinding.35201/ (somewhere in the middle of this thread)
While it doesn't work reliably, I haven't been able to work on this due to other projects.

 

[lindens]

I would use the GPU to do this stuff. There is actually code for this I made in this thread if you are interested.
https://forum.yoyogames.com/index.php?threads/ideas-for-advanced-platformer-pathfinding.35201/ (somewhere in the middle of this thread)
While it doesn't work reliably, I haven't been able to work on this due to other projects.

Using the GPU? That's interesting, i hope it doesn't require a DLL as my C++ skills are pretty bad. I will check out the thread, thanks

 

[Simon Gust]

Using the GPU? That's interesting, i hope it doesn't require a DLL as my C++ skills are pretty bad. I will check out the thread, thanks

You just need shader language GLSL, but that is nowhere near C++.

 

[NightFrost]

Did you compare how much faster a buffer is? I've been using a ds list on heatmap generation. However I begin with an operation that generates me a graph of the grid connections, giving me an array containing lists of neighbouring cells. The heatmap generation code itself looks like:

// Create queue for open positions and insert heatmap origin point.
ds_queue_create(FF_Frontier);
ds_queue_enqueue(FF_Frontier, Origin);
// Set up heatmap (size = width * height).
global.FF_HeatMap = ds_list_create();
global.FF_HeatMap[| Size] = 0;
// While frontier is not empty.
while(ds_queue_size(FF_Frontier) > 0){
    // Get a cell from frontier and fetch its list of neighbouring cells.
    var Current = ds_queue_dequeue(FF_Frontier);
    var Neighbours = FF_Graph[Current];
    // New distance is current cell's plus one.
    Distance = global.FF_HeatMap[| Current] + 1;
    // Iterate through neighbours.
    for(var i = 0; i < ds_list_size(Neighbours); i++){
        var Next = Neighbours[| i];
        // Set distance to cell if it doesn't already have it and add it to frontier.
        if(global.FF_HeatMap[| Next] == 0){
            ds_queue_enqueue(FF_Frontier, Next);
            global.FF_HeatMap[| Next] = Distance;
        }
    }
}

EDIT: Because of connection graph I don't need to think about coordinates, and the numbering of cells follows x + y * width scheme so I can represent them with a single number.

 

[lindens]

However I begin with an operation that generates me a graph of the grid connections, giving me an array containing lists of neighbouring cells.

Do you mean that, instead of me finding the neighbouring cells every time i generate the heat-map (like i currently do), i can just calculate them once and remember them in a separate data structure, and access them based on my current cell's coordinate? Sounds like a good optimization!
I'm going to need a ds_list for such a thing though, i would access it with an index which returns a 4x2 array of the 4 neighbour cells

Also, could you explain the connection graph a bit more? I'm assuming it allows iteration through the heatmap to bypass walls entirely (since they never change, why iterate through them, right?)

EDIT: i've just tested the speed of a ds_list by replacing my clear_heatmap() script. I thought it would slower but after testing with actual numbers, the speeds are very similar
Script:

repeat(10000) {
        var time = get_timer();
        time_avg++;
   
        // 666 microseconds average, uses buffers
        for (var i = 0; i < buffer_size; i++) {
            if (buffer_peek(heatmap, i, buffer_u8) != wall_value) {
                buffer_poke(heatmap, i, buffer_u8, 0);
            }
        }

 
        // 654 microseconds average, uses lists
        for (var i = 0; i < buffer_size; i++) {
            if (list[| i] != wall_value) {
                list[| i] = 0;
            }
        }
   
        time_diff += (get_timer() - time);
        var avg = time_diff div time_avg;
    }
    show(avg);

 

[NightFrost]

The graph is constructed like one would need on a A-star or similar pathfinder algorithm. You start with a terrain grid that represents the open and walled cells of the field. Then you iterate through the cells one by one and construct a master array (a ds list would do just as well) into which you insert lists of neighbouring open cells. For example, let's assume a 20 by 20 terraing grid. The top left corner is cell number zero, let's assume it is open. You check its neighbours, there are two since it is in the corner, which are cell two and cell twenty (x + y * width or 0 + 1 * 20). Assuming both of those are open (as checked from the terrain grid), you add them to a ds list and insert them to position zero of your master list. Loop proceeds to cell number one, Let's say one below (cell 21) is open but one to the right (cell 3) is closed, so you put zero (the cell to the left) and 21 to a ds list and insert that to positon one of your master list. Terrain cells with walls you simply skip over. And so on, until you have a 400 slot long (20 * 20) list of cells, each containing a list that contains its open neighbours.

This dataset of grid cells (points) and their connections (edges) is a graph. It doesn't need to present a grid and the edges don't need to be be of uniform length, but in a top-down game terrain graph they usually are.

Now when you need to go through neighbours of cell N, you simply read a ds list from the master list's position of x + y * width and go through its contents. Since terrain tends to be very static, you only need to construct the list once. You could even save it to a file and attach it to the game, so graph generation is not necessary during runtime at all. But you'd need to update the files every time you decide to change room layout.

 

[lindens]

The graph is constructed like one would need on a A-star or similar pathfinder algorithm. You start with a terrain grid that represents the open and walled cells of the field. Then you iterate through the cells one by one and construct a master array (a ds list would do just as well) into which you insert lists of neighbouring open cells. For example, let's assume a 20 by 20 terraing grid. The top left corner is cell number zero, let's assume it is open. You check its neighbours, there are two since it is in the corner, which are cell two and cell twenty (x + y * width or 0 + 1 * 20). Assuming both of those are open (as checked from the terrain grid), you add them to a ds list and insert them to position zero of your master list. Loop proceeds to cell number one, Let's say one below (cell 21) is open but one to the right (cell 3) is closed, so you put zero (the cell to the left) and 21 to a ds list and insert that to positon one of your master list. Terrain cells with walls you simply skip over. And so on, until you have a 400 slot long (20 * 20) list of cells, each containing a list that contains its open neighbours.

This dataset of grid cells (points) and their connections (edges) is a graph. It doesn't need to present a grid and the edges don't need to be be of uniform length, but in a top-down game terrain graph they usually are.

Now when you need to go through neighbours of cell N, you simply read a ds list from the master list's position of x + y * width and go through its contents. Since terrain tends to be very static, you only need to construct the list once. You could even save it to a file and attach it to the game, so graph generation is not necessary during runtime at all. But you'd need to update the files every time you decide to change room layout.

So my heatmap is a ds_list with a 1D array at every entry: [cell_cost, ds_list_create()]
Of course the ds_list_create is the list that holds the neighbours. Every entry of the neighbour list holds a 1D array [neighbour_x_pos, neighbour_y_pos]
I don't think its toooo much faster because of my wonky arrays but i'm sure that can be improved:

var center = argument0;    // the center, or 0 cost position, of the heatmap
ds_queue_enqueue(heatmap_q, center);

while (ds_queue_size(heatmap_q) > 0) {
    var current_cell         = ds_queue_dequeue(heatmap_q);
    var heatmap_index        = current_cell[@ 1] * grid_width + current_cell[@ 0];
    var heatmap_cell         = heatmap[| heatmap_index];
    var heatmap_nb_list      = heatmap_cell[@ 1];
    var heatmap_nb_list_size = ds_list_size(heatmap_nb_list);
  
    for (var i = 0; i < heatmap_nb_list_size; i++) {
        var nb_pos   = heatmap_nb_list[| i];
        var nb_index = nb_pos[@ 1] * grid_width + nb_pos[@ 0];
        var nb_cell  = heatmap[| nb_index];
        var nb_value = nb_cell[@ 0];
      
        if (nb_value == 0) {
            nb_cell[@ 0] = heatmap_cell[@ 0] + 1;
            ds_queue_enqueue(heatmap_q, nb_pos);
        }
    }
}