Hallo Leute,

folgendes Problem liegt mir vor und ich hoff ihr wisst ne Lösung drauf (und ich hoff ich erklär das jetzt verstädnlich )


Und zwar:

Gemacht wird das alles in C#, ist aber denk ich Sprachen unabhängig.

Ich hab ein Spielfeld, desen größe ich nicht weis (bekomm ich erst kurz vor Spielbeginn vom Server übermittelt). Auf diesem Spielfeld liegt irgendwo ein Item das ich mit einem Maxerl finden muss und zu einem bestimmten Punkt bringen muss (bei dem ich auch nicht weis wo er sein wird).

Das Maxerl kann immer nur ein Feld gehen, danach ist der andere Spieler drann.
Das Maxerl kann auch min. sein Nachbarfeld sehen (sprich alle 8 die rundherum sind), je nach Feld gegebenheit kann er auch auch 2 Felder weit sehen.
Wenn man an den Rand kommt, kommt man auf der anderen seite wieder raus.

Jetzt meine Frage:
Ich brauch einen Algorithmus und irgendeine Taktik, um dieses Feld möglichst schnell nach diesem Item zu durchsuchen, und danach möglichst schnell den Punkt zu finden, zu dem ich dieses Item bringen muss.

Weis einer was?

Wäre für jeden Tipp dankbar

Also das "Maxerl" soll möglichst schnell zum Item kommen, am besten vor dem anderen (menschlichen?) Spieler?

Laut deiner Beschreibung vermute ich, das Spielfeld ist in x mal y Quadrate eingeteilt, und bei jedem Schritt wechselt das Maxerl zu einem benachabrten; links rechts oben unten, aber nicht schräg. Ist das korrekt?

Gibts auf deinem Spielfeld auch Hindernisse/Mauern etc oder kann man sich überall frei bewegen?

Und wann kann man 1, wann 2 Felder weiter?

Also das "Maxerl" soll möglichst schnell zum Item kommen, am besten vor dem anderen (menschlichen?) Spieler?

Richtig. Aber dieses Spiel wird nicht menschlich gesteuert. Es soll vollkommen alleine Ablaufen.

Laut deiner Beschreibung vermute ich, das Spielfeld ist in x mal y Quadrate eingeteilt, und bei jedem Schritt wechselt das Maxerl zu einem benachabrten; links rechts oben unten, aber nicht schräg. Ist das korrekt?

Genau so ist es.

Gibts auf deinem Spielfeld auch Hindernisse/Mauern etc oder kann man sich überall frei bewegen?

Hab ich ganz vergessen. Ja es gibt Hindernisse: 1) einen See (da kann das "Maxerl" nicht durch sondern muss rund herum) .... 2) einen Berg. Auf diesen kann man hinauf, jedoch bedarf es dafür 2 Züge fürs hinauf gehen und 1 Zug fürs hinunter gehen.

Und wann kann man 1, wann 2 Felder weiter?

Man kann immer nur 1 Feld weiter GEHEN. Jedoch kann der das Maxerl das benachbarte Feld (links, rechts, vorn, hinten) sehen (ob was drauf ist) bei gewissen Feldern kann er auch 2 Felder weit sehen (also 2 links , 2 rechts, 2 vorn und 2 hinten).

Ahaa, jetzt wirds klarer.

Es geht also nicht darum, nur einen möglichst kurzen Weg zum Schon bekannten Item zu ermitteln, sondern die Itemposition muss auch erst gefunden werden?

In dem Fall musst du wohl alles durchlaufen.

Zum Beispiel links unten beginnend immer nach oben, wenn er oben rauskommt kommt er ja unten wieder rein und geht bei jedem Nach-unten-wechseln weiter nach rechts.
Man kann natürlich auch in der Mitte beginnen, muss halt wissen wo man angefangen hat; damit man da auch wieder aufhört.

Generell muss wegen der Einser-Sichtbarkeit nur jede dritte Spalte durchlaufen werden, da er ja eine links bzw. rechts sehen kann.
Spart schonmal viel.

