Iterieren über eine Liste in pseudozufälliger Reihenfolge, ohne eine gemischte Liste zu speichern
In einem Spiel verwenden wir eine Technik namens ' colour picking 'um Einheiten auszuwählen.
Dies bedeutet, dass jede sichtbare Einheit eine eindeutige Farbe erhält.
Hier ist ein Beispiel für eine Szene, die für die Farbauswahl gezeichnet wurde:
Da einige Benutzer über 16-Bit-Anzeigen verfügen, können diese Farben im Bereich 0..64K liegen.
Wenn wir den Einheiten jedoch inkrementelle Farben geben, z. unit0 ist 0, unitN ist N und die Farben sind für Menschen sehr schwer zu debuggen. Einheiten sind praktisch nicht unterscheidbar.
Wir möchten den Einheiten einzigartige und unverwechselbare Farben geben.
Wir erhöhen derzeit in einem festen Schritt einen binären Baum (C ++ map ), um die verwendeten Farben zu speichern, um nach Kollisionen zu suchen. Dies ist ein Leistungsproblem bei Low-End-Hardware. Selbst wenn dies eine Hash-Tabelle wäre und die Verwendung von string vermieden werden würde, ist die temporäre Speicherzuweisung in Spiel-Frames verpönt. Anstatt also den Code so zu optimieren, wie er ist, möchte ich herausfinden, ob es Möglichkeiten gibt, die vollständige Pflege einer Historie zu vermeiden.
Gibt es eine Möglichkeit, über die Zahlen 0..64K mit einem großen Schritt oder zufällig zu iterieren, so dass die meisten der 64K möglichen Werte verwendet werden und die Verwendung einer Historie von bereits zugewiesenen Farben zur Vermeidung von Kollisionen vermieden wird?
(Es ist so unwahrscheinlich, dass es mehr als 64K sichtbare Einheiten auf dem Bildschirm gibt, die wir in diesem Fall nicht behandeln müssen!)
5 Antworten
Mein Versuch:
- Wählen Sie eine Primzahl in der Nähe Ihres gewünschten Bereichs (64007 ist hier ein guter Kandidat).
- Finde das Wurzelmodulo p dieser Zahl.
-
Wählen Sie einen primitiven Stamm "mittlerer Reichweite" (
%Vor%4306243067 ist ein guter Kandidat).
Damit werden alle Zahlen im Bereich [1, 64007] genau einmal pseudozufällig zyklisch durchlaufen.
Können Sie einfach step_size verwenden, um die insgesamt verfügbaren Farben geteilt durch die Gesamteinheiten zu erhalten, und dann (unit_index * step_size) als Farbe für jede Einheit verwenden?
Sie könnten zum Beispiel die X / Y-Koordinaten der Einheiten so berücksichtigen, dass nahe beieinander liegende Koordinaten Farben mit hohem Kontrast erhalten, niedriger Kontrast nur bei Einheiten, die weit genug entfernt sind.
Eine erste Aufnahme könnte sein, ein einfaches Array a von 256 Farben zu haben, so dass zwischen a[n] und a[n+1] ein großer Kontrast besteht. Sie können dann die Farbe der Einheiten auswählen, indem Sie ihre X- und / oder Y-Koordinate modulo 256 als Index in das Array verwenden. Auf diese Weise erhalten Sie Farben, die für Einheiten, die mindestens 256 Pixel (oder eine andere Metrik, die Sie verwenden) verwenden, wieder verwendet werden, aber unterschiedliche Farben für Einheiten, die sehr nahe beieinander liegen.
Ich sehe das Problem nicht wirklich. Wie ich in den Kommentaren geschrieben habe, benötigen Sie nur 128K, um eine Permutation von [0..64K) zu speichern, und Sie benötigen keine Zuordnungen innerhalb der Hauptschleife. Hier ist ein statusbehafteter Farbspeicher in C ++ 11 (in älterem C ++ verwenden Sie vector oder new[] ):
Sie brauchen nur eine dieser Strukturen. Wenn Sie nun eine neue Einheit erstellen, rufen Sie next_color für ColorPicker auf und speichern Sie sie als Attribut auf der Einheit.
Diese Lösung wird die Farben durchlaufen. Wenn das nicht erwünscht ist, probiere jedes Mal, wenn der Index auf Null springt, random_shuffle .
Verwenden Sie zunächst binär, um Farbzustände zu speichern (1-used, 0-unused). 2 ^ 16 = 65536 (Zustände). Wenn wir 1 Bit für eine Farbe verwenden, werden 65536/8 = 8192 Bytes benötigt.
Die nächste Frage ist, wie diese Bytes zu verwalten sind. Ich schlage eine Baumstruktur vor: auf diesen 8192 Bytes werden andere (8192/8 =) 1024 Bytes benötigt, jedes Bit in diesen oberen Bytes repräsentiert ein Byte in 8192 Bytes, wenn eines der unteren Bytes ALL ist 1, ist sein oberes Bit 1.
Diese Regel kann nach oben und nach oben erweitert werden: 8192 - & gt; 1024 - & gt; 128 ... zuletzt auf 1 Byte (nicht vollständig verwendet).
Um diese Struktur zu verwenden, können Sie eine Zufallszahl in 0, 7 für viele Male generieren. Wenn das Bit des Basisbytes 1 ist, versuchen Sie es erneut. Wenn sie 0 ist, bis zum unteren Byte, wiederholen Sie diese Aktion, bis das niedrigste Byte erreicht ist.
Darüber hinaus können Sie diese Struktur in einem Array erstellen: genau wie der Heap in Heapsort. (mit einigen leeren Einheiten).
APPEND: Ein Int16 ist für eine Farbe erforderlich, einmal bis zu einem niedrigeren Byte, erhalten Sie eine Drei-Bit-Binärzahl, hängen Sie sie von links nach rechts an die Farbnummer an: int16. (Das Root-Byte repräsentiert nur 2 Zustände und erzeugt nur 1-Bit-Binärzahl, seine Form ist 111111 ??.