PHP Classes


Recommend this page to a friend!
  Classes of Vitalij Mik  >  PHP AStar Algorithm  >  >  Download  
Role: Documentation
Content type: text/markdown
Description: Documentation
Class: PHP AStar Algorithm
Find the path between two points in a grid with A*
Author: By
Last change:
Date: 20 days ago
Size: 3,135 bytes


Class file image Download


Scrutinizer Code Quality Code Coverage Build Status

A-star is a path finding algorithm, written in PHP. It can find the shortest path between two points in a two dimensional array by using different heuristics.


composer require blackscorp/astar


first create a two dimensional array for your map

  $map = [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 1, 1],
            [0, 0, 0, 1, 0],

each key represent the x and y position of the map. each value of the array represents the costs, A-star tries to find a way with lowest costs. you can use negative keys if your map requires it.

next convert the array to a Grid, a Grid is a collection of Nodes.

$grid = new BlackScorp\Astar\Grid($map);

now you can fetch nodes from the Grid like so

$startPosition = $grid->getPoint(3,1);
$endPosition = $grid->getPoint(0,0);

at the end pass the grid to the astar and search for the shortests path

$astar = new BlackScorp\Astar\Astar($grid);
$nodes = $astar->search($startPosition,$endPosition);
if(count($nodes) === 0){
   echo "Path not found";
  foreach($nodes as $node){
     echo $node->getY().'/'.$node->getX().'<br/>';


by default diagonal directions are disabled, they can be enabled like so


as soon as the diagonal option is enabled, the algorithm use the Manhattan heuristic to find the shortest path.

Manhattan is not precise but the caluclation costs are low, however you can use another heuristics like Diagonal or Euclidean with following code.

$astar->setHeuristic(new BlackScorp\Astar\Heuristic\Euclidean());

you can also create a custom heuristic.

Block locations

there are cases where you want to block a specific path completly, independant of the costs, you can do so with following code


this basicly means that in the initial map

  $map = [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 2, 2, 0, 0],
            [0, 3, 0, 1, 1],
            [0, 0, 0, 1, 0],

the values 3 and 2 cannot be passed.


Please feel free to make pull requests, there is still place for improvement, the Grid contains a two dimensional array which might be replaced by an SplFixedArray or something similar.

Run the tests to be sure nothing break.


A-Star is free software distributed under the terms of the MIT license.