gale.ai.pathfinding module

This file contains pathfinding support that builds on the primitives in gale.ai.search instead of replacing them: incremental_a_star and a_star_to_predicate are generator/open-goal variants of a_star, PathfindingRequest/PlannerPool let an incremental search be advanced a few steps at a time so its cost is spread across several frames instead of spiking on one, and HierarchicalGraph groups a graph’s nodes into clusters to pathfind over an auto-derived abstract graph first, then refine within each cluster – much cheaper than a flat search over a very large graph.

Re-planning when a graph changes needs no dedicated support here: since gale.ai.graph.Graph is a plain mutable object, the usual pattern is to just call a_star/incremental_a_star again (checking first, e.g., that every edge along the current path still exists) whenever the graph changes in a way that might affect a path already in use.

Author: Alejandro Mujica (aledrums@gmail.com)

gale.ai.pathfinding.incremental_a_star(start, goal, graph_or_neighbors_fn, heuristic)[source]

Like gale.ai.search.a_star, but as a generator that yields None after expanding each node instead of running to completion in one call – advance it a limited number of steps per frame (see PathfindingRequest/PlannerPool) to spread a search’s cost over several frames instead of spiking on the one that requested it.

Parameters:

start (T) – The node to start the search from.
goal (T) – The node to reach.
graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, describing the graph to search. Weights must not be negative.
heuristic (Callable[[T, T], float]) – Callable (node, goal) -> estimated cost to reach goal from node. Must not overestimate the real cost for the found path to be guaranteed optimal.

Yields:

None after every node expansion, then the cheapest list of nodes from start to goal (both included), or None if goal is unreachable, once the search is done.

Return type:

Iterator[List[T] | None]

gale.ai.pathfinding.a_star_to_predicate(start, goal_predicate, graph_or_neighbors_fn, heuristic_to_predicate)[source]

An “open goal” variant of gale.ai.search.a_star: instead of a single fixed goal node, any node satisfying goal_predicate is a valid destination – for instance, the nearest node tagged as cover, whichever one that turns out to be, rather than one decided in advance.

Parameters:

start (T) – The node to start the search from.
goal_predicate (Callable[[T], bool]) – Callable returning whether a node is an acceptable goal.
graph_or_neighbors_fn (Graph | Callable[[T], Iterable[Tuple[T, float]]]) – A Graph, or a callable node -> iterable of (neighbor, weight) pairs, describing the graph to search. Weights must not be negative.
heuristic_to_predicate (Callable[[T], float]) – Callable (node) -> estimated cost to reach the nearest node satisfying goal_predicate from node. Must not overestimate the real cost for the found path to be guaranteed optimal.

Returns:

The cheapest list of nodes from start to some node satisfying goal_predicate (both included), or None if no such node is reachable.

Return type:

List[T] | None

class gale.ai.pathfinding.PathfindingRequest(search)[source]

Bases: object

Wraps an incremental search (see incremental_a_star) so it can be advanced a limited number of steps at a time instead of run to completion in one call.

Usage example:

request = PathfindingRequest(incremental_a_star(start, goal, graph, heuristic)) # Each frame: if request.step(max_iterations=20):

path = request.result # None if unreachable

Parameters:: search (Iterator[List[T] | None])

step(max_iterations=1)[source]

Advance the underlying search by up to max_iterations node expansions.

Parameters:: max_iterations (int) – Maximum number of expansions to perform in this call.
Returns:: Whether the search finished (successfully or not) during this call. Once True, self.result holds the outcome and further calls do nothing.
Return type:: bool

class gale.ai.pathfinding.PlannerPool(iterations_per_update=100)[source]

Bases: object

Manages several concurrent PathfindingRequest objects, sharing a fixed per-update iteration budget round-robin across whichever are still pending – so having many outstanding pathfinding requests at once costs a predictable amount of work per frame instead of spiking however many of them happen to be expensive that frame.

Usage example:

pool = PlannerPool(iterations_per_update=100) request = pool.request(incremental_a_star(start, goal, graph, heuristic)) # Each frame: pool.update() if request.done:

path = request.result

Parameters:: iterations_per_update (int)

request(search)[source]

Parameters:: search (Iterator[List[T] | None]) – A generator such as one returned by incremental_a_star.
Returns:: A PathfindingRequest tracking this search, already queued for the next update().
Return type:: PathfindingRequest

update()[source]

Distribute this update’s iteration budget round-robin across every pending request, dropping each one from the pool as soon as it finishes.

Return type:: None

class gale.ai.pathfinding.HierarchicalGraph(graph, clusters)[source]

Bases: object

A two-level view over a Graph: nodes are grouped into clusters, and an abstract graph is automatically derived with one node per cluster “entrance” (a node with at least one neighbor outside its own cluster) and edges weighted by the shortest intra-cluster path between entrances of the same cluster, plus the original inter- cluster edges. find_path searches the (much smaller) abstract graph first, then refines each abstract edge into the real path segment within its cluster – cheaper than a flat search over a very large graph, at the cost of a possibly slightly longer path.

Parameters:

graph (Graph)
clusters (Dict[T, int])

find_path(start, goal, heuristic)[source]

Parameters:

start (T) – The node to start the search from.
goal (T) – The node to reach.
heuristic (Callable[[T, T], float]) – Callable (node, goal) -> estimated cost, used both on the abstract graph and to refine each segment within a cluster.

Returns:

The full path from start to goal, refined down to the fine-grained graph, or None if goal is unreachable.

Return type:

List[T] | None