Version vom 28. November 2012, 09:26 Uhr

Auf dieser Seite werde ich meine Artikel vorbereiten. Da sich diese in meinem Benutzernamensraum befindet, ist der vorhandene Inhalt nicht als Vollständig und nicht als Teil des Wikis anzusehen.

Drehung einer Geraden

Dieser Abschnitt ist eine Vorbereitung für die Kollisionserkennung zwischen einem Kreis und einer Geraden, unfertig und teilweise nur eine Nitoz für mich selbst.

senkrechte gerade, Kreis im Mittelpunkt
r > gx && -r < gx

senkrechte Gerade, Kreis verschoben
kx + r > gx && kx - r < gx
r > gx - kx && r < gx - kx

waagerechte Gerade, Kreis im Mittelpunkt
r > gy && -r < gy

waagerechte Gerade, Kreis verschoben
ky + r > gy && ky - r < gy
r > gy - ky && r < gy - ky


gedrehte Gerade
h = wurzel(a²+b²)
x1 < x2 && y1 < y2 || x1 > x2 && y1 > y2
    c = (y2 - y1) / h
    s = (x2 - x1) / h
    x' = x*c - y*s // senkrecht
x1 < x2 && y1 > y2 ||  x1 > x2 && y1 < y2
    c = (x2 - x1) / h
    s = (y1 - y2) / h
    y' = x*s + y*c // waagerecht

x' = x*cos(alpha) - y*sin(alpha)
y' = x*sin(alpha) + y*cos(alpha)

Spoiler Spoiler

Kollision zwischen zwei achsenausgerichteten Rechtecken

Die Prüfung einer Kollision zweier achsenausgerichteten (nicht rotierten) Rechtecken kann sehr effizient durchgeführt werden. Aufgrund der daraus r--Sacaldur 16:18, 23. Nov. 2011 (CET)esultierenden hohen Geschwindigkeit kann diese Prüfung komplexeren Prüfungen voran gestellt werden, um zu testen, ob zwei Objekte nah genug aneinander sind, damit eine Kollision möglich ist. Dazu testet man die sie umgebenden Rechtecke (Bounding Rectangles) auf Kollision.

Wenn mindestens eine Kante eines Rechtecks ein anderes Rechteck überschneidet, dann liegt eine Kollision vor. Es werden die Positionen der einzelnen Eckpunkte der Rechtecke benötigt. In den Implementierungsbeispielen werden Rechtecke durch die Position der linken oberen Ecke, die Breite und die Höhe beschrieben.

bool rectangleCollision(const Vector& position1, float width1, float height1,
                        const Vector& position2, float width2, float height2)
{
    return position1.x < position2.x + width2  &&
           position2.x < position1.x + width1  &&
           position1.y < position2.y + height2 &&
           position2.y < position1.y + height1;
}

bool rectangleCollision(Vector position1, float width1, float height1,
                        Vector position2, float width2, float height2)
{
    return position1.x < position2.x + width2  &&
           position2.x < position1.x + width1  &&
           position1.y < position2.y + height2 &&
           position2.y < position1.y + height1;
}

def rectangleCollision(position1, width1, height1, position2, width2, height2):
    return position1[0] < position2[0] + width2  and
           position2[0] < position1[0] + width1  and
           position1[1] < position2[1] + height2 and
           position2[1] < position1[1] + height1

boolean rectangleCollision(float[] position1, float width1, float height1,
                           float[] position2, float width2, float height2) {
    return position1[0] < position2[0] + width2  &&
           position2[0] < position1[0] + width1  &&
           position1[1] < position2[1] + height2 &&
           position2[1] < position1[1] + height1;
}

Tabellentest

geklaut von Wikipedia

minimalistisch

Tutorial: Reguläre Ausdrücke

Folgende kurze Anleitung habe ich bereits in einem Forum geschrieben und werde sie für das Wiki anpassen.

