regions_create

PathingX.cpp

#include "PathingX.h"

#include "BWAPI/GameImpl.h"
#include <cassert>
#include <utility>
#include <algorithm>

regions_t regions;

using namespace BWAPI;

void error(const char *msg) {
  assert(false);
}

regions_t::region* get_new_region() {
  if (regions.regions.capacity() != 5000) regions.regions.reserve(5000);
  if (regions.regions.size() >= 5000) error("too many regions");

  regions.regions.emplace_back();
  regions_t::region* r = &regions.regions.back();
  r->index = regions.regions.size() - 1;
  return r;
}
size_t map_tile_width() { return Broodwar->mapWidth(); };
size_t map_tile_height() { return Broodwar->mapHeight(); };
size_t map_walk_width() { return map_tile_width() * 4; }
size_t map_walk_height() { return map_tile_height() * 4; }
size_t map_width() { return map_tile_width() * 32; }
size_t map_height() { return map_tile_height() * 32; }

void regions_create() {

  std::vector<uint8_t> unwalkable_flags(256 * 4 * 256 * 4);

  auto is_unwalkable = [&](size_t walk_x, size_t walk_y) {
    return unwalkable_flags[walk_y * 256 * 4 + walk_x] & 0x80 ? true : false;
  };
  auto is_walkable = [&](size_t walk_x, size_t walk_y) {
    return ~unwalkable_flags[walk_y * 256 * 4 + walk_x] & 0x80 ? true : false;
  };
  auto set_unwalkable = [&](size_t walk_x, size_t walk_y) {
    unwalkable_flags[walk_y * 256 * 4 + walk_x] |= 0x80;
  };
  auto is_dir_walkable = [&](size_t walk_x, size_t walk_y, size_t dir) {
    return ~unwalkable_flags[walk_y * 256 * 4 + walk_x] & (1 << dir) ? true : false;
  };
  auto is_dir_unwalkable = [&](size_t walk_x, size_t walk_y, size_t dir) {
    return unwalkable_flags[walk_y * 256 * 4 + walk_x] & (1 << dir) ? true : false;
  };
  auto set_dir_unwalkable = [&](size_t walk_x, size_t walk_y, size_t dir) {
    unwalkable_flags[walk_y * 256 * 4 + walk_x] |= 1 << dir;
  };
  auto flip_dir_walkable = [&](size_t walk_x, size_t walk_y, size_t dir) {
    unwalkable_flags[walk_y * 256 * 4 + walk_x] ^= 1 << dir;
  };
  auto is_every_dir_walkable = [&](size_t walk_x, size_t walk_y) {
    return unwalkable_flags[walk_y * 256 * 4 + walk_x] & 0x7f ? false : true;
  };

  auto set_unwalkable_flags = [&]() {
    if (map_walk_width() == 0 || map_walk_height() == 0) error("map width/height is zero");

    for (size_t y = 0; y != map_walk_height(); ++y) {
      for (size_t x = 0; x != map_walk_width(); ++x) {
        if (!Broodwar->isWalkable(x, y)) {
          set_unwalkable(x, y);
        }
      }
    }

    for (size_t y = 0; y != map_walk_height(); ++y) {
      for (size_t x = 0; x != map_walk_width(); ++x) {
        if (is_unwalkable(x, y)) continue;
        if (y == 0 || is_unwalkable(x, y - 1)) set_dir_unwalkable(x, y, 0);
        if (x == map_walk_width() - 1 || is_unwalkable(x + 1, y)) set_dir_unwalkable(x, y, 1);
        if (y == map_walk_height() - 1 || is_unwalkable(x, y + 1)) set_dir_unwalkable(x, y, 2);
        if (x == 0 || is_unwalkable(x - 1, y)) set_dir_unwalkable(x, y, 3);
      }
    }
  };

  auto create_region = [&](rect_t<xy_t<size_t>> area) {
    auto* r = get_new_region();
    uint16_t flags = (uint16_t)regions.tile_region_index[area.from.y * 256 + area.from.x];
    if (flags < 5000) error("attempt to create region inside another region");
    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) {
        if (regions.tile_region_index[y * 256 + x] < 5000) error("attempt to create overlapping region");
        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, map_tile_height() - 1 },{ map_tile_width(), map_tile_height() } });
    r->area = { { 0, (int)map_height() - 32 }, { (int)map_width(), (int)map_height() } };
    r->center.x = ((r->area.from.x + r->area.to.x) * 256 / 2);
    r->center.y = ((r->area.from.y + r->area.to.y) * 256 / 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 = 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 = 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 = 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, map_tile_width());
          size_t max_end_y = std::min(begin_y + 7, map_tile_height());

          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 (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 (regions.tile_region_index[end_y * 256 + x] != index) {
                  y_is_good = false;
                  break;
                }
              }
            }

            if (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;

        if (regions.regions.size() >= 5000) error("too many regions (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 < map_tile_width()) ++end_x;
          size_t& end_y = r->tile_area.to.y;
          if (end_y < map_tile_height()) ++end_y;

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

          auto is_neighbor = [&](size_t x, size_t y) {
            if (x != 0 && regions.tile_region_index[y * 256 + x - 1] == index) return true;
            if (x != map_tile_width() - 1 && regions.tile_region_index[y * 256 + x + 1] == index) return true;
            if (y != 0 && regions.tile_region_index[(y - 1) * 256 + x] == index) return true;
            if (y != map_tile_height() - 1 && 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 (regions.tile_region_index[y * 256 + x] == flags && is_neighbor(x, y)) {
                  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 != regions.regions.size(); ++i) {
            expand(&regions.regions[i]);
          }
        }

      }
      else {
        if (regions.regions.size() >= 5000) error("too many regions (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++] = 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 < map_tile_width(), tile_x + 1, tile_y);
      test(tile_y + 1 < map_tile_height(), 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 < map_tile_width(), tile_x + 1, tile_y - 1);
      test(tile_y + 1 < map_tile_height() && tile_x > 0, tile_x - 1, tile_y + 1);
      test(tile_y + 1 < map_tile_height() && tile_x + 1 < map_tile_width(), tile_x + 1, tile_y + 1);
      return r;
    };

    auto refresh_regions = [&]() {

      for (auto& r : 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 != map_tile_height(); ++y) {
        for (size_t x = 0; x != map_tile_width(); ++x) {
          size_t index = regions.tile_region_index[y * 256 + x];
          if (index < 5000) {
            auto* r = &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 : regions.regions) {
        if (r.tile_count == 0) r.flags = 0x1fff;
      }

      for (auto& r : 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 (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 = &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 (!is_walkable(walk_x, walk_y)) return false;
                  if (!is_walkable(walk_x + 1, walk_y)) return false;
                  if (!is_walkable(walk_x, walk_y + 1)) return false;
                  if (!is_walkable(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 == &regions.regions.front() && &v != &r.non_walkable_neighbors.back()) std::swap(v, r.non_walkable_neighbors.back());
          }
        }

      }

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

      for (auto& r : 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 : 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 it = std::rbegin(regions.regions); it != std::rend(regions.regions); ++it) {
        auto& r = *it;
        if (r.tile_count == 0 || r.tile_count >= n || r.group_index >= 0x4000) continue;
        regions_t::region* smallest_neighbor = nullptr;
        auto eval = [&](regions_t::region* 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 = 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 : 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 != regions.regions.size(); ++i) {
      auto* r = &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;
        regions.regions[new_index] = std::move(*r);
      }
    }
    for (size_t y = 0; y != map_tile_height(); ++y) {
      for (size_t x = 0; x != map_tile_width(); ++x) {
        size_t& index = regions.tile_region_index[y * 256 + x];
        index = reindex[index];
      }
    }
    regions.regions.resize(new_region_count);

    refresh_regions();

    regions.split_regions.clear();

    for (size_t y = 0; y != map_tile_height(); ++y) {
      for (size_t x = 0; x != map_tile_width(); ++x) {
        ///////////////////// TODO
        //size_t index = y * map_tile_width() + x;
        //auto tile = st.tiles[index];
        //if (~tile.flags & tile_t::flag_partially_walkable) continue;
        /////////////////////
        auto neighbors = get_neighbors(x, y);
        auto* r = &regions.regions[regions.tile_region_index[y * 256 + x]];
        auto count_4x1_walkable = [&](size_t walk_x, size_t walk_y) {
          size_t r = 0;
          if (is_walkable(walk_x, walk_y)) ++r;
          if (is_walkable(walk_x + 1, walk_y)) ++r;
          if (is_walkable(walk_x + 2, walk_y)) ++r;
          if (is_walkable(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 (is_walkable(walk_x, walk_y)) ++r;
          if (is_walkable(walk_x, walk_y + 1)) ++r;
          if (is_walkable(walk_x, walk_y + 2)) ++r;
          if (is_walkable(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 (!Broodwar->isWalkable(WalkPosition(TilePosition(x, y)) + 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 = &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 = &regions.regions[highest_nindex];
            else r2 = 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] = is_walkable(walk_x, walk_y) ? 0 : 1;
          n_unwalkable[5] = is_walkable(walk_x + 3, walk_y) ? 0 : 1;
          n_unwalkable[6] = is_walkable(walk_x, walk_y + 3) ? 0 : 1;
          n_unwalkable[7] = is_walkable(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 = &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 && !is_walkable(walk_x - 1, walk_y - 1)) set = true;
              if (i == 5 && !is_walkable(walk_x + 4, walk_y - 1)) set = true;
              if (i == 6 && !is_walkable(walk_x - 1, walk_y + 4)) set = true;
              if (i == 7 && !is_walkable(walk_x + 4, walk_y + 4)) set = true;
              if (set) {
                highest_n = n;
                highest_nindex = nindex;
              }
            }
          }
          if (highest_n) {
            if (highest_nindex < 0x2000) r2 = &regions.regions[highest_nindex];
            else r2 = regions.split_regions[highest_nindex - 0x2000].b;
          }
        }
        if (!r2 || r2 == r) mask = r->walkable() ? 0 : 0xffff;
        else if (!r->walkable() && !r2->walkable()) mask = 0xffff;
        regions.tile_region_index[y * 256 + x] = 0x2000 + regions.split_regions.size();
        if (r->walkable()) {
          regions.split_regions.push_back({ mask, r, r2 ? r2 : r });
        }
        else {
          regions.split_regions.push_back({ mask, r2 ? r2 : r, r });
        }
      }
    }

  };

  auto create_contours = [&]() {

    regions.contours = {};

    size_t next_x = 0;
    size_t next_y = 0;
    auto next = [&]() {
      size_t x = next_x;
      size_t y = next_y;
      if (x >= map_walk_width()) {
        error("create_contours::next: unreachable");
        x = 0;
        ++y;
        if (y >= map_walk_height()) y = 0;
      }
      x = x / 4 * 4;
      size_t start_x = x;
      size_t start_y = y;
      while (is_every_dir_walkable(x, y) && is_every_dir_walkable(x + 1, y) && is_every_dir_walkable(x + 2, y) && is_every_dir_walkable(x + 3, y)) {
        x += 4;
        if (x == map_walk_width()) {
          x = 0;
          ++y;
          if (y == map_walk_height()) {
            y = 0;
          }
        }
        if (x == start_x && y == start_y) return false;
      }
      while (!is_walkable(x, y) || is_every_dir_walkable(x, y)) {
        ++x;
        if (x == map_walk_width()) error("create_contours: out of bounds");
      }
      next_x = x;
      next_y = y;
      return true;
    };

    while (next()) {

      std::array<int, 16> clut = { -1,  -1, 8, -1, 8, 8, -1, 8, 0, -1, 8, 0, 7, 8, -1, 7 };
      std::array<int, 16> nlut = { 8, -1, 8, 8, -1, 8, -1, -1, 7, -1, 8, 7, 0, 8, -1, 0 };

      size_t x = next_x;
      size_t y = next_y;

      if (is_dir_walkable(x, y, 0) && is_dir_walkable(x, y, 1) && is_dir_unwalkable(x, y, 2)) {
        ++y;
        --x;
      }
      size_t first_unwalkable_dir = 0;
      int lut1val = is_dir_unwalkable(x, y, 0) && is_dir_unwalkable(x, y, 3) ? 0 : 1;
      for (int i = 0; i < 4; ++i) {
        if (is_dir_unwalkable(x, y, i)) {
          first_unwalkable_dir = i;
          break;
        }
      }

      size_t clut_index = first_unwalkable_dir + 4 * lut1val;
      int start_cx = int(clut[clut_index * 2] + x * 8);
      int start_cy = int(clut[clut_index * 2 + 1] + y * 8);

      flip_dir_walkable(x, y, first_unwalkable_dir);

      int cx = start_cx;
      int cy = start_cy;

      auto cur_dir = first_unwalkable_dir;
      while (true) {
        auto next_dir = (cur_dir + 1) & 3;
        int relx = next_dir == 1 ? 1 : next_dir == 3 ? -1 : 0;
        int rely = next_dir == 0 ? -1 : next_dir == 2 ? 1 : 0;
        flip_dir_walkable(x, y, cur_dir);
        int next_walkable = 0;
        if (is_dir_walkable(x, y, next_dir)) {
          next_walkable = 1;
          while (is_dir_unwalkable(x + relx, y + rely, cur_dir)) {
            x += relx;
            y += rely;
            flip_dir_walkable(x, y, cur_dir);
            if (is_dir_unwalkable(x, y, next_dir)) {
              next_walkable = 0;
              break;
            }
          }
        }
        size_t nlut_index = cur_dir + 4 * next_walkable;

        int nx = int(nlut[nlut_index * 2] + x * 8);
        int ny = int(nlut[nlut_index * 2 + 1] + y * 8);

        uint8_t flags0 = (uint8_t)(cur_dir ^ 2 * lut1val ^ (~(2 * cur_dir) & 3));
        uint8_t flags1 = (uint8_t)(cur_dir ^ 2 * (next_walkable ^ (cur_dir & 1)) ^ 1);
        if (cur_dir == 0) {
          uint8_t flags = (flags0 & 3) | 4 * ((flags1 & 3) | 4 * (lut1val | 2 * next_walkable));
          regions.contours[cur_dir].push_back({ { cy, cx, nx }, cur_dir, flags });
        }
        else if (cur_dir == 1) {
          uint8_t flags = (flags0 & 3) | 4 * ((flags1 & 3) | 4 * (lut1val | 2 * next_walkable));
          regions.contours[cur_dir].push_back({ { cx, cy, ny }, cur_dir, flags });
        }
        else if (cur_dir == 2) {
          uint8_t flags = (flags1 & 3) | 4 * ((flags0 & 3) | 4 * (next_walkable | 2 * lut1val));
          regions.contours[cur_dir].push_back({ { cy, nx, cx }, cur_dir, flags });
        }
        else {
          uint8_t flags = (flags1 & 3) | 4 * ((flags0 & 3) | 4 * (next_walkable | 2 * lut1val));
          regions.contours[cur_dir].push_back({ { cx, ny, cy }, cur_dir, flags });
        }

        if (!next_walkable) cur_dir = next_dir;
        else {
          int nrel[4][2] = { { 1, -1 },{ 1, 1 },{ -1, 1 },{ -1, -1 } };
          x += nrel[cur_dir][0];
          y += nrel[cur_dir][1];
          if (cur_dir == 0) cur_dir = 3;
          else --cur_dir;
        }
        cx = nx;
        cy = ny;
        lut1val = next_walkable;

        if (cx == start_cx && cy == start_cy) break;
      }

      flip_dir_walkable(x, y, cur_dir);

    }

    for (auto& v : regions.contours) {
      std::sort(v.begin(), v.end(), [&](auto& a, auto& b) {
        if (a.v[0] != b.v[0]) return a.v[0] < b.v[0];
        return a.v[1] < b.v[1];
      });
    }

  };

  regions.tile_bounding_box = { { 0, 0 },{ map_tile_width(), map_tile_height() } };

  set_unwalkable_flags();

  for (size_t y = 0; y != map_tile_height(); ++y) {
    for (size_t x = 0; x != map_tile_width(); ++x) {
      auto& index = regions.tile_region_index[y * 256 + x];

      int height = Broodwar->getGroundHeight(x, y);

      ///////////////////// TODO
      // auto& t = st.tiles[y * map_tile_width() + x];
      // if (~t.flags & tile_t::flag_walkable) index = 0x1ffd;
      /////////////////////
      if (true) index = 0x1ffd;
      else if (height == 2 || height == 3) index = 0x1ff9;
      else if (height == 4 || height == 5) index = 0x1ffa;
      else index = 0x1ffb;
    }
  }

  create_unreachable_bottom_region();

  create_regions();

  create_contours();

}

PathingX.h

#pragma once

#include <cstdint>
#include <array>
#include <vector>

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 };
  }
};

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<size_t> center;
    rect_t<xy_t<int>> 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;
  };

  struct contour {
    std::array<int, 3> v;
    size_t dir;
    uint8_t flags;
  };

  // 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;

  std::array<std::vector<contour>, 4> contours;

};