Pathfinding

Door Pim -, 12 jaar geleden, 4.888x bekeken

Hiermee kan je de kortste route tussen punten vinden.

Voorbeeld:

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
<?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';
?>

Voorbeeld: http://pimwebdesign.nl/phphulp/pathfinding

Gesponsorde koppelingen

PHP script bestanden

  1. pathfinding

 

Er zijn 15 reacties op 'Pathfinding'

PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Yorick17
yorick17
12 jaar geleden
 
0 +1 -0 -1
ziet er leuk uit. ik heb zelf nog nooit zoiets nodig gehad maar misschien later nog eens.
Afra ca
Afra ca
12 jaar geleden
 
0 +1 -0 -1
Ziet er interessant uit. Ligt het aan mij(n computer) of is je online voorbeeld een beetje dood?
Pim -
Pim -
12 jaar geleden
 
0 +1 -0 -1
Volgens mij niet hoor, de server is wel een beetje heel langzaam...

Maar dit is de output ;)
Code (php)
PHP script in nieuw venster Selecteer het PHP script
1
2
A - 1 - B - 2 - E - 3 - I - 1 - J = 7
in 0.000473976135254 seconds
Nicoow Unknown
Nicoow Unknown
12 jaar geleden
 
0 +1 -0 -1
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)
Code (php)
PHP script in nieuw venster Selecteer het PHP script
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
steen
12 jaar geleden
 
0 +1 -0 -1
Waar zou je dit voor kunnen gebruiken dan? Geef eens een paar voorbeelden? Ik kan me zo niks bedenken.
Pim -
Pim -
12 jaar geleden
 
0 +1 -0 -1
@nico Het alogrithme is vermeld als phpdoc bij de class:
Code (php)
PHP script in nieuw venster Selecteer het PHP script
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
Nicoow Unknown
Nicoow Unknown
12 jaar geleden
 
0 +1 -0 -1
@Pim,
ik bedoel,
A* algoritme,
Dijkstra's Algoritme.

En dat met die array,
Dat kan veel sneller en beter dan.
Pim -
Pim -
12 jaar geleden
 
0 +1 -0 -1
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.
Nicoow Unknown
Nicoow Unknown
12 jaar geleden
 
0 +1 -0 -1
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 -
Pim -
12 jaar geleden
 
0 +1 -0 -1
Haha kan je lezen?
De zin
Quote:
Andere zijn hoogstwaarschijnlijk een stuk sneller

suggereert toch echt dat andere algoritmen op bepaalde punten beter zijn.
Jelmer -
Jelmer -
12 jaar geleden
 
0 +1 -0 -1
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?
Nicoow Unknown
Nicoow Unknown
12 jaar geleden
 
0 +1 -0 -1
@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
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.
Pim -
Pim -
12 jaar geleden
 
0 +1 -0 -1
@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.
Nicoow Unknown
Nicoow Unknown
12 jaar geleden
 
0 +1 -0 -1
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.
PHP hulp
PHP hulp
0 seconden vanaf nu
 

Gesponsorde koppelingen
Pim -
Pim -
12 jaar geleden
 
0 +1 -0 -1
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.

Om te reageren heb je een account nodig en je moet ingelogd zijn.

Inhoudsopgave

  1. pathfinding

Labels

  • Geen tags toegevoegd.

Navigatie

 
 

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.