Schlagwort-Archive: Algorithmus

Aus der Kategorie „zu doof für Mathematik, aber intelligent genug um sich trotzdem was einfallen zu lassen“: Heute habe ich mir mal wieder ausgiebig meinen alten Quellcode für meine Spacola-Maussteuerung vom August 2010 angesehen und mich daher auch mal wieder ein bisschen mit den mathematischen Grundlagen (Trigonometrie und Vektorarithmetik) auseinandergesetzt. Ein wenig Schmunzeln musste ich über meine unkonventionelle Lösung eines alten Problems, das ich damals hatte.

Man nehme einen Mauszeiger, der irgendwo in einem karthesischen Koordinatensystem liegt. Nun musste ich herausfinden, welchen Winkel der Richtungsvektor Ursprung->Mauszeiger mit der Y-Achse einschließt. Da ich selten mit der Mathematik einer Meinung war, aber dafür umso mehr gewillt, diese Aufgabe von alleine zu lösen, nahm ich mir seinerzeit Papier und Bleistift zur Hand und fing damit an, mir eine Lösung zu überlegen. Und ich fand einen Algorithmus, mit dem ich den Winkel näherungsweise bestimmen konnte.

Aber zunächst zur idealen und simpelsten Lösung:

Man benötigt im Prinzip nur Delta X und Delta Y zwischen den beiden Punkten, also den Ortsvektor. Anschließend teilt man Delta Y durch den Betrag des Vektors und berechnet aus diesem Wert den Arkus-Kosinus. Das Ergebnis muss dann noch mit 360 multipliziert und wieder durch 2 Pi geteilt werden. Schnell und effizient. Ich bin kein Mathegott, aber ein paar Minuten Suchen hat mich auf die richtige Lösung gebracht.

Witzig fand ich dagegen meinen Algorithmus, der folgendermaßen aussieht:

Ich habe beliebig viele Punkte (im Extremfall 360 Stück, in meinem Fall aber nur 40) auf einem Einheitkreis um den Mittelpunkt generiert und von jedem dieser gedachten Punkte den Abstand zur Mauszeigerkoordinate bestimmt. Mein gedanklicher Ansatz war der, dass der Punkt, der den kürzesten Abstand zur Zielkoordinate hat, mehr oder weniger exakt denselben Winkel zur Y-Achse hat. Mit dem Vorteil, dass ich dessen Winkel (da selbst generiert) genau kannte. Anschließend habe ich noch eine merkwürdige Umrechnung vom Bogenmaß ins Gradmaß durchgeführt. Das Ergebnis war zufriedenstellend.

Für letzteres Codebeispiel schlagt mich bitte nicht. Ich wusste damals schon, dass das nur ein Provisorium ist. Ich weiß noch nicht einmal mehr wofür „targetCnt“ steht.

Zugegeben, meine Lösung ist extrem unperformant und relativ ungenau, aber nichts stärkt das Ego mehr als die Gewissheit, ein Problem selbst und ohne Hilfe bewältigt zu haben, wenn man es sich vorher nicht zugetraut hätte. Wie dem auch sei, heute habe ich meinen provisorischen Algorithmus abgelöst und durch die exakte Berechnung ersetzt.

Nur ein paar Wochen ist es her, als der neueste Titel aus dem Hause id Software, „Rage„, veröffentlicht wurde. Nun zeigt man sich dort großzügig: John Carmack, Mitgründer und Chefentwickler von id Software veröffentlichte gestern den Quellcode zum First-Person-Shooter „Doom 3„, den er zwischen 2000 und 2004 entwickelte. Nachdem es zuvor Befürchtungen gab, ein Teil des Algorithmus zur Schattenberechnung könne Patentrechtsklagen nach sich ziehen, setzte er sich kurzerhand noch einmal an sein betagtes Kultwerk und schrieb einen Workaround, der die als „Carmack’s Reverse“ bekannte Berechnungsweise ersetzt. Laut ihm seien nur eine Handvoll Zeilen bearbeitet worden.

