Legacy GM Breadth-first pathfinding algorithm[problem][Solved]

[Sanil]

Hello fellow programmers, I was trying to create a pathfinding algorithm using breadth-first search and using enqueues and dequeues...... I had seen a post on a*(star) algorithm and I was adapting that to my algorithm(bad idea?) an ways here is the code I was trying to adapt it from...

/*
getShortestPath(SourceNode, TargetNode): ds_list
Computes the shortest path between the two nodes.
Returns a ds_list containing all the nodes in the path (first and last are included)
If a path could not be found, noone is returned
*/

var Source, Target, OpenedList, ClosedList, PreviousNodes, TentativeDistances, CurrentNode, End, Connections;
var tentativeDistance, Score, heuristicValue, lastConnection, currentScore;

Source = argument[0];
Target = argument[1];

OpenedList = ds_priority_create(); //{Value: Node, Priority: Score}
ClosedList = ds_list_create();
PreviousNodes = ds_map_create();//{Key: Node, Value: PreviousNode}
TentativeDistances = ds_map_create(); //{Key: Node, Value: Distance}

CurrentNode = noone;
ds_priority_add(OpenedList, Source, 1);
ds_map_add(TentativeDistances, Source, 0);

while (ds_priority_size(OpenedList) > 0) {
    CurrentNode = ds_priority_find_min(OpenedList);

    if (CurrentNode == Target) {
        break;
    }

    ds_priority_delete_min(OpenedList); //Remove current node
    ds_list_add(ClosedList, CurrentNode);
 
    Connections = __Nodes[CurrentNode, 1];
    End = false;
    lastConnection = ds_map_find_last(Connections);
    for (var Neighbour = ds_map_find_first(Connections); End == false;
        Neighbour = ds_map_find_next(Connections, Neighbour)) {
        if (Neighbour == lastConnection) {
            End = true;
        }
    
        if (ds_list_find_index(ClosedList, Neighbour) != -1) {
            continue;
        }
    
        if (!filterPath(id, Neighbour)) {
            continue;
        }
    
        tentativeDistance = ds_map_find_value(Connections, Neighbour) + ds_map_find_value(TentativeDistances, CurrentNode);
        heuristicValue = getHeuristic(Neighbour, Target);
    
        if (!ds_map_exists(TentativeDistances, Neighbour)) {
            ds_map_add(TentativeDistances, Neighbour, tentativeDistance);
        } else if (tentativeDistance < ds_map_find_value(TentativeDistances, Neighbour)) {
            ds_map_replace(TentativeDistances, Neighbour, tentativeDistance);
        }
    
        currentScore = ds_priority_find_priority(OpenedList, Neighbour);
        Score = ds_map_find_value(TentativeDistances, Neighbour) + heuristicValue + 1;

        if (Score < currentScore || currentScore == 0 || is_undefined(currentScore)) {
            if (currentScore == 0 || is_undefined(currentScore)) {
                ds_priority_add(OpenedList, Neighbour, Score);
            } else {
                ds_priority_change_priority(OpenedList, Neighbour, Score);
            }
        
            if (!ds_map_exists(PreviousNodes, Neighbour)) {
                ds_map_add(PreviousNodes, Neighbour, CurrentNode);
            } else {
                ds_map_replace(PreviousNodes, Neighbour, CurrentNode);
            }
        }
    }
}

ds_priority_destroy(OpenedList);
ds_list_destroy(ClosedList);
ds_map_destroy(TentativeDistances);
 
if (CurrentNode != Target) {
    ds_map_destroy(PreviousNodes);
    return(noone);
}


var Path;
Path = ds_list_create();
while (true) {
    ds_list_add(Path, CurrentNode);

    if (CurrentNode == Source) {
        reversedPath = ds_list_create();
        for (i = ds_list_size(Path) - 1; i >=0; i-=1) {
            ds_list_add(reversedPath, ds_list_find_value(Path, i));
        }
    
        ds_list_destroy(Path);
        ds_map_destroy(PreviousNodes);
        return(reversedPath);
    }

    CurrentNode = ds_map_find_value(PreviousNodes, CurrentNode);
}

and this is my own code .....

//scr_length_first(startnode, endnode);\

//This script will initialise a length first
//path finding search using queues
//and enqueue and dequeue functions

var UnexploredQueue, ExploredList, StartNode, EndNode, CurrentNode, Connections, End;

StartNode = argument[0];//The initial node
EndNode = argument[1];//Thelast node

ExploredList = ds_list_create();//Creates a list
UnexploredQueue = ds_queue_create();//Creates a queue

CurrentNode = noone;//Sets the current node to nothing

ds_queue_enqueue(UnexploredQueue, StartNode);//Puts the initial node at the top of the queue


while ds_queue_size(UnexploredQueue) > 0
{
    CurrentNode = ds_queue_head(UnexploredQueue);//Stores the top value of queue in a variable
  
    if CurrentNode == EndNode//Checks if we have reached the target
    {
        break;//Ends the script if the condition is true
    }

    ds_queue_dequeue(UnexploredQueue);//Removes the topmost node of queue
    ds_list_add(ExploredList, CurrentNode);//Adds the current(explored) node to the explored list
  
    Connections = Nodes[CurrentNode, 1]
    End = false;
  
  


}

please mind that it is still incomplete..... this is the link to the original post can someone please help me understand a few thing like what does the connections, end , filterpath do in the original code and how can I adapt it to my case. I know it is a lot to ask but anyone's help will be extremely appreciated.... thank you for atleast reading the whole post in advance.....
[Edit]- I just realized that you cannot color text in a code block so you will have to search for the words yourself I am sorry

 

[CaffeineJunky]