Reguläre Ausdrücke stellen ein weit verbreitetes Instrument zur Analyse von Zeichenketten dar. Mit ihnen lassen sich Zeichenketten auf bestimmte Inhalte Überprüfen oder Ersetzungen vornehmen. So ließe sich mit ihnen die Gültigkeit einer Eingabe, beispielsweise einer E-Mail Adresse oder einer IP-Adresse überprüfen.

Aufbau eines Regulären Ausdrucks

Die Bestandteile, aus denen ein regulärer Ausdruck bestehen kann, kann man in wenige Gruppen einteilen.

Zeichenliterale

Zeichen, die keine besondere Bedeutung haben, müssen genauso wie sie angegeben wurden auch in der Zeichenkette vorkommen. Zu diesen gehören beispielsweise die Buchstaben (von A bis Z in großer und kleiner Schreibweise) oder die Zahlen (0 bis 9).

Folgendes würde zutreffen, wenn abc enthalten ist:

abc

Platzhalter

Platzhalter symbolisieren das Vorhandensein eines anderen Zeichens. Nachfolgend eine Liste einiger Platzhalter. Der Slash (\) stellt in diesem Zusammenhang das Escape Zeichen dar, welches dem folgenden Zeichen eine andere Bedeutung gibt. Zeichen, die im Normalen Zusammenhang eine besondere Bedeutung haben, können mit Hilfe eines voran gestellten Slash dargestellt werden.

Nachfolgende eine Auflistung von wichtigen Platzhaltern.

Folgendes würde zutreffen, wenn eine Zahl, gefolgt von einem Buchstaben, gefolgt von abc enthalten ist:

\d\wabc

Anfang/Ende

Es gibt Symbole, die den Anfang und das Ende einer Zeichenkette darstellen und mit denen sich festlegen kann, dass ein bestimmter Inhalt am Anfang oder Ende stehen soll.

Folgendes trifft zu, wenn abc am Anfang steht:

^abc

Oder

Beim Oder, welches durch einen senkrechten Strich (|), auch Pipe genannt, dargestellt wird, muss nur der Ausdruck davor oder dahinter zutreffend sein.

Folgendes würde zutreffen, wenn abc oder eine Zahlen enthalten ist:

abc|\d

Gruppierung (Runde Klammern)

Runde Klammern gruppieren Zeichen. In neueren Implementierungen wird ein Vorkommen einer solche Gruppen gespeichert und kann für Ersetzungen verwendet werden. in den meisten Fällen wird \n oder $n verwendet, um auf die einzelnen Gruppen und somit auf die Treffer zuzugreifen, damit diese ersetzt werden können.

Folgendes würde zutreffen, wenn nach einer Zahl eine Zahl oder ein abc steht:

\d(\d|abc)

Zeichenauswahl (Eckige Klammern)

Aus den in eckigen Klammern angegebenen Zeichenliteralen oder Platzhaltern muss nur 1 Zeichen oder Platzhalter zutreffend sein.

Folgende Zeichen stellen eine Besonderheit dar:

Folgendes trifft bei 1 alphanumerischem Zeichen zu:

[0-9a-zA-Z]

Quantoren (Mengenangabe)

Quantoren sind Symbole zur Bestimmung der Häufigkeit. Sie stehen immer direkt hinter einem Zeichenliteral, einem Platzhalter, einer Zeichenklasse oder einer Gruppierung und geben für diesen die Häufigkeit an.

Beispiele

Im folgenden sind einige Beispiele für mögliche reguläre Ausdrücke aufgeführt, die die Kombinationsmöglichkeiten der verschiedenen Elemente eines regulären Ausdrucks demonstrieren sollen.

\d*

Dieser reguläre Ausdruck Trifft bei beliebig vielen Ziffern zu. Es handelt sich um eine sehr einfache Kombination eines Platzhalters mit einem Quantor. Wie man in der entsprechenden Übersicht sehen kann, repräsentiert \d eine beliebige Ziffer. Durch den * wird, wie in entsprechender Übersicht zu sehen, angegeben, dass dieses Zeichen beliebig oft vorkommen kann. Ein solcher regulärer Ausdruck wäre in der Praxis irelevant, da er immer zutreffen würde.

