Each square has up, down, left, and right neighbors. No diagonals.
"Road" squares cost 1, "Dirt" 3, "Water" 7. The goal square is free. Cost of traversing an edge is the cost of the destination square.
Breadth-First-Search ignores terrain cost, is only affected by walls.
A* uses Manhattan distance as its heuristic.