Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
47 / 47
100.00% covered (success)
100.00%
6 / 6
 CRAP
100.00% covered (success)
100.00%
1 / 1
Path
100.00% covered (success)
100.00%
47 / 47
100.00% covered (success)
100.00%
6 / 6
 18
100.00% covered (success)
100.00%
1 / 1
 __construct
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 addNode
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 getLength
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
 2
 getPath
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
 1
 expandPath
100.00% covered (success)
100.00%
14 / 14
100.00% covered (success)
100.00%
1 / 1
 4
 interpolate
100.00% covered (success)
100.00%
23 / 23
100.00% covered (success)
100.00%
1 / 1
 9
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
22/**
23 * Path in grids.
24 *
25 * @package phpOMS\Algorithm\PathFinding
26 * @license OMS License 2.0
27 * @link    https://jingga.app
28 * @since   1.0.0
29 */
30class Path
31{
32    /**
33     * Nodes in the path
34     *
35     * @var Node[]
36     * @since 1.0.0
37     */
38    public array $nodes = [];
39
40    /**
41     * Grid this path belongs to
42     *
43     * @var Grid
44     * @since 1.0.0
45     */
46    private Grid $grid;
47
48    /**
49     * Nodes in the path
50     *
51     * @var Node[]
52     * @since 1.0.0
53     */
54    private array $expandedNodes = [];
55
56    /**
57     * Cosntructor.
58     *
59     * @param Grid $grid Grid this path belongs to
60     *
61     * @since 1.0.0
62     */
63    public function __construct(Grid $grid)
64    {
65        $this->grid = $grid;
66    }
67
68    /**
69     * Add node to the path
70     *
71     * @param Node $node Node
72     *
73     * @return void
74     *
75     * @since 1.0.0
76     */
77    public function addNode(Node $node) : void
78    {
79        $this->nodes[] = $node;
80    }
81
82    /**
83     * Get the path length (euclidean)
84     *
85     * @return float
86     *
87     * @since 1.0.0
88     */
89    public function getLength() : float
90    {
91        $n = \count($this->nodes);
92
93        $dist = 0.0;
94
95        for ($i = 1; $i < $n; ++$i) {
96            $dx = $this->nodes[$i - 1]->getX() - $this->nodes[$i]->getX();
97            $dy = $this->nodes[$i - 1]->getY() - $this->nodes[$i]->getY();
98
99            $dist += \sqrt($dx * $dx + $dy * $dy);
100        }
101
102        return $dist;
103    }
104
105    /**
106     * Get the incomplete node path
107     *
108     * @return Node[]
109     *
110     * @since 1.0.0
111     */
112    public function getPath() : array
113    {
114        return $this->nodes;
115    }
116
117    /**
118     * Get the complete node path
119     *
120     * The path may only contain the jump points or pivot points.
121     * In order to get every node it needs to be expanded.
122     *
123     * @return Node[]
124     *
125     * @since 1.0.0
126     */
127    public function expandPath() : array
128    {
129        if (empty($this->expandedNodes)) {
130            //$reverse = \array_reverse($this->nodes);
131            $reverse = $this->nodes;
132            $length  = \count($reverse);
133
134            if ($length < 2) {
135                return $reverse;
136            }
137
138            $expanded = [];
139            for ($i = 0; $i < $length - 1; ++$i) {
140                $coord0 = $reverse[$i];
141                $coord1 = $reverse[$i + 1];
142
143                $interpolated = $this->interpolate($coord0, $coord1);
144                $expanded     = \array_merge($expanded, $interpolated);
145            }
146
147            $expanded[]          = $reverse[$length - 1];
148            $this->expandedNodes = $expanded;
149        }
150
151        return $this->expandedNodes;
152    }
153
154    /**
155     * Find nodes in bettween two nodes.
156     *
157     * The path may only contain the jump points or pivot points.
158     * In order to get every node it needs to be expanded.
159     *
160     * @param Node $node1 Node
161     * @param Node $node2 Node
162     *
163     * @return Node[]
164     *
165     * @since 1.0.0
166     */
167    private function interpolate(Node $node1, Node $node2) : array
168    {
169        $dx = \abs($node2->getX() - $node1->getX());
170        $dy = \abs($node2->getY() - $node1->getY());
171
172        $sx = ($node1->getX() < $node2->getX()) ? 1 : -1;
173        $sy = ($node1->getY() < $node2->getY()) ? 1 : -1;
174
175        $node = $node1;
176        $err  = $dx - $dy;
177
178        $x0 = $node->getX();
179        $y0 = $node->getY();
180
181        $line = [];
182        while (true) {
183            if ($node->getX() === $node2->getX() && $node->getY() === $node2->getY()) {
184                break;
185            }
186
187            $line[] = $node;
188
189            $e2 = 2 * $err;
190
191            if ($e2 > -$dy) {
192                $err -= $dy;
193                $x0  += $sx;
194            }
195
196            if ($e2 < $dx) {
197                $err += $dx;
198                $y0  += $sy;
199            }
200
201            $node = $this->grid->getNode($x0, $y0);
202
203            if ($node === null) {
204                break; // @codeCoverageIgnore
205            }
206        }
207
208        return $line;
209    }
210}