search

Smeagle / dungeongame

Inspired by "Spar Wars"
2 stars 1 forks source link

Algorithmus: Wegfindung #6

Closed Smeagle closed 8 years ago

Smeagle commented 8 years ago

Eingabe: ein Startfeld, eine Blickrichtung und ein Zielfeld Gesucht: ein Feld, das an das Startfeld angrenzt und der nächste Schritt auf dem kürzesten Weg zum Zielfeld ist. Gibt es mehrere solche Felder, dann entscheidet die Blickrichtung: das Feld gewinnt, welches weniger Drehung erfordert, um sich zu dem Feld auszurichten). Falls es immer noch mehrere solche Felder gibt, soll zufällig entschieden werden (Fällt euch noch eine deterministische Möglichkeit ein?).

Wozu: Ein Gegner bewegt sich auf eine Spielfigur oder auf einen Wegpunkt (Patrolie) zu. Oder der Spieler klickt auf ein nicht angrenzendes Feld, um sich dahin zu bewegen etc.

murchandamus commented 8 years ago

Würde einfach eine A*-Suche implementieren. Heuristik fürs Expandieren min(Schritte von Ausgangsfeld + Distanz zu Zielfeld).

Man könnte den Wachen einen Links- oder Rechtsdrall geben, so dass sie sich immer deterministisch drehen.

Smeagle commented 8 years ago

Das klingt gut. Ja, dann lassen wir sie im uhrzeigersinn drehen, falls es keine kürzeste Drehung gibt (falls es das überhaupt gibt...).

murchandamus commented 8 years ago

Pathfinding wurde implementiert: https://github.com/Smeagle/dungeongame/pull/8

murchandamus commented 8 years ago

Kann vermutlich geschlossen werden.