PHPackages jmgq/a-star - PHPackages - PHPackages [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register) 1. [Directory](/) 2. / 3. [Search & Filtering](/categories/search) 4. / 5. jmgq/a-star ActiveLibrary[Search & Filtering](/categories/search) jmgq/a-star =========== A\* (A Star) algorithm for PHP v2.1.1(4y ago)6354.1k↓15%18[3 issues](https://github.com/jmgq/php-a-star/issues)[1 PRs](https://github.com/jmgq/php-a-star/pulls)1MITPHPPHP >=8.0 Since May 20Pushed 4y ago5 watchersCompare [ Source](https://github.com/jmgq/php-a-star)[ Packagist](https://packagist.org/packages/jmgq/a-star)[ RSS](/packages/jmgq-a-star/feed)WikiDiscussions master Synced 1mo ago READMEChangelog (8)Dependencies (8)Versions (10)Used By (1) A Star algorithm for PHP ======================== [](#a-star-algorithm-for-php) [![Latest Stable Version](https://camo.githubusercontent.com/b06a5dd18f94ee1ce8939a9c852bccea44bc00585d2d22bfcfe9274dc3c05783/68747470733a2f2f706f7365722e707567782e6f72672f6a6d67712f612d737461722f762f737461626c652e737667)](https://packagist.org/packages/jmgq/a-star)[![Static Analysis](https://github.com/jmgq/php-a-star/actions/workflows/static-analysis.yml/badge.svg)](https://github.com/jmgq/php-a-star/actions/workflows/static-analysis.yml)[![Tests](https://github.com/jmgq/php-a-star/actions/workflows/tests.yml/badge.svg)](https://github.com/jmgq/php-a-star/actions/workflows/tests.yml)[![Coverage Status](https://camo.githubusercontent.com/8ab735413489165697a7084fcffb351aa0dfd1b711c8bc2d54ff6170a92ea893/68747470733a2f2f636f766572616c6c732e696f2f7265706f732f6769746875622f6a6d67712f7068702d612d737461722f62616467652e737667)](https://coveralls.io/github/jmgq/php-a-star)[![Scrutinizer Code Quality](https://camo.githubusercontent.com/cb7175e79884f4211e5692d270d4abc167bd775fa9a134029f207692c2d418da/68747470733a2f2f7363727574696e697a65722d63692e636f6d2f672f6a6d67712f7068702d612d737461722f6261646765732f7175616c6974792d73636f72652e706e67)](https://scrutinizer-ci.com/g/jmgq/php-a-star)[![SemVer](https://camo.githubusercontent.com/857810975b7081e6793f6fe7f5837bc047acc75680081d6a783603ea4ad675bc/68747470733a2f2f696d672e736869656c64732e696f2f3a73656d7665722d322e302e302d627269676874677265656e2e737667)](https://semver.org/spec/v2.0.0.html)[![License](https://camo.githubusercontent.com/969f54275bd13bdd4d89e83d9a762ec74941a46b33a7ef7fd79b0e0a122bc0a0/68747470733a2f2f706f7365722e707567782e6f72672f6a6d67712f612d737461722f6c6963656e73652e737667)](https://packagist.org/packages/jmgq/a-star) A Star pathfinding algorithm implementation for PHP. Requirements ------------ [](#requirements) You need PHP >= 8.0 to use this library, but the latest stable version of PHP is recommended. If you need to run this library on an older version of PHP (or HHVM), please install a 1.x version. Installation ------------ [](#installation) 1. Install [composer](https://getcomposer.org/). 2. Add the A Star algorithm package to your `composer.json` file and download it: ``` composer require jmgq/a-star ``` Usage ----- [](#usage) 1. Create a class that implements `DomainLogicInterface`. The parameters of the three methods in this interface are nodes. A node can be of any type: it could be a string, an integer, an object, etc. You decide the shape of a node, depending on your business logic. You can optionally provide a way to identify your nodes ([check why and how](#specifying-the-unique-node-id)). ``` use JMGQ\AStar\DomainLogicInterface; class DomainLogic implements DomainLogicInterface { // ... public function getAdjacentNodes(mixed $node): iterable { // Return a collection of adjacent nodes } public function calculateRealCost(mixed $node, mixed $adjacent): float | int { // Return the actual cost between two adjacent nodes } public function calculateEstimatedCost(mixed $fromNode, mixed $toNode): float | int { // Return the heuristic estimated cost between the two given nodes } // ... } ``` 2. Instantiate the `AStar` class, which requires the newly created Domain Logic object: ``` use JMGQ\AStar\AStar; $domainLogic = new DomainLogic(); $aStar = new AStar($domainLogic); ``` 3. That's all! You can now use the `run` method in the `AStar` class to generate the best path between two nodes. This method will return an ordered list of nodes, from the start node to the goal node. If there is no solution, an empty list will be returned. ``` $solution = $aStar->run($start, $goal); ``` ### Specifying the unique node ID [](#specifying-the-unique-node-id) In order to work correctly, the A\* algorithm needs to uniquely identify each node. This library will automatically generate a default ID for each node, which will be the result of serialising the node with PHP's [serialize](https://www.php.net/manual/function.serialize.php) function. This has two major disadvantages: 1. **It is not always correct**: for instance, let's assume that a node is represented by an associative array with two keys: `x` and `y`. The following two nodes are the same, but their serialised value is not: ``` $node1 = ['x' => 4, 'y' => 5]; $node2 = ['y' => 5, 'x' => 4]; serialize($node1); // a:2:{s:1:"x";i:4;s:1:"y";i:5;} serialize($node2); // a:2:{s:1:"y";i:5;s:1:"x";i:4;} ``` 2. **Performance issues**: if the node structure is very complex, serialising it could take too long. Rather than relying on this default mechanism, you can avoid the serialisation process and instead provide the node ID yourself, by ensuring that your node implements `NodeIdentifierInterface`, which only declares one method: ``` interface NodeIdentifierInterface { public function getUniqueNodeId(): string; } ``` For instance, this is how it has been implemented in the Terrain example: ``` use JMGQ\AStar\Node\NodeIdentifierInterface; class Position implements NodeIdentifierInterface { private int $row; private int $column; // ... public function getUniqueNodeId(): string { return $this->row . 'x' . $this->column; } // ... } ``` Examples -------- [](#examples) There are two working implementations in the [examples](examples) folder. ### Terrain Example [](#terrain-example) In order to execute this example, run the following command: ``` composer example:terrain ``` This example calculates the best route between two tiles in a rectangular board. Each tile has a cost associated to it, represented in a TerrainCost object. Every value in the TerrainCost array indicates the cost of entering into that particular tile. For instance, given the following terrain: ``` | 0 1 2 3 ----------- 0 | 1 1 1 2 1 | 1 2 3 4 2 | 1 1 1 1 ``` The cost to enter the tile `(1, 3)` (row 1, column 3) from any of its adjacent tiles is 4 units. So the real distance between `(0, 2)` and `(1, 3)` would be 4 units. ### Graph Example [](#graph-example) In order to execute this example, run the following command: ``` composer example:graph ``` Important notes: - This example calculates the shortest path between two given nodes in a directed graph. - A node's position is determined by its X and Y coordinates. - The `Link` class specifies an arc (unidirectional connection) between two nodes. For instance `Link(A, B, D)` represents an arc from the node `A` to the node `B`, with a distance of `D` units. Benchmark --------- [](#benchmark) This project contains a benchmark utility that can be used to test the algorithm's efficiency. This can be particularly useful to evaluate any changes made to the algorithm. The benchmark runs against the Terrain example. To execute it with the default parameters, simply run: ``` composer benchmark ``` For a full list of parameters, please run: ``` composer benchmark help benchmark ``` For instance, the following command runs the algorithm against 10 different terrains of size 5x5, another 10 different terrains of size 12x12, and it uses 123456 as its seed to randomly generate the costs of each one of the terrain tiles: ``` composer benchmark -- --iterations=10 --size=5 --size=12 --seed=123456 ``` Contributing ------------ [](#contributing) Contributions to this project are always welcome. If you want to make a contribution, please fork the project, create a feature branch, and send a pull request. ### Development environment [](#development-environment) In order to set up your development environment, please follow these steps: 1. Install [Docker](https://www.docker.com/). 2. Build the image: `docker build -t php-a-star .` 3. Run the image: ``` docker run -it \ --mount type=bind,source="$(pwd)",target=/opt/php-a-star \ php-a-star \ sh ``` ### Coding Standards [](#coding-standards) To ensure a consistent code base, please make sure your code follows the following conventions: - The code should follow the standards defined in the [PSR-12](https://www.php-fig.org/psr/psr-12/) document. - Use camelCase for naming variables, instead of underscores. - Use parentheses when instantiating classes regardless of the number of arguments the constructor has. - Write self-documenting code instead of actual comments (unless strictly necessary). In other words, please imitate the existing code. Please remember that you can verify that your code adheres to the coding standards by running `composer coding-standards`. ### Tests [](#tests) This project has been developed following the [TDD](https://en.wikipedia.org/wiki/Test-driven_development) principles, and it strives for maximum test coverage. Therefore, you are encouraged to write tests for your new code. If your code is a bug fix, please write a test that proves that your code actually fixes the bug. If you don't know how to write tests, please don't be discouraged, and send your pull request without tests, I will try to add them myself later. To run the test suite and the code coverage report, simply execute `composer test`. ### Static Analysis Tools [](#static-analysis-tools) To ensure the quality of the codebase is of a high standard, the following static analysis tools are run as part of the CI pipeline: ToolNotesHow to run[Scrutinizer](https://scrutinizer-ci.com/g/jmgq/php-a-star/)Tracks how data flows through the application to detect security issues, bugs, unused code, and moreOnline onlyPhanRuns on the lowest, most strict level`composer static-analysis:phan`PHPStanRuns on the highest, most strict level`composer static-analysis:phpstan`PsalmRuns on lowest, most strict level`composer static-analysis:psalm`You can run all the local static analysis tools with `composer static-analysis`. ### Contributors [](#contributors) Feel free to add yourself to the list of [contributors](CONTRIBUTORS.md). Changelog --------- [](#changelog) Read the [changelog](CHANGELOG.md). ### Health Score 43 — FairBetter than 91% of packages Maintenance19 Infrequent updates — may be unmaintained Popularity44 Moderate usage in the ecosystem Community19 Small or concentrated contributor base Maturity74 Established project with proven stability Bus Factor1 Top contributor holds 98.4% of commits — single point of failure How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window. **Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores. **Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement. **Maturity (30%)** — Project age, version count, PHP version support, and release stability. ### Release Activity Cadence Every ~397 days Recently: every ~327 days Total 8 Last Release 1597d ago Major Versions v1.2.0 → v2.0.02021-02-08 PHP version history (2 changes)v1.1.0PHP >=5.3.0 v2.0.0PHP >=8.0 ### Community Maintainers ![](https://www.gravatar.com/avatar/fb0368cc2ccbae0f06f56aa4c457a09ed933d397c357f2c0147a236af246bca3?d=identicon)[jmgq](/maintainers/jmgq) --- Top Contributors [![jmgq](https://avatars.githubusercontent.com/u/7648952?v=4)](https://github.com/jmgq "jmgq (126 commits)")[![nineff](https://avatars.githubusercontent.com/u/3100873?v=4)](https://github.com/nineff "nineff (1 commits)")[![pathway](https://avatars.githubusercontent.com/u/18753?v=4)](https://github.com/pathway "pathway (1 commits)") --- Tags a-starpathfindingsearchAlgorithmaa starpathfinding ### Code Quality TestsPHPUnit Static AnalysisPHPStan, Psalm Code StylePHP\_CodeSniffer Type Coverage Yes ### Embed Badge ![Health badge](/badges/jmgq-a-star/health.svg) ``` [![Health](https://phpackages.com/badges/jmgq-a-star/health.svg)](https://phpackages.com/packages/jmgq-a-star) ``` ### Alternatives [elasticsearch/elasticsearch PHP Client for Elasticsearch 5.3k178.3M943](/packages/elasticsearch-elasticsearch)[ruflin/elastica Elasticsearch Client 2.3k50.4M203](/packages/ruflin-elastica)[solarium/solarium PHP Solr client 93432.7M98](/packages/solarium-solarium)[opensearch-project/opensearch-php PHP Client for OpenSearch 15224.3M65](/packages/opensearch-project-opensearch-php) PHPackages © 2026 [Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)