Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Freie Sichtlinie in zweidimensionalem Raum suchen

Freie Sichtlinie in zweidimensionalem Raum suchen

Universität / Fachhochschule

Tags: Sichtlinie, Vektor

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
BegossenerPudel

BegossenerPudel aktiv_icon

14:52 Uhr, 19.04.2019

Antworten
Hallo.

Ich habe ein kleines Problem bei der Programmierung mit C# und komme einfach nicht auf dessen Lösung.

Gegeben sei ein zweidimensionaler Raum mit zwei Vektoren/Objekten, Start und Ziel.
Zwischen diesen beiden befindet sich ein Hindernis.

Ich möchte eine freie Sichtlinie zwischen S und Z ziehen.

S muss sich also entlang des Hindernisses bewegen um eine freie Sichtlinie zu generieren.
Wenn S sich unter oder über Z befindet, so suche ich links und rechts von S, also auf der X-Achse.
Ist S links oder rechts neben Z, suche ich über und unter S, auf der Y-Achse.

Wie kann ich determinieren, ob S nun entlang der X- oder der Y-Achse suchen muss?
Oder einen Algorithmus erstellen, welcher automatisch die Richtige Bewegungsrichtung nutzt?

Bitte bitte nur konkrete Anweisungen geben, keine Verweise auf Seiten mit Formeln, da diese mir höchwahrscheinlich nicht helfen werden.
Ich suche schon seit Tagen und stehe kurz davor zu verzweifeln.
Das letzte, was mir jetzt fehlt, sind kryptische Hinweise ala "Erinnere dich an die 11. Klasse, Mathematik..." gefolgt von Namen alter toter Griechen...

Optimal wären (Pseudo)Codeschnipsel.

Vielen lieben Dank im Voraus


Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Online-Nachhilfe in Mathematik
Antwort
ledum

ledum aktiv_icon

15:15 Uhr, 19.04.2019

Antworten
Hallo
deine Beschreibung versteh ich nicht, es kommt doch auf die Lage und Art, des Hindernisses an? warum muss sich S entlang des H bewegen? es schein Z ist fest? aber wie ist H beschrieben.
Warum kannst du es nicht an Hand einer Skizze klären, oder uns die posten?
Vielleicht kriegst du, wenn man deine Frage versteht Antworten ohne alte Griechen?
Gruß ledum

BegossenerPudel

BegossenerPudel aktiv_icon

15:27 Uhr, 19.04.2019

Antworten
Hallo,

auf dem beigefügtem Meisterwerk moderner Computergraphik ist oben Z, das bewegliche Ziel, der Zielvektor, unten S, der Sucher, der Startvektor zu sehen.

Zwischen diesen beiden ist das zu umgehende Hindernis.

S müsste sich nun in diesem Falle so lange entlang der X-Achse bewegen, bis es eine freie Sichtlinie auf Z hat, sprich, sich von diesem Punkt aus direkt auf Z zu bewegen kann.

Wie kann ich bestimmen, ob S sich, wie hier gegeben, entlang der X-Achse bewegen muss?
Eine Pendelbewegung?


PS: Ich mag alte Griechen, sie können oftmals sehr hilfreich sein. Oder verwirrend...

screen
Antwort
ledum

ledum aktiv_icon

15:38 Uhr, 19.04.2019

Antworten
Hab ich dich richtig verstanden, S ist auf der Waagerechten (x-Achse) unterhalb des "Bergs" dann ist doch das eigentliche Problem den Berg zu programmieren, wenn er ein Dreieck ist hat man freie Sicht wenn man an der Grundlinie vorbei ist, sonst "hüllt" man ihn in ein Dreieck und hat dasselbe. wäre der Berg ein Rechteck, Ziel in der Mitte oben kann man es mit Bewegungen längs x nie erreichen.
Dein Problem ist also noch immer nicht klar, hast du in deinem Programm irgendwie die Kontur von H?
Gruß ledum
BegossenerPudel

BegossenerPudel aktiv_icon

16:06 Uhr, 19.04.2019

Antworten
Tut mir leid, dass ich nicht sofort vollständig erklärt habe.

Ja, S befindet sich unterhalb des Hindernisses auf der X-Achse.

Ich möchte den "Berg" - eine Mauer, ist doch klar ersichtlich... - explizit nicht programmieren, sondern dem suchenden Objekt die Entscheidung überlassen.

Ich implementiere zur Zeit verschiende Bewegungsmuster, Stichwort "Steering Behaviors".
Die Grundlegenden Algorithmen gehen dabei immer von einer freien Sichtlinie aus, sprich, zwischen Start und Ziel befindet sich kein Hindernis.