Wenn er beim See anstösst wäre eine Möglichkeit ebendrei weiter nach rechts, umdrehen und von da an das Ganze nach unten weiter.
Wenn er am See nach rechts ist, darf er allerdings beim nächsten Rand-Oben-Unten-Wechsel nicht nach rechts,.

Die Zweiersicht-Felder, sind die einzeln verstreut oder gehäuft?
Wenn einzeln, bringen sie dir bei der Methode nicht viel.

Und für den Berg überleg ich noch...
Kann das Item auch am Berg oben sein?
Ist der Berg nur ein Feld oder hat der auch eine Ausdehnung?
Gibts eine Normal-Fläche oben oder muss man bis zu einer Spitze immer Bergsteigen (mit den Doppelschritten)?

Ich mach vllt. eine Skizze, dauert allerdings noch bis ich dazu komme.
edit: Dann wart ich doch lieber auf deinen Screenshot

Es geht also nicht darum, nur einen möglichst kurzen Weg zum Schon bekannten Item zu ermitteln, sondern die Itemposition muss auch erst gefunden werden?

richtig! und wenn ich das Item gefunden hab, dann muss ich es zu einem bestimmten Punkt bringen, den muss ich aber auch suchen. bzw. wenn ich ihn beim Item suchen sehe dann wird das auch gespeicher und ich kann gleich danach darauf zusteuern.

Die Zweiersicht-Felder, sind die einzeln verstreut oder gehäuft?

Das kommt auf den Server an der das Feld erstellt. Es kann alles so sein das man 2 Felder weit sieht, es kann vereinzelt sein oder es kann so sein das man nur 1 Feld weit sieht.

Kann das Item auch am Berg oben sein?

Nein.

Ist der Berg nur ein Feld oder hat der auch eine Ausdehnung?

Steht nur auf einem Feld. Es gibt da auch gewissen regeln, das nicht 2 Bergen nebeneinander stehen dürfen usw. aber die sind jetzt nicht relevant und zu lange um sie aufzulisten

Gibts eine Normal-Fläche oben oder muss man bis zu einer Spitze immer Bergsteigen (mit den Doppelschritten)?

Man muss ganz hinauf und kann nicht umdrehen.

-------
Ich hab ja auch schonmal darüber nachgedacht: Ist es vl. auch ne schnell möglichkeit das ganze in einem "Z" zu durchlaufen? Dann hätt ich ja schon mal einiges abgedeckt und nur mehr 2 "Punkte" die ich durchsuchen muss.

Was mir noch eingefallen ist: Meinen Startpunkt kann ich Festlegen (der ist dann immer dort) jedoch nur auf der X-Achse, d.h. wenn ich den Startpunkt rechts unten wähle dann kanns auch sein das der server sagt ich bin oben und der Gegner unten, dann is mein startpunkt rechts oben.

Danke schonmal im vorraus

ps: ich werd versuchen nen screenshot aufzutreiben, dann kann man sich das glaub ich besser vorstellen, kann aber leider noch etwas dauern.

Sind die Seen auch wie die Berge immer genau ein Feld groß?
Ob du diagonal gehst oder nicht ist egal. Wenn du einmal nach rechts gehst und dann z.B. nach unten, dann deckst du genau 6 vorher unbekannte Felder auf. Wenn du zwei Mal nach rechts gehst deckst du auch genau 6 vorher unbekannte Felder auf.
Allerdings würde ich Kurven in deinem Weg meiden. Denn wenn du in einem Z läufst, dann erzeugst du Felder die "teuer" sind um sie aufzudecken: im nächsten Durchlauf müsstest du in die Ecken vom Z hineinlaufen und brauchst dann zwei Züge um nur ein einziges unbekanntes Feld aufzudecken (einen Zug um zum Feld hinzulaufen und eines um wieder zurückzugehen). Diese Behauptung solltest du aber noch mal überprüfen - ich habe mir das nur im Kopf vorgestellt, da kann leicht ein Denkfehler auftreten

Sind die Seen auch wie die Berge immer genau ein Feld groß?

Jap, der See ist 1 Feld groß

