Best Practise: Path finding(op een grid)

Overzicht Reageren

Sponsored by: Vacatures door Monsterboard

Michael de Wal

Michael de Wal

26/03/2012 15:05:26
Quote Anchor link
Beste PHPers,

ik ben bezig met een applicatie waarbij ik routes op een grid moet creëren. Elke route moet berekend worden vanaf een startpunt aan een zijkant van de grid naar een eindpunt aan een zijkant.

Nu heb ik bepaalde coordinaten waar de route niet overheen mag, waar je een bepaalde richting aan moet houden en bochten. Hoe kan ik het best de route over de wegen leiden naar een eindpunt?

Oplossingen die ik zelf had bedacht:
- On the fly: Kijkt of het volgende blokje toegankelijk is (richting goed), Kijkt of er een bocht is en zo ja, hoeveel. Kies een random bocht. Etc etc.
- Vooraf: Maak een array van alle beschikbare routes, dit door het idee hierboven net zo lang toe te passen tot je elke unieke route hebt.

Beide van deze oplossingen vergen behoorlijk wat loops om tot eindresultaat te komen. Nu is dat niet een heel erg groot probleem aangezien de routes nooit veranderen (kunnen dus opgeslagen worden).

Mijn vraag aan jullie is dit:
Wat is de "beste" manier om routes te berekenen op een grid? Het moet zo min mogelijk resources kosten.
 
PHP hulp

PHP hulp

28/03/2024 10:09:03
 
Kris Peeters

Kris Peeters

26/03/2012 15:32:01
Quote Anchor link
Daar komt wel wat bij kijken, routering.

Vraag maar aan Dykstra
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Ik ben nog ooit een dykstra class tegengekomen (php). Als je die vindt, gebruik die dan.
Als je het echt zelf wil maken, lees dan eens deftig wat je voorgangers hebben gedaan; want het is iets lastiger dan je nu denkt.
Gewijzigd op 26/03/2012 15:35:48 door Kris Peeters
 
Michael de Wal

Michael de Wal

26/03/2012 15:36:55
Quote Anchor link
Kris Peeters op 26/03/2012 15:32:01:
Daar komt wel wat bij kijken, routering.

Vraag maar aan Dykstra
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Ik ben nog ooit een dykstra class tegengekomen (php). Als je die vindt, gebruik die dan.
Als je het echt zelf wil maken, lees dan eens deftig wat je voorgangers hebben gedaan; want het is iets lastiger dan je nu denkt.


Ik heb inderdaad ingelezen over dat algoritme, maar het is niet wat ik nodig heb. Dit omdat in mijn grid alles al gedefiniëerd is. Alle afstanden tot punten is gewoon 1. Ik heb gewoon alle routes nodig die mogelijk zijn. Niet de beste route die er is.
 
Kris Peeters

Kris Peeters

26/03/2012 16:14:42
Quote Anchor link
Dan nog ben ik geneigd te denken dat je beter af bent met een deftig algoritme, waar over nagedacht is.

Trouwens, Google gewoon "class.dijkstra.php", er zijn er genoeg te vinden.
 
Michael de Wal

Michael de Wal

26/03/2012 16:23:15
Quote Anchor link
Kris Peeters op 26/03/2012 16:14:42:
Dan nog ben ik geneigd te denken dat je beter af bent met een deftig algoritme, waar over nagedacht is.

Trouwens, Google gewoon "class.dijkstra.php", er zijn er genoeg te vinden.


Daar ben ik het mee eens. Maar dit algoritme is niet wat ik zoek. Vooral, omdat het niet werkt met hoe mijn routes opgezet zijn. Ik zal denk zelf een algortme moeten schrijven.
 
Kris Peeters

Kris Peeters

27/03/2012 16:41:02
Quote Anchor link
Laat je iets weten als het concreter wordt?
 
Pim -

Pim -

27/03/2012 18:15:33
Quote Anchor link
@Michael
Grapjas...
Pathfinding is een wetenschap, succes ermee.
Gewijzigd op 27/03/2012 18:15:52 door Pim -
 
Michael de Wal

Michael de Wal

27/03/2012 18:21:43
Quote Anchor link
Pim - op 27/03/2012 18:15:33:
@Michael
Grapjas...
Pathfinding is een wetenschap, succes ermee.


Als je niks zinnigs hebt bij te dragen kun je net zo goed niet posten.


Kris Peeters op 27/03/2012 16:41:02:
Laat je iets weten als het concreter wordt?


Ik zit er toch over te twijfelen Dijkstra's algoritme te gebruiken. Als ik namelijk alle ingangs punten en uitgangen al weet, kan ik deze methode wel toepassen. Uiteindelijk zal ik hem wel moeten wijzigen helaas, aangezien het niet precies is wat ik zoek.
 
Pim -

Pim -

29/03/2012 11:51:21
Quote Anchor link
Google eens op Minimum Spanning Tree.
 



Overzicht Reageren

 
 

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.