hi, im Prinzip ähnelt mein Problem diesem hier:

www.delphi-forum.de/...ghlight=sichtbarkeit

angenommen ich hätte einen Raum (2D), mit Hindernissen und zwei Objekten.
Jetzt möchte ich Prüfen, ob das eine Objekt im Sichtbereich des anderen liegt.

Es würde auch reichen wenn ich testen könnte, ob sich zwei Objekte durch eine Linie verbinden lassen, ohne dass sie von einem anderen Objekt geschnitten wird (ist denke ich identisch)

Wie stelle ich das geschickt an ?


mfg

Hi,

wenn du eine Kollisionsdetektion machen willst, könnte man es auch andersrum versuchen. Male eine Linie von Objekt zu Objekt und schaue dann auf der Linie, ob links oder rechts andere Pixel sind. Wenn links und rechts andere Pixel sind, hast du ein Objekt geschnitten.

das ist mir nicht elegant genug. eine mathematische methode wäre schon praktisch. es gibt zwar fertige segment polygon intersection algorithmen, die sich afaik für sowas eignen würden, aber ich möchte es doch gerne selbst verstehen und anwenden können.

mfg

Ich würde es mit Vektorrechnung und Schnittmengen versuchen. Sprich Vektoren der koordinaten bilden und mit anderen in Fragekommenden Objekten vergleichen. x( Frag mich nicht wie das geht.

dass das ganze über vektorrechnung laufen wird, ist mir klar, die frage ist, wie man das geschickt berechnet, ohne irgendwelche linearen gleichungssysteme auflösen zu müssen

praktisch wäre es dann noch, wenn ich den dichtesten schnittpunkt (von gerade und polygonen) zu einem punkt auf der geraden bestimmen könnte.

mfg

Hm, vielleicht wären ein paar Infos mehr besser:

Sind deine Objekte bekannt? Wie soll die Verbindung sich gestalten? Du kannst ja eine Gerade zwischen 2 Objekten (kann man hier auch von Punkten sprechen) ermitteln und dann mit einer anderen Geradengleichung den Schnittpunkt ermitteln. Wenns ein Polygon ist, wo soll der Vektor berechnet werden? Vom Prinzip ist die Gerade ja der Vektor, nur mit einem Offset. Vielleicht hast du auch ein Bild was du erreichen willst?

ich glaube ich vereinfache mein map format, um das problem ein wenig einfacher zu gestalten:

meine map besteht nun aus feldern (array of array of TObjekt), nun kann dies entweder wand oder boden sein. jedes feld ist gleich großs, also kann man von einem raster sprechen.
ein objekt ist ebenfalls so groß wie ein feld.

jetzt dachte ich daran, dass man hierfür doch den Bresenham Algorithmus verwenden könnte. Man zieht eine Bresenham Linie von Start zum Zielfeld und prüft, ob sich etwas dazwischen befindet, bzw ob an eine stelle der linie auf einer wand ist.

Aber ich denke, dass das zu ungenau ist, denn meine figuren können sich frei bewegen und drehen und eigentlich brauche ich eine gerade, die von der position der figur, in richtung der sicht geht.

Eigentlich möchte ich es so machen wie bei cs2d

freethings4u.qsh.sk/wp-in/images/cs2d.jpg

man schießt, trifft man den gegner, erleidet dieser schaden, andernfalls soll an der stelle wo eine wand getroffen wurde ein "funken" entstehen.

Für einen cs2d ähnlichen Fog-Of-War (Schatten) Effekt (den ich aber gerne fließend hätte und nicht feldweise), bin ich auf oben genanntes topic gestoßen (1. post). nur muss ich da genau die entgegengesetzten polygone berechnen um meine "shadow-map" zu zeichnen.

mfg

F34r0fTh3D4rk hat folgendes geschrieben:

Aber ich denke, dass das zu ungenau ist, denn meine figuren können sich frei bewegen und drehen und eigentlich brauche ich eine gerade, die von der position der figur, in richtung der sicht geht.

Genau das ist dein Vektor. Er berechnet sich aus Position des Spieler und geht in die Bewegungs/Sichtrichtung. Nun prüfst du alle Felder, die sich unter dem Vektor befinden, indem du über die Koordinaten die Felder berechnest. Den Vektor würde ich auch auf eine gewisse länge begrenzen. Wenn der Vektor auf ein "Hindernis" trift, bist du fertig.

MfG
freak

wie ich das rein theoretisch machen könnte ist mir völlig klar. nur wie ich das geschickt umsetze ist die frage. um zu prüfen, welche felder sich unter der geraden befinden bräuchte ich etwas bresenham ähnliches. aber das liefert mir nicht den genauen schnittpunkt. und die linie pixelweise entlang zu fahren halte ich für sehr unelegant.

mfg

In der Wiki ist doch ein Artikel mit einer Beispielimplementation in C. Kannst du damit nichts anfangen? Oder woran scheitert es?

MfG
freak

damit bekomme ich zwar heraus, ob ein objekt sichtbar ist (zumindest denke ich dass das zutreffen sollte), aber ich brauche es genau (das objekt kann ja auch zwischen zwei feldern stehen) und ich brauche den schnitt punkt mit dem objekt, bzw einem feld was dazwischen liegt.

mfg

Wie meinst du das? Ich glaube fast wir reden irgendwie an einander vorbei ... Du weißt jetzt (theoretisch) das ein Feld sichtbar ist. Was willst du denn noch? Wenn es um die darstellung geht, kannst du ja die Objekte die am weitesten Weg sind els erstas zeichen, dann ist es egal, wie viel zu sehen ist.
Aus welcher Sicht wird das, so wie cs2d? Dann versteh ich das mit der Sichtbarkeit auch nicht ganz ...

MfG
freak

Ein Bild sagt mehr als 1000 Worte:



Die blauen Felder sind meine Bodenfelder. Das dunkelgrüne Feld ist eine Wand.
Die gerade stellt den "Schuss" des Spielers da, ausgehend von der roten Figur
in eine beliebige Richtung. Jetzt möchte ich prüfen, ob dieser Schuss sein Ziel erreichen wird, wenn ja, an welcher position (pixelgenau), ansonsten wo er auftrifft (hindernis, ebenfalls pixelgenau) [gelber punkt].

Das hellblaue stellt in diesem Fall die Linie dar, die durch den Bresenham Algorithmus berechnet werden würde.

mfg

Genau so hab ich mir das vorgestellt. Wenn du die Felder hast die von der blauen/hellblauen Linie betroffen sind musst du noch prüfen, auf welches Ojekt die Linie als erstes trifft. Dann hast du es doch schon.
Die darstellung der blauen Linie ist ja idealisiert. Wenn man zum Beispiel von 2 Augen ausgeht, überlappen sich die Sichtkegel. Vielleicht solltest du für deine Kugel(Spieler) auch ein Sichtfeld einfügen, in dem nach Objekten "gescannt" wird.

die linie ist nicht idealisiert weil da eine kugel langfliegt aber mit unendlicher geschwindigkeit. es ist auch überhaupt kein problem, zu prüfen, mit welchem objekt die linie als erstes kollidiert usw. aber das bringt mir rein gar nichts, weil ich den exakten schnittpunkt brauche.

für die sichtbarkeit muss ich mir noch was anderes ausdenken (siehe oben verlinkter post) [damit meine ich den fog of war]

mfg

Warum schickst du eine Kugel und nicht einen unendlich dünnen Strahl? So kenne ich RayCasting, allerdings in 3D. Du hast deinen Startpunkt (Kreismittelpunkt?) und deine Richtung. In deinem Pixel steht doch drin, dass es eine Wand ist, also hast du doch auch das exakte Pixel, welches getroffen wird. :confused:

argh, ich schicke keine kugel. das ist ja eben das was ich nicht will. die gerade repräsentiert aber diese imaginäre kugel (das projektil)

die felder sind keine pixel (wie könnte sonst etwas in einem bereich innerhalb des feldes sein)
meine felder bestehen aus mehreren pixeln, ich definiere teile des rasters als wand.


mfg

Weisst du wie lang die "Linie" bis zum aufschlagspunkt ist?

nein, weil ich den aufschlagpunkt nicht kenne, sonst hätte ich das problem nicht

mfg

Der exakte Punkt ist die Schnittmenge vom Vektor der Linie und der Gerade zwischen den Eckpunkten der Aufschlagsfläche.