Beiträge von Janhektor

    Abhängig von deinen Informatikkenntnissen und Aufwand, den du betreiben möchtest, lässt sich auch schwereres Gerät auffahren: R-Bäume. Damit lässt sich das Problem besonders für viele Regionen und Spieler sehr effizient lösen.


    Edit: Du kannst auch Segment Trees benutzen und damit im Worst-Case eine (poly-) logarithmische Laufzeit garantieren. Hier habe ich im Gegensatz zu R-Bäumen auch etwas Erfahrung und könnte dir Quellcode schicken oder beim Implementieren helfen, falls du daran Interesse hast.

    Möchtest du einen 3D Raum behandeln: "distance" benutzen.
    Möchtest du einen 2D Raum behandeln: "distanceSquared" benutzen.

    Wie kommst du darauf?


    Beide Funktionen berechnen die Entfernung bzw. den euklidischen Abstand im R^3. Der Unterschied ist, dass Location#distanceSquared auf die rechenintensive Berechnung der Quadratwurzelfunktion verzichtet.

    Stimmt, geht aber trotzdem ohne Array mit Zuweisungen.


    Die Implementierung ist natürlich dir überlassen. Ich spreche das lediglich aus dem Grund an, dass es mich beim Lesen des Codes stutzig machte und sehr nach einem Workaround aussieht.

    Gut, das lässt sich beheben.


    Du generierst den Mittelpunkt des neuen Raums vor der while-Schleife. Kommt es dann zu einer Kollision, wird kein neuer Mittelpunkt berechnet, sondern mit dem alten Wert fortgefahren. Dadurch kommt es in einer Endlosschleife immer wieder zu einer Kollision, weil der Ort nicht geändert wird.


    Zudem ein Tipp: Um zu überprüfen, ob der Abstand mindestens 15 Blöcke beträgt, kannst du einfach den euklidischen Abstand ausrechnen. Sind (x, y, z) und (x', y', z') die Mittelpunkte, dann ist d = sqrt((x - x')^2 + (y - y')^2 + (z - z')^2) der euklidische Abstand. Überprüfe einfach, ob d >= 15 gilt. Um die Berechnung der Wurzel zu vermeiden, kannst du auch d^2 >= 15^2 überprüfen, ist effizienter. Das reduziert den Check auf 1-2 Zeilen Code.

    Sehr gut.


    Um die Orte der Räume zufällig zu wählen, musst du natürlich einen Bereich festlegen. Wir gehen mal davon aus, dass der Bereich groß genug ist, sodass dort deutlich mehr Räume hineinpassen als du generierst.


    Deine Idee, die bereits generierten Räume durchzuloopen, ist zielführend. Du kannst z.B. so vorgehen:

    1. Wähle einen zufälligen Ort aus (der Mittelpunkt M des neuen Raums)
    2. Loope durch alle Räume und berechne jeweils den Abstand des Mittelpunkts zu M
    3. Falls es in 2.) vorkommt, dass der Abstand < 15 ist, gehe zu Schritt 1.
    4. Falls 3.) nicht zutrifft, generiere den Raum und füge ihn zur Liste der Räume hinzu.

    Was beim Sprung von 3.) zu 1.) passiert, ist eine Kollision. Je nach Größe des Bereichs, in dem Räume generiert werden, und Anzahl bereits generierter Räume kommen Kollisionen selten oder häufiger vor. Das wird jedoch sehr wahrscheinlich kein Problem sein: Selbst wenn die Hälfte der Orte bereits blockiert ist (da Räume in der Nähe sind), wirst du nur mit einer extrem (!) geringen Wahrscheinlichkeit mehr als 25-mal Schritt 1 ausführen müssen, im Durchschnitt nur 1-2 mal.


    Weißt du, wie 2.) funktioniert?

    Dein Ziel ist nicht ganz klar. Es gibt mindestens zwei Fragen:

    • Was sind Räume? Verstehst du darunter die (Cuboid-) Region selbst oder eine bestimmte Anordnung von Blöcken und welche?
    • Du möchtest offenbar mehrere Räume generieren. Es gibt unendlich viele Möglichkeiten, das zu tun. Es ist kein Problem dafür zu sorgen, dass die Mittelpunkte einen bestimmten Mindestabstand zueinander haben. Die Frage ist jedoch, wie du dir die Anordnung der Räume vorstellst (z.B. in einem Gitter, in einem großen Ring, willkürlich, ...). Mit der Information ist es wahrscheinlich möglich, einen Algorithmus zu entwickeln.

    Eine präzise Beschreibung oder eine Skizze hilft hier nicht nur ungemein, sondern ist erforderlich.

    Falls dir ein Int-Random zur Verfügung steht und dir etwas Präzision genügt (z.B. auf % genau, aber auch 8 Nachkommastellen sind in Ordnung), hat Kronos197 eine sehr gute Methode beschrieben: Skaliere alle Werte mit einem Faktor, sodass sie ganzzahlig sind, siehe auch dieser Beitrag.


    Es gibt jedoch eine Methode, die dir beliebige (!) Genauigkeit erlaubt (rationale Zahlen sogar exakt) und mit einem Boolean-Random auskommt. Mit anderen Worten: Du kannst mit einer bloßen Münze (50/50-Wahrscheinlichkeit) jede beliebige Wahrscheinlichkeit (z.B. 1/7) exakt simulieren, erkaufst dir die Genauigkeit aber (recht billig bzw. mit extrem wenig) mit Laufzeit.


    Gehe dazu wie folgt vor. Die Zielwahrscheinlichkeit sei p/q (z.B. p = 1, q = 25 für 4%). Jetzt findest du das kleinste k, sodass 2^k >= q gilt (kannst du z.B. sehr schnell binary searchen, aber einfaches Durchtesten reicht auch). Dann lässt du den Zufallsgenerator k Booleans generieren (du wirfst k Münzen), interpretierst das Ergebnis als Binärzahl x (*) und entscheidest auf der Grundlage:

    • 0 <= x < p: Antworte "Ja"
    • p <= x < q: Antworte "Nein"
    • q <= x < 2^k: Wiederhole die gesamte Prozedur

    Man kann beweisen, dass die Antwort "Ja" exakt mit der Wahrscheinlichkeit p/q rauskommt und "Nein" mit 1 - p/q. Außerdem ist in jedem Durchlauf die Wahrscheinlichkeit für q <= x < 2^k höchstens 1/2, sodass das Verfahren mit Wahrscheinlichkeit 1/2 nur einen Durchlauf, mit Wahrscheinlichkeit 1/4 zwei Durchläufe, mit Wahrscheinlichkeit 1/8 Durchläufe usw. benötigt. Es ist extrem unwahrscheinlich, dass z.B. 50 Durchläufe stattfinden (Wahrscheinlichkeit ist ca. 1 zu 1 Billiarde) und dafür hast du ein exaktes Ergebnis ;)


    (*) Jeder Boolean / jede Münze entspricht einem Bit und die Reihenfolge ist egal. Es ist auch nicht ineffizient, den Zufallsgenerator k-mal auszuführen, weil k sehr klein ist.

    Vorweg: Brauchst du einen exakten Algorithmus oder genügt eine approximative Lösung?


    Ich mache nachfolgend mehrere Vorschläge und nähere mich deinem Problem in kleinen Schritten, erwarte also nicht gleich die Komplettlösung.


    Kürzeste Wege. Der Dijkstra-Algorithmus aus dem Lehrbuch löst das folgende Problem:

    • Gegeben: Ein (un)gerichteter Graph mit nichtnegativen Kantengewichten und ein Startknoten
    • Gesucht: Kürzeste Entfernungen zu allen Knoten als Summe von Kantengewichten ausgehend vom Startknoten und Kürzeste-Wege-Baum (Vorgängerinformationen)

    Je nach Implementierung kriegst du quadratische oder linear-logarithmische Laufzeit in der Anzahl der Knoten. In manchen Spezialfällen (z.B. alle Kantengewichte ganzzahlig) gibt es Modifikationen mit asymptotisch besserem Laufzeitverhalten. Falls alle Kantengewichte identisch sind, genügt eine Breitensuche.


    Knotengewichte. Falls es zusätzlich zu den Kantengewichte noch Knotengewichte gibt (es entstehen also Kosten für Knoten auf einem Weg), dann hilft folgender Trick: Splitte jeden Knoten in zwei Knoten A und B. Alle eingehenden Kanten verlaufen zu Knoten A und alle ausgehenden Kanten gehen von Knoten B aus. Zwischen A und B existiert genau eine Kante mit den gewünschten Knotengewicht. Damit ist das Problem auf das Kürzeste-Wege-Problem reduziert und kann mit dem Dijkstra-Algorithmus wie gewohnt gelöst werden.


    Verschiedene Linien. Jede Linie deckt wie in deinem Bild einen bestimmten Teilmenge von Knoten ab. Dann kannst du probieren, einen neuen Graph mit dem kartesischen Produkt aus der Knotenmenge und der Menge der Linien zu bauen. In diesem Graph werden zwei Knoten miteinander verbunden, wenn der Knoten aus der ursprünglichen Knotenmenge übereinstimmt (Umsteigen) oder wenn die Linie übereinstimmt und zwischen den Knoten verläuft. Die Kantengewichte zwischen zwei Knoten mit demselben Knoten im Ursprungsgraph sind 0 (oder eine gewünschte Umsteigezeit) und alle anderen Kantengewichte wie im Ursprungsgraph die Weglängen. Wieder ist das Problem auf das Kürzeste-Wege-Problem reduziert.


    Uhrzeiten. Falls die Minute als kleinste Zeiteinheit genügt, kannst du wieder einen neuen Graph bauen und für jeden Knoten 1440 Knoten für jede Minute am Tag erzeugen. Pro Knoten gibt es zwischen den 1440 Knoten paarweise Kanten (das entspricht im gerichteten Fall über 1 Million Kanten!) und zu anderen Knoten entsprechend der Abfahrts- und Ankunftszeiten Kanten. Der Graph wird dadurch extrem groß, aber bei recht wenigen Knoten oder größeren Zeitschritten oder keinen Nachtfahrten oder periodischen Fahrplänen lässt sich die Größe stark reduzieren.


    Mehrere kurze Wege. Um nicht nur den kürzesten Weg, sondern auch den zweitbesten, drittbesten, ... Weg zu finden, gibt es auch Modifikationen vom Dijkstra-Algorithmus. Ich verweise mal auf diesen Wikipedia-Eintrag, vielleicht ist das hilfreich.


    Mehrere Anfragen von unterschiedlichen Startknoten. Falls man nicht immer vom gleichen Ort startet, braucht man Kürzeste-Wege-Informationen von mehreren (allen) Startknoten ausgehend. Hält sich die Anzahl solcher Anfragen in Grenzen, kannst du den Dijkstra-Algorithmus einfach mehrfach anwenden. Möchtest du aber für alle Paare von Knoten die kürzesten Entfernungen (und ggf. zugehörige Wege) berechnen, gibt es schnellere Lösungen, z. B. den sehr einfach und in wenigen Zeilen zu implementierenden Algorithmus von Floyd-Warshall. Im Prinzip berechnest du die transitive Hülle mit Kantengewichten, ggf. für jede mögliche Startuhrzeit eine eigene.


    Und zum Schluss noch ein allgemeiner Hinweis: Für solche komplexen Optimierungsprobleme ist lineare Programmierung durchaus einen Versuch wert. Für das Kürzeste-Wege-Problem gibt es eine Formulierung als lineares Programm und der Vorteil ist, dass sich lineare Programme in der Regel sehr leicht modifizieren lassen (Hinzufügen neuer Nebenbedingungen). Falls du keine ganzzahligen Lösungen brauchst, gibt es sogar Algorithmen mit Effizienzgarantie.


    Zögere nicht, Verständnis- und Rückfragen zu stellen.


    Viel Erfolg beim Lösen des Problems!

    Aber sobald zu versucht etwas zu programmieren unterscheidet sich C++ auf jeder Plattform.

    Nein. Nicht nur die Syntax ist überall gleich, sondern auch die Semantik.



    Allein schon die primitiven Datentypen sind nicht auf jeder Plattform gleich

    Doch. Sie sind lediglich unterschiedlich implementiert und wenn sie sich tatsächlich unterscheiden, dann nur in Aspekten, die der Standard nicht vorgibt.


    Die Standardbibliothek liefert jeder Compiler mit und es ist natürlich richtig, dass sie sich unterscheidet (genauer: ihre Implementierung). Auf Anwenderebene spielt das aber keine Rolle, du kannst z.B. die ganzen Container (vector, set, queue, ....) auf allen Plattformen mit exakt dem gleichen Quellcode nutzen.

    Du kannst ja mal einen möglichst kleinen Brainfuck-Interpreter in Brainfuck schreiben WolverinDEV .

    Interessant wäre mal, wie viele Zeichen man für den kleinstmöglichen Brainfuck-Interpreter braucht.

    Oder ein Brainfuck-Programm, das für ein anderes Brainfuck-Programm entscheidet, ob es ein Brainfuck-Interpreter ist (das sollte unmöglich sein, Rice lässt grüßen).

    im Gegensatz zu Java oder PHP ist C/C++ sehr System abhängig

    C++ ist eine standardisierte Programmiersprache, die komplett unabhängig von irgendwelchen Betriebssystemen ist. Jeder vernünftige (im Sinne von: dem Standard genügende) Compiler implementiert den gleichen Sprachkern. Allerdings bringt der Sprachkern allein in der Praxis wenig, sodass Bibliotheken benötigt werden, die natürlich plattformabhängig sein können. Auch ein kompiliertes Programm kann nicht auf jeder Plattform ausgeführt werden. Aber es gibt durchaus Programme, die jeder Compiler ohne Anpassungen kompiliert und die dadurch ohne Mehraufwand auf jeder Plattform ausführbar sind.


    Ich weise auf den Unterschied hin, weil Clime im Startpost keinen speziellen Anwendungsbereich erwähnt, sondern einen allgemeinen Einstieg wünscht. Da gehören natürlich auch Programme dazu, die sich ausschließlich des Sprachkerns oder nur plattformunabhängiger Bibliotheken bedienen. Um die Sprache an sich zu lernen, ist dies sogar ausreichend. Zum Beispiel könnte ich meine ersten C++-Programme vom alten Windows-Rechner jetzt problemlos unter Linux kompilieren.

    Wie das Kommentar dort schon sagt, sind diese Verzweigungen für ein Nicksystem gedacht. An sich gibt es im Plugin noch kein Nicksystem, da ich das Plugin für beliebige Systeme kompatibel halten möchte

    Das ist sicher eine gute Grundhaltung in der Softwareentwicklung, aber der falsche Weg der Umsetzung. Java ist eine objektorientierte Programmiersprache und ermöglicht dir sehr große Flexibilität ohne unzählige Verzweigungen. Bei Modellierungsfragen gibt es viele hilfreiche Design Patterns, wozu Nathalie0hneHerz hier so viele Lexikon-Einträge veröffentlicht hat, dass der Tag "Design Patterns" in der Wolke der größte ist.


    In den meisten Fällen wirst du mit etwas Erfahrung wissen, wie du deine Ideen in ein Programm übersetzt. Es gibt jedoch auch Fälle, in denen man eine sehr gute Idee oder sehr viel Erfahrung braucht, um eine elegante Implementierung hinzukriegen. Da ist es äußerst hilfreich, einige grundlegende Design Patterns zu kennen, insbesondere um Code-Redundanz zu vermeiden.

    Ich habe einen Verbesserungsvorschlag für den Interpreter.


    In deiner Implementierung der eckigen Klammern bzw. Schleifen suchst du in den Methoden searchForOpeningBracket() und searchForClosingBracket() jedes Mal aufs Neue die Klammern – auch dann, wenn ein und dieselbe Schleife über Tausende Iterationen ausgeführt wird! Dadurch entsteht das merkwürdige Verhalten, dass beim Übergang zwischen zwei Schleifendurchläufen ein rechenintensiver Schritt kommt, dessen Dauer linear in der Anzahl Quellcodezeichen (!) im Rumpf der Schleife ist.


    Daher mein Vorschlag: Lies das Programm in einer Vorverarbeitung Zeichen für Zeichen und nutze einen Stack – der ist die perfekte Datenstruktur für solche Zwecke! Wenn du eine öffnende Klammer liest, schreib den Index auf den Stack. Wenn du eine schließende Klammer liest, nimm den obersten Eintrag vom Stack ("pop") und ordne ihn der Klammer zu. Wenn du das Programm dann interpretierst, kannst du bei einer geschlossenen Klammer bequem den Index (= Rücksprungadresse) der zugehörigen öffnenden Klammer auslesen und in konstanter Zeit zurückspringen.


    Viel Spaß mit dem Projekt!

    Ein sprachlicher Tipp, um mögliche Missverständnisse zu vermeiden: Ist dir klar, was eine Kodierung bzw. Codierung ist? Tatsächlich bezeichnet man so i.d.R. diesen Code, du meinst aber offensichtlich Quellcode!


    Natürlich ist hier aus dem Zusammenhang klar, was du meinst. Das muss aber nicht immer so sein und dann ist Quellcode oder einfach Code präziser bzw. führt nicht zur Verwirrung.

    Eine Queue ist vielseitiger als man ihr zunächst ansieht. Neben Anwendungen, in denen die Warteschlange offensichtlich ist ( Luca Feger nennt Support-Warteschlangen), ein paar Beispiele aus der Informatik:

    • Breitensuche: Die Queue wird zum Speichern der abzuarbeitenden Knoten des Graphen verwendet. Mit der Breitensuche findest du kürzeste Wege in ungewichteten Graphen.
    • Dijkstra-Algorithmus: Kürzeste Wege in Graphen mit nichtnegativen Kantengewichten, die Queue ist hier eine Prioritätswarteschlange (meistens Array oder Binomialheap), in ihr werden abzuarbeitende Knoten gespeichert und immer der Knoten mit der geringsten Entfernung zum Startknoten gewählt.
    • Algorithmus von Prim: Berechnung minimaler Spannbäume. Die Queue ist auch hier eine Prioritätswarteschlange und wird ähnlich wie beim Dijkstra-Algorithmus eingesetzt.
    • Konstruktion von Huffman-Bäumen: Entropiekodierung. Man kann die Queue benutzen, um in jeder Iteration zwei Knoten mit möglichst geringen Wahrscheinlichkeiten zu wählen.

    Es gibt natürlich noch mehr Anwendungen. Die letzten drei Beispiele sind übrigens sämtlich Greedy-Algorithmen, die ihre lokal beste Wahl über die Queue treffen.

    Zeichne dir ein Rechteck und einen Punkt auf. Welche Bedingungen müssen die Koordinaten des Punkts erfüllen, damit der Punkt im Rechteck liegt? Ich mache mal den Anfang:

    • Der Punkt muss rechts von der linken Seite des Rechtecks liegen
    • Der Punkt muss links von der rechten Seite des Rechtecks liegen

    Mit links und rechts sind hier natürlich negative bzw. positive x-Richtung im kartesischen Koordinatensystem gemeint. Zwei Bedingungen fehlen noch. Kannst du ergänzen?


    Dann probiere mal, das in Programmcode umzusetzen!

    Hey,


    wir verschieben die Items zunächst zyklisch, wie du forderst. Ein Schritt besteht darin, alle Items um eine Position nach links/rechts zu verschieben und das letzte Items an den Anfang zu setzen. Ein Zyklus besteht aus so vielen Schritten wie Items. Führt man einen Zyklus aus, dann wird wieder der Startzustand erreicht, also die Reihenfolge vom Anfang. Die Geschwindigkeit ist einfach die Zeit zwischen zwei aufeinanderfolgenden Schritten, die kannst du ja beliebig anpassen.


    Um den "Glücksspiel-Effekt" zu induzieren, führen wir einfach paar Zyklen aus. Danach machen wir einen unvollständigen Zyklus. Die Items seien zur Vereinfachung durchnummeriert: 0, 1, 2, 3, ..., n - 1 (n ist die Anzahl der Items). Jetzt zu den Wahrscheinlichkeiten. Die Wahrscheinlichkeit, dass Item i gewählt wird, soll p(i) sein (für i = 0, 1, 2, 3, ..., n - 1). In unserem unvollständigen Zyklus machen für nun mit der Wahrscheinlichkeit p(i) genau i Schritte und sind fertig.


    Wie ermitteln wir effizient die Schrittzahl i mittels Zufallsgenerator? Das habe ich in diesem Post schon mal erklärt. Kurz: Du legst entsprechend der Wahrscheinlichkeiten eine disjunkte Zerlegung des Intervalls [0; 1) fest und ziehst zufällig und gleichverteilt eine Zufallszahl aus diesem Intervall. Diese liegt in einem Teilintervall, das du bestimmst. Daraus kannst du auf die Anzahl der Schritte rückschließen.


    Ergänzung zum Zufallsgenerator. Du hast eine Zerlegung des Intervalls und kannst die Teilintervalle nummerieren. Es ist nicht sofort klar, wie man aus der Zufallszahl die Nummer des Teilintervalls, in dem sie liegt, ermittelt. Die einfachste Methode iteriert über alle Teilintervalle und prüft, ob die Zufallszahl im jeweiligen Teilintervall enthalten ist. Das funktioniert einwandfrei und ist einfach zu implementieren. Für deine Anwendung ist der Ansatz absolut zufriedenstellend, aber ich möchte zur Vollständigkeit erwähnen, dass du das Intervall auch mit einer binären Suche in Zeit O(log(n)) statt O(n) finden kannst, was sehr vielen Teilintervallen auch in der Praxis effizienter ist.


    Ich hoffe, das hilft dir und du bekommst das selbst programmiert. Falls nicht, frag einfach nicht.


    Viel Erfolg!