BWRegionGen in BWAPI

x.cpp

#include <vector>
#include <cstdint>
#include <cassert>
#include <array>
#include <algorithm>

#include <BWAPI/Game.h>
#include <BWAPI/Position.h>

template<typename utype>
struct xy_t {
  utype x{};
  utype y{};
  xy_t() = default;
  xy_t(utype x, utype y) : x(x), y(y) {}
  bool operator<(const xy_t& n) const {
    if (y == n.y) return x < n.x;
    return y < n.y;
  }
  bool operator>(const xy_t& n) const {
    if (y == n.y) return x > n.x;
    return y > n.y;
  }
  bool operator<=(const xy_t& n) const {
    if (y == n.y) return x <= n.x;
    return y <= n.y;
  }
  bool operator>=(const xy_t& n) const {
    if (y == n.y) return x >= n.x;
    return y >= n.y;
  }
  bool operator==(const xy_t& n) const {
    return x == n.x && y == n.y;
  }
  bool operator!=(const xy_t& n) const {
    return x != n.x || y != n.y;
  }
  xy_t operator-(const xy_t& n) const {
    xy_t r(*this);
    return r -= n;
  }
  xy_t& operator-=(const xy_t& n) {
    x -= n.x;
    y -= n.y;
    return *this;
  }
  xy_t operator+(const xy_t& n) const {
    xy_t r(*this);
    return r += n;
  }
  xy_t& operator+=(const xy_t& n) {
    x += n.x;
    y += n.y;
    return *this;
  }
  xy_t operator -() const {
    return xy_t(-x, -y);
  }
  xy_t operator/(const xy_t& n) const {
    xy_t r(*this);
    return r /= n;
  }
  xy_t& operator/=(const xy_t& n) {
    x /= n.x;
    y /= n.y;
    return *this;
  }
  template<typename T>
  xy_t operator/(T&& v) const {
    return xy_t(*this) /= v;
  }
  template<typename T>
  xy_t& operator/=(T&& v) {
    x /= v;
    y /= v;
    return *this;
  }
  xy_t operator*(const xy_t& n) const {
    xy_t r(*this);
    return r *= n;
  }
  xy_t& operator*=(const xy_t& n) {
    x *= n.x;
    y *= n.y;
    return *this;
  }
  template<typename T>
  xy_t operator*(T&& v) const {
    return xy_t(*this) *= v;
  }
  template<typename T>
  xy_t& operator*=(T&& v) {
    x *= v;
    y *= v;
    return *this;
  }
};

template<typename T>
struct rect_t {
  T from;
  T to;
  rect_t() = default;
  rect_t(T from, T to) : from(from), to(to) {}
  bool operator==(const rect_t& n) const {
    return from == n.from && to == n.to;
  }

  rect_t operator+(const rect_t& n) const {
    return { from + n.from, to + n.to };
  }
};

using xy = xy_t<int>;
using rect = rect_t<xy>;

template<size_t bits>
using int_fastn_t = typename std::conditional<bits <= 8, std::int_fast8_t,
  typename std::conditional<bits <= 16, int_fast16_t,
  typename std::conditional<bits <= 32, int_fast32_t,
  typename std::enable_if<bits <= 64, int_fast64_t>::type>::type>::type>::type;
template<size_t bits>
using uint_fastn_t = typename std::conditional<bits <= 8, std::uint_fast8_t,
  typename std::conditional<bits <= 16, uint_fast16_t,
  typename std::conditional<bits <= 32, uint_fast32_t,
  typename std::enable_if<bits <= 64, uint_fast64_t>::type>::type>::type>::type;

template<size_t t_integer_bits, size_t t_fractional_bits, bool t_is_signed, bool t_exact_integer_bits = false>
struct fixed_point {
  static const bool is_signed = t_is_signed;
  static const bool exact_integer_bits = t_exact_integer_bits;
  static const size_t integer_bits = t_integer_bits;
  static const size_t fractional_bits = t_fractional_bits;
  static const size_t total_bits = integer_bits + fractional_bits;
  using raw_unsigned_type = uint_fastn_t<total_bits>;
  using raw_signed_type = int_fastn_t<total_bits>;
  using raw_type = typename std::conditional<is_signed, raw_signed_type, raw_unsigned_type>::type;
  raw_type raw_value;

  void wrap() {
    if (!exact_integer_bits) return;
    raw_value <<= int_bits<raw_type>::value - total_bits;
    raw_value >>= int_bits<raw_type>::value - total_bits;
  }

  static constexpr fixed_point from_raw(raw_type raw_value) {
    return fixed_point{ exact_integer_bits ? (raw_type)((raw_type)(raw_value << (int_bits<raw_type>::value - total_bits)) >> (int_bits<raw_type>::value - total_bits)) : raw_value };
  }

  template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  static fixed_point integer(T integer_value) {
    return from_raw((raw_type)((raw_unsigned_type)integer_value << fractional_bits));
  }

