Logic Problem: Path Finding in grid-based game [SOLVED]

[andulvar]

I'm trying to optimizing the way I create movement grid highlighting in my game and I'm running into some problems.

Currently I use a square grid based system and to highlight the possible movement squares I call an A-star algorithm on every square within the movement range. This works fine for smaller movement ranges, but at the maximum movement range (12 squares), I need to perform this function on 312 squares in a single step.

This process currently takes about 5 seconds while the screen freezes during the calculation.

Logically speaking, is there a better method to display possible movement, while still making sure not to highlight accessible, but unreachable squares?

 

[anomalous]

Why A* and not built in mp_grid path? 5 seconds for 312 calls seems way too slow.

Generally, a flood fill algorithm can be used for this, although they are not known for speed either, especially written in gml. I think there are a few floating around, sorry I don't have a link.

A 12x12 flood fill, it just feels like that should run quick enough.

 

[andulvar]

I generally try to avoid the mp_grid functions as I can't control much of how things interact and in general it has been much slower.

I'm not sure what you mean by flood fill. I was thinking about trying a Dijkstra's Algorithm but I don't know that it would be any more efficient.

I have seen other methods where instead of doing direct path finding, you look at lists of connected neighbors with a recursive function - that might be more efficient.

 

[RealityShifter]

5 seconds is a bit much, but if there's a visual component to showing the available movement squares(like highlighting them) it might be cool to pace the A* over 30 steps or so and have the progress show on screen. might look cool and hides the slowness.

 

[Stratadox]