\d{3}$

Bei diesem Beispiel müssen am Ende der Zeichenkette genau 3 Ziffern stehen. Dass es Ziffern sein müssen, gibt das \d an, dass es exakt 3 sein müssen, gibt das {3} an und dass sie am Ende stehen müssen gibt das $ an, da sich dieses am Ende befindet.

^[^\.]*$

Dieser reguläre Ausdruck kann verwendet werden, wenn sich in einer Zeichenkette keine Punkte befinden dürfen. ^ und $ geben an, dass die gesamte Zeichenkette aus den dazwischen stehenden Symbolen bestehen muss. \. hebt die Wirkung des . auf, wodurch er an dieser Stelle als normaler Punkt dient. das ^ am Anfang der Eckigen Klammern negiert den Ausdruck, wodurch alle Zeichen gültig sind, abgesehen von den angegebenen, in dem Fall abgesehen von Punkten. Der Stern gibt an, dass diese Zeichen beliebig oft vorkommen dürfen. Dieses Beispiel ist aber nicht die einfachste Lösung für das Problem. Effizienter wäre es, zu überprüfen, ob sich in der Zeichenkette überhaupt Punkte befinden, was mit einem wesentlich einfacheren Ausdruck möglich ist.

\.+

Die Prüfung nach einzelnen Zeichen lässt sich teilweise viel schneller mit anderen Zeichenketten-Operationen durchführen. Sinn macht deswegen eine solche Prüfung eher, wenn mehrere verschiedene Zeichen nicht vorkommen dürfen und deswegen deren Vorhandensein geprüft werden muss.

^([-+]?[1-9]\d*|0)$

Mit diesem bereits sehr komplexen Ausdruck kann überprüft werden, ob es sich bei der Zeichenkette um eine gültige Ganzzahl (ohne Tausendertrennzeichen) handelt. ^ und $ bestimmen Anfang und Ende. In den runden Klammern befindet sich ein |, welches den Inhalt der Klammern in 2 Teile teilt. Die 0 ist ein normales Zeichenliteral und somit ist die einzige damit gültige Kombination eine 0. Die Andere Seite beginnt mit der Zeichenklasse [-+]?. Es darf ein - oder ein + einmal oder gar nicht vorhanden sein. Danach folgt die Zeichenklasse 1-9, welche alle Ziffern abgesehen von 0 zulässt. Dadurch wird sicher gestellt, dass die erste Ziffer keine 0 ist und somit werden führende Nullen vermieden. \d* steht für eine beliebige Anzahl weiterer Ziffern.

^([-+]?[1-9]\d*|0)([,\.]\d+)?$

Dieses Beispiel ermöglicht im Gegensatz zum letzten Beispiel zusätzlich Festkommezahlen. Dazu erweitert es das obere Beispiel um die Gruppierung ([,\.]\d+)? auf der rechten Seite. Sie beginntmit der Zeichenklasse [,\.], wodurch am Anfang der Gruppe ein Punkt oder ein Komma stehen muss. danach folgt mindestens 1 bis beliebig viele Ziffern. Durch das ? kann der gesamte Teil 1 Mal vorhanden sein oder entfallen.

^\d{3}\.\d{3}\.\d{3}\.\d{3}$

Dieser reguläre Ausdruck kann verwendet werden, um zu prüfen, ob es sich bei einer Zeichenkette um eine IPv4-Adresse handelt. Allerdings sind auch ungültige Adressen möglich, wie 342.68.001.3.

^(0|[1-9]\d?|1\d{2}|2[0-4]\d|25[0-5])\.(0|[1-9]\d?|1\d{2}|2[0-4]\d|25[0-5])\.(0|[1-9]\d?|1\d{2}|2[0-4]\d|25[0-5])\.(0|[1-9]\d?|1\d{2}|2[0-4]\d|25[0-5])$

