Wie lässt sich Auto-Aim implementieren?

[Kelven]

In den meisten Maker-Actionspielen ist es ja so, dass man nur in alle vier Himmelsrichtungen schießen kann. Doch vielleicht ist es besser oder interessanter, wenn der Spieler den Gegner automatisch anvisiert und immer trifft, falls kein Hindernis im Weg ist. Aber wie stellt man überhaupt fest, dass ein Hindernis zwischen zwei Figuren liegt?

Der Einfachheit halber würde ich die Hindernisse über die Terrain-ID festlegen. Man kann ja afaik das gesamte Spielfeld durchgehen und testen, welche Terrain-ID das Tile hat. Den ganzen Rand kann man außer Acht lassen, also dürfte die Menge der Hindernisse nicht so groß werden. Auf jeden Fall sollten die Hindernisse Rechtecke sein.

Nun hab ich so gut wie alle Mathematik schon wieder vergessen, aber eines meine ich noch zu wissen: Zwischen Held und Gegner liegt eine Strecke. Man wird sicher über das Verhältnis zwischen ihren beiden Endpunkten und den vier Eckpunkten des Rechtecks bestimmen können, ob die Strecke das Rechteck schneidet. Kennt sich jemand damit aus? Gibt es dafür vielleicht sogar schon ein Script? (Wobei ich das notfalls auch selbst schreiben könnte, wenn ich das System verstehen würde).

[-KD-]

Hm, bin mir nicht sicher ob ich dich richtig verstehe. Der Held zielt auf den Gegner. Die Schussbahn ist eine Gerade vom Helden zum Gegner, die eine Reihe von Tiles schneidet. Ist eines der Tiles ein Hinderniss, kann der Charakter den Gegner nicht treffen.
Die Schussbahn kann man ja folgendermaßen beschreiben:
(tx, ty) = (sx, sy) + (x, y)
tx/ty sind Zielkoordinaten, sx/sy sind Startkoordinaten, s/y ist die Richtung

Für ein gegebenes dx kann man jetzt nach einem dy suchen für das (dx,dy) von der Gerade geschnitten wird:
dx = sx+ x*a
a = (dx-sx)/x
dy = sy + y*a

Das kann man analog auch mit dy als Parameter und dx als gesuchte Variable machen.

So kannst du alle Tiles iterieren die von der Geraden geschnitten werden.

Mal als Beispielalgorithmus:

Code:

def cut_tiles sx, sy, tx, ty
  sx, tx = [sx, tx].sort
  sy, ty = [sy, ty].sort
  x = (tx-sx).to_f
  y = (ty-sy).to_f
  if x > y
    (sx..tx).each {|dx|
      a = (dx - sx)/x
      dy = (sy + a*y).to_i
      yield(dx, dy)
    }
  else
    (sy..ty).each {|dy|
      a = (dy - sy)/y
      dx = (sx + a*x).to_i
      yield(dx, dy)
    }
  end
end

def hinderniss? sx, sy, tx, ty
  cut_tiles(sx, sy, tx, ty) do |x, y|
    if terrain_id(x, y) == hinderniss_id
      return false
    end
  end
  true
end

[Kelven]

Schon mal Danke, aber ich hab immer große Schwierigkeiten diese komprimierte Schreibweise zu verstehen. Wie funktioniert die Methode hinderniss denn genau? Mir wird nicht ganz klar wie cut_tiles an die Koordinaten der zu prüfenden Tiles kommt. Und was ist denn terrain_id? Bei diesem Block bin ich mir auch nicht ganz sicher:

Code:

if terrain_id(x, y) == hinderniss_id
   return false
end

Wird die Methode mit false beendet, wenn die Terrain-ID gleich der Hindernis-ID ist? Das ist ja eigentlich das Gegenteil von dem was der Name der Methode assoziiert.

[Grandy]

Hallo Kelven, ist zwar nicht für RGSS - aber ich habe ein entsprechendes System mal für den 2k entwickelt. Praktischerweise veröffentliche ich gerade sowieso meinen Datenmüll: >> Guckst du hier <<. Ich kann es zwar gerade nicht überprüfen, aber wenn ich es nicht wegrationalisiert habe, werden auch Events auf der Strecke abgefragt. Das brauchst du ohnehin, schließlich gibt es auch lebende Hindernisse, die gefälligst erschossen werden sollen, wenn sie im Weg stehen.

