diff options
| -rw-r--r-- | src/common.hpp | 39 | ||||
| -rw-r--r-- | src/rand/pcg.hpp | 207 | ||||
| -rw-r--r-- | src/sandbox.cpp | 45 | ||||
| -rw-r--r-- | src/sandbox.hpp | 14 | ||||
| -rw-r--r-- | src/ui.cpp | 59 |
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(); @@ -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(); |