Tut: Wegfindung: Dijkstra
Übersicht
Sonstiges Smalltalk
|
pixelshooterBetreff: Tut: Wegfindung: Dijkstra |
 Di, Aug 07, 2007 19:15Antworten mit Zitat 
|
|---|---|---|
|
Wer schon einmal mit Wegfindung auf Netzen zu tun hatte - zum beispiel wenn ein zug seinen weg finden sollte - ist vllt über den Namen Dijkstra gestoßen. Dessen Wegfindungsalgo ist genau dafür gedacht.
Ich habe ihn mal ein wenig beschrieben, inklusive Programmbeispiele, da diese allerdings in C++ geschrieben sind, wage ich zu behaupten, dass die meisten hier lieber die codes bei Seite lassen und nur die Beschreibung des Algorithmus lesen. Da das ganze nicht direkt mit Blitz zu tun hat, schreibe ich das in den Smalltalk. Link: http://aintelligence.ai.funpic...6&t=19 PS: Kritik kann auch (sehr gerne sogar) in dortigem forum plaziert werden. mfg fabian |
||
| >> Musikerstellung, Grafik und Design: http://www.pixelshooter.net.tc | ||
|
TheShadowModerator |
Di, Aug 07, 2007 21:10 Antworten mit Zitat
|
|---|---|---|
| es funktioniert genau wie A* - nur gibt es statt eines Array-Gitters beliebig viele Verweigungen... Optimierungsvorteil: Länge der Zweige kann man vorberechnen | ||
| AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2 | ||
|
|
pixelshooter |
Mi, Aug 08, 2007 15:36 Antworten mit Zitat
|
|---|---|---|
|
Zitat: Optimierungsvorteil: Länge der Zweige kann man vorberechnen
wie meinst du das? |
||
| >> Musikerstellung, Grafik und Design: http://www.pixelshooter.net.tc | ||
|
StepTiger |
Mi, Aug 08, 2007 15:51 Antworten mit Zitat
|
|---|---|---|
|
@TheShadow
Mit A* ist es ebenfalls möglich, (annähernd) beliebig viele Verzweigungen zu implementieren. Einfach mit Types arbeiten, so habe ich das mal bei einem (Mini-)Routenplaner gemacht, den ich mit Blitz programmiert hatte. |
||
|
Noch gestern standen wir am Abgrund, doch heute sind wir schon einen Schritt weiter.
Computer: AMD Sempron 3000+; ATI Radeon 9800 Pro; 512 MB DDR RAM 400Mhz; Asus E7N8X-E Deluxe; Samsung 200GB HD 5.4ns acces t Gewinner: BP Code Compo #2 Π=3.141592653589793238...<--- und das aus dem kopf 
Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser. |
||
Dreamora |
Mi, Aug 08, 2007 16:35 Antworten mit Zitat
|
|
|---|---|---|
|
Hauptunterschied Dijkstra - A* ist das
Dijkstra von Start zu Ziel sucht ohne die Distanz zum Ziel zu berücksichtigen. Dabei wird eine Randschnittgruppe mitgeführt, aus welcher der Algorithmus jeweils den nächsten zu betrachtenden Knoten zieht. Dieser Knoten ist jener der die kürzeste Wegdistanz aufweist. A* sucht auch von Start zu Ziel und führt dabei eine Randschnittgruppe. Der Hauptunterschied besteht jedoch darin, dass A* eine heuristische Abschätzung macht, wie weit es von jedem Punkt aus zum Ziel in etwa noch sein wird. Das führt häufig zu besseren Ergebnissen als Dijkstra, da es mittlerweile sehr gute Heuristiken gibt um die Restdistanz abzuschätzen. Dies macht jedoch A* auch schwerer korrekt zu implementieren als Dijkstra. (denn falsche Implementation führt dazu das die AI ständig in Sackgassen endet) Denn Dijkstra kann jeder implementieren der mit Types umgehen kann und weiss wie man eine PriorityQueue bzw. Heap implementiert. |
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
Übersicht
Sonstiges Smalltalk
Powered by phpBB © 2001 - 2006, phpBB Group