PHP Classes

PHP AStar Algorithm: Find the path between two points in a grid with A*

Recommend this page to a friend!
  Info   Documentation   View files Files   Install with Composer Install with Composer   Download Download   Reputation   Support forum   Blog    
Ratings Unique User Downloads Download Rankings
StarStarStar 58%Total: 165 All time: 8,913 This week: 79Up
Version License PHP version Categories
astar 1.0.0Custom (specified...5Algorithms, PHP 5, Geography
Description 

Author

This package can find the path between two points in a grid with A* algorithm.

It can take as parameter an array that represents a grid of node points in a map that can be traversed or not.

It takes the coordinates of a start and end node and returns a path of nodes that represent the path to go from start and end point.

Innovation Award
PHP Programming Innovation award nominee
May 2017
Number 2


Prize: One big elePHPant Plush Mascott
Finding the path to traverse a region between two points in a map is a common problem of geography related applications.

This package implements the A* path finding algorithm to find a route between two points.

Manuel Lemos
Picture of Vitalij Mik
  Performance   Level  
Name: Vitalij Mik <contact>
Classes: 7 packages by
Country: Germany Germany
Age: 37
All time rank: 3482194 in Germany Germany
Week rank: 215 Up10 in Germany Germany Up
Innovation award
Innovation award
Nominee: 5x

Documentation

A-Star

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.

Installation

composer require blackscorp/astar

Usage

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";
}else{
  foreach($nodes as $node){
     echo $node->getY().'/'.$node->getX().'<br/>';
  }
}

Settings

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

$astar->enableDiagonal();

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

astar->blocked([3,2]);

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.

Contribute

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.

License

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


  Files folder image Files (15)  
File Role Description
Files folder imagesrc (6 files, 1 directory)
Files folder imagetest (1 file)
Accessible without login Plain text file .scrutinizer.yml Data Auxiliary data
Accessible without login Plain text file composer.json Data Auxiliary data
Accessible without login Plain text file coverage.xml Data Auxiliary data
Accessible without login Plain text file LICENSE Lic. License text
Accessible without login Plain text file readme.md Doc. Documentation

  Files folder image Files (15)  /  src  
File Role Description
Files folder imageHeuristic (3 files)
  Plain text file Astar.php Class Class source
  Plain text file Grid.php Class Class source
  Plain text file HeuristicInterface.php Class Class source
  Plain text file Node.php Class Class source
  Plain text file NodeCollectionInterface.php Class Class source
  Plain text file ScoreHeap.php Class Class source

  Files folder image Files (15)  /  src  /  Heuristic  
File Role Description
  Plain text file Diagonal.php Class Class source
  Plain text file Euclidean.php Class Class source
  Plain text file Manhattan.php Class Class source

  Files folder image Files (15)  /  test  
File Role Description
  Plain text file AstarTest.php Class Class source

The PHP Classes site has supported package installation using the Composer tool since 2013, as you may verify by reading this instructions page.
Install with Composer Install with Composer
 Version Control Unique User Downloads Download Rankings  
 100%
Total:165
This week:0
All time:8,913
This week:79Up
User Ratings User Comments (1)
 All time
Utility:83%StarStarStarStarStar
Consistency:83%StarStarStarStarStar
Documentation:83%StarStarStarStarStar
Examples:-
Tests:-
Videos:-
Overall:58%StarStarStar
Rank:1527