8 replies to this topic

[Fragment]

Hello GMC, I am creating a tactics engine using the script below for my pathfinding.

/*
    arg0 -- starting cell id
    arg1 -- movement range
*/

{
    var _start, _moverange;
    _start = argument0;
    _moverange = argument1;

    var _priorityOpen, _listClosed, _mapDist;
    _priorityOpen = ds_priority_create();
    _listClosed = ds_list_create();
    _mapDist = ds_map_create();
    
    ds_priority_add( _priorityOpen, _start, 0 );
    ds_map_add( _mapDist, _start, 0 );
    _start.Parent = 0;
    _start.Reachable = true;
    
    while ( ds_priority_size( _priorityOpen ) )
    {
        var _current;
        _current = ds_priority_delete_min( _priorityOpen );
        ds_list_add( _listClosed, _current );
        
        var _predist;
        _predist = ds_map_find_value( _mapDist, _current );
        
        with ( _current.Right )
        {
            var _dist;
            _dist = _predist + Cost;
            if ( ds_list_find_index( _listClosed, id ) == -1 && Cost && _dist <= _moverange )
            {
                if ( ds_priority_find_priority( _priorityOpen, id ) == 0 )
                {
                    ds_priority_add( _priorityOpen, id, _dist );
                    ds_map_add( _mapDist, id, _dist );
                    Parent = _current;
                    Reachable = true;
                }
                else
                {
                    if ( _dist < ds_priority_find_priority( _mapDist, id ) )
                    {
                        ds_priority_change_priority( _priorityOpen, id, _dist );
                        ds_map_replace( _mapDist, id, _dist );
                        Parent = _current;
                    }
                }
            }
        }

        with ( _current.Up )
        {
            var _dist;
            _dist = _predist + Cost;
            if ( ds_list_find_index( _listClosed, id ) == -1 && Cost && _dist <= _moverange )
            {
                if ( ds_priority_find_priority( _priorityOpen, id ) == 0 )
                {
                    ds_priority_add( _priorityOpen, id, _dist );
                    ds_map_add( _mapDist, id, _dist );
                    Parent = _current;
                    Reachable = true;
                }
                else
                {
                    if ( _dist < ds_priority_find_priority( _mapDist, id ) )
                    {
                        ds_priority_change_priority( _priorityOpen, id, _dist );
                        ds_map_replace( _mapDist, id, _dist );
                        Parent = _current;
                    }
                }
            }
        }
        
        with ( _current.Left )
        {
            var _dist;
            _dist = _predist + Cost;
            if ( ds_list_find_index( _listClosed, id ) == -1 && Cost && _predist + Cost <= _moverange )
            {
                if ( ds_priority_find_priority( _priorityOpen, id ) == 0 )
                {
                    ds_priority_add( _priorityOpen, id, _dist );
                    ds_map_add( _mapDist, id, _dist );
                    Parent = _current;
                    Reachable = true;
                }
                else
                {
                    if ( _dist < ds_priority_find_priority( _mapDist, id ) )
                    {
                        ds_priority_change_priority( _priorityOpen, id, _dist );
                        ds_map_replace( _mapDist, id, _dist );
                        Parent = _current;
                    }
                }
            }
        }
        
        with ( _current.Down )
        {
            var _dist;
            _dist = _predist + Cost;
            if ( ds_list_find_index( _listClosed, id ) == -1 && Cost && _predist + Cost <= _moverange )
            {
                if ( ds_priority_find_priority( _priorityOpen, id ) == 0 )
                {
                    ds_priority_add( _priorityOpen, id, _dist );
                    ds_map_add( _mapDist, id, _dist );
                    Parent = _current;
                    Reachable = true;
                }
                else
                {
                    if ( _dist < ds_priority_find_priority( _mapDist, id ) )
                    {
                        ds_priority_change_priority( _priorityOpen, id, _dist );
                        ds_map_replace( _mapDist, id, _dist );
                        Parent = _current;
                    }
                }
            }
        }
    }
    
    ds_priority_destroy( _priorityOpen );
    ds_list_destroy( _listClosed );
    ds_map_destroy( _mapDist );
}

However, I am having trouble allowing my player to simulate the movement along the path. I have got the script working but I only know how to make the player move instantly to their goal.
Could anyone help me out?

Preferably it would return something that would allow me to just get a list of movements such as
arrayvar[0]="up";
arrayvar[1]="up";
arrayvar[2]="left";
arrayvar[3]="left";
arrayvar[4]="down";

I am guessing the script has put the directions in the dslist in the form of 1/2/3/4 depending on the direction, however, i am not too familiar with ds lists.

Edited by Fragment, 16 May 2012 - 01:26 AM.

[Yal]

When I computed valid movement cells for characters in Daemon Detective, I used onion-peel recursion. The basic idea is:

fill grid CANMOVEHEREGRID with FALSE and grid MOVESTRINGGRID with empty strings.
Make a queue.
Make some storage structure OLDCELLS.
Push the cell you are at to the queue, together with a MOVESLEFT value and a empty movement string "".

