Dirty rect & UI features

- dirty rectangle (and the math library thereof)
  - drawing it
- no more std::vector in Sandbox
- single step
- cycle counter display

5 files changed, 334 insertions, 30 deletions

diff --git a/src/common.hpp b/src/common.hpp
index 1c64c34..e745ece 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -7,5 +7,42 @@
 // clang-format on
 
 struct Pt {
-    int x, y;
+    int x{}, y{};
+
+    Pt operator+(Pt o) const { return { x + o.x, y + o.y }; }
+    Pt operator-(Pt o) const { return { x - o.x, y - o.y }; }
+    Pt operator*(int k) const { return { x * k, y * k }; }
+    Pt operator/(int k) const { return { x / k, y / k }; }
+    bool operator==(const Pt&) const = default;
 };
+
+// avoid including <algorithm>
+#define MMIN(x, y) ((x) < (y) ? (x) : (y))
+#define MMAX(x, y) ((x) > (y) ? (x) : (y))
+inline Pt pt_min(Pt a, Pt b) {
+    return Pt{ MMIN(a.x, b.x), MMIN(a.y, b.y) };
+}
+inline Pt pt_max(Pt a, Pt b) {
+    return Pt{ MMAX(a.x, b.x), MMAX(a.y, b.y) };
+}
+#undef MMIN
+#undef MMAX
+
+struct Rect {
+    Pt bl, tr;
+
+    Rect() {}
+    Rect(Pt tl, Pt br)
+        : bl(tl), tr(br) {}
+    Rect(int x0, int y0, int x1, int y1)
+        : bl(x0, y0), tr(x1, y1) {}
+
+    bool operator==(const Rect&) const = default;
+};
+
+inline Rect rect_union(Rect a, Rect b) {
+    return Rect(pt_min(a.bl, b.bl), pt_max(a.tr, b.tr));
+}
+inline Rect rect_union(Rect a, Pt b) {
+    return Rect(pt_min(a.bl, b), pt_max(a.tr, b));
+}
diff --git a/src/rand/pcg.hpp b/src/rand/pcg.hpp
new file mode 100644
index 0000000..8e74d11
--- /dev/null
+++ b/src/rand/pcg.hpp
@@ -0,0 +1,207 @@
+/*
+ * Tiny self-contained version of the PCG Random Number Generation for C++
+ * put together from pieces of the much larger C/C++ codebase.
+ * Wenzel Jakob, February 2015
+ *
+ * The PCG random number generator was developed by Melissa O'Neill
+ * <[email protected]>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * For additional information about the PCG random number generation scheme,
+ * including its license and other licensing options, visit
+ *
+ *     http://www.pcg-random.org
+ */
+
+#pragma once
+
+#define PCG32_DEFAULT_STATE 0x853c49e6748fea9bULL
+#define PCG32_DEFAULT_STREAM 0xda3e39cb94b95bdbULL
+#define PCG32_MULT 0x5851f42d4c957f2dULL
+
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <cstdint>
+
+/// PCG32 Pseudorandom number generator
+struct Pcg32 {
+    /// Initialize the pseudorandom number generator with default seed
+    Pcg32() : state(PCG32_DEFAULT_STATE), inc(PCG32_DEFAULT_STREAM) {}
+
+    /// Initialize the pseudorandom number generator with the \ref seed() function
+    Pcg32(uint64_t initstate, uint64_t initseq = 1u) { seed(initstate, initseq); }
+
+    /**
+     * \brief Seed the pseudorandom number generator
+     *
+     * Specified in two parts: a state initializer and a sequence selection
+     * constant (a.k.a. stream id)
+     */
+    void seed(uint64_t initstate, uint64_t initseq = 1) {
+        state = 0U;
+        inc = (initseq << 1u) | 1u;
+        next_u32();
+        state += initstate;
+        next_u32();
+    }
+
+    /// Generate a uniformly distributed unsigned 32-bit random number
+    uint32_t next_u32() {
+        uint64_t oldstate = state;
+        state = oldstate * PCG32_MULT + inc;
+        uint32_t xorshifted = (uint32_t)(((oldstate >> 18u) ^ oldstate) >> 27u);
+        uint32_t rot = (uint32_t)(oldstate >> 59u);
+        return (xorshifted >> rot) | (xorshifted << ((~rot + 1u) & 31));
+    }
+
+    /// Generate a uniformly distributed number, r, where 0 <= r < bound
+    uint32_t next_u32(uint32_t bound) {
+        // To avoid bias, we need to make the range of the RNG a multiple of
+        // bound, which we do by dropping output less than a threshold.
+        // A naive scheme to calculate the threshold would be to do
+        //
+        //     uint32_t threshold = 0x100000000ull % bound;
+        //
+        // but 64-bit div/mod is slower than 32-bit div/mod (especially on
+        // 32-bit platforms).  In essence, we do
+        //
+        //     uint32_t threshold = (0x100000000ull-bound) % bound;
+        //
+        // because this version will calculate the same modulus, but the LHS
+        // value is less than 2^32.
+
+        uint32_t threshold = (~bound + 1u) % bound;
+
+        // Uniformity guarantees that this loop will terminate.  In practice, it
+        // should usually terminate quickly; on average (assuming all bounds are
+        // equally likely), 82.25% of the time, we can expect it to require just
+        // one iteration.  In the worst case, someone passes a bound of 2^31 + 1
+        // (i.e., 2147483649), which invalidates almost 50% of the range.  In
+        // practice, bounds are typically small and only a tiny amount of the range
+        // is eliminated.
+        for (;;) {
+            uint32_t r = next_u32();
+            if (r >= threshold)
+                return r % bound;
+        }
+    }
+
+    /// Generate a single precision floating point value on the interval [0, 1)
+    float next_f32() {
+        /* Trick from MTGP: generate an uniformly distributed
+           single precision number in [1,2) and subtract 1. */
+        union {
+            uint32_t u;
+            float f;
+        } x;
+        x.u = (next_u32() >> 9) | 0x3f800000u;
+        return x.f - 1.0f;
+    }
+
+    /**
+     * \brief Generate a double precision floating point value on the interval [0, 1)
+     *
+     * \remark Since the underlying random number generator produces 32 bit output,
+     * only the first 32 mantissa bits will be filled (however, the resolution is still
+     * finer than in \ref nextFloat(), which only uses 23 mantissa bits)
+     */
+    double next_f64() {
+        /* Trick from MTGP: generate an uniformly distributed
+           double precision number in [1,2) and subtract 1. */
+        union {
+            uint64_t u;
+            double d;
+        } x;
+        x.u = ((uint64_t)next_u32() << 20) | 0x3ff0000000000000ULL;
+        return x.d - 1.0;
+    }
+
+    /**
+     * \brief Multi-step advance function (jump-ahead, jump-back)
+     *
+     * The method used here is based on Brown, "Random Number Generation
+     * with Arbitrary Stride", Transactions of the American Nuclear
+     * Society (Nov. 1994). The algorithm is very similar to fast
+     * exponentiation.
+     */
+    void advance(int64_t delta_) {
+        uint64_t
+            cur_mult = PCG32_MULT,
+            cur_plus = inc,
+            acc_mult = 1u,
+            acc_plus = 0u;
+
+        /* Even though delta is an unsigned integer, we can pass a signed
+           integer to go backwards, it just goes "the long way round". */
+        uint64_t delta = (uint64_t)delta_;
+
+        while (delta > 0) {
+            if (delta & 1) {
+                acc_mult *= cur_mult;
+                acc_plus = acc_plus * cur_mult + cur_plus;
+            }
+            cur_plus = (cur_mult + 1) * cur_plus;
+            cur_mult *= cur_mult;
+            delta /= 2;
+        }
+        state = acc_mult * state + acc_plus;
+    }
+
+    /**
+     * \brief Draw uniformly distributed permutation and permute the
+     * given STL container
+     *
+     * From: Knuth, TAoCP Vol. 2 (3rd 3d), Section 3.4.2
+     */
+    template <typename Iterator>
+    void shuffle(Iterator begin, Iterator end) {
+        for (Iterator it = end - 1; it > begin; --it)
+            std::iter_swap(it, begin + next_u32((uint32_t)(it - begin + 1)));
+    }
+
+    /// Compute the distance between two PCG32 pseudorandom number generators
+    int64_t operator-(const Pcg32& other) const {
+        assert(inc == other.inc);
+
+        uint64_t
+            cur_mult = PCG32_MULT,
+            cur_plus = inc,
+            cur_state = other.state,
+            the_bit = 1u,
+            distance = 0u;
+
+        while (state != cur_state) {
+            if ((state & the_bit) != (cur_state & the_bit)) {
+                cur_state = cur_state * cur_mult + cur_plus;
+                distance |= the_bit;
+            }
+            assert((state & the_bit) == (cur_state & the_bit));
+            the_bit <<= 1;
+            cur_plus = (cur_mult + 1ULL) * cur_plus;
+            cur_mult *= cur_mult;
+        }
+
+        return (int64_t)distance;
+    }
+
+    /// Equality operator
+    bool operator==(const Pcg32& other) const { return state == other.state && inc == other.inc; }
+
+    /// Inequality operator
+    bool operator!=(const Pcg32& other) const { return state != other.state || inc != other.inc; }
+
+    uint64_t state; // RNG state.  All values are possible.
+    uint64_t inc; // Controls which RNG sequence (stream) is selected. Must *always* be odd.
+};
diff --git a/src/sandbox.cpp b/src/sandbox.cpp
index d0d918c..efc2bd0 100644
--- a/src/sandbox.cpp
+++ b/src/sandbox.cpp
@@ -25,23 +25,25 @@ uint32_t Tile::get_color() const {
     return material_color_lut[std::to_underlying(so)];
 }
 
