A Star Laravel Package

Getting Started

The package is a single-purpose library: no service provider, no config file, no facade. Install it and write two classes yourself.

composer require jmgq/a-star

1. A Node value object. Anything you want to search over implements JmGq\AStar\Node, which is essentially just a stable identity:

use JmGq\AStar\Node;

final class GridNode implements Node
{
    public function __construct(
        public readonly int $x,
        public readonly int $y,
    ) {}

    public function getNodeId(): string
    {
        return "{$this->x},{$this->y}";
    }
}

2. A DomainLogic implementation. This is where all the domain knowledge lives — the package knows nothing about your graph:

use JmGq\AStar\DomainLogic;
use JmGq\AStar\Node;

final class GridDomainLogic implements DomainLogic
{
    public function getAdjacentNodes(Node $node): array { /* neighbours */ }

    public function calculateRealCost(Node $node, Node $adjacent): float { /* edge weight */ }

    public function calculateEstimatedCost(Node $start, Node $end): float { /* heuristic */ }
}

3. Run it.

use JmGq\AStar\AStar;
use JmGq\AStar\Exception\NoSolutionFoundException;

try {
    $path = (new AStar(app(GridDomainLogic::class)))->run($start, $goal);
    // array<Node>, from $start to $goal inclusive
} catch (NoSolutionFoundException $e) {
    // no route exists
}

Look first at src/DomainLogic.php and src/AStar.php (both are short — read them fully before shipping), then the tests/ directory, which contains working DomainLogic implementations for grids and mazes that you can copy almost verbatim. First real use case: shortest path over a small, finite, in-memory graph — warehouse pick routes, grid movement on a map, course prerequisites, word-ladder/sliding-puzzle style problems. If your data lives in the database, read the next section before writing getAdjacentNodes.

Implementation Patterns

Wrap IDs, not Eloquent models. Do not make your models implement Node. Nodes are created and discarded constantly by the algorithm, and each one carries state the algorithm compares by getNodeId(). Use a lightweight value object (WarehouseBay, Coordinate, StateKey) and keep an id => Model lookup array alongside the search so you can rehydrate at the end. This also keeps the algorithm out of your persistence layer.

Make DomainLogic a repository-backed service. Inject what you need and let the container build it:

final class RouteDomainLogic implements DomainLogic
{
    public function __construct(private LocationRepository $locations) {}

    public function getAdjacentNodes(Node $node): array
    {
        return $this->locations->neighboursOf($node->getNodeId())
            ->map(fn ($l) => new BayNode($l->code))
            ->all();
    }
}

In a grid/maze you can compute neighbours in PHP and skip the DB entirely — far faster and easier to unit test.

Memoise aggressively. getAdjacentNodes() and calculateEstimatedCost() are called many times for the same node. Cache them on the DomainLogic instance (a private array $neighbours = [] keyed by node ID). Register the binding as scoped or build a fresh instance per search — never singleton — so cached state does not leak between requests or queued jobs:

$this->app->bind(RouteDomainLogic::class, RouteDomainLogic::class);

Decorate for observability. Rather than instrumenting your domain class, wrap it:

final class LoggingDomainLogic implements DomainLogic
{
    public function __construct(
        private DomainLogic $inner,
        private LoggerInterface $log,
    ) {}
    // delegate, incrementing counters / logging expanded nodes
}

Same trick works for a "node budget" decorator that throws once you exceed N expansions, which is the only defence the library gives you against a runaway search.

Push expensive searches to a job. run() is synchronous and blocking; on a graph of any size it will blow a request timeout. Dispatch a FindRouteJob, persist the resulting ID path, and broadcast/poll. The path is just an array of nodes — serialise the getNodeId() values, not the objects.

Test with a tiny in-memory graph. Because DomainLogic is a plain interface, a three-by-three grid fixture in a unit test covers your whole integration without touching the database. Assert on the ordered list of getNodeId() values.

Gotchas and Tips

• Catch NoSolutionFoundException. Disconnected graphs are normal, not exceptional. Decide up front whether "no route" is a 404, a fallback route, or a null return.
• The heuristic must never overestimate. calculateEstimatedCost() has to be admissible (and, in practice, consistent) or A* silently returns a suboptimal path rather than failing loudly. Manhattan distance for 4-way grids, Euclidean/octile for 8-way, Chebyshev for king moves. If in doubt, return 0.0 and you have Dijkstra — correct, just slower.
• getNodeId() is the entire notion of identity. Nodes are compared by that string only; two different PHP objects with the same ID are the same node to the algorithm. It must encode every bit of state that matters — in puzzle-style searches (keys collected, direction facing, doors opened) omitting state from the ID collapses distinct situations into one and produces wrong or missing solutions.
• Edge costs must be strictly positive. Zero-cost edges cause ties that can degrade into loops or extremely slow searches; negative costs break the algorithm's guarantees outright. Prefer integer costs and cast to float at the boundary — floating-point accumulation in long paths can produce visible drift.
• Watch memory, not CPU. The open set lives entirely in RAM and there is no pruning knob. Long routes over dense graphs (every grid cell a node, 8-way movement) will use tens of megabytes. Use a coarse graph (waypoints, road segments) rather than per-metre nodes wherever possible.
• The package is unmaintained since January 2022. Pin the version in composer.json, check composer why-not jmgq/a-star before upgrading PHP, and isolate it behind your own PathFinder interface with one adapter class. It is ~500 lines; if it ever breaks your constraints, reimplementing the adapter is trivial.
• No Laravel integration ships with it. No provider, no publishable config, no facade. Register your DomainLogic binding in AppServiceProvider and construct AStar directly — do not try to bind AStar itself as a singleton.
• Debugging: log every node passed to getAdjacentNodes() and the g/h values you compute. The two failure signatures are "expands thousands of nodes" (heuristic returning 0 or wildly inconsistent) and "returns a route you can beat by hand" (heuristic overestimating, or the node ID hiding state).
• getAdjacentNodes() should not return the node itself. The algorithm tolerates it only because costs are positive; filtering it out saves useless work.
• Extension points are the two interfaces, nothing else. There is no event system, no pluggable open-set implementation, no tie-breaking hook. All customisation — caching, budgets, logging, alternate heuristics — is done by decorating DomainLogic or by choosing what you put in getNodeId().