Graph Search

Graph search algorithms like Dijkstra’s Algorithm and A* work on weighted directed graphs, sets of nodes connected by edges that have numeric weights (movement costs) attached to them.

Graph Show

Properties of graphs

A mathematical graph is a set of nodes and edges. The nodes (also called vertices or objects) are connected together by the edges (also called links or connections or arrows or arcs). For any graph we need to know two things:

1. Set of nodes: A B C D E F G
2. Set of edges from eac node:
   • A: A →B A →D A → G
   • B: B → A B →C B → F

Variants

• An undirected graph has edges that go in both directions. This is pretty common for game maps. In the example earlier, each undirected edge such as B↔C was listed twice, once as B→C and once as C→B.
• A directed graph has edges that can go one direction but not the other. One-way doors, jumping off a ledge, and portals can be one-way edges in games. A graph can have edge B→C without having edge C→B.
• A multigraph can have multiple edges between the same nodes. Being able to swim across a river or take a raft across the same river is an example in games. Node B could have more than one edge B→C leading to node C.

Obstacles

1. Remove nodes: If obstacles occupy grid squares, you can remove those nodes from the graph (all_nodes). You also need to remove the corresponding edges, which happens automatically if you’re using “if neighbor in all_nodes” to test whether an edge is added, but not if you’re testing whether x/y are in range.
2. Remove edges: If obstacles occupy the borders between squares, you can remove those edges from the graph by adding an additional check in the neighbors() function. If obstacles occupy the squares, you can remove the edges that lead to those squares.
3. Infinite weight edges: If obstacles occupy the borders between squares, you can mark those edges with Infinity as the weight. If obstacles occupy the squares, you can mark edges leading to obstacles as having Infinity as the weight. In your graph search function, you’ll have to exit before visiting nodes with Infinity as the cost.

A Visual Explanation of Jump Point Search

Jump Point Search

PathFinding.js

Pseude Code

make an openlist containing only the starting node
   make an empty closed list
   while (the destination node has not been reached):
       consider the node with the lowest f score in the open list
       if (this node is our destination node) :
           we are finished 
       if not:
           put the current node in the closed list and look at all of its neighbors
           for (each neighbor of the current node):
               if (neighbor has lower g value than current and is in the closed list) :
                   replace the neighbor with the new, lower, g value 
                   current node is now the neighbor's parent            
               else if (current g value is lower and this neighbor is in the open list ) :
                   replace the neighbor with the new, lower, g value 
                   change the neighbor's parent to our current node

               else if this neighbor is not in both lists:
                   add it to the open list and set its g