Wegberechnung
-
Hallo Leute,
ich möchte ein Programm erstellen, wo man auf irgendeine Stelle drückt und das Objekt (PictureBox) mit dem schnellsten Weg dort hin geht, falls die Stelle unerreichbar ist, soll sich der Kursor ändern.
Ein Beispiel wäre zum Beispiel eine Grüne Map mit roten Gegenständen. Die Picture Box darf dabei keine Roten Gegenstände/Flecken/Linien berühren!Kennt jemand "Heroes Of Might And Magic 5" http://www.heise.de/software/download/heroes_of_might_and_magic_v/35414 (download Demo) oder bei Google Bilder nachkucken
Dieses möchte ich versuchen nachzuprogrammieren (2D, schlechte Grafik, nur von den Regeln her gleich/ähnlich) zur Übung und um mit C++ richtig benutzen zu können (kann man immer gebrauchen zB.: Navigation)!
Danke schon mal im Vorhin naus!
HUND123
-
Die Lösung ist den Raum in mehrere kleine aufzuteilen und dann immer jeden kleinen Raum zu durchqueren.
Immer so weit voraus wie möglich, nur so weit zurückgehen wie nötig (auch genannt Backtracking).
-
http://s14.directupload.net/images/120112/c9b6a5gf.png
Wenn wir dieses Beispiel nehmen, soll der Computer, wenn wir über den unerreichbaren, bzw. den Roten bereich gehen, das Ibeam ändern (No), wenn wir nun eine Gestimmte Sache machen (Doppenklick aufs Ziel oder Leertaste), (soll er eine Line Zeichnen, die er gehen wird [wenn möglich]) und dann zum Ziel auf schnellstem weg gehen.
Ich hoffe es ist so Verständlicher!
HUND123
-
HUND123 schrieb:
Ich hoffe es ist so Verständlicher!
Schau nach A*.
-
Wie?
-
Du Teilst alles in kleine Kästchen ein (Gitternetz über deine Karte). Wenn ein Kästchen rot enthält, kann dein Männchen nicht weitergehen etc. So musst du dir alles denken.
-
HUND123 schrieb:
Wie?
Sorry. Nach "A*" kann man nicht so einfach googlen.
http://de.wikipedia.org/wiki/A-Stern-Algorithmus
-
Ich habe schon etwas gegoogelt, aber immer werde ich vom Text "erschlagen", es wäre sehr nett, wenn ihr mir ein Code dafür geben könntet, diese Kilometer Lange Seiten, auf denen es kein konkretes Beispiel gibt, gibt mir nicht viel, nur dass ich Theoretisch weis, wie so etwas ungefähr funktioniert...
Nochmal zum Beispiel:
-rot = der Gegenstand
-grün = der Raum, auf dem bewegt werden kannSchön wäre, eine Line zu Malen, wie man zum Ziel kommen will, und beim zweiten Klicken, bzw. Leertaste drücken, die PictureBox die Line verfolgt.
-
Das liegt daran, dass man nur dann ein konkretes Beispiel geben kann, wenn man auch ein konkretes Einsatzgebiet hat.
Ich nehme einfach mal an, dass du deine Karte als eine Tilemap verwaltest. Such doch bei Google einfach mal nach "Tilemap path finding".
Das Prinzip ist eigentlich sehr einfach und gut programmierbar.
-
"Mal eben Code geben..." auf sowas reagiert man hier eher mit Belustigung. Dieses Forum dient dazu, Hilfe bei konkreten Problemen zu geben, vollständigen Code wirst du wohl nicht bekommen.
Als Alternative kannst du das im Unterforum "Projekte" einstellen, vielleicht findest du jemanden, der das (ggf. gegen Bezahlung) macht.
-
Okey, Danke an alle,
also muss ich mich nun wirklich zehntausent seiten durchlesen, um mir einen einigermaßen funktionierenden Code zu machen
Schade, aber egal, versuche ich mal ...
-
volkard schrieb:
HUND123 schrieb:
Wie?
Sorry. Nach "A*" kann man nicht so einfach googlen.
http://de.wikipedia.org/wiki/A-Stern-AlgorithmusGibt es den A* Algorithmus nicht schon in Boost? Da ich mit der Bibliothek keine Erfahrung hab, weiß ich es nicht, aber es schwebt bei mir im Hinterkopf das mal gehört zu haben.
-
Fang hält erstmal mit Dijkstra an (noch etwas einfacher) so umwerfend ist der Speedup von A* für die meisten Instanzen auch nicht...
-
EIn Vorredner meinte mit A* den A-Stern Algorithmus.
http://de.wikipedia.org/wiki/A*-AlgorithmusEs gibt so viele Algorithmen die funktionieren würden, aber der A* ist für Karten wo eher weniger "rote" Objekte sind besser als die anderen Gängigen, weil er als Heuristik die Richtung benutzt, wenn ich mich recht erinnern kann. Also du weißt ja wie die Karte aussieht und wo die Punkte sind. Würdest du einen Algorithmus für ein Labyrinth, also viele rote Blöcke, brauchen, ist ein rekursiver Alg mit Rollback besser, weil du nicht sehr viele Verzweigungen hast. Bei einer Karte hast du theoretisch 3 oder wenn diagonal möglich ist sogar 7 Verzweigungen.
Wir haben mal in der Schule für ein Smartphone eine Wegsuche gebraucht auf Android und Java. Wir haben beim Mapladen sogar schon alle möglichen Wege vorgespeichert, braucht zwar etwas Speicher, aber beim zocken hat die Funktion mit den zwei Punkten als parameter die Ergebnisse in konstanter Laufzeit ausgegeben.
-
Dieser Thread wurde von Moderator/in Marc++us aus dem Forum C++ (auch C++0x, bzw. C++11) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
seux schrieb:
Gibt es den A* Algorithmus nicht schon in Boost?
Doch, als Bestandteil von Boost.Graph.
