library astar {🖫 122, ⚐ 7, ★ 31}

blackscorp/astar

AStar path finding implementation in php

Friday, October 6, 2017
by BlackScorp
Repository
3 Watchers
31 Stars
122 Installations

PHP
0 Dependents
0 Suggesters
8 Forks
1 Open issues
7 Versions
11 % Grown

The README.md

A-Star

, _(*1)

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., _(*2)

Installation

composer require blackscorp/astar

Usage

first create a two dimensional array for your map, _(*3)

  $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., _(*4)

next convert the array to a Grid, a Grid is a collection of Nodes., _(*5)

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

now you can fetch nodes from the Grid like so, _(*6)

$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, _(*7)

$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, _(*8)

$astar->enableDiagonal();

as soon as the diagonal option is enabled, the algorithm use the Manhattan heuristic to find the shortest path., _(*9)

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

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

you can also create a custom heuristic., _(*11)

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, _(*12)

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

this basicly means that in the initial map, _(*13)

  $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],
        ];

11/03 2015

dev-heap

AStar pathfinding implementation in php

Sources Download

MIT

by Vitalij Mik

10/03 2015

dev-develop

AStar pathfinding implementation in php

Sources Download

MIT

The Development Requires

phpunit/phpunit ~4.5