Pathfinding
Door Pim -, 18 jaar geleden, 7.507x bekeken
Hiermee kan je de kortste route tussen punten vinden.
Voorbeeld:
Code (php)
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
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';
?>
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';
?>
Voorbeeld: http://pimwebdesign.nl/phphulp/pathfinding
Gesponsorde koppelingen
PHP script bestanden
Er zijn 15 reacties op 'Pathfinding'
0 
-0 
-0
ziet er leuk uit. ik heb zelf nog nooit zoiets nodig gehad maar misschien later nog eens.
0 -0
-0
Ziet er interessant uit. Ligt het aan mij(n computer) of is je online voorbeeld een beetje dood?
0 -0
-0
Volgens mij niet hoor, de server is wel een beetje heel langzaam...
Maar dit is de output ;)
Maar dit is de output ;)
Code (php)
1
2
2
A - 1 - B - 2 - E - 3 - I - 1 - J = 7
in 0.000473976135254 seconds
in 0.000473976135254 seconds
0 -0
-0
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)
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)
0 -0
-0
Waar zou je dit voor kunnen gebruiken dan? Geef eens een paar voorbeelden? Ik kan me zo niks bedenken.
0 -0
-0
@nico Het alogrithme is vermeld als phpdoc bij de class:
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
Code (php)
1
2
3
4
5
6
7
8
9
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
* 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
0 -0
-0
@Pim,
ik bedoel,
A* algoritme,
Dijkstra's Algoritme.
En dat met die array,
Dat kan veel sneller en beter dan.
ik bedoel,
A* algoritme,
Dijkstra's Algoritme.
En dat met die array,
Dat kan veel sneller en beter dan.
0 -0
-0
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.
Maar ik zal deze 2 even bestuderen.
0 -0
-0
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/
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/
0 -0
-0
Haha kan je lezen?
De zin
suggereert toch echt dat andere algoritmen op bepaalde punten beter zijn.
De zin
Quote:
Andere zijn hoogstwaarschijnlijk een stuk sneller
suggereert toch echt dat andere algoritmen op bepaalde punten beter zijn.
0 -0
-0
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?
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?
0 -0
-0
@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
suggereert inderdaad dat andere algoritmen op bepaalde punten beter zijn.
Alleen deze zin is gevolgd door:
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
Quote:
Andere zijn hoogstwaarschijnlijk een stuk sneller
suggereert inderdaad dat andere algoritmen op bepaalde punten beter zijn.
Alleen deze zin is gevolgd door:
Quote:
maar in geen geval beter.
0 -0
-0
@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.
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.
0 -0
-0
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.
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.
0 -0
-0
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.
Maar wel vrij lastig, want punten zoals hier gedefinieerd kunnen er op veel manieren uitzien, precies waarom A* niet werkt.
Om te reageren heb je een account nodig en je moet ingelogd zijn.
PHP hulp
0 seconden vanaf nu