PHPhulp
 
 
Header image
Username: Password:   registreren | wachtwoord kwijt
 


PHP scripts

Pathfinding

Niveau: Gevorderd
PHP versie: 5
Categorie: Overige
Voorbeeld: http://pimwebdesig....hphulp/pathfinding

Door Pim op 30.01.2010

Print versie PHP script

Toelichting:
Hiermee kan je de kortste route tussen punten vinden.

Voorbeeld:

 Selecteer deze code
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
<?php

ini_set('display_errors', 'on');
error_reporting(E_ALL | E_STRICT);

require_once 'Pathfinding.php';
require_once 'Pathfinding_Point.php';

// Create the points
$a = new Pathfinding_Point('A');
$b = new Pathfinding_Point('B');
$c = new Pathfinding_Point('C');
$d = new Pathfinding_Point('D');
$e = new Pathfinding_Point('E');
$f = new Pathfinding_Point('F');
$g = new Pathfinding_Point('G');
$h = new Pathfinding_Point('H');
$i = new Pathfinding_Point('I');
$j = new Pathfinding_Point('J', true);
$k = new Pathfinding_Point('K');
$l = new Pathfinding_Point('L');

// Create the links
$a->addLink($b)->addLink($g);
$b->addLink($e, 2)->addLink($d);
$c->addLink($g, 2)->addLink($d);
$d->addLink($f)->addLink($h);
$e->addLink($f)->addLink($i, 3);
$f->addLink($i, 3)->addLink($k);
$h->addLink($k)->addLink($l);
$i->addLink($j);
$l->addLink($j, 3);

// Create the object and adds the points
$pathFinding = new Pathfinding(array($a, $b, $c, $d, $e, $f, $g, $h, $i, $j, $k, $l));

// Calculate the route
$route = $pathFinding->find($a);

// Formats the route
echo Pathfinding::formatRoute($route);

echo '<br /> in '.$pathFinding->time().' seconds';
?>

Code:
Pathfinding.php

 Selecteer deze code
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 <pimdehaan@gmail.com>
 * @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
 Selecteer deze code
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 <pimdehaan@gmail.com>
 * @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'];
    }
}
?>


Meer PHP scripts in deze categorie Meer PHP scripts in deze categorie

Reacties

Voeg ook een reactie toe.

yorick17 schreef op 31.01.2010 00:24
ziet er leuk uit. ik heb zelf nog nooit zoiets nodig gehad maar misschien later nog eens.

Afra schreef op 31.01.2010 12:08
Ziet er interessant uit. Ligt het aan mij(n computer) of is je online voorbeeld een beetje dood?

Pim schreef op 31.01.2010 12:28
Volgens mij niet hoor, de server is wel een beetje heel langzaam...

Maar dit is de output ;)
 Selecteer deze code
1
2
A - 1 - B - 2 - E - 3 - I - 1 - J = 7
in 0.000473976135254 seconds

nico schreef op 31.01.2010 14:42
Misschien even leuk om te vermelden welk algohrithme je hebt gebruikt hiervoor.
En is het misschien niet makkelijker als je een array mee geeft, met eventueel eventueel nog een height map.
dus dat je array is als:
(1 = beloopbaar, 0 niet)
 Selecteer deze code
1
2
3
4
5
6
7
8
<?php
array(
1 => array(1,1,1,1,1,1,1,1,1,1,1,1,1,1),
2 => array(1,1,1,1,1,0,1,1,1,1,0,1,1,1),
3 => array(1,1,1,1,0,0,0,1,1,1,0,1,1,1),
4 => array(1,1,1,1,1,0,1,1,1,1,0,0,0,1),
5 => array(1,1,1,1,1,1,1,1,1,1,1,1,1,1));
?>

steen schreef op 31.01.2010 14:56
Waar zou je dit voor kunnen gebruiken dan? Geef eens een paar voorbeelden? Ik kan me zo niks bedenken.

Pim schreef op 31.01.2010 15:01
@nico Het alogrithme is vermeld als phpdoc bij de class:
 Selecteer deze code
1
2
3
4
5
6
7
8
9
* 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


En ja misschien maak ik dat wel, alleen een kwestie van met wat foreach'jes punten aanmaken en links leggen.

@steen
Stel dat je een PHP-GTK spel wilt maken.....
Maar meer in het algemeen: eigenlijk alleen om eerst te vertalen naar een andere taal en daarna in een spel verwerken.

EDIT: En het maken van verkeersroutes en het maken van een turnbased strategy spel

Gewijzigd op 31.01.2010 15:58 door Pim

nico schreef op 31.01.2010 15:27
@Pim,
ik bedoel,
A* algoritme,
Dijkstra's Algoritme.

En dat met die array,
Dat kan veel sneller en beter dan.

Pim schreef op 31.01.2010 15:54
Geen van beiden, ik heb mijn eigen algoritme bedacht. Andere zijn hoogstwaarschijnlijk een stuk sneller, maar in geen geval beter. Sterker nog, ik denk dat de mijne altijd een route geeft die sneller of even snel is als die andere routes, simpelweg omdat hij ze allemaal test.

Maar ik zal deze 2 even bestuderen.

Gewijzigd op 31.01.2010 16:06 door Pim

nico schreef op 31.01.2010 18:45
Ga nou niet beweren dat jou algoritme bet is als A*.
Ook A* geeft altijd de beste route, en gaat alle mogelijk oplossingen af, alleen die doet het heel slim.

Even een voorbeeld app,, waarbij je ook ziet wat A* doet:
http://www.codeguru.com/dbfiles/get_file/PathFinder_app.zip?id=12527&lbl=PATHFINDER_APP_ZIP&ds=20060906