  static fixed_point zero() {
    return integer(0);
  }
  static fixed_point one() {
    return integer(1);
  }

  raw_type integer_part() const {
    return raw_value >> fractional_bits;
  }
  raw_type fractional_part() const {
    return raw_value & (((raw_type)1 << fractional_bits) - 1);
  }

  template<size_t n_integer_bits, size_t n_fractional_bits, bool n_exact_integer_bits, size_t result_integer_bits = integer_bits, size_t result_fractional_bits = fractional_bits, typename std::enable_if<((result_integer_bits < n_integer_bits || result_fractional_bits < n_fractional_bits) && result_fractional_bits <= n_fractional_bits)>::type* = nullptr>
      static auto truncate(const fixed_point<n_integer_bits, n_fractional_bits, is_signed, n_exact_integer_bits>& n) {
        using result_type = fixed_point<result_integer_bits, result_fractional_bits, is_signed, exact_integer_bits>;
        typename result_type::raw_type raw_value = (typename result_type::raw_type)(n.raw_value >> (n_fractional_bits - result_fractional_bits));
        return result_type::from_raw(raw_value);
      }

      template<size_t n_integer_bits, size_t n_fractional_bits, bool n_exact_integer_bits, size_t result_integer_bits = integer_bits, size_t result_fractional_bits = fractional_bits, typename std::enable_if<((result_integer_bits > n_integer_bits || result_fractional_bits > n_fractional_bits) && result_fractional_bits >= n_fractional_bits)>::type* = nullptr>
  static auto extend(const fixed_point<n_integer_bits, n_fractional_bits, is_signed, n_exact_integer_bits>& n) {
    using result_type = fixed_point<result_integer_bits, result_fractional_bits, is_signed, exact_integer_bits>;
    typename result_type::raw_type raw_value = n.raw_value;
    raw_value <<= result_fractional_bits - n_fractional_bits;
    return result_type::from_raw(raw_value);
  }

  fixed_point floor() const {
    return integer(integer_part());
  }
  fixed_point ceil() const {
    return (*this + integer(1) - from_raw(1)).floor();
  }
  fixed_point abs() const {
    if (*this >= zero()) return *this;
    else return from_raw(-raw_value);
  }

  auto as_signed() const {
    return fixed_point<integer_bits, fractional_bits, true, exact_integer_bits>::from_raw(raw_value);
  }
  auto as_unsigned() const {
    return fixed_point<integer_bits, fractional_bits, false, exact_integer_bits>::from_raw(raw_value);
  }

  bool operator==(const fixed_point& n) const {
    return raw_value == n.raw_value;
  }
  bool operator!=(const fixed_point& n) const {
    return raw_value != n.raw_value;
  }
  bool operator<(const fixed_point& n) const {
    return raw_value < n.raw_value;
  }
  bool operator<=(const fixed_point& n) const {
    return raw_value <= n.raw_value;
  }
  bool operator>(const fixed_point& n) const {
    return raw_value > n.raw_value;
  }
  bool operator>=(const fixed_point& n) const {
    return raw_value >= n.raw_value;
  }

  fixed_point operator-() const {
    static_assert(is_signed, "fixed_point: cannot negate an unsigned number");
    return from_raw(-raw_value);
  }

  fixed_point& operator+=(const fixed_point& n) {
    raw_value += n.raw_value;
    wrap();
    return *this;
  }
  fixed_point operator+(const fixed_point& n) const {
    return from_raw(raw_value + n.raw_value);
  }
  fixed_point& operator-=(const fixed_point& n) {
    raw_value -= n.raw_value;
    wrap();
    return *this;
  }
  fixed_point operator-(const fixed_point& n) const {
    return from_raw(raw_value - n.raw_value);
  }

  template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  fixed_point& operator/=(T integer_value) {
    static_assert(std::is_signed<T>::value == is_signed, "fixed_point: cannot mix signed/unsigned in division");
    raw_value /= integer_value;
    wrap();
    return *this;
  }
  template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  fixed_point operator/(T integer_value) const {
    static_assert(std::is_signed<T>::value == is_signed, "fixed_point: cannot mix signed/unsigned in division");
    return from_raw(raw_value / integer_value);
  }
  template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  fixed_point& operator*=(T integer_value) {
    static_assert(std::is_signed<T>::value == is_signed, "fixed_point: cannot mix signed/unsigned in multiplication");
    raw_value *= integer_value;
    wrap();
    return *this;
  }
  template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  auto operator*(T integer_value) const {
    static_assert(std::is_signed<T>::value == is_signed, "fixed_point: cannot mix signed/unsigned in multiplication");
    return from_raw(raw_value * integer_value);
  }

  template<size_t n_integer_bits>
  fixed_point& operator*=(const fixed_point<n_integer_bits, fractional_bits, is_signed, exact_integer_bits>& n) {
    return *this = *this * n;
  }

