Aloha,

Ein kleines Strategiespiel hätte gerne Wegfindung für Einheiten. Dazu habe ich, da es sich prima auf den bereits existierenden Datenstrukturen machen lässt und ich keinen Graphen extra bauen muss, eine Breitensuche implementiert. Im Grunde mache ich also so etwas wie FloodFill und gucke nach, ob ich das Ziel erreiche. Dann existiert ein Weg, den man nur noch abschreiten muss.

Das ganze spielt sich auf HexTiles ab, und auf jedem Tile kann nur genau eine Einheit stehen. Und da nur Geister durch Wände gehen können, muss der Weg um Einheiten, die im Weg stehen, drumrumgeführt werden.

Das führt dazu, dass man z.B. Landengen einfach blockieren kann: Einheiten hinstellen, und schon existiert kein weg mehr. Wie das gedacht ist, sieht man hier:


Jetzt nehmen wir mal an, auf der Landenge eine Einheit. Dann müsste man ja eigentlich so weit gehen, wie geht, und dann da stehen bleiben. Hier mal ein Bild, wie es aussehen sollte.


Das geht aber nicht. Da das Zielfeld nicht erreichbar ist, wird kein Weg gefunden, und nix bewegt sich.

Das kann man sogar taktisch ausnutzen, um rauszubekommen, ob z.B. der Gegner da steht. Bewegt sich die Einheit, ist er nicht da. Bewegt sie sich, ist niemand im Weg.


Irgendwie müsste man also einen Weg ausrechnen, der bis vor das Hindernis geht. Und ich habe keine Ahnung wie man das machen kann, so dass aber trotzdem Einheiten, die man umgehen kann, auch umgangen werden.

Hat jemand kreative Ideen? Knoble da jetzt schon ein paar Tage dran, leider erfolglos... Ist bestimmt ein Fall von Betriebsblindheit.

Danke,
Martok

Erweiter den Suchradius pro Feld doch ein wenig.
Also nehmen wir an du willst wo lang, wo etwas steht, dann schaust du dir ja die Felder drum rum an, und guckst obs da weiter geht, wenn nicht fängst du bei nem anderen benachbarten Feld an, welches mit dem Feld verknüpft ist wo du grad stehst.
Das machst du so lange bis du nix findest oder kürzt das auf 3 Felder oder so.
Ich hoffe du verstehst was ich mein wenn nicht muss ich das vllt ein wenig Illustrieren. Ich bin nicht so toll beim erklären.

Doof gefragt: Kannst du das nicht einmal ohne und einmal mit Einheiten im Weg durchrechnen und dann die Ergebnisse vergleichen?

Du könntest probieren, den unterschiedlichen Feldern unterschiedliche Gewichte zu geben. Ein freies Feld hätte z.B. den Wert 1, ein Hindernis den Wert von z.B. 10. Dann gibt es immer einen Weg, und wenn einen Weg ohne Hindernisse gibt, der nicht viel weiter ist, wird der genommen. Und beim laufen stoppt man dann an einem Hindernis.

Man müsste dann ggf. die Breitensuche natürlich anpassen und mit Priority-Queues arbeiten, nicht mit der normalen FiFo.

jakobwenzel hat folgendes geschrieben :

Doof gefragt: Kannst du das nicht einmal ohne und einmal mit Einheiten im Weg durchrechnen und dann die Ergebnisse vergleichen?

Hatte ich mir auch überlegt, aber wenn die zwei vollkommen unterschiedliche Routen liefern, wird das mit dem Vergleichen schwierig .

@Martok: Geht es denn um einen "traditionellen" Fog of War? Dann würde ich sagen: Bis zur Grenze des Nebels den Einheiten ausweichen, danach dem Gelände bis zum Ziel oder dem ersten Feindkontakt folgen. Also wirklich nur die Informationen nutzen, die der Einheit zur Verfügung stehen.

Kha hat folgendes geschrieben :

jakobwenzel hat folgendes geschrieben : Doof gefragt: Kannst du das nicht einmal ohne und einmal mit Einheiten im Weg durchrechnen und dann die Ergebnisse vergleichen? Hatte ich mir auch überlegt, aber wenn die zwei vollkommen unterschiedliche Routen liefern, wird das mit dem Vergleichen schwierig .

Genau das dachte ich mir auch schon, und bin auch zu dem Schluss gekommen (muss am Namen liegen ), dass das knallen kann, wenn die eben ganz woanders lang führen.

Kha hat folgendes geschrieben :

@Martok: Geht es denn um einen "traditionellen" Fog of War? Dann würde ich sagen: Bis zur Grenze des Nebels den Einheiten ausweichen, danach dem Gelände bis zum Ziel oder dem ersten Feindkontakt folgen. Also wirklich nur die Informationen nutzen, die der Einheit zur Verfügung stehen.

So hab ich das noch gar nicht gesehen. Das würde das Problem sehr elegant umgehen und gleichzeitig realistischer erscheinen. Nur Einheiten beachten, die man auch sehen kann. Das hat was.

Mal ausprobieren und sehen wie sich das spielt.

Also, funktioniert wie gedacht. Problem ist nur, dass das etwas seltsam aussieht, wenn meine eigenen Einheiten so einen Weg zurücklegen. Dann könnte man das fast als Synchronisierungsverfahren nehmen, weil erstmal alle Stehen bleiben, während einer auf dem Weg durch ist und dementsprechend kein Weg existiert.

Ich denke, das schreit nach nicht immer neuberechneten, sondern nur nach wirklichen Mapänderungen angepassten Wegen, die dabei nur im unmittelbaren Umfeld blockierende Einheiten beachten. Also so eine Art "harte" und "weiche" Blocker.

Mal testen, wenn Zeit ist