Pathfinding using nodes

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


Top

1 Introduction

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


Example of path node grid (blue) connected with transitions. Yellow node is player spawn, but it can be also used as walkable node


2 Path finding algorithms

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

0-0 0-1 0-2 0-3 0-4 0-5 0-6 0-7 0-8 1-0 1-1 1-2 1-3 1-4 1-5 1-6 1-7 1-8 2-0 2-1 2-2 2-3 2-4 2-5 2-6 2-7 2-8 3-0 3-1 3-2 3-3 3-4 3-5 3-6 3-7 3-8 4-0 4-1 4-2 4-3 4-4 4-5 4-6 4-7 4-8 5-0 5-1 5-2 5-3 5-4 5-5 5-6 5-7 5-8 6-0 6-1 6-2 6-3 6-4 6-5 6-6 6-7 6-8 7-0 7-1 7-2 7-3 7-4 7-5 7-6 7-7 7-8 8-0 8-1 8-2 8-3 8-4 8-5 8-6 8-7 8-8

Node:

-

Heuristic value:

0-0 0-1 0-2 0-3 0-4 0-5 0-6 0-7 0-8 1-0 1-1 1-2 1-3 1-4 1-5 1-6 1-7 1-8 2-0 2-1 2-2 2-3 2-4 2-5 2-6 2-7 2-8 3-0 3-1 3-2 3-3 3-4 3-5 3-6 3-7 3-8 4-0 4-1 4-2 4-3 4-4 4-5 4-6 4-7 4-8 5-0 5-1 5-2 5-3 5-4 5-5 5-6 5-7 5-8 6-0 6-1 6-2 6-3 6-4 6-5 6-6 6-7 6-8 7-0 7-1 7-2 7-3 7-4 7-5 7-6 7-7 7-8 8-0 8-1 8-2 8-3 8-4 8-5 8-6 8-7 8-8

3 Character movement

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: