Letournel\PathFinder\Algorithms\ShortestPath\AStar

Complexity

Total Complexity

11

Size/Duplication

Total Lines	81
Duplicated Lines	0 %

Coupling/Cohesion

Components	1
Dependencies	7

Importance

Changes

0

4 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	5	1
A	setGrid()	0	4	1
A	computeLength()	0	6	1
C	computePath()	0	50	8

<?php

namespace Letournel\PathFinder\Algorithms\ShortestPath;

use Letournel\PathFinder\AlgorithmShortestPath;
use Letournel\PathFinder\Core\Heuristic;
use Letournel\PathFinder\Core\Node;
use Letournel\PathFinder\Core\NodeGrid;
use Letournel\PathFinder\Core\NodeMap;
use Letournel\PathFinder\Core\NodePath;
use Letournel\PathFinder\Core\NodePriorityQueueMin;
use Letournel\PathFinder\Distance;

class AStar implements AlgorithmShortestPath
{
    /*
     * For more info see
     * http://en.wikipedia.org/wiki/A*_search_algorithm
     */
    
    private
        $distance,

It is generally advisable to only define one property per statement.

The visibility should be declared for property $distance.

        $grid,
        $heuristic;
    
    public function __construct(Distance $distance, Heuristic $heuristic)
    {
        $this->distance = $distance;
        $this->heuristic = $heuristic;
    }
    
    public function setGrid(NodeGrid $grid)
    {
        $this->grid = $grid;
    }
    
    public function computeLength(Node $source, Node $target)
    {
        $shortestPath = $this->computePath($source, $target);
        
        return $shortestPath->computeLength($this->distance);
    }
    
    public function computePath(Node $source, Node $target)
    {
        if(! $this->grid instanceof NodeGrid)
        {
            throw new \RuntimeException('Invalid Grid');
        }
        
        $fScorePriorityQueue = new NodePriorityQueueMin();
        $gScoreMap = new NodeMap();
        $openedMap = new NodeMap();
        $closedMap = new NodeMap();
        $previousMap = new NodeMap();
        
        $fScorePriorityQueue->insert($source, 0);
        $gScoreMap->insert($source, 0);

0 is of type integer, but the function expects a boolean.

        $openedMap->insert($source);
        
        while(! $fScorePriorityQueue->isEmpty())
        {
            $node = $fScorePriorityQueue->extract();
            $closedMap->insert($node);
            
            if($node->getId() === $target->getId())
            {
                return new NodePath($previousMap->lookupFrom($node));
            }
            
            $neighbors = $this->grid->getWalkableNeighbors($node);
            foreach($neighbors as $neighbor)
            {
                if($closedMap->exists($neighbor))
                {
                    continue;
                }
                
                $gScore = $gScoreMap->lookup($node) + $this->distance->compute($node, $neighbor);
                if(! $openedMap->exists($neighbor) || $gScore < $gScoreMap->lookup($neighbor))
                {
                    $fScore = $gScore + $this->heuristic->compute($node, $target);
                    $fScorePriorityQueue->insert($neighbor, $fScore);
                    $gScoreMap->insert($neighbor, $gScore);

$gScore is of type double, but the function expects a boolean.

                    $openedMap->insert($neighbor);
                    $previousMap->insert($neighbor, $node);
                }
            }
        }
        
        // no path found
        return array();
    }
}