Den Quellcode des in C++ geschriebenen Gruselshooters kann man auf der extra angelegten GitHub-Seite herunterladen. Das Paket ist 9,1 MB groß und umfasst – bis auf besagten Depth-Fail-Algorithmus – den gesamten Quellcode, der nötig ist, um eine ausführbare Datei zu erhalten. Spieldateien sind logischerweise nicht enthalten, da Doom 3 auch weiterhin nicht Freeware ist. Entpackt wiegen die Quelldateien ungefähr 35 MB. Für das Kompilieren wird Microsoft Visual Studio 2010 empfohlen. Das DirectX SDK ist zwingend erforderlich.

Carmack, der leider seit einigen Jahren Mitglied der Apple-Sekte … äh, Verzeihung, bekennender Apple-Sympathisant ist, hat sich mit Wolfenstein 3D, Doom und Quake einen Namen als inoffizieller Vater der First-Person-Shooter gemacht, obwohl er auch für sehr bekannte 2D-Jump’n’Run-Spiele wie Commander Keen verantwortlich ist. Das Spezialgebiet des genialen Spieleentwicklerveteranen sind Game-Engines – die meisten seiner Werke reizten die vorhandene Technik in jeder Hinsicht aus. Man schreibt ihm sogar zu, mitverantwortlich für die Verbreitung von Grafikbeschleunigerkarten Mitte bis Ende der 90er Jahre gewesen zu sein.

Persönlich halte ich die Veröffentlichung des Quellcodes von Doom 3 für einen ganz großen Gewinn, da die Technik hinter dem Spiel sich auch heute noch sehen lassen kann. Erwartungsgemäß werden sich fleißige und talentierte Programmierer finden, die sich den Quellcode vornehmen und ihn verbessern oder auf dessen Basis neue Spiele entwickeln. Carmack macht das einzig richtige in meinen Augen: Anstatt seine Arbeit vergammeln zu lassen, gibt er sie frei und macht sie für andere nutzbar. Wenn doch nur alle so denken würden.

Wann immer man sich bei Youtube ein Video ansieht, empfiehlt ein ausgeklügelter Algorithmus in der Seitenleiste rechts themenverwandte Videos. Das ist wirklich sehr nützlich, vor allem dann, wenn es zu einem Video mehrere Teile gibt, die man hintereinander anschauen sollte. So braucht man in den wirklich seltensten Fällen die Suchfunktion. Man kann sich wunderbar von Video zu Video klicken. So ein Algorithmus muss aus vielen einzelnen Faktoren berechnen, welche Videos denn eigentlich für einen Vorschlag in Frage kommen, schließlich will ich nichts über Rennwagen sehen, wenn ich gerade Tieraufnahmen von Eisbären betrachte. Wichtig sind Faktoren, anhand derer man eine Themenverwandtschaft feststellen kann.

Welche Faktoren würden hier Sinn ergeben? Erstens könnte Youtube schauen, ob es Videos mit möglichst vielen gleichen Tags oder zumindest themenverwandten Tags gibt. Zweitens könnte man prüfen, ob es in der Beschreibung Ähnlichkeiten gibt, bestimmte Stichwörter könnte man herauspicken und eine Übereinstimmung feststellen. Drittens und ebenfalls naheliegend ist das Vergleichen der Titel der Videos. Möglicherweise gibts ja zu diesem Video mehrere Teile, die man im System gruppieren sollte. Viertens wäre es außerdem logisch, nachzuschauen, ob derselbe Uploader vielleicht noch andere Videos hochgeladen hat, die dasselbe Thema haben. Soll ja in der Tat recht häufig vorkommen.

