[mittel bis schwer]: Wegsuche

CDW

0
Mitarbeiter
Eingereicht von Extinction:
Ausgangssituation ist ein in gleich große Quadrate unterteiltes Spielfeld, wie ein Schachbrett. Wir haben eine Figur A, welche zum Punkt B gelangen soll. Hierfür ist der/die Kürzeste/n Weg/e zu berechnen.
Zunächst auf freiem feld, was recht einfach währe.
Dann, um ein Hinderniss herum.
Und zuletzt auch durch ein Labyrinth.

Um es etwas zu vereinheitlichen:

das Programm muss ein Spielbrett einlesen können:
####
####
####

Dieses hat ein Format "n * m". Also n Zeilen zu m Spalten. Ihr könnt davon ausgehen, dass alle Bretter rechteckig sind.
Code:
###=#Z#
~######
##...+#
#######
#A#####

Dabei gibt ein '#' ein freies Feld an, ein Großbuchstabe (außer Z) den Spieler (und damit seine Koordinaten) und das Z steht für Ziel. Alle anderen Zeichen sind als Hindernisse zu betrachten.

Das Programm soll den Weg von dem aktuellen Punkt mit dem Spieler zum Zielpunkt berechnen und ausgeben. Die Ausgabe kann grafisch sein (wer mag) oder simpel mit (x,y) Koordinaten erfolgen (nur eben einheitlich):
(3, 4) -> (3, 3) -> (2, 3) -> Ziel

Einfache Version: der Spieler kann sich nicht diagonal bewegen, nur links/rechts/oben/unten. Der Algorithmus muss nicht "Realapplication" tauglich sein ;)

Schwere Version: der Spieler kann sich auch diagonal bewegen.
Also oben/unten/links/rechts/oben-rechts, oben-links usw.
Der Algorithmus/Ansatz muss halbwegs "Realapplication" tauglich sein - z.B für 30 Spielfiguren auf einem 100x100 Spielfeld [0].
Dabei muss der Weg nicht nachweisbar der "kürzeste" sein - sollte aber nicht zu sehr davon abweichen.

Bsp Karte mit Figuren A, B und Zielpunkt Z, dazu mit "Hindernissen":
Code:
 #====================================+
 |#########//\\#################Z#####|
 |########//##\\######################|
 |#############\\######\----------/\/\|
 |##############\\####################|
 |####//\\############################|
 |#######\\###()()()()()##############|
 |########\\#####\\\\\\\##############|
 |#########\\\########################|
 |####################################|
 |####################################|
 |####################################|
 |#A##############################B###|
 |####################################|
 +====================================+

[0] das ist jetzt Pi mal Daumen geschätzt und kommt auch auf die benutzte Sprache und andere Faktoren an ;) - ihr solltet einfach (in etwa )einschätzen können, ob eure Umsetzung mehrere Routen pro Sekunde für ein halbwegs realistisch gerastertes Spielfeld schafft :)
 
Zuletzt bearbeitet:
Lösung unter der Annahme dass ein Schritt, egal ob diagonal oder nicht, einer Distanz von 1 entspricht.

Algorithmus nach Dijkstra:
=> Der gewählte Pfad hat minimale Länge.
=> Die Berechnung wird nur einmal durchgeführt, danach sind die kürzesten Pfade von jeder Ausgangsposition bekannt und können für beliebig viele Spieler abgerufen werden, ohne dass aufwändige Berechnungen anfallen.

