Ich hab mal ein Logik-Problem.

Und zwar möchte ich einen Quix-Klon basteln. (Quix oder Qix war das spiel wo man versuchte möglichst viel Fläche in einem Feld einzufärben ohne erwischt zu werden. Für mehr Infos siehe Wikipedia)

Ein ganz zentrales Problem ist nun herauszufinden was eingefärbt werden muss.
Ich hab dazu mal eine Grafik angehängt.

Die Qix-Regeln besagen: Färbe die Seite ein wo kein Gegner ist. Falls auf beiden Seiten ein Gegner ist, wird nur
die Linie eingefärbt.

Nun ist das Problem aber herauszufinden wo der Gegner sich befinden (bezüglich der Linie).
Das nächste Problem ist dann die Fläche einzufärben. (Wie färbt man am effizientesten einen abgeschlossenen Bereich. Vergleichbar mit Zeichnprogrammen.)



Wie würdet ihr das angehen. Hab jetzt schon 1 1/2 Tage lang drüber nachgedacht - ohne Erfolg.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

die wikipedia war leider nicht sehr hilfreich... gerade linien sind sehr weit fassbar ich darf nur senkrecht und waagerecht gehen? dann muss es eigentlich leicht sein, man muss dann die linien nur sinnvoll zerstückeln und das spielfeld anhand dieser information in rechtecke zerlegen. dafür muss ich aber zeichen. und damit sich der aufwandt lohnt muss ich wissen, ob die linien nur waagrecht und senktrecht gehen...

Also folgendes... Ist eigentlich ganz leicht Du nimmst die Punkte deiner Linie und projezierst sie an den Rand des Spielfeldes, schmeisst doppelte Projektionen heraus und sortierst diese (ein paar der Projektionen s8ind im Bild bepunktet angedeutet, wobei projektionen anch oben und unten auf das selbe hinauslaufen, es ist nur ein platzproblem). Anhand dieser Intervallteilungen stückelst du Spielfeld in Rechtecke und bekommst so ein Gitter (lässt sich dann prima als array beschreiben). Die Linien kannst du dann genauso einteilen. Jedes dieser Rechtecke bekommt den Wert 0 für nicht besucht zugeteilt und du beginnst am rechteck links oben den Rechtecken Werte zuzuteilen. Nämlich das rechteck rechts oben bekommt den Wert 1 statt 0 und ist damit besucht. Dann gehst du von dort rekursiv in die vier richtungen oben, unten, links und rechts aber NIEMALS diagonal. Wenn du beim Übergang zu einer dieser Seiten die Linie überquerst, hörst du an dieser Stelle mit der Rekursion auf und setzt den Wert für das Gitter an dieser Stelle NICHT auf 1. Wenn du keine Linie dabei überquerst, setzt du den Wert des Gitterpunktes auf 1. Wenns schon auf 1 war (also schon besucht und nicht durch die linie verdeckt), brichst du die rekursion ab. Am Ende hast du das Gitter zerteilt in den besuchten und den nicht besuchten teil: du hast das Feld in die Bereiche unterteilt die du brauchst. Dann schaust du wie sich die Gegner auf diese Flächen verteilen (ob in 1 oder 0er Bereiche). Naja, das wirds nicht rausreißen.
Die Flächen kannst du jetzt auch ganz leicht färben, weil du hast sie schon in Rechtecke unterteilt. Ich hoffe das war verstädlich ausgedrückt.
Ach ja.. Schief gehen tut das, wenn die linie sich kreuzt oder an sich selbst entlangläuft, aber das ist wahrscheinlich nicht erlaubt.
[edit]Wenn man nicht bis zum Rand auf einer Seite mit seinem Weg kommt, weil man vorher einen alten Weg getroffen hat, dann trennt man diesen alten Weg einfach an der Stelle auf, an der man ihn getroffen hat und läuft diesen weiter bis man an einer Seite ankommt und macht dann selbigen algorithmus wieder - es sollte dabei auch egal sein, ob man den alten Weg vorwärts oder rückwärts entlanggeht... Müsste also alles Klappen, wenn man alle Wege derart "erweitert" und sie so immer bis zu einem Rand führen.

Ich hab da noch ein bischen drüber nachgedacht. Wenn man mehr als einen Gegner hat, ist die Sache etwas komplizierter - am besten behält man dann die alten Gitterunterteilungen und merkt sich linien nur anhand ihrer Kanten. Nicht mehr gebrauchte Kanten (d.h. solche, die abgetrennte Bereiche nur von abgetrennten Bereichen trennen) entsorgt man dann am besten und die Wege zum Rand, wenn man eine Linie getroffen hat, muss man geschickt wählen. Aber ich will ja jetzt auch nicht zuviel verraten, wie ich das machen würde. Vielleicht fällt Dir ja noch was besseres ein als mir, aber im Bedarfsfall verrate ich auch gerne noch, wie mans machen könnte.

Hallo,

also ich habe bei wikipedia das hier gefunden (mit hübscher Animation) : Floodfill

Mal ausgehend davon, dass du eine Fläche mit einer Linie in zwei Flächen teilst :
Du wendest den Floodfill-Algorithmus zuerst ohne zu zeichnen an, um herauszufinden auf welchen Seiten sich Gegner befinden (im Hintergrund müssen sich Bitfelder oder ähnliches befinden)
Wenn du dann weisst auf welchen Seiten sich Gegner befinden (oder auch nicht), wendest du den Algorithmus entsprechend zum Füllen der Flächen an.

Viele Grüße
dj3hut1

Hmmm Floodfill wollt ich net benutzen. Ist bisl zu rekursionslastig. Ich hab nur ca. 200MHz und wenigAbeitsspeicher zur verfügung.

@Nico: Werd mal drüber nachdenken.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Hallo Flash,

ich habe Floodfill schon auf einem 386er ohne Probleme benutzt
Zur Not benutzt du deinen eigenen Stack, man kann ja alle rekursiven Algorithmen auch iterativ aufschreiben.

Viele Grüße
dj3hut1

Die Verbesserung dadurch hält sich aber in grenzen und Rechtecke kann man sehr leicht ausfüllen
@Flash: Man muss seine Linien auch gar nicht bis zum Rand fortsetzen. Das war ne seltsamer Schluss den ich da gestern gezogen habe. Geht einfacher, aber das Zerlegen der Welt in die beschriebenen Rechtecke ist tatsächlich höchst hilfreich bei der Überlegung und man bekommt die Sache dann auch ganz gut mit beliebig vielen Gegnern und der späteren Linienfühung unter Kontrolle.

Ich bin dem Problem erstmal aus dem Weg gegangen. Es hat zu lange aufgehalten. Ich werd darauf aber definitv nochmal zurückkommen (müssen).

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Anstelle des Stacks ist auch eine Queue möglich.