This describes how the character moves in the game world, including navigation and action queue.
We use the fact, that the game world was divided to tiles (as described
Therefore, a node is placed on each tile / square, and the nodes are connected. By default, a node is connected to all adjacent, with connection length of \(1\).
In this case, Dijkstra's algorithm (BFS) is used.
It is worth saying, that all computed graphs are cached along with all queries and results passed to navigation mesh, maximizing the speed and performance
The graph, allthough it looks like it is simple grid, is not a simple grid.
Each transition between nodes can have any weight \(w\), defining the length of transition.
All nodes, however, are placed in grid-like structure (they follow pattern).
However, if in map shall be long corridor, then instead of using 9 nodes, only 2 nodes with longer edge can be used.
Dijkstra's algorithm takes advantage of weights on edges between nodes, to prioritize the shortest path.
Another huge advantage is, that entire graph can be precomputed and saved, and multiple queries can be satisfied
using one precomputed graph.
This is because of algorithm progress depends on start node, but not on end nodes.
In other words, for fixed start node \(A\), one precomputed graph instance can be used to find shortest path to any node \(B\).
A* algorithm takes advantage of the grid-like structure (or any structure) of graph.
The graph structure is used to determine heuristic function to prioritize next explored node.
Entire graph can not be precomputed and saved for multiple queries, because algorithm progress depends on start node, but also on set of end nodes.
Saved precomputed graph can be reused on same sets of destination and start nodes.
Considering game, this does not make so much of a sense to cache it. The advantage is, however, that A* algorithm will perform better (with less steps then Dijstra) in wide, large graphs (such as \(K_n\) graphs
In order to move character, destination node must be known. Then,
path from current node to destination node is found, and if exists, then
it is saved in character's AI structure.
The movement then proceeds as follows: