Skip to content

HPA* fallback in a_star_search returns a partial cost trail when no path exists #3631

Description

@brendancol

Describe the bug

When a_star_search falls back to hierarchical pathfinding (auto search radius under memory pressure with a long start-goal distance), _hpa_star_search can return a partially written cost surface. If a refinement segment fails to connect after the radius escalation loop, the function bails with

return path_img  # partial result

leaving the pixels of already-refined segments holding finite costs even though no start-to-goal path was found. Everywhere else in the module, "no path" means an all-NaN output (the plain kernel, the bounded search, and test_search_radius_too_small all follow that contract), so a caller checking np.isfinite(result).any() for reachability gets a false positive, and the finite trail dead-ends partway across the grid.

Reproduction (run on this host):

import numpy as np
from xrspatial.pathfinding import _hpa_star_search, _neighborhood_structure

# grid fully split by a 1-px NaN wall: no path exists
H = W = 200
data = np.ones((H, W))
data[:, 100] = np.nan
dy, dx, dd = _neighborhood_structure(1.0, 1.0, 8)
barriers = np.array([], dtype=np.float64)

path = _hpa_star_search(data, None, 0, 0, 199, 199, barriers, dy, dx, dd,
                        1.0, False, 1.0, 1.0, H, W)
print(np.isfinite(path[199, 199]))   # False - goal not reached
print(np.isfinite(path).sum())       # 89   - but 89 pixels carry finite costs

The coarse grid sees the wall's blocks as passable (each block contains non-NaN cells), routes across, and the fine refinement then fails at the wall after writing the earlier segments.

Expected behavior

An all-NaN surface when the goal cannot be reached, consistent with the other search paths in the module.

Additional context

Found by the accuracy sweep (Cat 2/5, rated MEDIUM). Reachable through the public API only in the auto-radius HPA* regime (grid too large for RAM and manhattan distance > 1000), which is also exactly the setting where a user cannot easily cross-check against a full-grid run.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions