Man sieht den Wald vor lauter Bäumen nicht

Das fertige Programm mit deaktivierten Erweiterungen

Aufgabenstellung

In einem rechtwinkligen Gitter von 20x20 Gitterpunkten steht auf einem Gitterpunkt der Förster Pudlig, auf allen anderen Gitterpunkten stehen Bäume. Förster und Bäume seien punktförmig, haben also keine Ausdehnung. Ein Baum sei dann sichtbar, wenn der Sehstrahl vom Gitterpunkt des Försters zum Gitterpunkt des Baumes durch keinen anderen Gitterpunkt verläuft. Wenn der Sehstrahl jedoch vorher durch einen anderen Gitterpunkt geht, so sieht Förster Pudlig sprichwörtlich den Wald vor lauter Bäumen nicht.

Es soll folglich ein Programm geschrieben werden, das errechnet welche Bäume Förster Pudlig nun tatsächlich zu gesicht bekommt und diese grafisch darstellt.

Umsetzung

Grundidee

Die Grundidee, die Ich zur Lösung der Aufgabenstellung verfolgte, war die, dass jeder Baum im Wald in einem bestimmten Winkel zum Förster steht. Wenn nun ein Baum der einzige Baum im Wald mit diesem Sichtwinkel ist, so ist er für den Förster prinzipiell sichtbar. Wenn es jedoch auf der direkten Sichtlinie vom Förster zum Baum nun noch einen anderen Baum gibt, so muss dieser exakt den gleichen Sichtwinkel vom Förster aus haben - und verdeckt den anderen Baum somit.

Ein Baum B ist nur dann sichtbar, wenn sich direkt zwischen ihm und dem Förster kein anderer Baum befindet, sich also kein Baum näher am Förster befindet, der in demselben Winkel wie Baum B zu diesem steht.

Das Programm muss also lediglich die Winkel/Steigungen der einzelnen Bäume berechnen, diese mit den anderen abgleichen und nur die sichtbaren Bäume auch tatsächlich zeichnen bzw. stehenlassen.

Umsetzung der Grundidee

Bei meinem Programm habe ich bewusst auf objektorientierte Modellierung/Programmierung verzichtet, da sie sich in meinem Falle als nicht zielführend erwies: Sowohl die Bäume als auch der Förster sind Programmintern nicht existent, sondern werden im Falle der Bäume als grafische Ausgabe aus Schleifenzähler-Variablen errechnet. Die Position des Försters wird in zwei gesonderten Variablen festgehalten. Anfangs wird der Wald, der aus 20*20 Bäumen besteht (eigentlich 399, weil der förster ebenfalls auf einem Gitterpunkt steht) in Form von grünen Punkten auf einen Canvas gezeichnet.Der Förster wird durch einen roten Punkt dargestellt.

In der Programmlogik ist der Wald wie bei einem Koordinatensystem in 4 Quadranten aufgeteilt, wobei die Position des Försters den Schnittpunkt der Koordinatenachsen darstellt. In jedem dieser 4 Quadranten werden nun, ausgehend vom Förster, die Koordinaten jedes Baumes in relative Koordinaten mit Bezug auf den Förster umgerechnet und die daraus resultierende Steigung in einem Array hinterlegt - jedoch nur, wenn es diese Steigung im zu berechnenden Quadranten zuvor noch nicht gab! War die Steigung neu, wird der Baum nicht angetastet, denn er muss wie oben gesagt für den Förster sichtbar sein. War sie jedoch bereits einem anderen Baum zugeordnet, so kann der Förster den Baum nicht sehen und er wird gelöscht.

Probleme...

Das einzige wirkliche Problem das sich mir in den Weg stellte war, dass ich die absoluten Koordinaten der Bäume in relative im Bezug zum Förster umrechnen musste, um eben auch an die relative Steigung zu kommen. Schließlich ist die Position des Försters eine andere als die des Computers.

Da die Umrechnungsformel für jeden der 4 Quadranten ein bisschen anders war, habe ich mich entschlossen für jeden dieser Quadranten eine eigene Routine zu schreiben, um die Komplexität des Codes zu reduzieren und die Übersichtlichkeit zu bewahren.

Ein weiteres, jedoch sehr kleines Problem ergab sich bei der Berechnung der Bäume Kreuzförmig um den Förster, aber dazu später mehr unter Ausnahmen.

Die Hauptprozedur (Vereinfacht)

Das Herzstück des Programms könnte eigentlich simpler nicht sein:

Zwei verschachtelte for-Schleifen arbeiten sytematisch sämtliche Bäume eines Quadranten ab, während der Inhalt der Schleifen diese entweder stehenlässt oder löscht.

Auf die hier der übersichtlichkeit halber weggelassenen Zusatzfunktionen werde ich später noch zu sprechen kommen.

 1  for i:=PosFX+1 to 20 do
 2    begin
 3      for j:=PosFY-1 downto 1 do
 4        begin
 5          quotient := (PosFY-j)/(i-posFX);                  
 6            if Form1.CheckNew(quotient) then
 7              begin
 8                quotienten[n] := quotient;
 9                inc(n);
 10             end
 11           else
 12             Form1.DrawBaum(i,j,false);
 13       end;
 14   end;  

Des Verständnisses halber will ich hier die einzelnen Teile der Routine ausführlicher erklären:

Die äußere Hülle bilden zwei for-Schleifen, die, ausgehend von der Position des Försters, mithilfe der restlichen Routine alle Bäume bis zum Waldrand abarbeiten. Die beiden Variablen PosFX und PosFY beinhalten die x- und y-Koordinaten des Försters.

Die innere Routine (Z.5-Z.12) beinhaltet die Errechnung und Überprüfung sowie die Auswertung der Steigungen:

Diese Formel berechnet den Quotienten aus relativer y- und x-Koordinate eines Baumes, auch Steigung genannt:

 quotient := (PosFY-j)/(i-posFX);

Da sie für jeden Quadranten, genauso wie die for-Schleifen, unterschiedlich ist, habe ich für jeden Quadranten eine eigene Routine geschrieben.

Der errechnete Quotient wird nun einer Hilfsfunktion übergeben, die das Quotienten-Array durchsucht und ermittelt, ob es diesen im aktuellen Quadranten schon einmal gegeben hat:

 if Form1.CheckNew(quotient) then
   begin
     quotienten[n] := quotient;
     inc(n);
   end
 else
   Form1.DrawBaum(i,j,false);

Falls der Quotient neu ist, wird er in das Array geschrieben, um für zukünftige Prüfungen zur Verfügung zu stehen. Die zugehörige grafische Darstellung des Baums bleibt unangetastet, da sie schon existiert und aufgrund der weiterhin bestehenden Sichtbarkeit nicht verändert werden muss.

Tritt jedoch der Fall ein, dass die CheckNew-Prozedur den Quotienten im Array wiederfindet, so ist der zugehörige Baum nichtmehr sichtbar und wird mithilfe einer weiteren Prozedur gelöscht. Diese kann einen Baum sowohl zeichnen als auch wieder löschen, indem sie ihn mit der Hintergrundfarbe überschreibt, falls der Prozedur "false" statt "true" als Parameter übergeben wird.

Ausnahmen

Einen Sonderfall stellen die kreuzförmig um den Förster angeordneten Bäume dar, also die direkt über, unter, links und rechts von ihm befindlichen:
Bei den Bäumen direkt über und unter ihm müsste die Hauptprozedur eine Division durch 0 durchführen, da die Bäume in x-Richtung 0 relative Einheiten vom Förster entfernt ständen.
Die Bäume links und rechts vom Förster würden mit der Initialisierung des Quotienten-Arrays in Konflikt geraten, da diese dieselbe y-Koordinate wie der Förster und dementsprechend die Steigung 0 besäßen. Da nun aber das Quotienten-Array zu Beginn standardmäßig mit Nullen initialisiert wird, würde die CheckNew-Funktion bereits beim ersten Baum einen Treffer verzeichnen und dieser von der weiteren Prozedur gelöscht werden.

Um diesem Problem entgegenzukommen wurden diese Bäume von separaten Routinen bearbeitet:

 for w:=PosFX-2 downto 1 do
   Form1.DrawBaum(w,PosFY,false);//links
 for x:=PosFY-2 downto 1 do
   Form1.DrawBaum(PosFX,x,false);//oben
 for y:=PosFX+2 to 20 do
   Form1.DrawBaum(y,PosFY,false);//rechts
 for z:=PosFY+2 to 20 do
   Form1.DrawBaum(PosFX,z,false);//unten

Wie vielleicht auffällt werden hier ohne mathematische Berechnungen einfach Bäume gelöscht - denn Berechnen lassen sich diese mit den gegebenen Mitteln nicht.

Hilfsprozeduren/-funktionen

