Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
97.56% covered (success)
97.56%
40 / 41
0.00% covered (danger)
0.00%
0 / 1
 CRAP
0.00% covered (danger)
0.00%
0 / 1
AStar
97.56% covered (success)
97.56%
40 / 41
0.00% covered (danger)
0.00%
0 / 1
 14
0.00% covered (danger)
0.00%
0 / 1
 findPath
97.56% covered (success)
97.56%
40 / 41
0.00% covered (danger)
0.00%
0 / 1
 14
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\PathFinding
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 *
13 * Extended based on:
14 * MIT License
15 * (c) 2011-2012 Xueqiao Xu <xueqiaoxu@gmail.com>
16 * (c) PathFinding.js
17 */
18declare(strict_types=1);
19
20namespace phpOMS\Algorithm\PathFinding;
21
22use phpOMS\Stdlib\Base\Heap;
23
24/**
25 * Perform path finding.
26 *
27 * @package phpOMS\Algorithm\PathFinding
28 * @license OMS License 2.0
29 * @link    https://jingga.app
30 * @since   1.0.0
31 */
32final class AStar implements PathFinderInterface
33{
34    /**
35     * {@inheritdoc}
36     */
37    public static function findPath(
38        int $startX, int $startY,
39        int $endX, int $endY,
40        Grid $grid,
41        int $heuristic, int $movement
42    ) : Path
43    {
44        /** @var null|AStarNode $startNode */
45        $startNode = $grid->getNode($startX, $startY);
46        /** @var null|AStarNode $endNode */
47        $endNode = $grid->getNode($endX, $endY);
48
49        if ($startNode === null || $endNode === null) {
50            return new Path($grid);
51        }
52
53        $startNode->setG(0.0);
54        $startNode->setF(0.0);
55        $startNode->setOpened(true);
56
57        $openList = new Heap(function (AStarNode $node1, AStarNode $node2) {
58            return $node1->getF() - $node2->getF();
59        });
60
61        $openList->push($startNode);
62        $node = null;
63
64        while (!$openList->isEmpty()) {
65            $node = $openList->pop();
66            if ($node === null) {
67                break;
68            }
69
70            /** @var AStarNode $node */
71            $node->setClosed(true);
72
73            if ($node->isEqual($endNode)) {
74                break;
75            }
76
77            /** @var AStarNode[] $neighbors */
78            $neighbors       = $grid->getNeighbors($node, $movement);
79            $neighborsLength = \count($neighbors);
80            for ($i = 0; $i < $neighborsLength; ++$i) {
81                $neighbor = $neighbors[$i];
82
83                if ($neighbor->isClosed()) {
84                    continue;
85                }
86
87                $ng = $node->getG() + (($neighbor->getX() - $node->getX() === 0 || $neighbor->getY() - $node->getY() === 0) ? 1 : \sqrt(2));
88
89                if (!$neighbor->isOpened() || $ng < $neighbor->getG()) {
90                    $neighbor->setG($ng);
91                    $neighbor->setH($neighbor->getH() ?? (
92                        $neighbor->getWeight() * Heuristic::metric($neighbor->getCoordinates(), $endNode->getCoordinates(), $heuristic)
93                    ));
94                    $neighbor->setF($neighbor->getG() + $neighbor->getH());
95                    $neighbor->parent = $node;
96
97                    if (!$neighbor->isOpened()) {
98                        $openList->push($neighbor);
99                        $neighbor->setOpened(true);
100                    } else {
101                        $openList->update($neighbor);
102                    }
103                }
104            }
105        }
106
107        $path = new Path($grid);
108
109        while ($node !== null) {
110            $path->addNode($node);
111            $node = $node->parent;
112        }
113
114        return $path;
115    }
116}