While the queue is not empty,
{
__take the first element of the queue. Remove it from the queue.
__Read its MOVESLEFT into var MV and its MOVESTRING into var MS.
__For all neighbouring cells (up, down, left, right),
__{
____if the cell is valid (aka not outside the map, for instance),
____if the cell is NOT in the OLDCELLS structure,
____{
______put the cell in OLDCELLS.
______add the cell to the queue with a MOVESLEFT of MV - 1 and a movestring of MS + "u" (if this cell is the ABOVE cell)
______set the cell with these coords in the CANMOVEHEREGRID to TRUE
______set the cell with these coords in the MOVEMENTSTRINGGRID to the movestring you just computed (MS + "u" in this case)
____}
__}
}

When you try to move the character to a cell, check the CANMOVEHEREGRID to see if that cell is valid (value TRUE) and if so make a "moving character" object with the movestring at the corresponding cell in the MOVEMENTSTRINGGRID. Then just chew one letter at a time and move one cell in that direction.

The good thing with this method? It works for ALL sorts of grid layouts, including hex grids and multilevel playfields.

[Gamer3D]

However, I am having trouble allowing my player to simulate the movement along the path. I have got the script working but I only know how to make the player move instantly to their goal.
Could anyone help me out?

For each cell in the open and closed sets, store the cell that it was reached from (or instructions on how to reach it). An array or grid would work just fine; no need to initialize it to some value either, so you can re-use the array without wasting time to reset it. When the goal is found, backtrack.

By the way, ds_priority_find_priority is a slow operation with no good way to improve it. In GM it's not slower than the other ds_priority functions, but even if the others are improved, it remains at that slow speed. Same goes for ds_priority_find_value.

Edited by Gamer3D, 16 May 2012 - 11:04 PM.

[Yal]

For each cell in the open and closed sets, store the cell that it was reached from (or instructions on how to reach it).

Which is exactly what my Onion Peeling Recursion does with you appending to a movement string.


In my implementation I used directional vars to be able to for loop through stuff, something like this:

var dx, dy, ds;
dx[0] = 1
dy[0] = 0
ds[0] = "r"
dx[1] = 0
dy[1] = -1
ds[1] = "u"
dx[2] = -1
dy[2] = 0
ds[2] = "l"
dx[3] = 0
dy[3] = 1
ds[3] = "d"


//<snip>


while(queue_isnt_empty()){

pan = panel_get_from_queue()
at_x = pan.x
at_y = pan.y
at_string = pan.string

for(c = 0;c < 4;c += 1){
  new_x = at_x + dx[c]
  new_y = at_y 0 dy[c]
  movestring = at_string + ds[c]
  if(panel_is_valid(new_x,new_y)){
    if(panel_is_not_visited_before(new_x,new_y)){
      panel_visit(new_x,new_y)
      panel_add_to_queue(new_x,new_y,movestring)
    }
  }
}
}

[Zeddy]

When I computed valid movement cells for characters in Daemon Detective, I used onion-peel recursion. The basic idea is:

...

That sounds a lot like the ancient, tried-and-true A*

Edited by zeddidragon, 21 May 2012 - 08:25 AM.

[Yal]

Oh. It actually does. Rats.

[Mnementh]

Wow. Who wrote that code? It's awful.

Anyway, the idea for movement is that the algorithm's "map" is stored in the parent map - by "parent", I merely meant "cell from which this cell was reached". Like Gamer3D said, backtracking through the map will produce the path. You can see an example of this in the tutorial in my signature.

By the way, ds_priority_find_priority is a slow operation with no good way to improve it. In GM it's not slower than the other ds_priority functions, but even if the others are improved, it remains at that slow speed. Same goes for ds_priority_find_value.

There is an alternative to the priority queue. For most games, each cell has a movement cost, rather than each transition. Dijkstra's algorithm is optimal for a general graph, but for a graph with this constraint, a modified breadth-first search is equivalent. However, where Dijkstra's algorithm in this usage will never expand a node twice, breadth-first search may perform many repeated expansions. My thoughts were that BFS will probably perform better for short searches, and Dijkstra's will probably perform better on longer searches, or whenever there is a lot of variation in movement cost.

Oh. It actually does. Rats.

Not quite. What you've posted is essentially an augmented version of breadth-first search, which doesn't return a minimum spanning tree in general, although it does in this case. Dijkstra's algorithm, on the other hand, does return the minimum spanning tree; it's a natural extension from BFS, using a priority queue. A*, in comparison, returns a single shortest path between two points; it is also a natural extension of Dijkstra's algorithm which uses a heuristic function to weight movement costs.

Aside: I've never heard the term "onion-peel recursion" before. What does it mean?

[Desert Dog]

Aside: I've never heard the term "onion-peel recursion" before. What does it mean?

I'd assume that onion-peel refers the the way a BFS search checks each 'layer' of connecting nodes first, before progressing onto the next depth. Like eating an onion (starting from the inside)

[Yal]

Yup, that's what I meant. Like an onion (and some other fruits) the BFS is "layered" with each layer being at the same distance from the point you start at. I envisioned the algorithm creating an onion around the starting point rather than eating it, though.

The recursion path comes from the fact that the algorithm code is along the lines of "for each node, do this stuff; then for each neighbour node, do this stuff, then for each of their neighbour nodes,..."... but I'm not sure if it's recursive or iterative using the queue approach, actually.



Also, in my approach I've never tried to find the "shortest" path, I've just wanted to find all panels possible to reach together with the [shortest] movement one has to take to reach it. The player can move to any desired panel; enemies check all panels they can reach using this and chooses the one with the highest score (mainly computed via player positioning).