BlackScorp\Astar\Astar

Complexity

Total Complexity

18

Size/Duplication

Total Lines	102
Duplicated Lines	0 %

Coupling/Cohesion

Components	1
Dependencies	5

Test Coverage

Coverage

100%

Importance

Changes	15
Bugs	0	Features	6

7 Methods

Rating	Name	Duplication	Size	Complexity
A	blocked()	0	4	1
A	__construct()	0	4	1
A	setHeuristic()	0	4	1
A	search()	0	17	3
D	fillHeap()	0	31	9
A	getReversedPath()	0	9	2
A	enableDiagonal()	0	4	1

<?php
namespace BlackScorp\Astar;

use BlackScorp\Astar\Heuristic\Manhattan;

class Astar
{

    private $diagonal = false;
    private $blocked = array();
    /**
     * @var HeuristicInterface
     */
    private $heuristic = null;
    private $grid = null;


    public function blocked(array $types)
    {
        $this->blocked = $types;
    }

    public function enableDiagonal()
    {
        $this->diagonal = true;
    }

    public function __construct(Grid $grid)
    {
        $this->grid = $grid;
    }

    public function setHeuristic(HeuristicInterface $heuristic)
    {
        $this->heuristic = $heuristic;
    }

    public function search(Node $start, Node $end)
    {

        if (!$this->heuristic) {
            $this->setHeuristic(new Manhattan());
        }

        $heap = new ScoreHeap();
        $heap->insert($start);

        $current = $this->fillHeap($heap, $start, $end);
        if ($current !== $end) {
            return [];
        }
        return $this->getReversedPath($current);

    }

    /**
     * @param Node $end
     * @param $heap
     * @param $current
     * @return Node
     */
    private function fillHeap(\SplHeap $heap, Node $current, Node $end)
    {
        while ($heap->valid() && $current !== $end) {
            /**
             * @var Node $current
             */
            $current = $heap->extract();

            $current->close();
            $neighbors = $this->grid->getNeighbors($current, $this->diagonal);
            foreach ($neighbors as $neighbor) {
                if ($neighbor->isClosed() || in_array($neighbor->getCosts(), $this->blocked)) {
                    continue;
                }
                $score = $current->getScore() + $neighbor->getCosts();
                $visited = $neighbor->isVisited();
                if (!$visited || $score < $neighbor->getScore()) {
                    $neighbor->visit();
                    $neighbor->setParent($current);
                    $neighbor->setGuessedScore($this->heuristic->compare($neighbor, $end));
                    $neighbor->setScore($score);
                    $neighbor->setTotalScore($neighbor->getScore() + $neighbor->getGuessedScore());
                    if (!$visited) {
                        $heap->insert($neighbor);
                    }
                }

            }
        }
        return $current;
    }

    /**
     * @param Node $current
     * @return array
     */
    private function getReversedPath(Node $current)
    {
        $result = [];
        while ($current->getParent()) {
            $result[] = $current;
            $current = $current->getParent();
        }
        return array_reverse($result);
    }
}