A* / Dijkstra pathfinding

Here's an immediate view of what the pathfinding does in the framework...

So here's the explanation. Bot Tournament #2 required pathfinding for the specific LO for it. So here it is, I did it.
In terms of how we went about this, here's some pseudo code, that I totally didn't already have written by our lecturer and just rewrote, of how the path is calculated.

-> Clear map data
-> Push the start node to the open node list
-> Loop, and keep looping, until the open node list is empty and the path is found
    -> Loop over the open node list and store the lowest F value temporarily, at the end, simply return the temporary variable
    -> Remove the current node from the open node list and change its state to closed

    -> Loop from -1 to 1 as oy | for(var oy = -1; oy < 2; oy++)
        -> Loop from -1 to 1 as ox | for(var ox = -1; ox < 2; ox++)
            -> If ox and oy == 0, then skip this loop iteration
            -> If ox and oy != 0, then skip this loop iteration
            -> If the adjacent node is a wall, then skip  this loop iteration
            -> Adjacent_node = The current node position + (ox, oy)
            -> New G = current node G + adjacent_node.C
            -> If adjacent_node is closed, then just do nothing (don't skip)
            -> Else if adjacent_node is open and new G less than (<) adjacent_node.G
                -> Adjacent_node.G = new G
                -> Adjacent_node.H = Heuristic | absolute(adjacent_node.X - destination.X) + absolute(adjacent_node.Y - destination.Y)
                -> Adjacent_node.Parent = The current node position
                -> Adjacent_node.F = adjacent_node.G + adjacent_node.H

            -> Else if adjacent_node is unused
                -> Adjacent_node.G = new G
                -> Adjacent_node.H = Heuristic | absolute(adjacent_node.X - destination.X) + absolute(adjacent_node.Y - destination.Y)
                -> Adjacent_node.Parent = The current node position
                -> Adjacent_node.F = adjacent_node.G + adjacent_node.H
                -> Set adjacent_node to open and push it to the open node list
            -> If adjacent_node = The target node
                -> Path has been found, set it to true so the first loop can break
        -> End loop
    -> End loop
--> End loop

Following that pseudo code makes the program look at every possible node and make it branch out. Basically using Dijkstra to fill the map of known values, then follow it the shortest path based on the values of each node. This isn't quite A* since it looks around itself for the smallest value to the destination, then moves based on that. So it only fills in what it needs rather than keeping information about the whole map when you probably don't need to.

Tom Lynn

Read more posts by this author.

Australia http://rubbix.net