12.01.2011, 17:21
Hallo allerseits,
wer bei den Logic Masters 2009 dabei war, wird sich vermutlich an das dort zu lösende Kipplabyrinth erinnern. Man kann es übrigens im Trainingscamp downloaden.
Kurz zusammengefaßt: Auf einem ebenen Spielfeld mit einigen aufgeklebten, unbeweglichen Hindernissen befinden sich mehrere Blöcke, die jeweils durch Kippen parallel zu den Koordinatenachsen bewegt werden können. Ziel ist es, einen bestimmten Block in eine bestimmte Position zu befördern, wobei ein Hilfsblock mehrfach als Brücke dienen muß.
Um die Lösungen der LM-Teilnehmer zu überprüfen, hatte ich damals ein kleines Computerprogramm geschrieben, mit dem man die Lösungen sozusagen nachspielen kann. Mittlerweile habe ich einige Bugs beseitigt (die aber auf das Ergebnis 2009 keinen Einfluß hatten
) und das Programm erweitert - und jetzt stehe ich vor einem Problem, wo ich allein momentan nicht weiterkomme.
Und zwar geht es um die Frage der Stabilität. Nach jedem Zug soll überprüft werden, ob die erreichte Position physikalisch stabil ist oder ob einer der Blöcke umkippt. Bei den LM 2009 war das kein Problem, da die Blöcke alle quaderförmig waren und überstehende, also in der Luft hängende Teile ohnehin nicht erlaubt waren. Mittlerweile können die Blöcke mehr oder weniger beliebige Formen annehmen: jeder Block ist aus gleich großen Einzelwürfeln zusammengesetzt, wobei jeder Eckpunkt jedes Einzelwürfels ganzzahlige Koordinaten hat - weitere Bedingungen gibt es nicht.
Wann ein einzelner Block umkippt, weiß ich: nämlich wenn sich der Schwerpunkt außerhalb der konvexen Hülle der Auflagefläche befindet (wobei man immer senkrechte Projektionen auf die xy-Ebene betrachtet). Labile Gleichgewichte, wenn der Schwerpunkt genau auf dem Rand liegt, werden auch nicht zugelassen.
Soweit der einfache Teil.
Allerdings werden in den geplanten Labyrinthen häufig mehrere Blöcke interagieren, so daß ein Block (teilweise) auf einem anderen zu liegen kommt. Denkbar wäre auch, daß ein Block für sich allein betrachtet umkippen würde, aber an einen anderen stützenden Block angelehnt ist. Wie kann man dann möglichst allgemein herausfinden, ob eine bestimmte Lage stabil ist?
Ich hoffe, daß sich hier ein paar mathematisch/physikalisch gebildete Leute finden, die mir helfen können, einen brauchbaren Algorithmus zu finden...
wer bei den Logic Masters 2009 dabei war, wird sich vermutlich an das dort zu lösende Kipplabyrinth erinnern. Man kann es übrigens im Trainingscamp downloaden.
Kurz zusammengefaßt: Auf einem ebenen Spielfeld mit einigen aufgeklebten, unbeweglichen Hindernissen befinden sich mehrere Blöcke, die jeweils durch Kippen parallel zu den Koordinatenachsen bewegt werden können. Ziel ist es, einen bestimmten Block in eine bestimmte Position zu befördern, wobei ein Hilfsblock mehrfach als Brücke dienen muß.
Um die Lösungen der LM-Teilnehmer zu überprüfen, hatte ich damals ein kleines Computerprogramm geschrieben, mit dem man die Lösungen sozusagen nachspielen kann. Mittlerweile habe ich einige Bugs beseitigt (die aber auf das Ergebnis 2009 keinen Einfluß hatten
) und das Programm erweitert - und jetzt stehe ich vor einem Problem, wo ich allein momentan nicht weiterkomme.Und zwar geht es um die Frage der Stabilität. Nach jedem Zug soll überprüft werden, ob die erreichte Position physikalisch stabil ist oder ob einer der Blöcke umkippt. Bei den LM 2009 war das kein Problem, da die Blöcke alle quaderförmig waren und überstehende, also in der Luft hängende Teile ohnehin nicht erlaubt waren. Mittlerweile können die Blöcke mehr oder weniger beliebige Formen annehmen: jeder Block ist aus gleich großen Einzelwürfeln zusammengesetzt, wobei jeder Eckpunkt jedes Einzelwürfels ganzzahlige Koordinaten hat - weitere Bedingungen gibt es nicht.
Wann ein einzelner Block umkippt, weiß ich: nämlich wenn sich der Schwerpunkt außerhalb der konvexen Hülle der Auflagefläche befindet (wobei man immer senkrechte Projektionen auf die xy-Ebene betrachtet). Labile Gleichgewichte, wenn der Schwerpunkt genau auf dem Rand liegt, werden auch nicht zugelassen.
Soweit der einfache Teil.
Allerdings werden in den geplanten Labyrinthen häufig mehrere Blöcke interagieren, so daß ein Block (teilweise) auf einem anderen zu liegen kommt. Denkbar wäre auch, daß ein Block für sich allein betrachtet umkippen würde, aber an einen anderen stützenden Block angelehnt ist. Wie kann man dann möglichst allgemein herausfinden, ob eine bestimmte Lage stabil ist?
Ich hoffe, daß sich hier ein paar mathematisch/physikalisch gebildete Leute finden, die mir helfen können, einen brauchbaren Algorithmus zu finden...