Best Practise: Path finding(op een grid)
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.
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
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.
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.
Trouwens, Google gewoon "class.dijkstra.php", er zijn er genoeg te vinden.
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.
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.
Grapjas...
Pathfinding is een wetenschap, succes ermee.
Gewijzigd op 27/03/2012 18:15:52 door Pim -
Pim - op 27/03/2012 18:15:33:
@Michael
Grapjas...
Pathfinding is een wetenschap, succes ermee.
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.