Vielleicht kannst du ein paar Elemente ja als Inspiration gebrauchen.

[Kelven]

Danke für den Hinweis. Weißt du denn noch ungefähr wie du das umgesetzt hast? Ich hab mir den Eventcode mal angeschaut, aber da blicke ich nicht wirklich durch.

Ganz vergessen, @-KD-, ich frage bei deinem Beispiel übrigens vor allem deswegen nach, weil ich bisher nicht weiß wie ich es einbauen soll. Mir kommt das zumindest so vor, als würde da noch etwas fehlen. Ich selbst würde das so machen: Ich würde alle Felder der Map durchlaufen, testen ob das Feld die Terrain-ID des Hindernisses hat und dann schauen, ob die Strecke zwischen Spieler und Ziel das Hindernis schneidet. Wahrscheinlich sollte man dabei wohl auch nicht mit den Tile-Koordinaten arbeiten, denn mit denen lässt sich ja kein Rechteck beschreiben. Ich hab gelesen, dass das Problem bei achsenparallelen Rechtecken gar nicht so kompliziert sein soll, doch einen Algorithmus hab ich trotzdem noch nicht gefunden.

Falls noch nicht ganz klar ist was ich eigentlich will: Es soll geprüft werden, ob zwischen Spieler und einem anderen Event Hindernisse liegen. Im Prinzip das was Grandy in seinem Projekt umgesetzt hat.

[DNKpp]

du musst doch nichmal alle felder auf der map abfragen, es reicht ja, wenn du das rechteck zwischen

startpunkt x

und
endpunkt y

durchläufst.

wäre also dein startpunkt 3/1 und dein endpunkt 5/3
sähe das ja wie folgt aus:

Code:

  1 2 3 4 5 6
1 x x o o o x
2 x x o o o x
3 x x o o o x
4 x x x x x x

x wird nicht geprüft, o wird geprüft.

und jetzt ist es eigentlich eine reine mittelstufen aufgabe, zu berechnen, ob ein quadrat geschnitten wird, oder nicht.

