Hindernis auf Schachbrett

[fallencake]

Hi
Ich brauche eine Funktion die mir in einer 2d Map mit Hindernissen sagt, ob Punkt A Punkt B sieht, habe aber leider keine Idee wie ich das umsetze.

So sieht die Map etwa aus, die Infos die ich habe sind also:
beide punkte green: 3,1; red:5,5
Felder die blockiert sind: 4,2; 4,3; 4,4
Und wenn nötig die Seitenlänge eines Feldes (im Moment 30px), ist dies nötig oder geht es auch allgemein?

Für Links, oder bisschen (Pseudo)code wäre ich echt dankbar!

grüsse
fallencake

 

[muckelzwerg]

Na was ist denn Dein erster Gedanke dazu? So spontan kommt man doch auf die Idee, die von der Linie überstrichenen Felder zu suchen und alle zu prüfen.
Wenn Du nach "Rasterisierung Linien" suchst, bekommst Du zum Beispiel sowas:
Rasterisierung und Antialiasing
Das ist aber nur ein winziger Einstieg, da gibt es noch deutlich mehr. Da solltest Du aber eigentlich jetzt weiterkommen.

 

[SlaterB]

ich erzähle alternativ zu Links mal von meinen spontanen Ideen
(edit und anscheinend etwas komplizierter als der schon genannte Link):
ein mögliches Vorgehen ist, die Liste der Felder zu bestimmen, die die Linie berührt, der Weg durchs Schachbrett,

dafür könntest du Mathematik einführen, schon von Ebene mit Vektoren und Gerade gehört?
Schnittpunkt zweier Geraden? letztere wäre ein eine gute Grundfunktion, wobei hier besonders einfach, da mit senkrechten und waagerechten Geraden,
genau an x=0, 1, 2, 3, .., y genauso

für die Linie von A nach B brauchst du aber schon eine genaue Geradengleichung,
fall genau senkrecht bzw. waagerecht, wären dase Sonderfälle mit trivialer Felder-Bestimmung
ansonsten sind die Punkte sicher genau die Mittelpunkte von Feldern, z.B. 2.5/1.5 nach 4.5/4.5
das ergibt eine Gerade von .. (Gerade aus zwei Punkten bestimmen)

sei die Gerade z.B. y = 0.5 + 2*x
nun für alle senkrechten und waagerechen Linien zwischen den beiden Punkten die Schnittpunkte berechnen,
für die waagereche Linie y = 3 gilt eingesetzt 3 = 0.5 + 2*x, also x = 1.25

x = 1.25 bedeutet auf der waagerechen Linie y = 3 dass zwei bestimmte Felder (oben und unten) auf dem Weg der Linie liegen,
nämlich die Felder, die die waagerechen Linie y = 3 als Kante haben sowie noch zwischen den senkrechten Kanten x = 1 und x = 2 liegen
klingt alles kompliziert, kann man aber nach und nach erarbeiten, falls ein bisschen Grundverständis besteht,

ein Sonderfall ist noch wenn die Linie von A nach B genau den Schnittpunkt von 4 Feldern bzw. einer waagerechen
und senkrechten Kante trifft, einen Eckpunkt,
dann sind entweder alle 4 Felder aufzunehmen oder gar keine, falls das hinsichtlich der Hindernis-Betrachtung als erlaubte Lücke gilt,
im letzteren Fall ist es kritisch, wenn das zweimal hintereinander passiert, siehe Bild im Anhang,
aber das kann als weiteren Sonderfall vorher ausschließen, das passiert nur wenn die der Winkel genau 45 Grad ist,
wenn der Unterschied zwischen A und B in x- und y-Richtung gleich ist,
für diesen Fall kann man auch wieder auf relativ einfache Weise die Felder direkt bestimmen

hat man letztlich alle zu betrachenen Felder auf dem Weg von A nach B, dann nur noch schauen, ob eines davon ein Hindernis ist

 

[muckelzwerg]