Ein Beispiel: Wenn ich mir also ein Video über Basketball anschaue, das „Basketball-Crap 2008“ heißt, es in der Beschreibung um Basketball und Crap geht, und auch die Tags alle irgendwas mit Basketball und Crap zu tun haben, dann wäre es doch eigentlich nur sinnvoll, wenn Youtube mir daneben andere Basketball-Videos empfiehlt, im Idealfall z.B. ganz oben auch die Videos „Basketball-Crap 2009“ und „Basketball-Crap 2010“ vom Youtube-Benutzer „basketballheinz0815“.

Geht Youtube so vor? Irgendwie nicht so wirklich. Youtube geht nämlich als allererstes danach, ob das Video viele Aufrufe hat. Wie wir alle wissen, ist natürlich allein die Zahl der Clicks ein brauchbares Maß für die Qualität eines Videos. Folglich muss ein Video mit sehr wenigen Aufrufen ziemlich scheiße sein, und so behandelt Youtube das Video auch: Es wird nämlich erst gar nicht empfohlen. Solange ein Video nicht beliebt genug ist, ist dem System völlig egal, ob die Tags, die Beschreibung und sogar der Titel weitestgehend identisch sind.

So verwundert es also nicht, dass ich bei jedem der inzwischen zehn hochgeladenen Videos über alte Songs der Gruppe „Gigas“ daneben meistens kein einziges anderes Gigas-Video empfohlen bekomme. Empfohlen werden mir Videos über Leguane, Final Fantasy, MegaMan Battle Network, Digimon, Resident Evil und viele weitere lustige Dinge, die weder was mit Gigas, noch mit Trance, noch überhaupt irgendwas mit Musik zu tun haben. Die Tags sind zu 99% identisch, die Beschreibung ist zu 99% identisch, der Titel ist zur Hälfte der gleiche. Wieso zeigt Youtube mir diese Videos nicht in der Seitenleiste an, obwohl sie ganz offensichtlich dazugehören? Wieso meint Youtube, mir irgendeinen Müll empfehlen zu dürfen, nur weil dieser Müll beliebter ist als die wirklich passenden Videos?

Bei der Suchfunktion derselbe Mist. Videos mit wenigen Clicks werden extrem stiefmütterlich behandelt und vom System so lange wie möglich versteckt. Sucht man nach „Gigas“ und „Trance“, bekommt man alle Ergebnisse, die mit „Giga“ (ohne S) und „Trance“ zu tun haben. Erst das neunte(!) Suchergebnis beinhaltet überhaupt beide Suchbegriffe. Ist nicht das wichtigste Kriterium für einen Treffer, dass die gesuchten Begriffe im Zusammenhang mit dem Video genannt werden? Nicht bei Youtube!

Nach einer etwas längeren Upload-Pause konnte ich mich heute dazu durchringen, drei Songs von Gigas bei Youtube hochzuladen: Zwei Stücke im Dream Progressive Trance-Stil und eines das mehr so in Richtung Jungle und DnB geht. Die Songs heißen „Virus„, „Emotional Vacancy“ und „Anadroid„.

Die Sammlung dürfte vermutlich in den kommenden Monaten komplett werden. Viel fehlt jedenfalls nicht mehr. Wie immer gilt: Wer die MP3-Dateien will, soll sich einfach bei mir melden. Interessanterweise hat Youtube bei „Anadroid“ einen „Treffer für die Inhalte Dritter“ gelandet, was ich mir so aber überhaupt nicht vorstellen kann. Youtube kennt sonst keinen einzigen der Gigas-Songs, wieso also ausgerechnet diesen? Zumal Gigas wirklich eine ziemlich unbekannte und zudem eine freie und unabhängige Band war. Da gibt es kein Label, das auf irgendwelche Urheberrechte pocht.

Der Youtube-Algorithmus zum Erkennen von urheberrechtlich geschützten Werken erscheint mir doch recht bedenklich, wenn ich davon ausgehe, dass ich nicht der einzige bin, bei dem Youtube einen Fehlalarm auslöst. Wie auch immer. Hier sind die Links:

Gigas – Anadroid
Gigas – Emotional Vacancy
Gigas – Virus