Wie kann ich diesen Sichtlinienalgorithmus ändern, um Strahlen zu akzeptieren, die durch die Ecken gehen?

Question

Ich arbeite an einem Pfadfindungsalgorithmus basierend auf Theta *, einer Variante von A *, die ein gutes System zur Pfadfindung bietet, das nicht auf ein Gitter beschränkt ist, obwohl das Gelände/die Hindernisse auf einem Gittermuster basieren. Dieses System benötigt einen Sichtlinienalgorithmus, um zu bestimmen, ob ein bestimmter Pfad blockiert ist oder nicht.

Ich fand this extrem nützliche Sichtlinie Algorithmus, und ich habe es erfolgreich in meinem Code implementiert. Leider hält es die folgenden ein ungültiger Pfad zu sein:

jedoch für meine Zwecke, ich ein solcher Weg wollen gültig betrachtet werden. Ich habe versucht, den Algorithmus zu modifizieren, indem ich mit der grundlegenden Formel y = mx + b erfasste, ob ein Punkt auf der Linie selbst ist oder nicht, aber die Inkonsistenzen des Algorithmus hindern mich daran, sich auf ein solches System zu verlassen.

Gibt es eine effiziente Möglichkeit, diesen Algorithmus zu ändern, um einen solchen Pfad zu ermöglichen? Gibt es einen anderen Algorithmus, der besser funktioniert? Denken Sie daran, dass die Start- und Endpunkte des Pfades nicht notwendigerweise auf ein Gitter beschränkt sind, so dass alle Punkte double Präzision verwenden.

Answer 1

Der Code, auf den Sie verweisen, lässt explizit den Fall unberücksichtigt, in dem die Linie durch einen Gitterpunkt verläuft (wobei sich vier Quadrate berühren). Sie müssen nach error == 0 suchen.

In diesem Fall kann höchstens eines der vier Quadrate, die den Gitterpunkt berühren, blockiert werden, um noch einen gültigen Pfad zu haben.

Grüße, Erich