  template<size_t n_integer_bits>
  fixed_point& operator/=(const fixed_point<n_integer_bits, fractional_bits, is_signed, exact_integer_bits>& n) {
    return *this = *this / n;
  }

  // rounds towards negative infinity
  template<size_t n_integer_bits, size_t n_fractional_bits>
  auto operator*(const fixed_point<n_integer_bits, n_fractional_bits, is_signed, exact_integer_bits>& n) {
    using result_type = fixed_point<(integer_bits > n_integer_bits ? integer_bits : n_integer_bits), (fractional_bits > n_fractional_bits ? fractional_bits : n_fractional_bits), is_signed, exact_integer_bits>;
    using tmp_t = typename fixed_point<result_type::integer_bits, fractional_bits + n_fractional_bits, is_signed>::raw_type;
    tmp_t tmp = (tmp_t)raw_value * (tmp_t)n.raw_value >> n_fractional_bits;
    return result_type::from_raw((typename result_type::raw_type)tmp);
  }

  // rounds towards 0
  template<size_t n_integer_bits, size_t n_fractional_bits>
  auto operator/(const fixed_point<n_integer_bits, n_fractional_bits, is_signed, exact_integer_bits>& n) const {
    using result_type = fixed_point<(integer_bits > n_integer_bits ? integer_bits : n_integer_bits), (fractional_bits > n_fractional_bits ? fractional_bits : n_fractional_bits), is_signed, exact_integer_bits>;
    using tmp_t = typename fixed_point<result_type::integer_bits, fractional_bits + n_fractional_bits, is_signed>::raw_type;
    tmp_t tmp = ((tmp_t)raw_value << n_fractional_bits) / (tmp_t)n.raw_value;
    return result_type::from_raw((typename result_type::raw_type)tmp);
  }

  // returns a * b / c
  // rounds towards 0
  static fixed_point multiply_divide(fixed_point a, fixed_point b, fixed_point c) {
    constexpr raw_type max_value_no_overflow = std::numeric_limits<raw_type>::max() >> (int_bits<raw_type>::value / 2);
    using tmp_t = typename fixed_point<integer_bits, fractional_bits + fractional_bits, is_signed>::raw_type;
    if (!is_native_fast_int<tmp_t>::value && a.raw_value <= max_value_no_overflow && b.raw_value <= max_value_no_overflow) {
      return from_raw(a.raw_value * b.raw_value / c.raw_value);
    }
    else {
      return from_raw((tmp_t)a.raw_value * b.raw_value / c.raw_value);
    }
  }

  // returns a / b * c
  // rounds towards 0
  static fixed_point divide_multiply(fixed_point a, fixed_point b, fixed_point c) {
    return from_raw(a.raw_value / b.raw_value * c.raw_value);
  }

};

using fp8 = fixed_point<24, 8, true>;

struct regions_t {

  struct region {
    uint16_t flags = 0x1FFD;
    size_t index = ~(size_t)0;
    xy_t<size_t> tile_center;
    rect_t<xy_t<size_t>> tile_area;
    xy_t<fp8> center;
    rect area;
    size_t tile_count = 0;
    size_t group_index = 0;
    std::vector<region*> walkable_neighbors;
    std::vector<region*> non_walkable_neighbors;

    mutable int pathfinder_flag = 0; // fixme: remove
    mutable void* pathfinder_node = nullptr; // fixme: remove

    bool walkable() const {
      return flags != 0x1ffd;
    }
  };

  struct split_region {
    uint16_t mask;
    region* a;
    region* b;
  };

  // tile_region_index values -
  //  [0, 5000) index into regions
  //  [5000, 0x2000) unmapped (0x1ffd unwalkable, otherwise walkable)
  //  [0x2000, ...] index + 0x2000 into split_regions
  std::vector<size_t> tile_region_index = std::vector<size_t>(256 * 256);

  rect_t<xy_t<size_t>> tile_bounding_box;

  std::vector<region> regions;

  std::vector<split_region> split_regions;
};

struct tile_t {
  enum {
    flag_walkable = 1,
    flag_unk0 = 2,
    flag_unwalkable = 4,
    flag_unk1 = 8,
    flag_provides_cover = 0x10,
    flag_unk3 = 0x20,
    flag_has_creep = 0x40,
    flag_unbuildable = 0x80,
    flag_very_high = 0x100,
    flag_middle = 0x200,
    flag_high = 0x400,
    flag_occupied = 0x800,
    flag_creep_receding = 0x1000,
    flag_partially_walkable = 0x2000,
    flag_temporary_creep = 0x4000,
    flag_unk4 = 0x8000
  };
  uint8_t visible;
  uint8_t explored;
  uint16_t flags;
};

struct game_state {
  regions_t regions;
  std::vector<tile_t> tiles;
};

struct state_functions {
  game_state& game_st;


  regions_t::region* get_new_region() {
    if (game_st.regions.regions.capacity() != 5000) game_st.regions.regions.reserve(5000);
    assert(game_st.regions.regions.size() < 5000);
    game_st.regions.regions.emplace_back();
    regions_t::region* r = &game_st.regions.regions.back();
    r->index = game_st.regions.regions.size() - 1;
    return r;
  }

