This describes how the character moves in the game world, including navigation and action queue.

This is sub-layout for documentation pages

Top

We use the fact, that the game world was divided to tiles (as described here).
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

2.1 The graph upon which search is done

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.

2.2 Dijkstra

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\).

2.3 A*

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

2.4 A* vs Dijkstra

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:

• Peek the first node in path, and move character to the center of the node
• When character's position changes:
• Get distance from character to the centre of target pathnode.
• If distance is smaller than movement step of character, and position of character does not strictly equal the centre position of target node:
• set character's position to be exatly the centre of target pathnode
• remove the node from path queue, as character just arrived on it
• move character towards next node in path queue, if such node exists