Algorithmus gesucht

[gufi]

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

 

[sheel]

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?

 

[gufi]

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).

 

[sheel]

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

 

[gufi]

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.

 

[Shakie]

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 ;-)

 

[gufi]

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

Jap, der See ist 1 Feld groß

 

[tombe]

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

http://www.o-bizz.de/qbtuts/ai-tuts/pathfind/html/pathfinding.htm

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

http://en.giswiki.net/wiki/Dijkstras_algorithm

 

[sheel]

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?

 

[gufi]

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.