Ich möchte S sich entweder entlang der X- oder der Y-Achse bewegen lassen, bis diese Sichtlinie wieder hergestellt ist. Danach greift der ursprüngliche Bewegungsalgorithmus.
S soll sich also solange parallel ( X- oder Y-Achse) zum Hindernis bewegen, bis es Z wieder "sehen" kann.

Mein Problem besteht nun darin, eine Möglichkeit zu finden, zu entscheiden, auf welcher Achse sich der Sucher, S, bewegen muss.
Auf der im Screenshot ersichtlichen Konstelation wäre es die X-Achse.

Ich könnte S auch einfach erratisch alle Richtungen absuchen lassen, aber das möchte ich nicht.


Danke für deine Geduld...





Antwort
ledum

ledum aktiv_icon

12:35 Uhr, 21.04.2019

Antworten
Hallo ich weiss noch immer nicht, wie dein Hindernis gegeben ist, wenn es einfach gefärbte Pixel sind, bleibt nix übrig ls SZ zu ziehen und festzustellen, ob es ein gefärbtes Pixel trifft. wenn die Kontur gegeben ist, verbindet man Z mit den oberen Ecken, die Schnitte mit der x. Achse geben dann den verbotenen und freien Bereich?
Aber unsere Diskussion leidet an fehlenden Informationen
Gruß ledum
BegossenerPudel

BegossenerPudel aktiv_icon

18:16 Uhr, 22.04.2019

Antworten
Hallo und frohe Ostern,

Stell dir einen zweidimensionalen Raum vor.
In diesem befinden sich nur zwei Objekte, S und Z, oder A und B.
Die Objekte können sich auf jeder möglichen Position im Raum befinden, in jeder möglichen Relation zueinander.

Eine imaginäre Linie verbindet diese beiden Objekte miteinander.

Nun möchte ich Objekt S-A- in einem Winkel von +90 Grad und -90 von dieser Linie, genauer, dem Schnittpunkt der Linie und S, wegbewegen.
Wenn die Linie zum Beispiel senkrecht (=entlang der Y-Achse) ist, soll S-A- sich auf der X-Achse bewegen.

Um diese Bewegung geht es mir, ich weiss jedoch nicht, wo ich da ansetzen soll.





Antwort
ledum

ledum aktiv_icon

23:41 Uhr, 22.04.2019

Antworten
Hallo
für mich wird es immer wirrer: S,Z ODER A,B, kurz danach S-A ist jetzt A=Z? du hast eine Linie S-A ich nehme an die Verbindungslinie ist gemein? von dem Schnittpunkt einer Linie mit einem Punkt zu reden, ist recht unsinnig.
willst du S-A bewegen oder S? Wo sind die Hindernisse von den vorigen posts geblieben? wenn man die Linie SA kennt ist es doch leicht die senkrechte dazu zu finden, und S oder SA in der Richtung zu bewegen? kurz ich versteh gar nichts mehr. kannst du nich mal ne Skizze machen, auf der aber angegeben ist, welche Punkte man genau kennt.
Gruß ledum

BegossenerPudel

BegossenerPudel aktiv_icon

14:27 Uhr, 23.04.2019

Antworten
Guten Tag.

Es tut mir leid, aber so langsam denke ich, dass Sie mich veräppeln wollen.
Ich arbeite nur im Bereich Datenbanken, meine Welt ist die der Mengenlehre.
Nach so vielen Jahren geht nunmal anderes Wissen mangels Nutzung verschütt.

Ich gehe davon aus, dass die Lösung meines Problems trivial ist, aber ich komme einfach nicht darauf.
Deshalb frage ich ja auch hier.

Zwei Objekte, egal, ob S und Z oder A und B oder Gyros oder Döner genannt, beliebig positioniert in einem zweidimensionalen Raum.

Eine imaginäre HILFSlinie zwischen den beiden gezogen.

Eines der Objekte, zwischen denen diese Linie gezogen wird, S,A, Gyros soll sich nun in einem Winkel von 90 Grad dazu bewegen.
Beispiel: imaginäre HILFSlinie verläuft entlang der Y-Achse (oben - unten), so soll S,A, Gyros sich entlang der X-Achse bewegen.

Ich will nur wissen, wie man universell diese 90-Grad-Drehung berechnet, z-B einen Vektoren drehen, ohne dass ich feststellen muss, ob ich nun die X- oder Y-Achse nehmen muss.

Oder die HILFSlinie um 90 Grad drehen, ich weiss es doch nicht.

Als Ergebnis möchte ich Vektor 1- Ernie - und Vektor 2- Bert - haben, zwischen denen sich S,A, Gyros bewegen soll.

Noch einfacher lässt sich das doch nicht beschreiben, oder?
Antwort
ledum

