Editing User:Sanust/Guides/Firewall (section)

= Pathfinding =

[[File:Firewall Guide Hexagonal Principle.png|200px|thumb|right|The maximum movement range for a [[Battle Dwarf]] form a hexagon with a radius (r) of 5.]]

[[File:Firewall Guide Coordinate Priority Principle.png|200px|thumb|right|Priority decreases gradually from 1 to 6.]]

When a unit takes its turn, if it wants to move to a certain tile, how does it plan its route? The following rules explain how the AI calculates pathfinding on the [[battlefield]].

== Rule 1: The Shortest Path Principle ==

A unit will always choose the shortest path to reach its target. As a result, the unit would minimize turns whenever possible.

It's worth noting that the AI initially only calculates the shortest straight-line path, ignoring obstacles.
* For more details, see Example 2 below.

== Rule 2: The Hexagonal Principle ==

The battlefield in Heroes III is designed as a hexagonal grid, similar to a chessboard, which results in units' attack ranges also being presented in hexagonal patterns.

In the example shown, for the {{Cn|Battle Dwarf}}, all the green-highlighted hexes represent equally short paths.
* If the battlefield is large enough, the theoretical maximum movement range for {{Cn|Arch Devil}} would form a hexagon with a radius (r) of 17.

== Rule 3: The Coordinate Priority Principle ==
When multiple shortest paths exist, the game then determines the final choice based on coordinate priority.

Using the starting tile as the origin, draw rays in six directions to establish a six-quadrant coordinate system. Following ''The Shortest Path Principle'', the monster's movement order is determined by quadrant priorities numbered 1 to 6.

Provided ''The Shortest Path Principle'' is satisfied, if the tile in the direction of the current highest priority is blocked and thus inaccessible, the unit will consider the tile corresponding to the next priority direction. Moreover, each time the unit moves to a new target hex, it re-establishes the six-directional coordinate system relative to that individual hexagon.

== Rule 4: The Flying Principle ==

[[Flying]] units follow ''The Shortest Path Principle'': "the shortest distance between two points is a straight line" and do not calculate the hexagonal grid along the path. They only consider the final destination tile.

== Examples ==

* In Example 1, the {{Cn|Familiar}} moves upward along the right edge of the battlefield.
** The direction with priority 1 becomes inaccessible due to the boundary obstruction. Following ''The Shortest Path Principle'', the unit will instead move one tile in the priority 6 direction, because following in priority 4 or 5 direction would make the Familiar move more tiles that following in priority 6 direction.
** Upon reaching this new tile, it re-establishes the coordinate system centered on that hex. At this point, the direction with priority 1 becomes accessible again, so the Familiar moves one tile in that direction.
** In this manner, repeating the process, the Familiar continues its movement until it reaches the desired destination.
** As a result, the Familiar moves in 6-1-6-1-6.
* In Example 2, the {{Cn|Familiar}} (on the left) moves towards enemy's Familiar (on the right). How does it move?
** Yellow or Black path seems to be a good choice because the first step is to move in the direction of priority 1. However, Yellow or Black path is 7 tiles long, while the Green and Red paths would only require 6 tiles if there were no obstacles, it does not satisfy ''The Shortest Path Principle''. Therefore, the AI will prioritize the Red and Green paths.
** Due to the obstacle in the direction of priority 2, the Familiar can only move one step in the direction of priority 3, and then re-establishes the coordinate system at that new tile.
** At this new position, the direction of priority 1 is again blocked, so it moves one step in the direction of priority 2.
** It then moves one tile in the direction of priority 1, and proceeds along the path where Green and Yellow overlap until it reaches the enemy.
** As a result, the Familiar moves in blue path.

<gallery widths="300px" heights="200px">
Image:Firewall Guide Hexagonal Principle Obstacle.png|Example 1: The Familiar moves in 6-1-6-1-6.
Image:Firewall Guide Hexagonal Principle Example.png|Example 2: How does the Familiar move?
Image:Firewall Guide Hexagonal Principle Answer.png|Example 2 Answer: The Familiar moves in blue path.
</gallery>