Ist im Prinzip sogar fast das gleiche. Es geht ja um eine Rasterisierung die keine Lücken hat.
Bei den Senkrechten und Waagerechten lasen sich die Schnittpunkte sehr schnell berechnen. Man braucht ja wirklich nur die "Steigungsdreiecke" basteln.
Die Feldauflösung ist bekannt, also kann man auch mittels Division direkt das "Schnittfeld" an einer Linie bestimmen.
Dann muss man noch "durchzählen" wenn die Schnittfelder bei benachbarten Linien nicht auf gleicher Höhe/Breit liegen.

 

[fallencake]

Danke für die Antworten.
Ich wäre jetzt so vorgegangen, dass ich alle Punkte (oder jeden 4ten Punkt, oder sowas in der Art) der Linie rausgerechnet hätte und dann geschaut hätte ob diese in einem blockierten Feld liegen.
Aber da ich das ganze brauche um mein Pathfinding zu verbessern (Unnötige Notes raushauen - Damit nicht mehr Zigg-Zagg geloffen wird) dachte ich das ist ein bisschen übertrieben.

> dafür könntest du Mathematik einführen, schon von Ebene mit Vektoren und Gerade gehört?
> Schnittpunkt zweier Geraden
Jop genau! aber leider viel zu lange her..
Dabei müsste ich dann alle 4 Seiten von jedem Block prüfen, richtig? (Natürlich das ganze eingrenzen und nur die Blöcke nehmen die im hypothetischen 4eck um die zwei Punkte liegen)

Zum Rasterisierungslink: Nicht überall wo die Linie durchgeht werden auch Pixel gemacht, was für mich ja schlecht wäre. Aber muss es mir genauer anschauen.

Ich denke wenn ich mir nochmal anschaue wie ich die Geradengleichung mache bringe ich das hin.
> Man braucht ja wirklich nur die "Steigungsdreiecke" basteln.
genau *schäm* - echt viel zu lange her.

Und zu deinem Sonderfall mit den Eckpunkten. Es gibt 2 unterschiedliche Einheiten. kleine die da durch kommen und grosse die da nicht durchkommen, aber bei den grossen suche ich mit A* einfach nicht alle Nachbarn sondern nur obenUntenLinksRechts und somit wird das Problem da gar nicht auftauchen.

Jo also danke für die Anstösse, jetzt gehts weiter

 

[SlaterB]

Dabei müsste ich dann alle 4 Seiten von jedem Block prüfen, richtig? (Natürlich das ganze eingrenzen und nur die Blöcke nehmen die im hypothetischen 4eck um die zwei Punkte liegen)

je nach Vorgehen kann das so oder so sein,
ich dachte bei meinem Text an 'alle senkrechten und waagerechen Kanten zwischen Start und Ziel',
so dass man in deinem Bild von Grün nach Rot sagen könnte dass pro Feld nur die rechte und untere Kante interessant ist,
aber im Grunde theoretische Diskussion ohne konkreten Algorithmus

 

[muckelzwerg]

Bei größeren Objekten kannst Du einen Pfad testen, der aus mehreren parallelen Suchstrahlen besteht. Dann musst Du nur noch überlegen, wie weit die Strahlen voneinander entfernt sein dürfen, damit ein zu großes Objekt nicht links und rechts an einem einzelnen besetzten Feld vorbeitestet.

Falls Du das für weiterführende Spielentwicklung nutzen willst, solltest Du Dich WIRKLICH in solche Themen einlesen. Es gibt viele Tricks, die den A* und andere Verfahren erst richtig hilfreich machen.
Und ohne Mathe, speziell lin. algebra und Geometrie, kann man viele coole Sachen gar nicht erst machen.

 

[Logaff]

mmmh man könnte das hinderniss durch die eckpunkte entfeder so polygon mäßig definieren und denn gucken ob die gerade ein punkt innerhalb des polygones hat oder einfach eine art koordinatensystem einsetzen so von wegen unten links (0/0) und denn oben y achse und rechts x achse und denn die hinderniss eckpunkte durch vektoren beschreiben und gucken ob der vektor irg rot nach grün irg ein anderen vektor schneidet.