pathfinding

Gesponsorde koppelingen

PHP script bestanden

  1. pathfinding

« Lees de omschrijving en reacties

Pathfinding.php

Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
<?php
/**
 *
 * @author Pim <[email protected]>
 * @version 1.0
 * @package Pathfinding
 *
 */

/**
 * The Pathfinding class
 *
 * Finds the shortest path between a starting point and an ending point
 * Uses the following algorithm
 *     1. Starts at the starting point
 *     2. Finds all connected points
 *     3. Then does the following with every connected point
 *         - If the point is an ending point, add this route to {@link $_goodRoutes}
 *         - If the point is reached quicker in another route, do not do anything
 *         - Else add the last distance to the total distance and go to step 2
 *     4. After all {@link $_goodRoutes} have been found, they are sorted by distance
 *     5. The shortest {@link $_goodRoutes} is returned
 *
 * @package Pathfinding
 */

class Pathfinding
{
    /**
     * Stores the points
     * @var array
     */

    private $_points = array();
    
    /**
     * Stores the shortest distance to every point
     * @var array
     */

    private $_shortestRouteTo = array();
    
    /**
     * Stores all routes leading to an ending point
     * @var array
     */

    private $_goodRoutes = array();
    
    /**
     * The time the finding took
     * @var int
     */

    private $_findingTime;
    
    /**
     * The constructor, if an parameter is given, they are passed through to {@link addPoints()}
     * @param array|null $array
     */

    public function __construct($array = null)
    {

        if(!is_null($array)) {
            $this->addPoints($array);
        }
    }

    
    /**
     * Adds an point to {@link $_points}
     * @param Pathfinding_Point $p
     * @return Pathfinding
     */

    public function addPoint(Pathfinding_Point $p)
    {

        $this->_points[$p->getName()] = $p;
        
        return $this;
    }

    
    /**
     * Adds multiple points to {@link $_points}
     * @param array $a
     * @return Pathfinding
     */

    public function addPoints(array $a)
    {

        foreach($a as $point) {
            $this->_points[$point->getName()] = $point;
        }

        return $this;
    }

    
    /**
     * The main finding function, doing steps 1, 4 and 5 of the previous discribed algorithm
     * @param Pathfinding_Point $start
     * @return array The found route
     *
     * @todo Return multiple routes if more than one route is the shortest
     */

    public function find(Pathfinding_Point $start)
    {

        if($start instanceof Pathfinding_Point) {
            $startingPoint = $start;
        }
else if (is_string($start)) {
            $startingPoint = $this->_points[$start];
        }

        
        // Time the finding
        $startingTime = microtime(true);
        
        $this->_shortestRouteTo[$startingPoint->getName()] = 0;
        $this->_findRecursion(array($startingPoint), 0);
        
        // Sorts the found routes by distance, ascending
        usort($this->_goodRoutes, array($this, '_sortRoutes'));
        
        $this->_findingTime = microtime(true) - $startingTime;
        
        // Returns the shortest of the found routes
        return reset($this->_goodRoutes);
    }

    
    /**
     * Step 2 and 3 of the previous discribed algorithm
     * @param array $route The route until this point
     * @param int $distance The distance until this point
     * @return null
     */

    private function _findRecursion(array $route, $distance)
    {

        $point = end($route);
        foreach($point->getLinks() as $link) {
            // If the point has not been reached yet, or has only been reached in a longer distance
            if(!isset($this->_shortestRouteTo[ $link['point']->getName() ]) ||
                $this->_shortestRouteTo[ $link['point']->getName() ] > $distance + $link['distance']) {
                    
                $newRoute = $route;
                $newRoute[] = $link['point'];
                $newDistance = $distance + $link['distance'];
                
                // If the point is an ending point
                if($link['point']->isEnd()) {
                    $this->_goodRoutes[] = array('route' => $newRoute, 'distance' => $newDistance);
                }
else {
                    $this->_shortestRouteTo[ $link['point']->getName() ] = $newDistance;
                    // Continues the search
                    $this->_findRecursion($newRoute, $newDistance);
                }
            }
        }
    }

    
    /**
     * Sorts the routes by distance, ascending
     * @see usort()
     * @param array $a
     * @param array $b
     *
     * @return int
     */

    private function _sortRoutes(array $a, array $b)
    {

        return ($a['distance'] < $b['distance']) ? -1 : 1;
    }

    
    /**
     * Returns the time the finding took
     * @return float
     */

    public function time()
    {

        return $this->_findingTime;
    }

    
    /**
     * Formats the found route nicely
     * @static
     * @param array $route
     * @return string
     */

    public static function formatRoute(array $route)
    {

        $string = '';
        $previous = null;
        foreach($route['route'] as $point) {
            if(!is_null($previous)) {
                // Prints the distance between points
                $string .= ' - '.$point->getDistance($previous).' - ';
            }

            $string .= '<strong>'.$point->getName().'</strong>';
            $previous = $point;
        }

        // Prints the total distance
        $string .= ' = '.$route['distance'];
        return $string;
    }
}

?>

Pathfinding_Point.php
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
<?php
/**
 *
 * @author Pim <[email protected]>
 * @version 1.0
 * @package Pathfinding
 *
 */

/**
 * The Pathfinding point class
 *
 * Discribes a point and the links to other points
 *
 * @package Pathfinding
 */

class Pathfinding_Point
{
    /**
     * The links
     * @var array
     */

    private $_links = array();
    
    /**
     * The points name
     * @var string
     */

    private $_name;
    
    /**
     * Wether the point is an ending point
     * @var boolean
     */

    private $_isEnd;
    
    /**
     * The consructor, sets {@link $_name} and {@link $_isEnd}
     * @param string $name
     * @param boolean $isEnd
     */

    public function __construct($name, $isEnd = false)
    {

        $this->_name = $name;
        $this->_isEnd = $isEnd;
    }

    
    /**
     * Returns {@link $_name}
     * @return string
     */

    public function getName()
    {

        return $this->_name;
    }

    
    /**
     * Returns {@link $_isEnd}
     * @return boolean
     */

    public function isEnd()
    {

        return $this->_isEnd;
    }

    
    /**
     * Adds an link to this and the other point
     *
     * @param Pathfinding_Point $p
     * @param int $distance The distance between the two points, default is 1
     * @param boolean $forwarded If the call is made by the other point
     *
     * @see $_links
     *
     * @return Pathfinding_Point
     */

    public function addLink(Pathfinding_Point $p, $distance = 1, $forwarded = false)
    {

        $this->_links[ $p->getName() ] = array('point' => $p, 'distance' => $distance);
        
        if(!$forwarded) {
            $p->addLink($this, $distance, true);
        }

        
        return $this;
    }

    
    /**
     * Adds multiple links
     * @see addLink()
     * @param array $a
     *
     * @return Pathfinding_Point
     */

    public function addLinks(array $a)
    {

        foreach($a as $distance => $point) {
            $this->addLink($point, $distance);
        }

        
        return $this;
    }

    
    /**
     * Returns {@link $_links}
     *
     * @return array
     */

    public function getLinks()
    {

        return $this->_links;
    }

    
    /**
     * Returns the distance between the points
     * @param Pathfinding_Point $p
     * @return int
     */

    public function getDistance(Pathfinding_Point $p)
    {

        return $this->_links[ $p->getName() ]['distance'];
    }
}

?>

 
 

Om de gebruiksvriendelijkheid van onze website en diensten te optimaliseren maken wij gebruik van cookies. Deze cookies gebruiken wij voor functionaliteiten, analytische gegevens en marketing doeleinden. U vindt meer informatie in onze privacy statement.