Dieser reguläre Ausdruck hingegen prüft exakt, ob es sich um eine gültige IPv4 Adresse handelt. Der enorme Anstieg der Komplexität dürfte offensichtlich sein. Entsprechend rechenintensiv ist der Ausdruck bei einer Überprüfung im Gegensatz zu dem oberen, ungenauen Beispiel. Da die Bibliotheken für Netzwerkkommunikation in der Regel eine derartige Prüfung bereits mitliefern, die grundsätzlich schneller sein könnte, empfiehlt es sich, auf diese zurück zu greifen.

Ein praktikableres Beispiel wäre es, wenn in einem Spiel die Wahl des Namens einen Einfluss auf das Spielgeschehen hat. so könnte ein Name, der mit einem Buchtaben von A bis L beginnt andere folgen haben, als einer, der mit einem Buchstaben von M bis X beginnt.

^[a-lA-L]
^[m-xM-X]

Alternativ könnte im Quellcode des Spiel eine Fallunterscheidung vorgenommen werden, die in der Regel aber zu schwerer lesbarem Code führen würde.

Vorteile

• Reguläre Ausdrücke bilden eine vereinheitlichte Möglichkeit zur Überprüfung einer Zeichenkette auf bestimmte Inhalte und in Verbindung damit zum ersetzen von Teilen eines regulären Ausdrucks.
• Für sehr viele Programmiersprachen sind bereits Implementierungen vorhanden.
• Sie können ebenfalls zur Förderung der Übersichtlichkeit des Quelltextes eines Programms beitragen, da so komplexe Fallunterscheidungen oder andere Konstrukte zur Überprüfung erspart bleiben.
• Im Gegensatz zu derartigen Konstrukten können sie ebenfalls dynamisch verwendet werden, was bei der Spieleprogrammierung jedoch von geringerer Bedeutung sein sollte.

Nachteile

• Die Dauer der Auswertung einer Zeichenkette hängt von der Komplexität eines Ausdrucks ab. Wenn man nicht darauf achtet, die Ausdrücke so einfach wie möglich zu halten, können sie zu viel Rechenzeit für sich beanspruchen.
• Häufig gibt es bereits Implementierungen für die Üperprüfung von Zeichenketten für ganz bestimmte Zwecke, beispielsweise als IP-Adresse, welche in der Regel effizienter sein dürften, da sie sowohl präzise, als auch schnell sind.

Praktische Verwendungsmöglichkeiten

Wie bereits unter den Beispielen für den Aufbau regulärer Ausdrücke Erkennbar war gibt es kaum Verwendungszwecke für reguläre Ausdrücke in Spielen, die besonders häufig vorkommen. In den meisten Fällen wärend die Ausdrücke sehr primitiv gehalten und eine einfache Prüfung mit anderen Zeichenketten-Operationen könnte bereits ausreichend sein oder die Ausdrück werden zu kompliziert und sind deshalb anderen Mitteln, wie vorgefertigten Prüfungen unterlegen.

Bei der auswertung von Logdateien oder ähnlichen textuellen Dateien, die nach einem festen Muster aufgebaut sind, können reguläre Ausdrücke in Verbindung mit einer Skriptsprache, die diese bereits in sich integriert, ihre volle Stärke unter Beweis stellen. Die Struktur der Dateien lässt sich schnell in regulären Ausdrücken darstellen und mit einer Skriptsprache wie Perl lassen sich schnell Skripte schreiben, die die damit ausgewerteten Werte verarbeiten. Somit können reguläre Ausdrücke ein gutes Mittel bei der Entwicklung eines Programms, eines Spiels oder eines Plugins sein.

Gerade weil reguläre Ausdrücke weit verbreitet und einheitlich sind, bieten viele Entwicklungsumgebungen bei der Suche in den Dateien neben Wildcards die Möglichkeit, reguläre Ausdrücke zu verwenden. So kann man einfach alle Stellen im Programmcode finden, von denen aus eine Methode auf eine bestimmte Weise aufgerufen wird.

Genauigkeit von Zahlen