Greedy algorithm for grid navigation

For navigation problems that can be modeled as a grid with obstacles, we present a greedy algorithm that can determine a navigable path between any two given points on the grid.

Grid properties

• Rectangular board of size $m$ by $n$, so it has $m*n$ squares
• A square can be navigable or blocked (e.g. an obstacle)
• A square $(i, j)$ has the following adjacent squares:
1. $(i-1, j-1)$ - corresponds to the south-west direction
2. $(i-1, j)$ - corresponds to the west direction
3. $(i-1, j+1)$ - corresponds to the north-west direction
4. $(i, j-1)$ - corresponds to the south direction
5. $(i, j+1)$ - corresponds to the north direction
6. $(i+1, j-1)$ - corresponds to south-east direction
7. $(i+1, j)$ - corresponds to the east direction and
8. $(i+1, j+1)$ - corresponds to the north-east direction
• From a given square, one can navigate to any of the adjacent squares, unless that square is blocked or is beyond the board margins.

The objective

Given 2 points on the board - the source $s$ and the destination $d$, find a navigable path between $s$ and $d$.

Navigation algorithm

1. We use a vector $\overrightarrow{v}$  ("the destination vector") to determine the direction of our destination from our current position $p$. \[\overrightarrow{v}=\overrightarrow{d}-\overrightarrow{p}=(d_x-p_x,d_y-p_y)\] 
2. A direction vector is a vector of unit length in a direction. E.g. east direction vector $\overrightarrow{i_{1}}=(1,0)$, north-east =$\overrightarrow{i_{2}}=(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$.
3. We use vector dot product to determine the degree of alignment between the destination vector $\overrightarrow{v}$ and each of the direction vectors ($\overrightarrow{i_{1}},\cdots,\overrightarrow{i_{8}}$).
4. The direction vector with the best possible alignment with the destination vector, i.e. the one with the largest dot product, is the direction we take. In other words, the direction corresponding to the largest of {$(\overrightarrow{v}\cdot\overrightarrow{i_{1}}),(\overrightarrow{v}\cdot\overrightarrow{i_{2}}),\cdots,(\overrightarrow{v}\cdot\overrightarrow{i_{8}})$} is our choice.
5. If we have already visited the square corresponding to this direction, we choose the next best direction available based on the dot product.
6. We repeat the above steps till we reach our destination (or a pre-determined upper bound on the path length, at which point we abort.)

Properties of the algorithm

• This is a greedy algorithm. It chooses the direction to navigate in, based only on the current square it is in.
• For a grid with low obstacle ratio (e.g. less than half the squares are obstacles), this algorithm converges to a navigable path fairly quickly - in about 2 times the global shortest path or less, discounting outliers.

Implementation
You can find java source code here - https://github.com/briangu/amaitjo/blob/master/src/main/java/ravi/contest/ants/movement/NavigationAdvisor.java