Vektoriales Rechnen

[Maurooon]

oder ich zeichne mit canvas eine Linie von den beiden Punkten... nur wie frage ich ab ob die durch die Shapes geht?

[BrightAngel]

Hey :)

Ich glaube, es wäre auch noch ganz interessant, wie deine Datenstruktur intern aussieht: Also wie sind Objekte und Hindernisse repräsentiert?

Beispiel: Man kann zum Beispiel intern ein zweidimensionales Array vorhalten, welche das Spielfeld repräsentieren. Kann man zum Beispiel in einem Schachspiel verwenden, weil da nur eine Figur pro "Zelle" erlaubt ist.
Du merkst dir intern nur für die Figuren die Positionen?

Auch die "Art wie Bewegung" implementiert ist, wäre vmtl. noch informativ: Wie findest du denn bisher heraus, ob deine Figur gegen eine Wand läuft. Im Prinzip ist das eventuell fast das selbe: Ob ein Projektil oder ein Männchen die Wand durchkreuzt, kann je nach Implementierung/Datenhaltung signifikante Unterschiede machen.

Wenn ich jetzt raten müsste, dann könnte ich mir vorstellen, dass du die Hindernisse in einer Art "Liste" (oder listenähnlich) gespeichert hast. Die "naive" Vorgehensweise ist einfach alle durchzutesten. Bei kleinen Szenenaufbauten funktioniert das mit moderner Hardware im Allgemeinen ganz gut. Und 2D spielt auch noch in deine Karten ;)

Brighty :D

[Maurooon]

Zitat:

Zitat von BrightAngel (Beitrag 1371166)

Hey :)

Ich glaube, es wäre auch noch ganz interessant, wie deine Datenstruktur intern aussieht: Also wie sind Objekte und Hindernisse repräsentiert?

Beispiel: Man kann zum Beispiel intern ein zweidimensionales Array vorhalten, welche das Spielfeld repräsentieren. Kann man zum Beispiel in einem Schachspiel verwenden, weil da nur eine Figur pro "Zelle" erlaubt ist.
Du merkst dir intern nur für die Figuren die Positionen?

Auch die "Art wie Bewegung" implementiert ist, wäre vmtl. noch informativ: Wie findest du denn bisher heraus, ob deine Figur gegen eine Wand läuft. Im Prinzip ist das eventuell fast das selbe: Ob ein Projektil oder ein Männchen die Wand durchkreuzt, kann je nach Implementierung/Datenhaltung signifikante Unterschiede machen.

Wenn ich jetzt raten müsste, dann könnte ich mir vorstellen, dass du die Hindernisse in einer Art "Liste" (oder listenähnlich) gespeichert hast. Die "naive" Vorgehensweise ist einfach alle durchzutesten. Bei kleinen Szenenaufbauten funktioniert das mit moderner Hardware im Allgemeinen ganz gut. Und 2D spielt auch noch in deine Karten ;)

Brighty :D

Also Die Figuren sind Images und die Hindernisse Shapes. Wenn die Koordinaten der Figuren mit den Shapes übereinstimmen, dann ist die Bewegung in diese Richtung gesperrt. Frage also alles durch einfache if-Anweisungen ab... eine Liste habe ich nicht, nein :D Und im Nachhinein noch ein Array auf mein Spielfeld zu verlegen wollte ich eigentlich vermeiden... gibt es keine Funktion die überprüft ob sich zwei gezeichnete Linien kreuzen? Ich könnte ja die Hindernisse sowie eben die Linie zwischen Spieler und KI jeweils zeichnen über Canvas und dann abfragen ob sie sich kreuzen... ist das nicht möglich? :?::?::?:

[hanvas]

Zitat:

gibt es keine Funktion die überprüft ob sich zwei gezeichnete Linien kreuzen?

Zweier gezeichneter Linien ?. Nein die gibt es so ohne weiteres nicht. Man kann so was schon machen, aber das ist relativ aufwendig. (Hough Transformation)

Es ist viel einfacher den Schnittpunkt zweier Linien zu ermitteln wenn die Koordinaten bekannt sind :

http://www.delphipraxis.net/71754-sc...it-delphi.html

Deswegen vermutlich auch die Frage des Vorposters nach der Datenstruktur. Wenn Du eine Liste, Array etc. der dargestellten Objekte hast, dann hast Du normalerweise auch die Koordinaten der Objekte und kannst eines nach dem anderen Testen. Wenn das Ganze dann komplexer wird, dann nennt man das eine Sprite-Engine. So was findest Du beispielsweise hier

http://chapmanworld.com/2015/02/27/d...-the-viewport/

cu Ha-Jö

[BrightAngel]

Zitat:

Zitat von hanvas (Beitrag 1371172)