ledum aktiv_icon

23:52 Uhr, 23.04.2019

Antworten
Hallo
ein Linie die durch S geht in Richtung z um 90° zu drehen ist ganz einfach. ich nehme mal an S hat die Koordinaten (s1,s2)
Z die Koordinaten (z1,z2) der Vektor von S mach z dann die Richtung (z1-s1,z2-s2) die Gerade von S Richtung z hat die Gleichung (s1,s2)+t(z1-s1,z2-s2)
der zu senkrechte (z1-s1,z2-s2) senkrechte Vektor hat die Richtung (z2-s2,-(z1-s1)) die senkrechte Gerade, auf der sich S bewegen soll ist dann (s1,s2)+t(z2-s2,-(z1-s1))
Beispiel: S=(1,2),Z=(5,7), SZ=(4,5) senkrecht dazu (-5,4) also die Gerade auf der sich S bewegen soll ist (1,2)+t(-5,,4)
ist es das, was du wolltest?
Gruß ledum
BegossenerPudel

BegossenerPudel aktiv_icon

17:07 Uhr, 24.04.2019

Antworten
Hallo.

Danke, Danke und nochmal Danke.

Genau das ist es. Beschämend, aber ich wäre wohl nie darauf gekommen.
(s1,s2)+t⋅(z2−s2,−(z1−s1)). So einfach. Das war alles.
Ich hätte eventuell mal das altmodische Karopapier zur Hand nehmen sollen, darauf wird es klar ersichtlich.


Jetzt kommt das Hindernis ins Spiel.

S soll sich direkt auf Z zubewegen.
Befindet sich ein Hindernis zwischen S und Z, so soll S, dem die Größe des Hindernisses unbekannt ist, sich parallel zum Hindernis bewegen, um einen freien Weg zu Z zu finden.

Auf den Screenshots mit der atemberaubenden Graphik siehst du die weisse Linie, welche die Sichtlinie/Verbindungslinie darstellt, die roten Punkte repräsentieren die Punkte, von denen aus S mittels Raycast versuchen wird, eine ununterbrochene Sichtlinie zu Z herzustellen.

Es funktioniert tadellos.

Für einfache Implementierungen einer Wegfindung ist das sehr hilfreich.
Für eine vollwertige Wegfindung inklusive des Umgehens von Hindernissen verwende ich eine eigene, and die UNITY-Engine angepasste, Implementierung des A*Star-Algorithmus.

Dies nur am Rande, da du dich nach dem Vebleib des Hindernisses erkundigtest.


Nun nochmals Danke für deine Hilfe.

Liebe Grüße

Screen01
Screen02
Antwort
ledum

ledum aktiv_icon

17:18 Uhr, 24.04.2019

Antworten
Hallo
wie vermeidest du den Zusammenstoß von S mit dem Hindernis? was Raycast ist weiss ich nicht, ausser es stellt fest, dass ein gefärbtes Pixel getroffen ist. Und mit "UNITY-Engine angepasste, Implementierung des A*Star-Algorithmus." kann ich auch nix anfangen, aber ich bin ja auch kein Informatiker.
Ist dir klar, dass erst dein letzter post wirklich gesagt hat, was du willst? Aber gut, dass cos dann wenigstens lösen konnte. Hak ab, wenn es erledigt ist.
Gruß ledum
Frage beantwortet
BegossenerPudel

BegossenerPudel aktiv_icon

18:20 Uhr, 24.04.2019

Antworten
Ich vermeide den Zusammenstoß, indem ich die nächste vorgesehene Position von S abfrage.
Hierzu habe ich ein Grid erstellt, in welchem einmalig die Spielfläche gerastert und mittels Raycast Hindernisse gefunden und verzeichnet werden.
Wenn grid[x,y].state =0, dann ist die Position begehbar, andernfalls nicht.

Raycast stellt fest, ob eine Kollision des projizierten Strahls mit einem Collider-Objekt stattfindet, welches an gefärbte-Pixel-Objekte, Sprites, gehangen wird.
Anhand des Namens oder Tags dieses Objekts identifiziert und klassifiziert man dieses Objekt als Hindernis, Spielfigur, Gegner usw.

Ich möchte ja nicht den Eindruck erwecken, undankbar und kleinlich zu sein, aber ich bin der Ansicht, dass mein Post >18:16 Uhr, 22.04.2019< mein Begehren klar definiert.
Ich wurde jedoch nur für die fälschliche Verwendung des Terminus "Schnittpunkt" gescholten...
Wieso dort "+90 +90 Grad und −90 −90" steht, weiss ich nicht, es hätte +90 und -90 Grad heißen sollen.
Gut möglich, dass es nur von meiner Warte aus verständlich ist.