  void regions_create(BWAPI::Game& game) {

    auto create_region = [&](rect_t<xy_t<size_t>> area) {
      auto* r = get_new_region();
      uint16_t flags = (uint16_t)game_st.regions.tile_region_index[area.from.y * 256 + area.from.x];
      assert(flags >= 5000);
      r->flags = flags;
      r->tile_area = area;
      r->tile_center.x = (area.from.x + area.to.x) / 2;
      r->tile_center.y = (area.from.y + area.to.y) / 2;
      size_t tile_count = 0;
      size_t index = r->index;
      for (size_t y = area.from.y; y != area.to.y; ++y) {
        for (size_t x = area.from.x; x != area.to.x; ++x) {
          assert(game_st.regions.tile_region_index[y * 256 + x] >= 5000);
          game_st.regions.tile_region_index[y * 256 + x] = (uint16_t)index;
          ++tile_count;
        }
      }
      r->tile_count = tile_count;
      return r;
    };

    auto create_unreachable_bottom_region = [&]() {
      auto* r = create_region({
        {0, game.mapHeight() - 1},
        {game.mapWidth(), game.mapHeight()}
      });

      r->area = { {0, game.mapHeight()*32 - 32}, {game.mapWidth()*32, game.mapHeight()*32} };
      r->center.x = ((fp8::integer(r->area.from.x) + fp8::integer(r->area.to.x)) / 2);
      r->center.y = ((fp8::integer(r->area.from.y) + fp8::integer(r->area.to.y)) / 2);
      r->flags = 0x1ffd;
      r->group_index = 0x4000;
    };

    auto create_regions = [&]() {

      size_t region_tile_index = 0;
      size_t region_x = 0;
      size_t region_y = 0;

      auto bb = game_st.regions.tile_bounding_box;

      auto find_empty_region = [&](size_t x, size_t y) {
        if (x >= bb.to.x) {
          x = bb.from.x;
          y = y + 1 >= bb.to.y ? bb.from.y : y + 1;
        }
        size_t start_x = x;
        size_t start_y = y;
        while (true) {
          size_t index = game_st.regions.tile_region_index[y * 256 + x];
          if (index >= 5000) {
            region_tile_index = index;
            region_x = x;
            region_y = y;
            return true;
          }
          ++x;
          if (x >= bb.to.x) {
            x = bb.from.x;
            y = y + 1 >= bb.to.y ? bb.from.y : y + 1;
          }
          if (x == start_x && y == start_y) return false;
        }

      };

      size_t next_x = bb.from.x;
      size_t next_y = bb.from.y;

      bool has_expanded_all = false;
      size_t initial_regions_size = game_st.regions.regions.size();

      size_t prev_size = 7 * 8;

      while (true) {
        size_t start_x = next_x;
        size_t start_y = next_y;
        if (start_x >= bb.to.x) {
          start_x = bb.from.x;
          ++start_y;
          if (start_y >= bb.to.y) start_y = bb.from.y;
        }
        if (find_empty_region(start_x, start_y)) {

          auto find_area = [&](size_t begin_x, size_t begin_y, size_t index) {
            size_t max_end_x = std::min(begin_x + 8, (size_t)game.mapWidth());
            size_t max_end_y = std::min(begin_y + 7, (size_t)game.mapHeight());

            size_t end_x = begin_x + 1;
            size_t end_y = begin_y + 1;
            bool x_is_good = true;
            bool y_is_good = true;
            bool its_all_good = true;
            while ((x_is_good || y_is_good) && (end_x != max_end_x && end_y != max_end_y)) {
              if (x_is_good) {
                for (size_t y = begin_y; y != end_y; ++y) {
                  if (game_st.regions.tile_region_index[y * 256 + end_x] != index) {
                    x_is_good = false;
                    break;
                  }
                }
              }
              if (y_is_good) {
                for (size_t x = begin_x; x != end_x; ++x) {
                  if (game_st.regions.tile_region_index[end_y * 256 + x] != index) {
                    y_is_good = false;
                    break;
                  }
                }
              }

              if (game_st.regions.tile_region_index[end_y * 256 + end_x] != index) {
                its_all_good = false;
              }
              if (its_all_good) {
                if (y_is_good) ++end_y;
                if (x_is_good) ++end_x;
              }
              else {
                if (y_is_good) ++end_y;
                else if (x_is_good) ++end_x;
              }
            }

            size_t width = end_x - begin_x;
            size_t height = end_y - begin_y;
            if (width > height * 3) width = height * 3;
            else if (height > width * 3) height = width * 3;
            end_x = begin_x + width;
            end_y = begin_y + height;

            return rect_t<xy_t<size_t>>{ {begin_x, begin_y}, { end_x, end_y } };
          };

          auto area = find_area(region_x, region_y, region_tile_index);

          size_t size = (area.to.x - area.from.x) * (area.to.y - area.from.y);
          if (size < prev_size) {
            auto best_area = area;
            size_t best_size = size;

            for (size_t n = 0; n != 25; ++n) {
              if (!find_empty_region(area.to.x, region_y)) break;
              area = find_area(region_x, region_y, region_tile_index);
              size_t size = (area.to.x - area.from.x) * (area.to.y - area.from.y);
              if (size > best_size) {
                best_size = size;
                best_area = area;
                if (size >= prev_size) break;
              }
            }

            area = best_area;
            size = best_size;
          }

          prev_size = size;

          next_x = area.to.x;
          next_y = area.from.y;

          assert(game_st.regions.regions.size() < 5000); // nooks and crannies

          auto* r = create_region(area);

          auto expand = [&](regions_t::region* r) {

            size_t& begin_x = r->tile_area.from.x;
            if (begin_x > 0) --begin_x;
            size_t& begin_y = r->tile_area.from.y;
            if (begin_y > 0) --begin_y;
            size_t& end_x = r->tile_area.to.x;
            if (end_x < game.mapWidth()) ++end_x;
            size_t& end_y = r->tile_area.to.y;
            if (end_y < game.mapHeight()) ++end_y;

            uint16_t flags = r->flags;
            size_t index = r->index;

            auto is_neighbor = [&](size_t x, size_t y) {
              if (x != 0 && game_st.regions.tile_region_index[y * 256 + x - 1] == index) return true;
              if (x != game.mapWidth() - 1 && game_st.regions.tile_region_index[y * 256 + x + 1] == index) return true;
              if (y != 0 && game_st.regions.tile_region_index[(y - 1) * 256 + x] == index) return true;
              if (y != game.mapHeight() - 1 && game_st.regions.tile_region_index[(y + 1) * 256 + x] == index) return true;
              return false;
            };

            for (int i = 0; i < 2; ++i) {
              for (size_t y = begin_y; y != end_y; ++y) {
                for (size_t x = begin_x; x != end_x; ++x) {
                  if (game_st.regions.tile_region_index[y * 256 + x] == flags && is_neighbor(x, y)) {
                    game_st.regions.tile_region_index[y * 256 + x] = index;
                  }
                }
              }
            }

          };

          expand(r);

          if (size <= 6 && !has_expanded_all) {
            has_expanded_all = true;
            for (size_t i = initial_regions_size; i != game_st.regions.regions.size(); ++i) {
              expand(&game_st.regions.regions[i]);
            }
          }

        }
        else {
          assert(game_st.regions.regions.size() < 5000); // nooks and crannies
          break;
        }
      }

      auto get_neighbors = [&](size_t tile_x, size_t tile_y) {
        std::array<size_t, 8> r;
        size_t n = 0;
        auto test = [&](bool cond, size_t x, size_t y) {
          if (!cond) r[n++] = 0x1fff;
          else r[n++] = game_st.regions.tile_region_index[y * 256 + x];
        };
        test(tile_y > 0, tile_x, tile_y - 1);
        test(tile_x > 0, tile_x - 1, tile_y);
        test(tile_x + 1 < game.mapWidth(), tile_x + 1, tile_y);
        test(tile_y + 1 < game.mapHeight(), tile_x, tile_y + 1);
        test(tile_y > 0 && tile_x > 0, tile_x - 1, tile_y - 1);
        test(tile_y > 0 && tile_x + 1 < game.mapWidth(), tile_x + 1, tile_y - 1);
        test(tile_y + 1 < game.mapHeight() && tile_x > 0, tile_x - 1, tile_y + 1);
        test(tile_y + 1 < game.mapHeight() && tile_x + 1 < game.mapWidth(), tile_x + 1, tile_y + 1);
        return r;
      };

      auto refresh_regions = [&]() {

        for (auto& r : game_st.regions.regions) {
          int max = std::numeric_limits<int>::max();
          int min = std::numeric_limits<int>::min();
          r.area = { { max, max }, { min, min } };
          r.tile_count = 0;
        }
        for (size_t y = 0; y != game.mapHeight(); ++y) {
          for (size_t x = 0; x != game.mapWidth(); ++x) {
            size_t index = game_st.regions.tile_region_index[y * 256 + x];
            if (index < 5000) {
              auto* r = &game_st.regions.regions[index];
              ++r->tile_count;
              if (r->area.from.x > (int)x * 32) r->area.from.x = int(32 * x);
              if (r->area.from.y > (int)y * 32) r->area.from.y = int(32 * y);
              if (r->area.to.x < ((int)x + 1) * 32) r->area.to.x = int(32 * (x + 1));
              if (r->area.to.y < ((int)y + 1) * 32) r->area.to.y = int(32 * (y + 1));
            }
          }
        }

        for (auto& r : game_st.regions.regions) {
          if (r.tile_count == 0) r.flags = 0x1fff;
        }

        for (auto& r : game_st.regions.regions) {
          if (r.tile_count == 0) continue;

          r.walkable_neighbors.clear();
          r.non_walkable_neighbors.clear();

          for (int y = r.area.from.y / 32; y != r.area.to.y / 32; ++y) {
            for (int x = r.area.from.x / 32; x != r.area.to.x / 32; ++x) {
              if (game_st.regions.tile_region_index[y * 256 + x] != r.index) continue;
              auto neighbors = get_neighbors(x, y);
              for (size_t i = 0; i != 8; ++i) {
                size_t nindex = neighbors[i];
                if (nindex == 0x1fff || nindex == r.index) continue;
                auto* nr = &game_st.regions.regions[nindex];
                bool add = false;
                if (i < 4 || !r.walkable() || !nr->walkable()) {
                  add = true;
                }
                else {
                  auto is_2x2_walkable = [&](size_t walk_x, size_t walk_y) {
                    if (!game.isWalkable(walk_x, walk_y)) return false;
                    if (!game.isWalkable(walk_x + 1, walk_y)) return false;
                    if (!game.isWalkable(walk_x, walk_y + 1)) return false;
                    if (!game.isWalkable(walk_x + 1, walk_y + 1)) return false;
                    return true;
                  };


                  size_t walk_x = x * 4;
                  size_t walk_y = y * 4;
                  if (i == 4) {
                    if (is_2x2_walkable(walk_x - 2, walk_y - 2) && is_2x2_walkable(walk_x, walk_y)) {
                      if (is_2x2_walkable(walk_x - 2, walk_y)) add = true;
                      else if (is_2x2_walkable(walk_x, walk_y - 2)) add = true;
                    }
                  }
                  else if (i == 5) {
                    if (is_2x2_walkable(walk_x + 4, walk_y - 2) && is_2x2_walkable(walk_x + 2, walk_y)) {
                      if (is_2x2_walkable(walk_x + 2, walk_y - 2)) add = true;
                      else if (is_2x2_walkable(walk_x + 4, walk_y)) add = true;
                    }
                  }
                  else if (i == 6) {
                    if (is_2x2_walkable(walk_x, walk_y + 2) && is_2x2_walkable(walk_x - 2, walk_y + 4)) {
                      if (is_2x2_walkable(walk_x - 2, walk_y + 2)) add = true;
                      else if (is_2x2_walkable(walk_x, walk_y + 4)) add = true;
                    }
                  }
                  else if (i == 7) {
                    if (is_2x2_walkable(walk_x + 2, walk_y + 2) && is_2x2_walkable(walk_x + 4, walk_y + 4)) {
                      if (is_2x2_walkable(walk_x + 4, walk_y + 2)) add = true;
                      else if (is_2x2_walkable(walk_x + 2, walk_y + 4)) add = true;
                    }
                  }
                }
                if (add) {
                  if (nr->walkable()) {
                    if (std::find(r.walkable_neighbors.begin(), r.walkable_neighbors.end(), nr) == r.walkable_neighbors.end()) {
                      r.walkable_neighbors.push_back(nr);
                    }
                  }
                  else {
                    if (std::find(r.non_walkable_neighbors.begin(), r.non_walkable_neighbors.end(), nr) == r.non_walkable_neighbors.end()) {
                      r.non_walkable_neighbors.push_back(nr);
                    }
                  }
                }
              }
            }
          }

          if (!r.non_walkable_neighbors.empty()) {
            for (auto& v : r.non_walkable_neighbors) {
              if (v == &game_st.regions.regions.front() && &v != &r.non_walkable_neighbors.back()) std::swap(v, r.non_walkable_neighbors.back());
            }
          }

        }

        for (auto& r : game_st.regions.regions) {
          r.center = { fp8::integer(r.tile_center.x * 32 + 16), fp8::integer(r.tile_center.y * 32 + 16) };
        }

        for (auto& r : game_st.regions.regions) {
          if (r.group_index < 0x4000) r.group_index = 0;
        }
        std::vector<regions_t::region*> stack;
        size_t next_group_index = 1;
        for (auto& r : game_st.regions.regions) {
          if (r.group_index == 0 && r.tile_count) {
            size_t group_index = next_group_index++;
            r.group_index = group_index;
            stack.push_back(&r);
            while (!stack.empty()) {
              auto* cr = stack.back();
              stack.pop_back();
              for (auto* nr : (cr->walkable() ? cr->walkable_neighbors : cr->non_walkable_neighbors)) {
                if (nr->group_index == 0) {
                  nr->group_index = group_index;
                  stack.push_back(nr);
                }
              }
            }
          }
        }

      };

      refresh_regions();

      for (size_t n = 6;; n += 2) {
        for (auto r = game_st.regions.regions.rbegin(); r != game_st.regions.regions.rend(); ++r) {
          if (r->tile_count == 0 || r->tile_count >= n || r->group_index >= 0x4000) continue;
          
          regions_t::region* smallest_neighbor = nullptr;
          auto eval = [&](auto* nr) {
            if (nr->tile_count == 0 || nr->group_index >= 0x4000 || nr->flags != r->flags) return;
            if (!smallest_neighbor || nr->tile_count < smallest_neighbor->tile_count) {
              smallest_neighbor = nr;
            }
          };

          for (auto* nr : r->walkable_neighbors) eval(nr);
          for (auto* nr : r->non_walkable_neighbors) eval(nr);
          if (smallest_neighbor) {
            auto* merge_into = smallest_neighbor;
            for (size_t y = r->area.from.y / 32u; y != r->area.to.y / 32u; ++y) {
              for (size_t x = r->area.from.x / 32u; x != r->area.to.x / 32u; ++x) {
                size_t& index = game_st.regions.tile_region_index[y * 256 + x];
                if (index == r->index) index = merge_into->index;
              }
            }
            merge_into->tile_count += r->tile_count;
            r->tile_count = 0;
            r->flags = 0x1fff;
            if (r->area.from.x < merge_into->area.from.x) merge_into->area.from.x = r->area.from.x;
            if (r->area.from.y < merge_into->area.from.y) merge_into->area.from.y = r->area.from.y;
            if (r->area.to.x > merge_into->area.to.x) merge_into->area.to.x = r->area.to.x;
            if (r->area.to.y > merge_into->area.to.y) merge_into->area.to.y = r->area.to.y;
          }
        }

        size_t n_non_empty_regions = 0;
        for (auto& r : game_st.regions.regions) {
          if (r.tile_count) ++n_non_empty_regions;
        }
        if (n_non_empty_regions < 2500) break;
      }

      std::vector<size_t> reindex(5000);
      size_t new_region_count = 0;
      for (size_t i = 0; i != game_st.regions.regions.size(); ++i) {
        auto* r = &game_st.regions.regions[i];
        r->walkable_neighbors.clear();
        r->non_walkable_neighbors.clear();
        if (r->tile_count == 0) continue;
        size_t new_index = new_region_count++;
        reindex[i] = new_index;
        if (i != new_index) {
          r->index = new_index;
          game_st.regions.regions[new_index] = std::move(*r);
        }
      }
      for (size_t y = 0; y != game.mapHeight(); ++y) {
        for (size_t x = 0; x != game.mapWidth(); ++x) {
          size_t& index = game_st.regions.tile_region_index[y * 256 + x];
          index = reindex[index];
        }
      }
      game_st.regions.regions.resize(new_region_count);

      refresh_regions();

      game_st.regions.split_regions.clear();

      for (size_t y = 0; y != game.mapHeight(); ++y) {
        for (size_t x = 0; x != game.mapWidth(); ++x) {
          size_t index = y * game.mapWidth() + x;
          auto tile = game_st.tiles[index];
          if (~tile.flags & tile_t::flag_partially_walkable) continue;
          auto neighbors = get_neighbors(x, y);
          auto* r = &game_st.regions.regions[game_st.regions.tile_region_index[y * 256 + x]];
          auto count_4x1_walkable = [&](size_t walk_x, size_t walk_y) {
            size_t r = 0;
            if (game.isWalkable(walk_x, walk_y)) ++r;
            if (game.isWalkable(walk_x + 1, walk_y)) ++r;
            if (game.isWalkable(walk_x + 2, walk_y)) ++r;
            if (game.isWalkable(walk_x + 3, walk_y)) ++r;
            return r;
          };
          auto count_1x4_walkable = [&](size_t walk_x, size_t walk_y) {
            size_t r = 0;
            if (game.isWalkable(walk_x, walk_y)) ++r;
            if (game.isWalkable(walk_x, walk_y + 1)) ++r;
            if (game.isWalkable(walk_x, walk_y + 2)) ++r;
            if (game.isWalkable(walk_x, walk_y + 3)) ++r;
            return r;
          };
          uint16_t mask = 0;
          for (size_t sy = 0; sy != 4; ++sy) {
            for (size_t sx = 0; sx != 4; ++sx) {
              mask >>= 1;
              if (game.isWalkable(BWAPI::WalkPosition{ BWAPI::TilePosition(x, y) } + BWAPI::WalkPosition(sx, sy))) {
                mask |= 0x8000;
              }
            }
          }

          size_t walk_x = x * 4;
          size_t walk_y = y * 4;
          regions_t::region* r2 = nullptr;
          if (!r->walkable()) {
            std::array<size_t, 4> n_walkable{};
            n_walkable[0] = count_4x1_walkable(walk_x, walk_y);
            n_walkable[1] = count_1x4_walkable(walk_x, walk_y);
            n_walkable[2] = count_1x4_walkable(walk_x + 3, walk_y);
            n_walkable[3] = count_4x1_walkable(walk_x, walk_y + 3);
            size_t highest_n = 0;
            size_t highest_nindex;
            for (size_t i = 4; i != 0;) {
              --i;
              size_t n = n_walkable[i];
              if (n <= highest_n) continue;
              size_t nindex = neighbors[i];
              if (nindex == r->index) continue;
              if (nindex < 0x2000) {
                if (nindex >= 5000) continue;
                auto* nr = &game_st.regions.regions[nindex];
                if (nr->walkable()) {
                  highest_n = n;
                  highest_nindex = nindex;
                }
              }
              else {
                bool set = false;
                if (i == 0 && count_4x1_walkable(walk_x, walk_y - 1)) set = true;
                if (i == 1 && count_1x4_walkable(walk_x - 1, walk_y)) set = true;
                if (i == 2 && count_1x4_walkable(walk_x + 4, walk_y)) set = true;
                if (i == 3 && count_4x1_walkable(walk_x, walk_y + 4)) set = true;
                if (set) {
                  highest_n = n;
                  highest_nindex = nindex;
                }
              }
            }
            if (highest_n) {
              if (highest_nindex < 0x2000) r2 = &game_st.regions.regions[highest_nindex];
              else r2 = game_st.regions.split_regions[highest_nindex - 0x2000].a;
            }
          }
          else {
            std::array<size_t, 8> n_unwalkable{};
            n_unwalkable[0] = 4 - count_4x1_walkable(walk_x, walk_y);
            n_unwalkable[1] = 4 - count_1x4_walkable(walk_x, walk_y);
            n_unwalkable[2] = 4 - count_1x4_walkable(walk_x + 3, walk_y);
            n_unwalkable[3] = 4 - count_4x1_walkable(walk_x, walk_y + 3);
            n_unwalkable[4] = game.isWalkable(walk_x, walk_y) ? 0 : 1;
            n_unwalkable[5] = game.isWalkable(walk_x + 3, walk_y) ? 0 : 1;
            n_unwalkable[6] = game.isWalkable(walk_x, walk_y + 3) ? 0 : 1;
            n_unwalkable[7] = game.isWalkable(walk_x + 3, walk_y + 3) ? 0 : 1;
            size_t highest_n = 0;
            size_t highest_nindex;
            for (size_t i = 8; i != 0;) {
              --i;
              size_t n = n_unwalkable[i];
              if (n <= highest_n) continue;
              size_t nindex = neighbors[i];
              if (nindex == r->index) continue;
              if (nindex < 0x2000) {
                if (nindex >= 5000) continue;
                auto* nr = &game_st.regions.regions[nindex];
                if (!nr->walkable()) {
                  highest_n = n;
                  highest_nindex = nindex;
                }
              }
              else {
                bool set = false;
                if (i == 0 && count_4x1_walkable(walk_x, walk_y - 1) != 4) set = true;
                if (i == 1 && count_1x4_walkable(walk_x - 1, walk_y) != 4) set = true;
                if (i == 2 && count_1x4_walkable(walk_x + 4, walk_y) != 4) set = true;
                if (i == 3 && count_4x1_walkable(walk_x, walk_y + 4) != 4) set = true;
                if (i == 4 && !game.isWalkable(walk_x - 1, walk_y - 1)) set = true;
                if (i == 5 && !game.isWalkable(walk_x + 4, walk_y - 1)) set = true;
                if (i == 6 && !game.isWalkable(walk_x - 1, walk_y + 4)) set = true;
                if (i == 7 && !game.isWalkable(walk_x + 4, walk_y + 4)) set = true;
                if (set) {
                  highest_n = n;
                  highest_nindex = nindex;
                }
              }
            }
            if (highest_n) {
              if (highest_nindex < 0x2000) r2 = &game_st.regions.regions[highest_nindex];
              else r2 = game_st.regions.split_regions[highest_nindex - 0x2000].b;
            }
          }
          if (!r2 || r2 == r) mask = r->walkable() ? 0 : 0xffff;
          else if (!r->walkable() && !r2->walkable()) mask = 0xffff;
          game_st.regions.tile_region_index[y * 256 + x] = 0x2000 + game_st.regions.split_regions.size();
          if (r->walkable()) {
            game_st.regions.split_regions.push_back({ mask, r, r2 ? r2 : r });
          }
          else {
            game_st.regions.split_regions.push_back({ mask, r2 ? r2 : r, r });
          }
        }
      }

    };

    game_st.regions.tile_bounding_box = { {0, 0}, {game.mapWidth(), game.mapHeight()} };

    for (size_t y = 0; y != game.mapHeight(); ++y) {
      for (size_t x = 0; x != game.mapWidth(); ++x) {
        auto& index = game_st.regions.tile_region_index[y * 256 + x];
        auto& t = game_st.tiles[y * game.mapWidth() + x];
        if (~t.flags & tile_t::flag_walkable) index = 0x1ffd;
        else if (t.flags & tile_t::flag_middle) index = 0x1ff9;
        else if (t.flags & tile_t::flag_high) index = 0x1ffa;
        else index = 0x1ffb;
      }
    }

    create_unreachable_bottom_region();
    create_regions();
  }
};