jede strecke hat eine steigung, in dem fall 1/1 bzw in pixel dann 16/16.
diese steigung findest du heraus und rechnest sie eben auf die tiles runter (bei 24/8 z.b. wärst du dann bei 16/5,33 (die kleinere zahl durch die größere * 16, die größere wird automatisch 16). dann kannst du einfach immer einmal die steigung drauf rechnen und testen ob das tile passierbar ist oder nicht.

EDIT: und da dein geschoss ja sicherlich auch eine gewisse größe hat, musst du eben in einer schleife dann noch die horizontale/vertikale in eben der größe des objects berechnen.
sähe in pseudo code dann vll so aus:

Code:

int XStart, YStart;
int XEnde, YEnde;
float XSteigung, ySteigung;
int XGeschoss, YGeschoss;
if (XSteigung >= YSteigung)
{
   YSteigung = YSteigung / XSteigung * 16;
}
else
{
  entsprechend dann für den anderen fall
}

bool canMove = true;
int curX = XStart, curY = YStart;
while (canMove)
{
   for (für die geschossbreite und höhe in die richtungen wiederholen)
       canMove = CheckMapTile(curX, curY);

   curX += XSteigung;
   curY += YSteigung;
}

natürlich nicht komplett ausformuliert, wie es sein muss, aber sollte zur verdeutlichung reichen, was ich meine.

[Grandy]

Danke für den Hinweis. Weißt du denn noch ungefähr wie du das umgesetzt hast? Ich hab mir den Eventcode mal angeschaut, aber da blicke ich nicht wirklich durch.

...

Ich habe jetzt zwar erfolgreich den alten Maker installieren können, musss jetzt aber kurzfristig weg. Soweit ich weiß wird quasi eine Linie zwischen den Events gezogen, im nächsten Schritt wird auf das Map-Koordinaten-System runtergerechnet und dann festgestellt, durch welche Koordinaten die Linie läuft. Anschließend werden die entsprechenden Felder auf Terrain ID und eventeull darauf befindliche Events geprüft. Wenn ein Event vorhanden ist, wird es "gecallt". Die Basisfunktionen beginnen ab Common Event 31, welches dann wieder andere Events aufruft. Jetzt muss ich aber weg *hetz*

[-KD-]

Der Teil mit hinderniss? (was eigentlich passable? heißen müsste, wie du selbst festgestellt hast) ist nur Pseudocode. Da ich nicht weiß welchen Maker du verwendest, konnt ich auch nicht genau wissen wie die Terrain-ID abgefragt wird.

Das Prinzip des Algorithmus ist eigentlich, alle Tiles zu berechnen die die Linie schneiden. Da ist aber noch ein Denkfehler drin. Zum einen ist die Frage wo man die Linie ansetzt (ob im oberen linken Punkt des Tiles oder in der Mitte des Tiles), zum anderen überspringt der Algorithmus unter Umständen Tiles, die nur an der Ecke angeschnitten werden.
Die Methode von anti-freak ist da exakter, hat aber den Nachteil dass sie jeden Pixel prüfen muss (was aber eigentlich egal ist. So viel performance kostet der Algorithmus nicht).

Ich hab nur momentan einfach keine Zeit mich damit zu befassen, sry ^^°

[DNKpp]

wieso jeden pixel?
hab das ganze ja extra so versucht zu erklären, das man mit den schnittpunkten der tiles rechnen kann. also das die einze steigung auf 16pixel hoch gerechnet wird, und die andere dann dementsprechend angepasst wird. demnach musst du eigentlich nur die tiles berechnen, die wirklich betroffen sind.

[Kelven]

@-KD-
Kein Problem, ich würde es wenn dann nur mit dem XP umsetzen. Neuere Maker hab ich nicht und auf den alten wäre mir das zu doof.

@anti-freak
Ich beherrsche gerade noch so die Grundschulmathematik. xD Ich verstehe grundsätzlich worauf du hinaus willst. Die Steigung bekommt man durch (y2 - y1) / (x2 - x1), oder? Zumindest sagt das Internet das. Nicht ganz klar ist mir, warum man die kleinere Steigung durch die größere teilen muss. Und gehst du bei der Multiplikation mit 16 von den alten Makern aus oder soll damit quasi die Mitte der Tiles getroffen werden? (Beim XP sind die Tiles 32x32 Pixel groß). Die Geschosse wären übrigens unsichtbar, also kann man von einer Größe von einem Pixel ausgehen.

[Grandy]

Ich bin noch mal über die Verfahrensweise drübergegangen, die ich damals angewendet habe, und verstehe selbst nur noch die Hälfte (Hey, das Ding ist sieben, acht Jahre alt) - streckenweise ist es aber auch übertrieben umständlich gehandhabt, was auch daran liegt, dass es eine abgespeckte Version des London-Gothic-Systems ist, das viel mehr Parameter berücksichtigen musste (Entfernung, Körperhaltung, Rückstoß, Zieldauer - hier ein kleiner Gruß an real troll, der daraus in der Allreise ein Lotteriespiel gemacht hat; im Spiel war die sich verändernde Trefferchance ein Zeichen dafür, dass man länger auf den Gegner "anlegt".)
Ein paar Gedanken, die ich mir damals gemacht habe, könnten dir vielleicht etwas Arbeit ersparen:

1. Eine hundertprozentig exakte Berechnung ist m.E. unnötig, da der Spieler die Umgebung aufgrund des "unsichtbaren Projektilsl" und der Pseudo Perspektive des Makers ohnehin anders auffasst, als es realistisch wäre - es sei denn, du planst eine Perspektive direkt von oben ein (was ich übrigens für eine nette Abwechslung hielte - in dem alten DOS-Spiel Dreamweb hats das auch ganz gut funktioniert... und es spart Zeit).
2. Bedenke die bei der Trefferabfrage, dass der Gegner, de am nächsten steht, auch als erstes getroffen wird.
3. Eine Zimmerpalme, die im Weg steht, *kann* ein Hindernis darstellen, muss es aber nicht.
4. Noch was zur hundertprozentig genauen Berechnung - nicht jeder Schuss muss automatisch ein Treffer sein - Ungenauigkeiten bei der Trefferberechnung könnten theoretisch (also aus der Sicht des Spielers) auch darauf zurückzuführen sein, dass der Charakter halt nicht immer 100% trifft - damit hast du ein Feature, ohne dir Arbeit damit machen zu müssen. Angesichts der Tatsache, dass sich die Gegner in einem Action-KS die ganze Zeit bewegen, ist eine genaue Überprüfung, ob du nur geschludert hast, ohnehin kaum möglich.

Btw: Ich habe auch noch ein Spiel in der Pipeline, bei der ein entsprechendes Kampfsystem eingesetzt wird, bin aber noch nicht an dem Punkt angekommen, an dem ich mich damit auseinandersetzen müsste.

[DNKpp]

stimmt, wäre ja die tilegröße der alten maker.

und sehe grade ich habe da einen kleinen denkfehler drin, werd ich mir heute abend dann nochmal anschauen, und berichtigen, aber mit der steigung an sich müsstest du das genauste ergebnis hinbekommen, nur eben noch an die gegebenheiten des makers anpassen.

[Kelven]

@Grandy
Ja, ich hab mich auch schon gefragt, ob es überhaupt nötig ist ganz exakt zu sein. Vielleicht reicht es auch, wenn man gar nicht mit Pixeln, sondern nur mit den Tiles rechnet. Und zwar so:

- man startet entweder mit dem Tile des Spielers oder des Zieles
- dann addiert man die x- und y-Steigung in Tiles, aber nicht auf einen Schlag, sondern man legt quasi eine Bewegungsliste an. Eine Steigung von 3/1 wird z. B. zu [x+1, x+1, x+1, y+1]. Nach jedem Schritt testet man, ob dort ein Hindernis ist oder das Ziel erreicht wurde. Ich hab hier jetzt immer nur +1 geschrieben, aber je nach Lage müsste man natürlich gegebenenfalls subtrahieren.

Keine Ahnung, ob das wirklich funktioniert und wie genau das ist, aber so müsste es sich relativ leicht umsetzen lassen.

[DNKpp]

also aus meiner erfahrung kann ich sagen, das es wesentlich mehr sinn macht, genau zu berechnen, und ne ungenauigkeit per parameter angeben zu lassen, wie schon ungenau zu programmieren. eine kugel fliegt nicht um ecken, und das sollte sie auch nicht in einem game (meine meinung zumindest), deswegen sollte die gerade schon recht exakt berechnet werden, wie weit man dann aber in der berechnung vom eigentlichen zielpunkt abweicht, ist dann eine andere sache.

[Todu]

Kelven: Ich hab mir zwar noch nicht die Zeit genommen, mir das genauer anzuschauen, aber in der Theorie überspringst du praktisch Tiles, die dein Projektil aber passiert. Bei einer Steigung von 3 würde ausgehend vom Mittelpunkt bei Start/Zeil deine Gerade folgende Tiles treffen auf ihrer Flugbahn

Code:

* Start, wird geschnitten
+ Ziel, wird geschnitten
O wird geschnitten
X wird nicht geschnitten

  0 1 2 3 
0 * O X X
1 X X O +

Die Gerade würde genau zwischen 0/1 und 1/2 auf der Ecke in die zweite Zeile rutschen. Bei deiner Überprüfung wie du sie anwenden würdest würdest du prüfen:

Code:

  0 1 2 3 
0 * O O O
1 X X X +

In dem Fall fliegt deine Kugel wie anti-freak schrieb, um Ecken.

Du müsstest tatsächlich irgendwie versuchen eine gerade Linie zu berechnen - auf welche Methode auch immer, ob per Skript oder Events (ich persönlich würd da zu ner Skriptlösung tendieren, aber das liegt daran dass ich damit besser arbeiten kann als mit Events) - und zu testen, welche Tiles die schneidet. (auch wenn ich grad Befürchte, dass dieser Absatz nicht mehr ist , als schon gesagt wurde bisher ~.~, sorry!)