GameMaker Grid based movement range

T

TomKai

Guest
Hi everybody, I need some help !

The game I'm working on is a grid based tactical rpg, and even if I'm managing the rpg part well enough I have some trouble figuring out the tactical movement part.

Here a quick summary of what I'm looking to do :
- When you select a unit, every square in it's movement range gets highlighted.
- You can then click on one of these squares to move to it, without diagonals
- You should not be able to go to a square inside of your range if the path to get there is longer than your range
- When you move, "movement points" are used and your range shortens

To accomplish this I created a ds_grid and stored every wall inside. Then I call this script when my unit is selected :

Code:
// Script Movement_grid
// Takes an origin (x,y) on the grid and a movement range, an returns a movement grid

var x_origin = argument0; // Position on the grid
var y_origin = argument1;
var range = argument2; // Remaining movement points

var mo_grid = ds_grid_create(2*range+1,2*range+1);
var xx, yy, xo, yo;

for(var i = 0; i < 2*range+1; i++)
{
    for(var j = 0; j < 2*range+1; j++)
    {
        xx = (x_origin - range + i) * global.cell_size;
        yy = (y_origin - range + j) * global.cell_size;
        xo = x_origin * global.cell_size;
        yo = y_origin * global.cell_size;
        
        if(mp_grid_path(o_master.map_grid,o_master.map_navigate,xo,yo,xx,yy,false))
        {
            mp_grid_path(o_master.map_grid,o_master.map_navigate,xo,yo,xx,yy,false);
            if( path_get_length(o_master.map_navigate) <= (range * global.cell_size)+1 )
            {
                
            mo_grid[# i,j] = true;
            }
        }
        else
        {
            mo_grid[# i,j] = false;
        }
    }
}

return mo_grid;

ds_grid_destroy(mo_grid);
The ds_gird this returns is then used to display where I can move using squares and to allow movement using mp_ functions. And here's the result with a range of 3 cells :




Could someone help me with this mess ? Please ?
 

NightFrost

Member
Save all the paths that are generated and draw them to get an idea what is happening. Note that mp_grid first tends to path to the center of cell if the origin is not there, and from there towards destination. This does not account for all the oddities in your image, but should give you a start.
 
T

TomKai

Guest
After tweaking with the code I managed to make some stuff work more as intended. Removing temporarily the path length condition restored the range to what it should be and corrected the shape of my range, but pathing around walls still makes you travel more distance than you should (the initial problem I wanted to solve).

But what intrigues me is another problem. When I am closing up to a wall from the top of the left, the square behind that wall can't be pathed to by my loop, but a draw_path function shows that a path clearly exists. So I put my mp_grid back on top and put an empty draw event for the walls and here is what I found :



Don't mind the green square top left of my object, that's just where the cursor was before taking the picture. The weird stuff is lower than that, inside the red squares. Those are where my walls are. As you can see, my loop is not only telling me it can't reach perfectly good to go to cells of the grid, but it is telling me that inside this solid wall there is a valid movement target.

Now if anyone on this forum can explain to me what is going on, I'd be very grateful thank you

Here's the code :

Player Object
Code:
// Step Event
// Position
x_pos = x div global.cell_size;
y_pos = y div global.cell_size;

x_to = global.grid_mouse_x;
y_to = global.grid_mouse_y;
        
if(left_click)
{
    var cond_xx = x_to-x_pos;
    var cond_yy = y_to-y_pos;
            
    var condition_move = (cond_xx <= dep) && (cond_xx >= -dep) && (cond_yy <= dep) && (cond_yy >= -dep);
    condition_move = condition_move && move_range[# (range+cond_xx),(range+cond_yy)] == true
            
    if(condition_move)
    {
        scr_navigate( (x_pos+0.5)*global.cell_size, (y_pos+0.5)*global.cell_size, (x_to+0.5)*global.cell_size, (y_to+0.5)*global.cell_size);
        x = floor(x);
        y = floor(y);
    }
}

Movement Range Script
Code:
// Script Mouvement_grid
// Takes an origin (x,y) on the grid and a movement range, an returns a movement grid

var x_origin = argument0 +0.5;
var y_origin = argument1 +0.5;
var range = argument2;

var mo_grid = ds_grid_create(2*range+1,2*range+1);
var xx, yy, xo, yo;

for(var i = 0; i < 2*range+1; i++)
{
    for(var j = 0; j < 2*range+1; j++)
    {
        xx = (x_origin - range + i) * global.cell_size;
        yy = (y_origin - range + j) * global.cell_size;
        xo = x_origin * global.cell_size;
        yo = y_origin * global.cell_size;
       
        if(mp_grid_path(o_master.map_grid,o_master.map_navigate,xo,yo,xx,yy,false))
        {
            //if( path_get_length(o_master.map_navigate) <= (range * global.cell_size)+1.5 )
            if(abs(xx-xo) + abs(yy-yo) <= range * global.cell_size)
            {
               
            mo_grid[# i,j] = true;
           
            }
        }
        else
        {
            mo_grid[# i,j] = false;
        }
    }
}

return mo_grid;

ds_grid_destroy(mo_grid);

Grid Setup
Code:
global.cell_size = 16;
map_grid_height = ceil(room_height/global.cell_size);
map_grid_width = ceil(room_width/global.cell_size);

map_grid = ds_grid_create(map_grid_width,map_grid_height);
ds_grid_clear(map_grid, 0);
map_mp_grid = mp_grid_create(0,0,map_grid_width,map_grid_width,global.cell_size,global.cell_size);
mp_grid_add_instances(map_grid,o_wall_parent,false);
map_navigate = path_add();

turn_order = ds_list_create();



turn = 0;
turn_max = ds_list_size(turn_order);
turn_ended = true;
need_turn_order = true;

global.grid_mouse_x = mouse_x div global.cell_size;
global.grid_mouse_y = mouse_y div global.cell_size;

Navigation Script
Code:
///scr_navigation(start_x,start_y,end_x,end_y);
var start_x = argument0;
var start_y = argument1;
var end_x = argument2;
var end_y = argument3;

if ! (mp_grid_path(o_master.map_grid,o_master.map_navigate,start_x,start_y,end_x,end_y,false))
{
    show_message("Unable to navigate");
}
else
{
    mp_grid_path(o_master.map_grid,o_master.map_navigate,start_x,start_y,end_x,end_y,false)
    path_start(o_master.map_navigate, 3,0,false);
    is_moving = true;
    return true;
}
 

Yal

🐧 *penguin noises*
GMC Elder
One thing that intrigues me is that the area blocked by the wall is the correct size, just not the correct place. Could perhaps be a sprite / collision mask / origin issue?

Back when I made Shattered World, I coded my own A* algorithm... the good thing with doing that is that you've got more control, and especially the range check is super easy (keep track of how far the total path is, and if you've reached range cells, stop adding neighbor cells to the queue when processing cells). My path-creating approach was giving each movement cell a string, adding "u", "d", "l" or "r" based on which direction it was a neighbor to the previously checked tile.

A* is pretty simple to implement:
  1. Create a queue and a "already checked" list. Figure out a format for data to store in them (you need to store the path needed to reach them, possibly their x/y coordinates as well).
  2. Start with the current cell and put it in a queue.
  3. While the queue isn't empty:
    1. Check if any of the neighbors is a valid destination, and haven't been checked before yet.
    2. Valid destinations aren't blocked, and are within your movement range.
    3. Any neighbor that is valid: add it to the queue. Base their path data on the currently considered cell, and append a step in the direction from current cell to neighbor. Also add it to the "already checked" list.
  4. When the queue is empty, the "already checked" list contains all valid destinations. Now you can draw them or create a menu for the player to pick a destination or whatnot.
 

TheouAegis

Member
Out of curiosity, what happens if you swap i and j around here:
mo_grid[# i,j] = true;​
and here:
mo_grid[# i,j] = false;​
 
T

TomKai

Guest
Big news, I found what what causing the misplaced walls weirdness. It was simply a dumb mistake.

You see, I was storing my grid position at the start of every frame using a "div x/y". But since I was calling my range check at the path end, the top left corner (my sprite's origin point) is always registered one frame too late. So the game calculates my range from the wrong cell before displaying it.

I changed my function call so it takes my target cell as a starting point instead of my stored position, and it worked ! So now my script works like a charm even when i put a path length check.

Thank you Yal, your comment on the range being "the right shape but wrong position" made me realize my mistake. My game jam is saved !
 
T

TomKai

Guest
Out of curiosity, what happens if you swap i and j around here:
mo_grid[# i,j] = true;​
and here:
mo_grid[# i,j] = false;​
Unfortunately not much, except the range drawn is diagonally flipped from what it should be.
 
I'm also working on a game with strategy-RPG-style combat. I'm a little beyond figuring out pathfinding, but I'd love to share some pointers!

I highly recommend looking up Dijkstra maps -- in particular, how some roguelikes use them for pathfinding. A* isn't ideal for situations when you don't have a set goal (such as creating a movement range grid) and using a Dijkstra map to set up a range grid is extremely simple. Here's a visualization and basic explanation of the exact steps required to achieve it:
screenshot(10).png
 

NightFrost

Member
Yeah Djikstra's is good for goal-less "grid painting" because A* is the same as Dijkstra plus an added heuristic calculation that attempts to bias the search towards goal. With small search areas like that though, I'm not sure if hand-written Dijkstra would be faster than GMS mp_grid (already optimized, and written in C++?). I have wrtitten a Dijkstra but never really done a comparison.
 

Yal

🐧 *penguin noises*
GMC Elder
Yeah Djikstra's is good for goal-less "grid painting" because A* is the same as Dijkstra plus an added heuristic calculation that attempts to bias the search towards goal. With small search areas like that though, I'm not sure if hand-written Dijkstra would be faster than GMS mp_grid (already optimized, and written in C++?). I have wrtitten a Dijkstra but never really done a comparison.
There's some caveats, like how GMS' built-in mp_grid only works on a square flat grid (so it can't be used for hex grids or 3D pathfinding)... all you need to change in a custom implementation is how to define / list neighbors and the same core can be used for arbitrary pathfinding. In programming, speed is almost always achieved through loss off generality, and generality always achieved through loss of speed.
 

NightFrost

Member
Indeed. Dijkstra code (and A*) can be sped up on a grid (as is OP's case) by not using a neighbours list, because grid neighbours always are [current + 1], [current - 1], [current - width] and [current + width]. There's the issue of grid edges, but if you make sure your outermost grid cells are always impassable, you don't need to check for edges because the search never goes there.

(digression: one would want to write their own A* instead of using mp_grid in cases like variable movement costs, as mp_grid always has the cost of one to enter a new cell.)

EDIT I should have specified that those neighbour values are for 1d array. I haven't found a reason to use 2d array as it just adds a second variable to position tracking, making it [x, y] instead of [position]. Since grid width is known, 1d array can be used.
 
Last edited:

Yal

🐧 *penguin noises*
GMC Elder
(digression: one would want to write their own A* instead of using mp_grid in cases like variable movement costs, as mp_grid always has the cost of one to enter a new cell.)
Good point! Also reminded me of another important factor a lot of tactics-RPGs uses: terrain height. Cells might be obstacles based on which direction you enter them from if jump height is a factor, even if they're free. Not to mention objects that are obstacles normally but valid terrain if you can reach the top of them (crates, storage containers, and anything else with a flat upper surface).
 
Top