Deswegen vermutlich auch die Frage des Vorposters nach der Datenstruktur. Wenn Du eine Liste, Array etc. der dargestellten Objekte hast, dann hast Du normalerweise auch die Koordinaten der Objekte und kannst eines nach dem anderen Testen.[...]

Genau so war das gemeint :)

[Maurooon]

Okay, also ich habe mir jetzt eine Funktion gebaut, die jede Millisekunde die Geradengleichung durch die Punkte Figur1 und Figur2 berechnet. Durch meine Hindernisse hab ich nun auch geraden gelegt. Jetzt muss ich nur noch die Schnittpunkte berechnen und dann überprüfen ob die Schnittpunkte innerhalb der Hindernisse liegen (weil diese ja eigentlich nur Strecken sind) und falls ja, siehen die Figuren sich nicht und falls nein sehen sie sich.

Ich habe mir den Link einmal angeschaut, nur verstehe ich die Funktion nicht ganz und verwende sehr ungern Code den ich nicht versthe... Könntest du mir erklären, was dort jeweils passiert? Hier nochmal die Funktion:

Zitat:

Delphi-Quellcode:

{
  Diese Funktion berechnet den Schnittpunkt von Line A
  und Linie B. Haben beide Linien keinen Schnittpunkt
  dann ist das Ergebnis 'false', sonst werden die
  Koordinaten des Schnittpunktes in den Var-Paramtern X
  und Y zurückgegeben und das Ergebnis ist 'true'
}
Function CrossingPoint(AX1,AY1,AX2,AY2, BX1,BY1,BX2,BY2:Integer; Var X,Y:Integer):Boolean;
Var
  T,S,N:Extended;
Begin
  Result:=false;
  // Nenner berechnen (Matrize)
  N:=AX1*BY2 + BX2*AY2 + AX2*BY1 + BX1*AY1 - BX2*AY1 - AX1*BY1 - BX1*AY2 - AX2*BY2;
  // Möglicherweise Abruch wegen Divison durch Null
  If N=0 then Exit;
  // T berechnen (Matrize)
  T:=(AX1*AY2 + AX2*BY1 + BX1*AY1 - AX2*AY1 - BX1*AY2 - AX1*BY1) / N;
  // Wenn T nicht im Intervall [0,1] liegt dann haben
  // beide Linien keinen Schnittpunkt
  If (T<0) or (T>1) then Exit;
  // S berechnen (Matrize)
  S:=(AX1*BY2 + BX2*BY1 + BX1*AY1 - BX2*AY1 - BX1*BY2 - AX1*BY1) / N;
  // Wenn S nicht im Intervall [0,1] liegt dann haben
  // beide Linien keinen Schnittpunkt
  If (S<0) or (S>1) then Exit;
  // Berechnung mit T
  X:=Round(BX1+T*(BX2-BX1));
  Y:=Round(BY1+T*(BY2-BY1));
  // Berechnung mit S
  // X:=Round(AX1+S*(AX2-AX1));
  // Y:=Round(AY1+S*(AY2-AY1));
  Result:=true;
End;

Was bedeutet Matrize, was für einen Nenner berechnet man da? Und sind dann AX1 und AY1 die Koordinaten von Figur 1 z.B. und AX2 und AY2 die von Figur 2 und BX1, BY1, BX2 und BY2 Punkte auf dem Hindernis?

Ich hoffe mir kann jemand helfen.

LG

[Namenloser]

Zitat:

Zitat von Maurooon (Beitrag 1371250)

nur verstehe ich die Funktion nicht ganz und verwende sehr ungern Code den ich nicht versthe... Könntest du mir erklären, was dort jeweils passiert?

Das ist löblich. Ich versuche mal den groben Ansatz zu erklären, weil ich mich noch daran erinnern kann, dass ich damals in der Mittelstufe auch ziemlich daran hing, da wir noch keine Vektorrechnung hatten.

Man kann die Lösung in zwei Teile untergliedern
(1) Tu so als wären die Strecken Geraden (also unendlich lang). Berechne die Schnittpunkte der Geraden.
(2) Prüfe, ob der Schnittpunkt tatsächlich auf den Strecken liegt.

(1) Zuerst betrachten wir mal nur die Schnittpunkte von Geraden (also unendlich langen Strecken), weil der Fall einfacher ist. Man kann eine Gerade durch zwei Punkte und einen Parameter darstellen:

Gerade g: g(t) = g0*(1-t) + g1*t
Gerade h: h(s) = h0*(1-s) + h1*s

g0, g1: Stützpunkte von Gerade g (Vektoren)
h0, h1: Stützpunkte von Gerade h (Vektoren)
t, s: Parameter (Skalare)

Du kannst dir vorstellen, dass man, wenn man für t und s beliebige Werte einsetzt, alle Punkte auf den jeweiligen Geraden bekommt.