First comment: Don't really care to check the head of the queue. Just pop off the next item on the queue and be done with it, unless you explicitly have a reason to keep it on the queue. (This is rare and you should have a really compelling reason why; checking the element to break a loop is not one of them.) Do the comparison after the item has been dequeued, or you might be subject to subtle bugs.

Second, the idea of this search is that we need to understand the following information about a breadth first search:

1.) What a node is. Typically, a node is a vertex of some graph, and is connected to other nodes by edges. A square grid in the x, y plane can be viewed as nodes, and each node here has four neighbors. The pair (node, neighbor node) is the edge, or connection if you like.

2.) We need to understand how the breadth first search is working:

1. We start with a single node as the starting point.
2. We create a queue (why?)
3. We add the single starting node to the queue.
4. We start a generic loop until the queue is completely exhausted that does the following:
   1. Take the next item on the queue off of the queue so we can inspect it.
   2. If this is the goal node, then we are done, and we want to return the goal node and we can stop searching.
   3. If it is not the goal node, then we get all of the neighbors that have not been checked (why do we only want the ones that we haven't checked?) and then we put each of these onto the queue.
   4. We add this node to the list of nodes that we have checked already.
5. If at this point nothing has been returned and the queue has been exhausted, we return nothing (because nothing was to be found).

This is the general strategy for a breadth first search. If you cannot immediately answer the whys above, that's OK. But play around with this and you should be able to answer this. If it is helpful, manually walk through the process using a pencil and paper with a grid on it.

3.) One you come to an understanding of how the breadth first search works, then it should be clear on how it can be used to find one (of possibly several) shortest paths through the graph that we have. A few things to point out though:

1. HopWe will have additional restrictions on which neighbors we are adding onto the queue. For example, if node is 'impassable', then we shouldn't add that node to the queue when it comes time to check for the neighbors and add them to the queue.
2. It is important to keep track of the entire path, which is a list of nodes, instead of just the final node. That path is what we are looking for, after all.
3. We (and this is important) have modified the usage of a queue in the simple breadth first search to use a priority queue. Simply put, this will always grab the element with the lowest priority first, which will typically be the length of the path that we're keeping track of. However, it appears the original script also wants to account for diagonal movement, so they use a heuristic function to compute that priority instead of just the number of elements on the path. (A diagonal movement is scored as 1.4, because that's roughly the length of the diagonal of a square.) This isn't explicitly provided, but I'm assuming that this is what the author of the script is going for.

Hopefully this isn't too confusing and it helps.

 

[Sanil]

Hey @CaffeineJunky thanks for replying I know it must have been tough to read all that code, I think I now have a really clear understanding of how a breadth first search works but I have a couple of questions....
1. You said

we get all of the neighbors that have not been checked (why do we only want the ones that we haven't checked?) and then we put each of these onto the queue.

Now my question is how do we ask the program to, like check all the neighboring nodes
2. This system uses nodes which are basically grids right, so how do I create a grid like system in gml(sorry I am not too familiar with all this).
3. My last question would that how would we create a number system for each node because this program does not take x, y coordinates?

Sorry if these questions are really dumb.... it is my first time doing something like this so I am not sure as to what to do. I would highly appreciate it if you replied......Thank you in advance

[edit]- I think I got the answer to the first question.... If you look somewhere after the loop ending statement there is a variable"Connections" which is a 2D array(?) and stores the value of neighbors into a variable.... Am I right?

 

[CaffeineJunky]

Now my question is how do we ask the program to, like check all the neighboring nodes

The assumption in advance is that you are working with a concept called a graph. A graph in this context is a set of nodes, called vertexes, which are points, and a collection of connections between nodes, called edges. In particular, for any given vertex, you should know what the edges that are connected to it, and consequently since you know the edges, you know the vertexes on the other side of the edges, which are called the neighbors.

When working with a grid that has (u, v) coordinates, we can implicitly come up with a graph and 'skip' the edges entirely by saying that a neighbor is (u -1, v), (u +1, v), (u, v - 1), (u, v + 1), for up, down, left, and right, and (u - 1, v - 1), (u - 1, v + 1), (u + 1, v - 1), and (u + 1, v + 1) if you allow diagonals. I would discourage this use and instead create all of the nodes that you want in a data structure (a vertex is a map, an edge is a map, and a vertex holds an array of edges) for each grid item that you want, because I tend to find this makes handling corner cases easier.

Then the question of "how do I find my neighbors" becomes "how do I look at my data structures to find my neighbors".

This system uses nodes which are basically grids right, so how do I create a grid like system in gml(sorry I am not too familiar with all this)

Use a loop to do this at first, but then consider using a JSON data structure that you can edit outside of your application for designing the node sets. Save this aspect for later though until you understand the full picture.

My last question would that how would we create a number system for each node because this program does not take x, y coordinates

I wouldn't worry about this at the moment, as usually it is not needed. Instead, you'll typically infer the distances using a "manhattan distance" at first, which is the number of nodes that are away. Later on, you can assign as part of an edge data structure a weight on the cost to travel along an edge. The A* algorithm, for example, uses a score of 1 for traveling up, down, left, and right, and a score of 1.4 for moving diagonally. The coordinates should not matter, but if you find you still need them, contact me later after you've explored not using them and I can help provide some guidance of that. I'm not super active though, so sorry if I miss the response.

 

[Sanil]

@CaffeineJunky Thank you for your help I highly appreciate it... this post along with some more research on data structures especially ds_map and ds_grid really helped me understand what the above A* algorithm was all about....As far as x, ,,y coordinates go, yes this system does not require x, y coordinates and I will hopefully be able to create a grid myself.... Again thank you for all your help it must have been difficult to go through all that code....