En de uitleg:
http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527/

Pim schreef op 31.01.2010 18:53
Haha kan je lezen?
De zin
Andere zijn hoogstwaarschijnlijk een stuk sneller

suggereert toch echt dat andere algoritmen op bepaalde punten beter zijn.

Jelmer schreef op 31.01.2010 19:09
De snelheid zit hem puur in hoeveel mogelijke combinaties hij probeert voordat hij een route teruggeeft. A* checkt zeker niet alle mogelijke routes, maar levert mits je een goeie heuristiek gebruikt wel bijna altijd de snelste route op. Daarnaast levert het altijd minstens één route op als er eentje is (maar hoe lang dat duurt staat niet vast, en ligt aan je landschap en je heuristiek)

Jouw algoritme lijkt me depth-first. Depth-first zoekt zeg maar eerst naar een route, en gaat daarna backtracken om bij iedere keuze die is gemaakt ook de andere keuze te proberen, van beneden naar boven terug. Bij depth-first moet je altijd oppassen voor recursie (a->b->a->b->a..etc) Is dat door jouw algoritme gedekt?

Gewijzigd op 31.01.2010 19:10 door Jelmer

nico schreef op 31.01.2010 19:20
@Jelmer,
A* checkt niet ALLE mogelijk routes,,
Hij gaat probeert steeds zo dichtbij mogelijk te komen, en zoekt dan de snelste weg eromheen.
hij probeert niet naar links te gaan, als hij direct naar rechts kan, waar het doel ongeveer licht.
Maar voor hoelang het duurt, word vaak gebruikt gemaakt van een maximaal aantal steps die hij gaat proberen.

@Pim,
Haha kan je lezen?
De zin
Andere zijn hoogstwaarschijnlijk een stuk sneller

suggereert inderdaad dat andere algoritmen op bepaalde punten beter zijn.

Alleen deze zin is gevolgd door:
maar in geen geval beter.

Pim schreef op 31.01.2010 19:48
@jelmer
Ja ik kijk bij elke aankomst op een punt of dit punt al eerder bereikt is met een kortere route. Dit voorkomt automatisch recursie en zorgt meteen voor een flinke optimalisatie.

@nico Daarmee bedoelde ik dus dat mijn algoritme altijd de optimale route zal vinden, A* doet dat, zoals Jelmer zei, niet. Ook is A* onbruikbaar voor de input die ik gebruik. Zoals Wikipedia vermeldt is bij A* het noodzakelijk de locaties van punten te weten, deze zijn bij mijn input onbekend. Dijkgraaf's algoritme kan daarintegen inderdaad wel het script verbeteren en daar zal ik me, zoals ik eerder zei, me ook in verdiepen.

Gewijzigd op 31.01.2010 19:53 door Pim

nico schreef op 31.01.2010 19:56
Nu moet ik ook wel zeggen,
A* is gebaseerd op een grid,
Dijkstra, en dat van jou, op plaatsen.
met verschillende afstanden tussen plaatsen (neem ik aan, iig dijkstra wel).
Maar het zou leuk zijn als je het kon visualiseren. met van die rondjes enzo.

Pim schreef op 31.01.2010 20:24
Hmm dat is ook wel leuk ja.
Maar wel vrij lastig, want punten zoals hier gedefinieerd kunnen er op veel manieren uitzien, precies waarom A* niet werkt.

Voeg een reactie toe

Alleen leden mogen reacties toevoegen. Dit i.v.m. het vele spam die we de laatste tijd hebben gekregen. Je kunt je registreren op de registratie pagina. Ben je al lid? Dan kun je inloggen aan de bovenkant van de website.

Ga naar het overzicht met PHP scripts.
php hosting | faq | over ons | php tutorials | php scripts | php boeken | php links | php faq | php howto | forum | contact FlexServers
Wat snel webhosting

tracker Laatste PHP tutorials

10.02
Hoe kun je inloggen op PHPHul..
30.01
setlocale()
22.01
Uploadsysteem
19.01
Sleep
30.12
OOP Beginnershandleiding (PHP..

tracker Laatste PHP scripts

04.02
Veilige email adress weergave..
31.01
[UPDATE] Server Status v2
30.01
Pathfinding
30.01
Query script
30.01
Pagination Script

tracker Laatste PHP boeken

03.11
Basiscursus PHP 5
04.10
Object-Oriented Analysis & De..
04.05
Mysql 5 in 10 minuten
11.03
MySQL 5 Certification Study G..
03.08
PHP 5 in 10 minuten, 2e editi..

tracker Laatste forum berichten

13:24
PHPhulp Welkom terug op PHPHulp!
13:24
PHPhulp Welkom terug op PHPHulp!
13:24
PHPhulp Welkom terug op PHPHulp!
23:04
PHPhulp Bas, waarom kan ik niet m..
19:07
Bas, waarom kan ik niet meer ..
19:04
Hulp nodig: Script generator
14:41
menu is fout
14:06
Script met navigatie en filte..
14:06
[Jquery] Probleem met .html()..
13:41
normalisatie vraag
11:29
Javascript en php
10:15
Zoekfunctie met php

tracker Laatste reacties

13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)
13:27
Hoe kun je inlogge.. (PHP tutorial)

PHP zoeken PHP zoeken

 Zoekterm

Zoeken in

tracker Voting poll

 Welke browser heeft jouw voorkeur?

Google Chrome
Mozilla Firefox
Internet Explorer
Apple Safari
Opera Software
Een andere browser


tracker Actieve leden

 
 Er zijn 41 gasten en 4 leden actief.
Actieve leden: peter-jan@blitz.nu, Arjen Halma, Marco, Wieland