Den Schnittpunkt erhält man jetzt einfach, indem man g = h setzt. Da bekommt man ein Gleichungssystem heraus, das man dann auflösen muss. Wie man sich denken kann, gibt es einen Fall, in dem das Gleichungssystem nicht bzw. nicht eindeutig lösbar ist, nämlich wenn g und h parallel sind (führt in der Praxis zu einer Division durch 0). Diesen Fall muss man abfangen.

Andernfalls erhält man die Lösung in Form einer Formel für t bzw. s. Wenn man den Wert in die oben gegebene Definition für g bzw. h einsetzt, erhält man den Schnittpunkt.

(2) Wie prüfen wir jetzt, ob der Schnittpunkt tatsächlich auf den Strecken liegt? Nun, schauen wir uns mal an, was passiert, wenn wir für t den Wert 0 oder den Wert 1 einsetzen.

g(0) = g0*(1-0) + g1*0 = g0
g(1) = g0*(1-1) + g1*1 = g1

Aha! Das heißt, 0 und 1 ergeben genau die Endpunkte der Strecke. Und nicht nur das, alle Werte zwischen 0 und 1 ergeben genau die Punkte zwischen den Endpunkten.

D.h. man muss nur prüfen, ob t im Bereich [0,1] liegt, und ob s im Bereich [0,1] liegt. Wenn beides wahr ist, dann schneiden sich die Strecken im berechneten Punkt. Andernfalls schneiden sie sich nicht.

---

Ich hoffe, der grobe Ansatz ist so verständlich. Ich hatte jetzt keine Lust, das hier alles im Detail aufzulösen. ;) Du kannst ja mal versuchen, das nachzurechnen. Wenn du dabei Fragen hast, kannst du sie hier stellen.

Zitat:

Zitat von Maurooon (Beitrag 1371250)

Was bedeutet Matrize

Der Singular ist eigentlich "Matrix". Ist hier einfach nur eine kompakte Schreibweise für ein lineares Gleichungssystem.

[hanvas]

Zitat:

Delphi-Quellcode:

Function CrossingPoint(AX1,AY1,AX2,AY2, BX1,BY1,BX2,BY2:Integer; Var X,Y:Integer):Boolean;

Was bedeutet Matrize, was für einen Nenner berechnet man da? Und sind dann AX1 und AY1 die Koordinaten von Figur 1 z.B. und AX2 und AY2 die von Figur 2 und BX1, BY1, BX2 und BY2 Punkte auf dem Hindernis?
LG

Normalerweise kann man den Schnittpunkt zweier Geraden berechnen in dem man die allgemeine Form der Geradengleichung für jede Gerade aufstellt und aus beiden Gleichungen ein Gleichungsystem aufstellt. Das wurde aber schon im Post vor mir beantwortet, weshalb ich mir das spare und stattdessen etwas zur konrekten Verwendung sage.

Genau das Beschriebene macht die Funktion. AX1,AY1 und AX2,AY2 sind die Koordinaten des Anfangs.- und Endpunktes einer Strecke, BX1,BY1 und BX2 und BY2 sind die Koordinaten des Anfangs.- und Endpunktes der zweiten Strecke. Die Funktion liefert wahr zurück wenn sich die beiden Strecken schneiden und false wenn nicht. X und Y sind die Koordinaten des Schnittpunktes falls sich die Strecken schneiden, ansonsten undefiniert.


cu Ha-Jö

[Maurooon]

Okay, vielen Dank.

Was bringt das

Code:

Result := false;

in der ersten Zeile und könnte man statt dem

Code:

Exit

nicht auch

Code:

result := false;

nehmen?

[BrightAngel]

Hey :)

Das

Delphi-Quellcode:

Exit

"unterbricht" den Kontrollfluss in der Funktion und kehrt zum "Aufrufer" zurück.

Delphi-Quellcode:

Result

ist der Rückgabewert und fasst erstmal den Kontrollfluss nicht an, sondern setzt nur den Rückgabewert.

Der Gedanke ist der: Diese Funktion ist so aufgebaut, dass man viele Kriterien überprüfen muss, bevor ein positives Ergebnis herauskommt. Man kann in jedem Zwischenschritt abbrechen und verkürzt damit die Ausführungszeit.

Warum kein if-else-Baum? Ja, man kann das auch mit verschachtelten if-else Statements ausdrücken. Aber optisch ist das eventuell nicht so schön, da man in jeder Verschachtelung optisch einmal mehr "einrückt". Klar, das ist Stil. Der Autor dieses Codes hat sich entschieden, dass das optisch für ihn schöner ist, wenn das alles optisch in einer Ebene liegt. Diese Entscheidung hat zum Beispiel zur Folge, dass die Symmetrie der Berechnung von S und T direkt allein schon durch den selben Zeilenbeginn und die interne Struktur der Zeile sichtbar ist.

Brighty