• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Path finding for custom tiles

Nyymi

Member
I'm trying to create a path finding function to get a list of provinces (tile_id) from start to target. This one works fine until you add actual obstacles when will loop forever. I've tried to rewrite this many times but just can't wrap my mind around it.
I've been using point_distance to jump in the next one but this obviously doesn't work with barriers. My attempts to filter out dead ends haven't worked. Any advice on how to approach this?

About the provinces:
Each province has x, y and a unique string identifier stored as string (tile_id) in a JSON file. They're actually all a top of each other on the room.

GML:
function get_path_to_province(_tile_id, _target_tile_id, _war_list, _name){ // tile id as string
    var path_to_target_lis = ds_list_create();
    
    var _target_x = global.data[? _target_tile_id][? "x"],
        _target_y = global.data[? _target_tile_id][? "y"],
        _found = false;
    
    while (!_found){
            var _lis = global.data[? _tile_id][? "path"],
                _lis_len = ds_list_size(_lis),
                _last_distance = 0,
                _next_tile = _lis[| 0];
            
            for (var i = 0; i < _lis_len; i++;){
                
                var tile = _lis[| i],
                    _id = global.province_id_list[? tile];
                
                if _id.owner == _name or ds_list_find_index(_war_list, _id.owner) != -1{//check if can move to province
                
                    var _distance = point_distance(global.data[? tile][? "x"], global.data[? tile][? "y"], _target_x, _target_y);
                
                    if _last_distance > _distance or _last_distance == 0{
                        _last_distance = _distance;
                        _next_tile = tile;
                    }
                    if tile == _target_tile_id{
                        _next_tile = tile;
                        _found = true;
                        break;
                    }
                }
                // Change province to new tile for next loop
            }//end for
            if _tile_id != _next_tile{
                _tile_id = _next_tile;
                ds_list_add(path_to_target_lis, _next_tile);
            }else{// no next step was found
                _found = true;
                break;
            }
            
    }//end of while
    return path_to_target_lis;
}
 

Attachments

NightFrost

Member
For any pathfinding / traversal through graph-like connectivity - such as your province nodes connected by path edges - you should look at how well-established algorithms such as Breadth-First, Dijkstra and A* solve it. You are on the right mindset but as you've noticed there's still some problems that needs solutions.
 

Nyymi

Member
Thx for the resources bros. I read trough em and reworked mine. This one works for 300+ rounds till it manages to get stuck forever in the second while loop, so it's progress I guess.



GML:
function get_path_to_province(tile_id, target_tile_id, war_list, name){ // tile id as string
    show_debug_message("ENTERING PATH FINDING!");
    
    if tile_id == target_tile_id return undefined;
    
    var target_reached = false,
        frontier_queue = ds_priority_create();
        
    var target_x = global.data[? target_tile_id][? "x"],
        target_y = global.data[? target_tile_id][? "y"],
        path_to_target_list = ds_list_create(),
        reached_list = ds_list_create();
        
    ds_priority_add(frontier_queue, tile_id, 0);
    
    show_debug_message("ENTERING 1st WHILE");
    while (ds_priority_size(frontier_queue) > 0){// GET LIST OF PATH OR CANCEL SEARCH IF IMPOSSIBLE
        
        tile_id = ds_priority_find_min(frontier_queue);
        
        if tile_id == target_tile_id{
            ds_list_add(reached_list, target_tile_id);
            target_reached = true;
            break;
        }
        
        ds_list_add(reached_list, tile_id);
        
        ds_priority_delete_min(frontier_queue);
        
        var paths_list = global.data[? tile_id][? "path"],
            lis_len = ds_list_size(paths_list);
            
            
        for (var i = 0; i < lis_len; i++){// loop trough paths
            var tile = paths_list[| i],
                _id = global.province_id_list[? tile];
            
            if _id.owner == name or ds_list_find_index(war_list, _id.owner) != -1{//check if owner or at war to move in prov

                if ds_list_find_index(reached_list, tile) == -1 and ds_priority_find_priority(frontier_queue, tile) == undefined{//check if owner or at war to move in prov
                    ds_priority_add(frontier_queue, tile, round(point_distance(_id.my_x, _id.my_y, target_x, target_y)));
                }
            }
        }
    }
    
    
    if target_reached{// PATH IS POSSIBLE
        
        ds_list_add(path_to_target_list, reached_list[| 0]);
        ds_list_delete(reached_list, 0);
        show_debug_message("ENTERING 2nd WHILE");
        while (target_reached){// FILTER LIST AND CONSTRUCT PATH
            lis_len = ds_list_size(reached_list)
            var direct_paths = 0,
                path_tiles = array_create(0),
                last_distance = 0,
                next_tile = "";
            for (var i = 0; i < lis_len; i++){// loop trough paths
                tile = reached_list[| i];
                
                if ds_list_find_index(global.data[? tile][? "path"], path_to_target_list[| ds_list_size(path_to_target_list)-1]) != -1{
                    path_tiles[direct_paths] = tile;
                    direct_paths++;
                    
                }else if i == lis_len-1 and direct_paths == 0{// continuation for path not found, take a step back
                    ds_list_delete(path_to_target_list, ds_list_size(path_to_target_list)-1);
                }
            }
            
            for (var i = 0; i < direct_paths; i++){
                _id = global.province_id_list[? path_tiles[i]];
                if last_distance > round(point_distance(_id.my_x, _id.my_y, target_x, target_y)) or last_distance == 0{
                    tile = path_tiles[i];
                    next_tile = "found";
                }
            }
            
            if next_tile != ""{
                ds_list_add(path_to_target_list, tile);
                if tile == target_tile_id target_reached = false;
                ds_list_delete(reached_list, ds_list_find_index(reached_list, tile));
            }
        }
        
        
        ds_list_delete(path_to_target_list, 0);
        show_debug_message("Exiting with ready path");
        return path_to_target_list;
    }else{
        show_debug_message("Exiting no path found");
        return undefined;
    }
}
 

Nidoking

Member
it manages to get stuck forever in the second while loop
while (target_reached)
What were you expecting to cause target_reached to become false? What, in other words, did you think was going to cause the infinite loop to stop?

EDIT: Never mind, I finally spotted it. But it sounds like you're not catching an error state somewhere. Are you finding a path to confirm existence, then throwing it away and searching for another path in a manner that may never reach the goal? You need some kind of sanity check there.
 

Nyymi

Member
What were you expecting to cause target_reached to become false? What, in other words, did you think was going to cause the infinite loop to stop?

EDIT: Never mind, I finally spotted it. But it sounds like you're not catching an error state somewhere. Are you finding a path to confirm existence, then throwing it away and searching for another path in a manner that may never reach the goal? You need some kind of sanity check there.
First while loop crawls towards the target and if it can be reached it passes a list of provinces it visited on the way to the 2nd while where it's used to construct a path.

Basically it checks each province on the list connected to the first prov, locks the shortest option and repeats unless it's a dead end. Then it'll take a step back and delete it.
 

Nidoking

Member
Sounds like a good case study for the debugger, then. Set a breakpoint at the start of the second loop, step through line by line, watch what the program is doing, and see where it isn't doing what you say it's supposed to do.
 
Top