DrawBaum(1,2,3)
Diese Prozedur zeichnet einen Punkt an der ihr per Parameter (1,2) übergebenen Position. Dieser ist grün und soll einen sichtbaren Baum darstellen, falls zusätzlich "true" als 3.Parameter übergeben wurde. Wurde hingegen "false" übergeben, so hat der Punkt die Hintergrundfarbe des Canvas und überzeichnet den Vorher dort befindlichen Baum - der Baum ist unsichtbar.

DrawWald
DrawWald macht nichts weiter, als DrawBaum 400 mal mit verschiedenen Koordinaten und dem Parameter "true" aufzurufen, damit auf dem Canvas ein Wald mit 20*20 Bäumen entsteht.

DrawF(1,2)
DrawF, also "ZeichneFörster" dient dazu, Förster Pudlig als roten Punkt an den übergebenen Koordinaten (1,2) im Wald einzuzeichnen. Sie ist prinzipiell mit DrawBaum vergleichbar, zeichnet jedoch einen roten statt einen grünen Punkt und hat nicht die Fähigkeit, ihren selbst gezeichneten Punkt wieder zu löschen.

CheckNew(1): boolean
Diese Funktion(!) ist programmintern von essentieller Bedeutung, da sie den ihr übergebenen Quotienten der relativen Baumkoordinaten (1) mit sämtlichen Quotienten im Quotienten-Array vergleicht. Findet sie ihn dort wieder, so ist der übergebene Quotient nicht "New" und folglich wird ein "false" als Ergebnis zurückgegeben. Ist er hingegen "New", so lautet das Ergenbis "true".

Das Programm mit aktivierten Zusatzfunktionen

Zusatzfunktionen

Um das recht trockene Programm ein bisschen aufzulockern, habe ich einige kleine Zusatzfunktionen integriert:

1. Frei beweglicher Förster (von Gitterpunkt zu Gitterpunkt)
2. Ausgabe der Anzahl sichtbarer/unsichtbarer Bäume
3. Optionale Verlangsamung des Programmablaufs zur Veranschaulichung
4. Optionales Einzeichnen der "Sichtstrahlen" des Försters zur Veranschaulichung

Alle diese Zusatzfunktionen außer der Bewegung des Försters konnten durch wenige zeilen Code in die Hauptprozedur implemetiert werden. Sie sind jedoch so einfach, dass ich sie hier nicht weiter zu erklären brauche.

Einzig die kreuzförmig um den Förster angeordneten Bäume machten in Verbindung mit den Sichtstrahlen mal wieder eine Ausnahme und benötigten wiederum eigene Routinen, da sie in der eigentlichen Hauptroutine, in der diese Funktion eigentlich implementiert war, nicht vorkamen.

Bezüglich der Sichtstrahlen kann man anhand des rechten Bildes sehr gut erkennen, dass sämtliche "Sichtstrahlen" keinen einzigen Baum kreuzen und der Förster wirklich nur an den Bäumen vorbeischauen kann. Dass es letzendlich so gut passt, obwohl die Bäume eine größere Ausdehnung als nur einen Punkt haben liegt daran dass 400 Bäume doch recht wenig sind und der Wald im vergleich zu den Bäumen ausreichend groß ist.

Abschließendes

Wenn man sich das erste Bild einmal genauer ansieht, so kann man erkennen dass die Berechnungen ein sehr regelmäßiges Muster ergeben - theorethisch wäre es also garnicht nötig die einzelnen Bäume zu berechnen: Man könnte einfach eine fest vorgegebene Maske über den Wald legen, die alle unsichtbaren Bäume löscht und die lediglich der Position des Försters angepasst wird.
Leider fällt sowas erst im nachhinein auf - irgendwoher braucht man ja die Vorlage. Und im Sinne des Projekts wärs wohl auch nicht gewesen, obwohl die Aufgabenstellung erfüllt worden wäre.

Insgesamt ging mir mein Projekt recht leicht von der Hand, nachdem ich erst einmal herausgefunden hatte wie ich die relativen Koordinaten zu berechnen hatte (im Nachhinein ziemlich banal), denn mehr als die Idee mit den Steigungen und deren Berechnung steckten eigentlich nicht dahinter.
Auch auf jegliche objektorientierte Modellierung konnte ich hier (glücklicherweise) verzichten, da diese keinen praktischen Vorteil bot - etwas verwirrend, da unsere Dokumentationen doch unter dieser Kategorie im Wiki stehen.
Ich beantrage hiermit eine Verschiebung meines Artikels in "Grundlagen der Programmierung"! ;)

Download

Hier mein komplettes Programm inkl. Quelltext:

• Wald.zip