If your grid is static (i.e. the shortest paths don't change during the game) you could look at Floyd-Warshall.

It is an easy to implement algorithm that finds the shortest paths from every start point to every goal.
You can run the algorithm, which is very slow (On^3) when you create the game world.
In the game you only use the result of the algorithm, which is very very fast.

If that isn't an option, look at other A* implementations.
As was said before, 5 seconds is not normal for only 312 squares.
There are implementations that make paths on 100 times the nodes 100 times faster.

 

[NightFrost]

If you're writing your own A* instead of using the inbuilt one (of the mp grid system) you may want to look at A* with Jump Point Search. I haven't looked into it myself because mp grid has been enough for my limited needs of pathfinding so far, but the article claims it speeds up A* "by orders of magnitude."

 

[anomalous]

What do you want:
A. all valid move locations within a radius (range) from the player?
OR
B. all valid move locations near the player based on a fixed number of squares the player can move...which includes extra squares to get around obstacles, etc.

If A: Flood fill is designed for that:
https://en.wikipedia.org/wiki/Flood_fill

if B: you do need pathing of some kind. I assume mp_grid_path if faster than anything you're going to write, largely optimized, in GML. That's just from my experience using all those various algorithms. But if you tested it fairly, so be it!

I think I used this one and it worked, but anyway now you know what I mean.
https://www.reddit.com/r/gamemaker/...rflow_with_flood_fill_script/#bottom-comments

/// floodfill(x,y,oldcolor,newcolor,width,height)

var x1, y1, oldcolor, newcolor, width, height;

oldcolor = argument2;
newcolor = argument3;
width = argument4;
height = argument5;

stack = ds_stack_create();
ds_stack_push(stack, argument0, argument1);

while (ds_stack_size(stack) > 0) {
    y1 = modit(ds_stack_pop(stack), height);
    x1 = modit(ds_stack_pop(stack), width);
    if (var_pixel[x1, y1] != newcolor && var_pixel[x1, y1] == oldcolor) {
        var_pixel[x1, y1] = newcolor;
        ds_stack_push(stack, x1 + 1, y1);
        ds_stack_push(stack, x1 - 1, y1);
        ds_stack_push(stack, x11, y1 + 1);
        ds_stack_push(stack, x11, y1 - 1);
    }
}

 

[NightFrost]

I assume mp_grid_path if faster than anything you're going to write, largely optimized, in GML.

Perhaps. There are refinements to A* and if GML uses vanilla version, it might be possible to write a faster one yourself, like with JPS I mentioned above. It would be interesting to see speed comparisons of various methods (also measured in GM2).

 

[anomalous]

yoyo staff commented that mp_grid_path is not A*, but Mark's home brew.

All I really mean is that based on running other options, I would personally try mp_grid_path on that size, because 5 seconds on 12x12 on a fairly small grid, seems extreme. And mp_grid_path is basically "done", no work required. If he needs A* for other reasons, try them both, no doubt!

 

[andulvar]

If you're writing your own A* instead of using the inbuilt one (of the mp grid system) you may want to look at A* with Jump Point Search. I haven't looked into it myself because mp grid has been enough for my limited needs of pathfinding so far, but the article claims it speeds up A* "by orders of magnitude."

That's an interesting site, I'll look into it. Thanks!

What do you want:
if B: you do need pathing of some kind. I assume mp_grid_path if faster than anything you're going to write, largely optimized, in GML. That's just from my experience using all those various algorithms. But if you tested it fairly, so be it!

All I really mean is that based on running other options, I would personally try mp_grid_path on that size, because 5 seconds on 12x12 on a fairly small grid, seems extreme. And mp_grid_path is basically "done", no work required. If he needs A* for other reasons, try them both, no doubt!

Definitely B. Which is why I need pathing. I can try and see if using mp_grid for the highlighting only works, but my grid it might be difficult to get the grid cells of the mp_grid in the right state. Also remember the move range is the radius so it's actually a 25x25 grid, but that is still relatively small.

5 seconds is a bit much, but if there's a visual component to showing the available movement squares(like highlighting them) it might be cool to pace the A* over 30 steps or so and have the progress show on screen. might look cool and hides the slowness.

It's an interesting idea, but not something I really want to pursue. If I can't get the highlight grid optimized I'll either just remove it or lower the movement maximum.

If your grid is static (i.e. the shortest paths don't change during the game) you could look at Floyd-Warshall.

It is an easy to implement algorithm that finds the shortest paths from every start point to every goal.
You can run the algorithm, which is very slow (On^3) when you create the game world.
In the game you only use the result of the algorithm, which is very very fast.

If that isn't an option, look at other A* implementations.
As was said before, 5 seconds is not normal for only 312 squares.
There are implementations that make paths on 100 times the nodes 100 times faster.

The grid is not static, it changes often.
I will go through the code and make sure I'm not missing something.

 

[andulvar]

I think the found the problem, the A* algorithm I used tested all F and G values to determine the best path to chose. For highlighting, I don't need to find the BEST path, I just need to find out IF a path exists. So anomalous was right that the mp_grid functions would be faster, and they are in this case. So I'll use a hybrid system with mp_grids making the highlight and A* actually choosing the path once movement has been confirmed.

Thanks everyone!

if anyone is curious here on the approach, here is the code for the mp_grid highlight:

Spoiler: mp_grid highlight

//scr_mp_grid_path (x_start, y_start,range,color to tint, alpha of tint, object to create)
//mp grid function using the GML pathing

//vars
var mp_xstart, mp_y_start, mp_origin_x, mp_origin_y, mp_range, mp_color, mp_alpha, mp_object, mp_grid1, world_cell, mp_cell_x, mp_cell_y, mp_row, mp_col, move_cell;

mp_x_start = argument0 //center
mp_y_start = argument1 //center
mp_range = argument2 //movement range
mp_color = argument3 //tint color
mp_alpha = argument4 //tint alpha
mp_object = argument5 //object to create

//set the origin
mp_origin_x = mp_x_start
mp_origin_y = mp_y_start

//convert x,y from center to top left of center cell
mp_x_start -= cell_size/2
mp_y_start -= cell_size/2

//convert from center cell to top left cell
mp_x_start -= mp_range*cell_size
mp_y_start -= mp_range*cell_size

//create the grid
mp_grid1 = mp_grid_create(mp_x_start, mp_y_start, mp_range*2+1,mp_range*2+1,cell_size,cell_size)

//==============   fill the grid with accessible/inaccessible cells  =============
for(mp_col=0;mp_col<mp_range*2+1;mp_col++)
{
    for(mp_row=0;mp_row<mp_range*2+1;mp_row++)
    {
        //get the center x and y coords
        mp_cell_x = mp_x_start+cell_size/2+mp_row*cell_size
        mp_cell_y = mp_y_start+cell_size/2+mp_col*cell_size
      
        //get the real grid cell object
        world_cell = scr_get_cell_at_x_y(mp_cell_x,mp_cell_y,global.grid,global.map,0)
  
        //if not accessible
        if(!world_cell.accessible)
        {
            //do not highlight this cell
            mp_grid_add_cell(mp_grid1,mp_row,mp_col)
        }
    }//rows
}//col

//===================   Test for pathing  ==================
//clear center cell
mp_grid_clear_cell(mp_grid1,mp_range,mp_range)

//check each cell
for(mp_col=0;mp_col<mp_range*2+1;mp_col++)
{
    for(mp_row=0;mp_row<mp_range*2+1;mp_row++)
    {   
        //clear the test path
        path_clear_points(mp_path)
      
        //get the cell center x and y coords
        mp_cell_x = mp_x_start+cell_size/2+mp_row*cell_size
        mp_cell_y = mp_y_start+cell_size/2+mp_col*cell_size
      
        //if no path found
        if(!mp_grid_path(mp_grid1,mp_path,mp_origin_x,mp_origin_y,mp_cell_x,mp_cell_y,1))
        {
            //do not highlight this cell
            mp_grid_add_cell(mp_grid1,mp_row,mp_col)
        }
        else
        {
            //if path found
            //check that the path length does not exceed the range
            if(path_get_length(mp_path)>mp_range*cell_size)
            {
                //do not highlight this cell
                mp_grid_add_cell(mp_grid1,mp_row,mp_col)
            }
            else
            {
                //create a highlighted movement cell
                move_cell = instance_create(mp_cell_x,mp_cell_y,mp_object)
                move_cell.image_alpha = mp_alpha
                move_cell.image_blend = mp_color
              
            }
        }
      
    }
}
//destroy the grid
mp_grid_destroy(mp_grid1)