Grid Shortest Path Variants, in depth: 4 vs 8 connectivity, corner cutting, octile A*, weighted cells, portals and k-jump BFS with skip pointers

Two questions pick the algorithm

Every grid shortest-path problem is a graph whose vertices are cells, possibly augmented with extra state, and whose edges are the allowed moves. Two properties pick the algorithm:

Before writing code, write down the move set and the cost of each move as a sentence. Most wrong answers on grid problems come from an algorithm that silently assumes unit costs, or from an ambiguous rule such as whether a cell's cost is paid on entry, on exit, or on both.

Worked example: one grid, four answers

One 5 x 8 grid, four move models. # is a wall, S is (0,0) and G is (4,7). The COST table gives the price of entering each open cell for the weighted variant.

import heapq, math
from collections import deque

GRID = ["S..#....",
        ".#.#.##.",
        ".#...#..",
        ".####.#.",
        "......#G"]
COST = [[1, 1, 1, 0, 1, 1, 1, 1],
        [1, 0, 5, 0, 1, 0, 0, 1],
        [1, 0, 5, 5, 1, 0, 1, 1],
        [1, 0, 0, 0, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 0, 1]]      # walls' entries are never read
R, C, S, G = len(GRID), len(GRID[0]), (0, 0), (4, 7)
FOUR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
EIGHT = FOUR + [(1, 1), (1, -1), (-1, 1), (-1, -1)]

def free(r, c):
    return 0 <= r < R and 0 <= c < C and GRID[r][c] != "#"

def dijkstra_entry():                  # a move costs COST of the cell entered
    dist = {S: 0}; pq = [(0, S)]
    while pq:
        d, (r, c) = heapq.heappop(pq)
        if d > dist[(r, c)]:
            continue                   # stale heap entry
        if (r, c) == G:
            return d
        for dr, dc in FOUR:
            nr, nc = r + dr, c + dc
            if free(nr, nc):
                nd = d + COST[nr][nc]
                if nd < dist.get((nr, nc), math.inf):
                    dist[(nr, nc)] = nd; heapq.heappush(pq, (nd, (nr, nc)))

def octile(a, b):
    dx, dy = abs(a[0] - b[0]), abs(a[1] - b[1])
    return max(dx, dy) + (math.sqrt(2) - 1) * min(dx, dy)

def astar8(allow_corner_cut):
    g = {S: 0.0}; pq = [(octile(S, G), 0.0, S)]; pops = 0
    while pq:
        f, d, (r, c) = heapq.heappop(pq)
        if d > g[(r, c)]:
            continue
        pops += 1
        if (r, c) == G:
            return round(d, 3), pops
        for dr, dc in EIGHT:
            nr, nc = r + dr, c + dc
            if not free(nr, nc):
                continue
            diag = dr != 0 and dc != 0
            if diag and not allow_corner_cut and not (free(r + dr, c) and free(r, c + dc)):
                continue               # both orthogonal neighbours must be open
            nd = d + (math.sqrt(2) if diag else 1.0)
            if nd < g.get((nr, nc), math.inf):
                g[(nr, nc)] = nd
                heapq.heappush(pq, (nd + octile((nr, nc), G), nd, (nr, nc)))

Measured results: 4-connected BFS needs 15 moves. Cost-on-entry Dijkstra finds a path costing 27. 8-connected A* with corner cutting allowed finds a path of length 10.071 after 15 pops; forbidding corner cutting raises the length to 15.0 and the pops to 26, because in this maze almost every useful diagonal squeezes past a wall corner. The same grid gives four different answers, and each is correct for its rules, which is the point: the rule is part of the problem statement.

Diagonals, corner cutting and the octile heuristic

With 8-connectivity, the diagonal cost decides the algorithm. If a diagonal costs 1 (Chebyshev movement, like a chess king), every edge has equal weight and BFS is exact. If a diagonal costs sqrt(2), BFS is wrong: it minimises the number of moves, so to reach a cell four rows down and zero across it may return four zigzag diagonals (length about 5.66) instead of four straight moves (length 4), since both are four moves. Use Dijkstra or A*.

Corner cutting is a separate rule. A diagonal from (r, c) to (r+1, c+1) passes the corner shared by (r+1, c) and (r, c+1). Games and robots usually forbid the move if either of those cells is a wall (a robot with width would clip the corner), and some puzzles forbid it only if both are walls. The code above implements the strict version. State the rule explicitly, because tests written under one convention fail under the other.

For A* on 8-connected grids with costs 1 and sqrt(2), the octile distance, max(dx, dy) + (sqrt(2) - 1) x min(dx, dy), is the exact cost on an empty grid, so it is admissible and consistent and expands far fewer cells than Dijkstra in open terrain. Manhattan distance is admissible for 4-connected grids but overestimates on 8-connected ones, which silently breaks optimality. The A* article covers heuristic properties and tie breaking; A* variants covers jump point search, which prunes symmetric paths on uniform-cost 8-connected grids.

Weighted cells: who pays, and when

Weighted grids attach costs to cells, not edges, so decide when the cost is paid. Cost on entry (pay for the cell you step into) is the most common, excludes the start cell and includes the goal. Cost on exit includes the start and excludes the goal. Some problems charge the average of the two cells or both. All are valid; mixing them between the solver and the test data produces off-by-one-cell errors that look like algorithm bugs.

Once costs vary, the first time BFS reaches a cell is no longer the cheapest, so use Dijkstra with the stale-entry check shown in dijkstra_entry. Two specialisations are worth knowing. If costs are only 0 and 1, for example free moves along a direction arrow and paid moves against it, a deque replaces the heap; the 0-1 BFS article proves why. If costs are small integers from 1 to W, Dial's algorithm keeps an array of buckets indexed by distance and scans them in order, replacing the heap's log factor.