Code:
Routing für: (A: 12,2)
Station: (A: 12,2)
Station: (#: 11,3)
Station: (#: 10,4)
Station: (#: 9,5)
Station: (#: 8,6)
Station: (#: 7,7)
Station: (#: 7,8)
Station: (#: 6,9)
Station: (#: 5,10)
Station: (#: 4,11)
Station: (#: 3,12)
Station: (#: 3,13)
Station: (#: 2,14)
Station: (#: 1,15)
Station: (#: 1,16)
Station: (#: 1,17)
Station: (#: 1,18)
Station: (#: 1,19)
Station: (#: 1,20)
Station: (#: 1,21)
Station: (#: 1,22)
Station: (#: 1,23)
Station: (#: 1,24)
Station: (#: 1,25)
Station: (#: 1,26)
Station: (#: 1,27)
Station: (#: 1,28)
Station: (#: 1,29)
Station: (Z: 1,30)

#====================================+
|##########/\##AAAAAAAAAAAAAAAA######|
|#########/##\A######################|
|###########AA\#######\----------/\/\|
|##########A###\#####################|
|#####/\##A##########################|
|#######\A###()()()()()##############|
|######AA\\#####\\\\\\\##############|
|#####A###\\\########################|
|####A###############################|
|###A################################|
|##A#################################|
|#A##############################B###|
|####################################|
+====================================+

Routing für: (B: 12,33)
Station: (B: 12,33)
Station: (#: 11,32)
Station: (#: 10,31)
Station: (#: 9,30)
Station: (#: 8,29)
Station: (#: 7,28)
Station: (#: 6,27)
Station: (#: 5,26)
Station: (#: 4,25)
Station: (#: 4,24)
Station: (#: 4,23)
Station: (#: 4,22)
Station: (#: 3,21)
Station: (#: 2,22)
Station: (#: 1,23)
Station: (#: 1,24)
Station: (#: 1,25)
Station: (#: 1,26)
Station: (#: 1,27)
Station: (#: 1,28)
Station: (#: 1,29)
Station: (Z: 1,30)

#====================================+
|##########/\##########BBBBBBBB######|
|#########/##\########B##############|
|#############\######B\----------/\/\|
|##############\######BBBB###########|
|#####/\##################B##########|
|#######\####()()()()()####B#########|
|########\\#####\\\\\\\#####B########|
|#########\\\################B#######|
|#############################B######|
|##############################B#####|
|###############################B####|
|#A##############################B###|
|####################################|
+====================================+
 
Das kompiliert bei mir nicht mit Monodevelop...

Naja einen vollständigen Dijkstra braucht man ja nicht, eine leicht modifizierte BFS reicht da. Andererseits habe ich für diagonale Bewegung dann doch die etwas zu große Distanz 2 gewählt. Ich wollte eben nur mit ganzen Zahlen arbeiten.

Geschrieben in Ada, für beste Performance mit gnatmake -O2 -gnatN kompilieren.
Ich bin zuversichtlich, dass das trotz des schlechten Codes ziemlich schnell ist, also her mit einem großen Testfeld. :)

Ich sage "schlechter Code", weil ich damit auch etwas experimentiert habe. Das Einlesen von Strings in Ada ist nicht so schön, ihr seht sicher, was ich meine. :rolleyes:

edit: Achja, das "Spielfeld" muss als field.txt im selben Verzeichnis sein.
 
Zuletzt bearbeitet:
Aha, man muss die node.cs manuell hinzufügen, dann geht es. Soso. :)


mono ./wegfindung.exe > /dev/null 0,27s user 0,01s system 96% cpu 0,291 total

./wegsuche > /dev/null 0,01s user 0,00s system 20% cpu 0,033 total

Ob das an Mono liegt? Ich lese ja auch noch ein und schiebe ein bisschen vom Heap auf den Stack und zurück. :)

Dafür habe ich auch das meiste selbst gemacht und nicht Standard Libs verwendet... Die sind ja bei java oft nicht die schnellsten, vielleicht ist es ja bei mono besser, weiß ich ja nicht.
 
[OFFTOPIC]
mono ./wegfindung.exe > /dev/null 0,27s user 0,01s system 96% cpu 0,291 total

./wegsuche > /dev/null 0,01s user 0,00s system 20% cpu 0,033 total

Ob das an Mono liegt? Ich lese ja auch noch ein und schiebe ein bisschen vom Heap auf den Stack und zurück. :)
Dir ist schon klar, dass du auch die Frameworkstartzeit misst UND dazu noch die Debugversion? ;)

Für einen halbwegs realistischen Vergleich bräuchte man schon ein paar große Karten - und hier kann jeder etwas posten (z.B ein Spielfeld, bei dem gerade sein Programm am schnellsten ist ;) )
 
Also ich habe zumindest von Debug auf Release umgestellt...

Aber der Unterschied scheint nicht so groß zu sein:

Code:
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,29s user 0,02s system 47% cpu 0,663 total
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,20s user 0,02s system 81% cpu 0,280 total
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,21s user 0,01s system 97% cpu 0,227 total
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,21s user 0,00s system 98% cpu 0,209 total
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,24s user 0,01s system 98% cpu 0,253 total
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,19s user 0,02s system 95% cpu 0,219 total
chris@chrispc ...esktop/wegfindung/wegfindung/bin/Debug % cd ..
chris@chrispc ~/Desktop/wegfindung/wegfindung/bin % cd Release
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,22s user 0,01s system 87% cpu 0,263 total
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,21s user 0,01s system 98% cpu 0,227 total
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,19s user 0,01s system 95% cpu 0,205 total
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,20s user 0,02s system 92% cpu 0,238 total
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,20s user 0,02s system 101% cpu 0,211 total
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release % time mono ./wegfindung.exe > /dev/null
mono ./wegfindung.exe > /dev/null  0,25s user 0,01s system 93% cpu 0,274 total
chris@chrispc ...ktop/wegfindung/wegfindung/bin/Release %
 
bleibt noch das problem der framework startzeit...

wenn du halbwegs verwertbare zahlen haben willst, hole dir vor und nach der zu testenden funktion ein datetime objekt und vergleiche ihren tick wert ...

einen wirklichen vorteil durch dijkstra wird man nur sehen, wenn sehr viele spielfiguren zum gleichen ziel pfade brauchen ...

ich hab hier mal ein spielfeld von 69x157 feldern mit 1840 zufällig verteilten spielfiguren getestet

die dijkstra implementation braucht auf meiner kiste gute 40,4 Sec für die karte ...

das finden der 1840 pfade dauerte danach noch ca. 25 ms

###
Nachtrag:
die distanz queue in meiner dijkstra implementation wurde ineffizient sortiert. nachdem die sortierung nun effizient abläuft ändert sich das laufzeitverhalten:

Kartengröße wieder 69x157

Benötigte Zeit:
Einlesen der Spielfeld-Datei: 1ms
Splitten des Spielfeldes: 1ms
Erzeugen der Wegpunkte: 26ms
Finden aller Startpunkte: 13ms
Finden aller Zielpunkte: 2ms
Wegfindung: 697ms
Ausgabe: 633ms
Zeit seit Start: 1372ms

Anzahl der Zielpunkte: 1
Anzahl der Startpunkte: 1827
Anzahl der Pfade: 1827
 
Zuletzt bearbeitet:
Da hatte soxx im IRC schon Recht: Wenn es langsam läuft, ist oft nicht nur die Sprache schuld, sondern auch ungeeignete Datenstrukturen und Algorithmen. :)

Ich habe jetzt eine "endgültige" Version, die das Einlesen etwas besser regelt. Außerdem ist genau ein Argument erlaubt, nämlich der Dateiname des Spielfeldes, bzw. field.txt wird bei keinem Argument genommen.
Dein Spielfeld3 fand ich ziemlich gut, habe ich mal bei mir dazu getan.

Ich habe auch mal eine Version mit einem generischen Min-Heap probiert und dazu getan, der immer die Koordinaten mit dem geringsten Distanzwert zurückgibt.
Die Laufzeitunterschiede scheinen allerdings nicht allzugroß zu sein. Vermutlich lohnt sich einfach nur dieser Overhead bei Distanzwerten von nur 1 und 2 nicht sonderlich. :)
edit: und dass ich den Weg für jede Figur extra berechne, trägt sicher auch nicht zur Geschwindigkeit bei...
Code:
chris@chrispc ~/Desktop/wegsuche/wegsuche_habo % cd wegsuche-heap
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,02s system 85% cpu 0,109 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,03s system 92% cpu 0,108 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,01s system 90% cpu 0,100 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,03s system 90% cpu 0,114 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,05s system 83% cpu 0,136 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,05s user 0,04s system 89% cpu 0,105 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,02s system 90% cpu 0,104 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,04s system 92% cpu 0,115 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,06s user 0,03s system 80% cpu 0,116 total
chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,06s user 0,04s system 90% cpu 0,115 total

chris@chrispc ...p/wegsuche/wegsuche_habo/wegsuche-heap % cd ..
chris@chrispc ~/Desktop/wegsuche/wegsuche_habo % cd wegsuche-queue

chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,01s system 87% cpu 0,103 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,03s system 88% cpu 0,121 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,06s user 0,03s system 97% cpu 0,100 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,02s system 92% cpu 0,115 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,06s user 0,03s system 86% cpu 0,108 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,06s user 0,04s system 88% cpu 0,120 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,04s system 89% cpu 0,127 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,06s user 0,04s system 93% cpu 0,103 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,05s system 85% cpu 0,133 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,09s user 0,01s system 91% cpu 0,113 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,08s user 0,03s system 89% cpu 0,123 total
chris@chrispc .../wegsuche/wegsuche_habo/wegsuche-queue % time ./wegsuche > /dev/null
./wegsuche > /dev/null  0,07s user 0,03s system 88% cpu 0,114 total
 
Zuletzt bearbeitet:
Zurück
Oben