-Sandbox::Sandbox(int w, int h)
-    : _bitmap(w * h)
-    , _a(w * h)
-    // TODO random seed
-    , _rand()
+Sandbox::Sandbox(int w, int h, RandomState rand)
+    : bitmap(new uint32_t[w * h])
+    , tiles(new Tile[w * h])
+    , _rand(std::move(rand))
     , _wall_tile{ Tile::ROCK }
     , width{ w }
     , height{ h } //
 {
-    memset(_bitmap.data(), 0xff, _bitmap.size() * sizeof(_bitmap[0]));
+    memset(bitmap, 0xff, (w * h) * sizeof(bitmap[0]));
+}
+
+Sandbox::~Sandbox() {
+    delete[] bitmap;
+    delete[] tiles;
 }
 
 static void simulate_sand_tile(Sandbox& self, int x, int y) {
     const auto at0 = self.gs(x, y);
     if (at0.updated) {
-        // Clear update bit for next cycle
-        self.gs(x, y).updated = false;
         return;
     }
 
@@ -91,13 +93,20 @@ static void simulate_sand_tile(Sandbox& self, int x, int y) {
 }
 
 void Sandbox::simulate_step() {
-    _x = 0;
-    _y = 0;
-    for (; _y < height; ++_y) {
-        for (; _x < width; ++_x) {
+    dirty_curr = dirty_writeto;
+    dirty_writeto = {};
+    const auto [x0, y0] = dirty_curr.bl;
+    const auto [x1, y1] = dirty_curr.tr;
+    // Clear update bit for this cycle
+    for (_y = y0; _y <= y1; ++_y) {
+        for (_x = x0; _x <= x1; ++_x) {
+            gs(_x, _y).updated = false;
+        }
+    }
+    for (_y = y0; _y <= y1; ++_y) {
+        for (_x = x0; _x <= x1; ++_x) {
             simulate_sand_tile(*this, _x, _y);
         }
-        _x = 0;
     }
     ++ncycle;
 }
@@ -105,16 +114,20 @@ void Sandbox::simulate_step() {
 Tile& Sandbox::gs(int x, int y) {
     if (x < 0 || x >= width || y < 0 || y >= height)
         return _wall_tile;
-    return _a[y * width + x];
+    return tiles[y * width + x];
 }
 
 void Sandbox::set_sand(int x, int y, Tile sand) {
-    auto& target = _a[y * width + x];
+    auto& target = tiles[y * width + x];
     target = sand;
     // Set update bit if the target is after cursor
     if (y < _y || x > _x)
         target.updated = true;
-    _bitmap[y * width + x] = sand.get_color();
+    bitmap[y * width + x] = sand.get_color();
+    if (dirty_writeto == Rect())
+        dirty_writeto = Rect(x, y, x, y);
+    else
+        dirty_writeto = rect_union(dirty_writeto, Pt(x, y));
 }
 
 // std::vector<uint32_t> Sandbox::to_bitmap() const {
diff --git a/src/sandbox.hpp b/src/sandbox.hpp
index bc6f928..03a6a85 100644
--- a/src/sandbox.hpp
+++ b/src/sandbox.hpp
@@ -1,9 +1,9 @@
 #pragma once
 
+#include "common.hpp"
 #include "rand.hpp"
 
 #include <cstdint>
-#include <vector>
 
 const int MBIT_DISPLACABLE = 1;
 
@@ -28,15 +28,21 @@ struct Tile {
 };
 
 struct Sandbox {
-    std::vector<uint32_t> _bitmap;
-    std::vector<Tile> _a;
+    uint32_t* bitmap;
+    Tile* tiles;
+    /// Dirty rects used by the current simulation step. Only used during it.
+    // TODO use multiple dirty rects?
+    Rect dirty_curr;
+    /// Dirty rects to be used, when the next simulation step happens. May write to this during simulation, or outside of simulation.
+    Rect dirty_writeto;
     RandomState _rand;
     Tile _wall_tile;
     int width, height;
     int _x, _y;
     int ncycle = 0;
 
-    Sandbox(int w, int h);
+    Sandbox(int w, int h, RandomState rand = {});
+    ~Sandbox();
 
     void simulate_step();
 
diff --git a/src/ui.cpp b/src/ui.cpp
index f356afa..cb68c66 100644
--- a/src/ui.cpp
+++ b/src/ui.cpp
@@ -12,26 +12,67 @@ static void AddSand(Sandbox& sb) {
     }
 }
 
+constexpr int kWidth = 40;
+constexpr int kHeight = 100;
+constexpr float kScale = 4.0f;
+constexpr ImVec2 kSize(kWidth* kScale, kHeight* kScale);
+
+static ImVec2 TrSandbox2Screen(ImVec2 origin, Pt pt) {
+    return ImVec2(origin.x + kScale * pt.x, origin.y - kScale * pt.y);
+}
+
+struct ImRect {
+    ImVec2 top_left;
+    ImVec2 bottom_right;
+};
+// Assuming inclusive-inclusive rectangle
+static ImRect TrSandbox2Screen(ImVec2 origin, Rect r) {
+    return {
+        ImVec2(origin.x + kScale * r.bl.x, origin.y - kScale * (r.tr.y+1)),
+        ImVec2(origin.x + kScale * (r.tr.x + 1), origin.y - kScale * r.bl.y),
+    };
+}
+
 void ShowEverything() {
     ImGui::Begin("Sandbox");
-    constexpr int kWidth = 40;
-    constexpr int kHeight = 100;
-    static bool running = false;
     static Sandbox sandbox(40, 100);
     static OglImage gl;
-    sandbox.simulate_step();
-    gl.upload(reinterpret_cast<const char*>(sandbox._bitmap.data()), kWidth, kHeight);
 
-    if (ImGui::Button("Reset sandbox")) {
-        sandbox = Sandbox(40, 100);
+    static bool running = false;
+    ImGui::Checkbox("Run", &running);
+    static bool show_dirty_rect = true;
+    ImGui::Checkbox("Show dirty rects", &show_dirty_rect);
+
+    ImGui::Text("ncycle = %d", sandbox.ncycle);
+    ImGui::SameLine();
+    bool step = ImGui::Button("Step");
+
+    if (step || running) {
+        sandbox.simulate_step();
+        gl.upload(reinterpret_cast<const char*>(sandbox.bitmap), kWidth, kHeight);
     }
+
+    // TODO this makes things very wrong (no proper assignment operator)
+    // if (ImGui::Button("Reset sandbox")) {
+    //     sandbox = Sandbox(40, 100);
+    // }
+    // ImGui::SameLine();
     if (ImGui::Button("Add sand")) {
         AddSand(sandbox);
     }
 
-    constexpr float kScale = 4.0f;
-    constexpr ImVec2 kSize(kWidth * kScale, kHeight * kScale);
+    auto sandbox_topleft = ImGui::GetCursorScreenPos();
     ImGui::Image(gl.as_imgui(), kSize, ImVec2(0, 1), ImVec2(1, 0));
+    // bottom-left corner of the sandbox, in screen space
+    auto origin = sandbox_topleft;
+    origin.y += kSize.y;
+
+    if (show_dirty_rect) {
+        auto dl = ImGui::GetWindowDrawList();
+        auto [top_left, bottom_right] = TrSandbox2Screen(origin, sandbox.dirty_writeto);
+        dl->AddRect(top_left, bottom_right, IM_COL32(255, 0, 0, 255));
+    }
+
     ImGui::End();
 
     ImGui::ShowDemoWindow();