Zero-cost cells are fine for Dijkstra and 0-1 BFS but break any optimisation that assumes distance strictly increases along a path, such as stopping a slide at the first visited cell. Negative costs on grids usually signal a modelling error.

Knights, slides and portals

Some problems replace the neighbourhood entirely. A knight has eight L-shaped moves of equal cost, so BFS over that move list is exact. Slide until wall (ice puzzles, rolling-ball mazes) makes each move continue until blocked, so the neighbours of a cell are at most four stopping points; precompute them, then BFS over stopping points. If the cost is the distance rolled rather than the number of moves, the edges are weighted and Dijkstra is required.

Portals join all cells sharing a label. The trap is quadratic work: if a label has m cells, expanding every one of them across all m partners costs O(m squared). In unit-cost BFS, the first time any cell with that label is dequeued, every partner reaches its final distance, so enqueue the partners and then clear the label's list. Each portal group is expanded once and the total stays linear.

When a move's legality depends on history (keys collected, obstacles broken, direction of the last move), the vertex must carry that history, which is the subject of BFS with augmented state. The cost model and move model choices in this article apply unchanged to the augmented graph.

K-jump grids: from O(RCk) to each cell once

In a k-jump grid one move slides 1 to k cells in a straight line and stops early at a wall; every move costs 1. The obvious BFS loops over four directions and k steps per cell, so the work is O(RC x k), which hurts when k is large.

The fix observes that each cell needs to be discovered once; rescanning visited cells is wasted. Keep, for every row and column, a union-find style "next unvisited cell" pointer in each direction. A slide hops from one unvisited cell to the next, and visiting a cell links it past itself. Walls are never visited, so the pointer lands on a wall before it could skip over one, and the slide stops there.

def kjump_skip(grid, src, dst, k):
    R, C = len(grid), len(grid[0])
    # Per row and column, "next unvisited" pointers in each direction. Backward
    # pointers store index + 1, so 0 means "off the grid". Walls are never
    # visited, so a pointer stops on a wall before it can skip past one.
    row_f = [list(range(C + 1)) for _ in range(R)]
    row_b = [list(range(C + 1)) for _ in range(R)]
    col_f = [list(range(R + 1)) for _ in range(C)]
    col_b = [list(range(R + 1)) for _ in range(C)]

    def find(p, x):
        root = x
        while p[root] != root:
            root = p[root]
        while p[x] != root:                    # path compression
            p[x], x = root, p[x]
        return root

    def visit(r, c):
        row_f[r][c] = c + 1; row_b[r][c + 1] = c
        col_f[c][r] = r + 1; col_b[c][r + 1] = r

    def next_cell(r, c, d):                    # nearest unvisited cell in direction d
        if d == 0: return r, find(row_f[r], c + 1)
        if d == 1: return r, find(row_b[r], c) - 1
        if d == 2: return find(col_f[c], r + 1), c
        return find(col_b[c], r) - 1, c

    dist = {src: 0}; visit(*src); q = deque([src])
    while q:
        r0, c0 = q.popleft(); d = dist[(r0, c0)]
        if (r0, c0) == dst:
            return d
        for direction in range(4):
            r, c = r0, c0
            while True:
                r, c = next_cell(r, c, direction)
                if not (0 <= r < R and 0 <= c < C) or grid[r][c] == "#" \
                        or abs(r - r0) + abs(c - c0) > k:
                    break
                visit(r, c); dist[(r, c)] = d + 1; q.append((r, c))
    return -1

The skip is valid only because every move costs 1: in BFS order a visited cell already has its final distance and can never be improved. With weighted jumps that argument fails, and you need Dijkstra over explicit edges or a range-relaxation structure.

Testing: this code agreed with the naive BFS on 1,000 random grids up to 12 x 12 with 30% walls and k from 1 to 6. On an open 300 x 300 grid, corner to corner, both return 598 moves at k = 1, 60 at k = 10, 6 at k = 100 and 2 at k = 300. The naive version performs 360,000 slide steps at k = 1 and 54,180,000 at k = 300; the skip version enqueues each of the 89,999 non-source cells exactly once at every k.

Failure modes

• BFS on sqrt(2) diagonals. Minimises move count, not length; a returned path can be up to sqrt(2), about 41%, longer than the shortest.
• Manhattan heuristic on 8-connected grids. Overestimates, so A* returns suboptimal paths without any error.
• Ambiguous cost timing. Solver charges on entry, test data on exit; every answer is off by the start or goal cell.
• Skipping cells in weighted jumps. The next-unvisited trick is valid only for unit costs.
• Quadratic portal expansion. Forgetting to clear a label's list after the first expansion.
• Corner-cutting mismatch. Strict and permissive diagonal rules give different answers, as the worked example shows (10.071 against 15.0).

Trade-offs

What to do next

1. For your problem, write the move set and the cost of each move as one sentence each, including the corner-cutting rule and when cell costs are paid.
2. Pick the algorithm from the cost table, not from habit; if all costs are equal, use BFS.
3. Run the worked example, then flip allow_corner_cut and change one COST entry to watch the answer move.
4. If you use A*, check admissibility of the heuristic for your exact move model, and compare against Dijkstra on random grids.
5. For k-jump problems, implement the skip-pointer BFS and differential-test it against the naive BFS before trusting it on large inputs.
6. Read the linked BFS, 0-1 BFS and state-augmented BFS articles to cover the remaining grid patterns.