Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Studio Chat / Dijkstra pathfinding Algorithm

Years of Service
User Offline
Joined: 27th Mar 2021
Posted: 4th Jan 2022 20:22 Edited at: 4th Jan 2022 21:41
Hi folks. I have a working pathfinding function which is great for AI. The main function requires three things, the start node, the end node and a graph. You also need some support functions to help gather and process AI information. The main ones are:
makeGraph() // creates a list of nodes which represent the graph input data into the pathfinding function. For example, in a grid[50,50] there will be nodes which contain paths we want to use for the pathfinding. So the makeGraph() function makes a list of all the nodes which have a path: grid[34,65] grid[35,65] grid[36,64] etc. This makeGraph() will also contain the cost to move from one node to another. In a simple pathfinding this cost would be the same (unity or 1). If the paths ever change as part of your game you will need to rerun this function.
smallestElement() //a function which looks through a list and looks for the smallest costSoFar. We use this function because to find the shortest route we should be searching the nodes closest to the start.
callBack() //this function is run after the pathFinding() function has found the endNode. It looks at each nodeNode tracing the route back to the start node. The pathFinding function should leave behind chalk arrows (like breadcrumbs) to show the node it came from (think Hansel and Gretel) and puts these nodes in turn into a list. Because the list is working from the endNode to the startNode the list is in reverse so the last part of the function would be callBackList.reverse(). This list is the shortest route from startNode to endNode.
pathFinding() // makes two lists. One called open and one called closed. These are lists which contain nodes. The open list has all nodes currently open to the pathFinding() function and the closed list holds all the nodes which have been processed by the pathfinding() function.

The pathFinding Pseudo-Code goes something like this:
function pathFinding(graphData , startNode, endNode)
create a new record with the startNode data and place it in the openlist.
mainWhile: openList.length > -1 (remember -1 list length means the list is empty)
smallestElement() /// find the smallest element in the open list
check to see if the node is the endNode, if so then exitFunction
if it isn't the endNode then we carry on with the function
now we look at the graphData and find every node connected to the node we are looking at (the one we got from smallestElement())
whileEveryNode: for every node connected to the node we are looking at:
find out the cost of going to this next node and add it to the costSoFar (for just this node we are looking at. Every node will have a costSoFar depending on how far it is from the start node)
Now check to see if this next node is in the closed list. If it is, do not process this node or add it to the open list, it has already been processed. If it is in the open list then we have found a worse route so just ignore the open list.
If it is not in the closedList then we have found a node not yet processed. Add this unprocessed node to the open list, make sure the nodeCostSoFar has been recorded along with it. (we aren't processing this node, just adding it to the open list) Also make a note in this node of the node it came from (breadcrumbs).
endWhileEveryNode //Now look at another node connected to the node we are looking at by going back to whileEveryNode until we have looked at all the nodes connected to the current node.
Now we have looked at every node connected to the node we are looking at and so the current node has been processed. Add it to the closed list.
endMainWhile// while loop here ends and so we go to the start again for every node in the open list until all the open list nodes have been processed.
We are hear if we have either found the goal or if we've no more nodes to search. If there are no more nodes in the open list and we are not at the endNode then the endNode can not be found from the start location.
If we have found the endNode then run the callBack() function and trace back through each node looking for the one it last came from. Store all this node information in sequence in a list.
Reverse the callBack() list.

Here is a video I made showing Dijkstra at work. The green nodes are open, the red are closed, the blue is the current processed node.

It is possible to make this work with just simple vectors and variables, however, I suggest you create class objects for the nodes. For example my type looked like this

Login to post a reply

Server time is: 2023-10-02 14:47:28
Your offset time is: 2023-10-02 14:47:28