Vielleicht findest du hier ja ein paar Ideen wie es zu lösen ist:

http://www.o-bizz.de/qbtuts/ai-tuts/...athfinding.htm

http://www.policyalmanac.org/games/aStarTutorial.htm

http://en.giswiki.net/wiki/Dijkstra's_algorithm

Berge und Seen sind also immer nur ein Feld groß. Gut, erleichert einiges.

Sind Berge/Seen schon von Anfang an bekannt oder müssen die auch erst während dem Herumgehen erkannt werden?

Und die 2-Sicht-Felder, bekannt/durch sehen findbar/erst beim draufstehen erkennbar?

von dem spielfeld weis ich garnichts, außer die größe und die hol ich mir kurz vor beginn.

die 2 sicht felder seh ich bzw. weis ich erst beim draufstehen.

aStar A* ist der wohl passende Algorithmus.

http://de.wikipedia.org/wiki/A*-Algorithmus

mfg chmee

Ich kannte A* zwar nicht, aber Wiki sagt:

Der A*-Algorithmus findet allgemein einen optimalen Pfad zwischen zwei Knoten in einem Graphen.

Ich verstehe nicht wie A* für die Schatzsuche behilflich sein sollte. Schließlich ist der Zielknoten nicht bekannt!?

Zitat von chmee

aStar A* ist der wohl passende Algorithmus.

Tiefen- und Breitensuche funktioniert hier nicht da die Karte unbekannt ist.
Der A* Algorithmus funktioniert leider erst recht nicht da das Ziel unbekannt ist.
Es gibt also keine Heuristik mit der man einen optimalen weg bestimmen kann.

Es bleibt dir also nichts anderes übrig als die gesammte Karte abzulaufen.
Da du jedoch über den Rand laufen kannst ist das jedoch relativ einfach.

- Laufe solange nach Links bis du wieder zu deiner Ausgangspositon gelangst.
- Gehe zwei Felder nach unten und definiere die aktuelle Position als Ausgangspunkt.
- Beginne wieder von vorne.

Kommt während dieses Ablaufs das Item in deinen Sichtbereich musst du
natürlich unterbrechen und darauf zulaufen. Merke dir bei dem Vorgang alle
Felder. Bist du bei deiner Suche nach dem Item auf das Zielfeld gestoßen zu
dem du das Item später bringen musst, dann kannst du anschließend den
A* Algorithmus anwenden um den kürzesten weg zu finden.

Sorry, ich hab dann zu schnell überfolgen und nicht gelesen, dass Punkt B nicht bekannt ist, sondern erst gesucht werden muß. Folgend: Wenn Du auf der Karte losgehst, erscheinen also mehr Felder als nur das betretene..

Die eben genannte Idee scheitert an Löchern zwischen zwei Hindernissen. Und man sieht an einer Zeichnung, dass es in der Vertikalen auch mehr Schritte sein dürfen..

Letztlich muß ein Alg.s gefunden werden, der die Welt vollständig absucht - da würd ich erstmal definieren, dass es freie und unfreie Felder gibt. Unter den unfreien Feldern gibt es welche, die nicht passierbar sind und jene, die etwas bringen (sprich: Schatz). Da sollte sich etwas in der Robotik finden (zB Bug-Alogrithmus?).

Auch wenn folgende Links nicht immer direkt mit diesem Problem zu tun haben,
pack ich sie mal hier rein:
http://www.phpgangsta.de/algorithmus...-shortest-path
http://www.o-bizz.de/qbtuts/ai-tuts/...athfinding.pdf

Diese beiden PDFs klingen vielversprechend:
http://www.brichzin.de/seminarfach/SA07_Pfadsuche.pdf
http://page.mi.fu-berlin.de/alt/vorl...ien-hempel.pdf

mfg chmee

Hei

danke für euere Antworten. Ich werd die Woche den Algo. mal einbaun und am 25.1. weis ich dann wies ausgegangen is! Geb euch natürlich bescheid

Sollte noch wer andere Vorschläge haben, werd ich auch diese gerne ausprobieren.

lg