Xonix mechanics

[Geckoo]

Hello everyone. I would like to submit to you a problem with which I am struggling hard. I am developing a little project which is a clone of a famous game - Xonix. Maybe you know it. I am trying to fill a polygon when a player reaches the border, an erased zone or a segment which he drawed. I tried to implement a scanline computation, but it is not really efficient. I tested some vectors with corners as points (so when the player starts or when he changes his direction), trying to fill the polygon, checking which pixels are inside, but it is not really relevant - too big as computation. So this is my question :

It seems to me that the best way to achieve my goal is to fill separated pixels blocks (blocks which are surrendered by erased pixels or borders). Do you have an idea about the best way in order to reach my goal ?

A picture so as to show the main gameplay and my goal...
https://lh3.googleusercontent.com/qcWJqZdoUWxrdJ6a8uQWsAO_0FS7ub8XHWi8QiX5eiBym_YxnVdZbieL-mwKmeJ0Ww

[jonnin]

your graphics library should support filling a square (or rectangle) for you with either a color or an image.
If it does not, if you are doing pixel by pixel, you can do it that way, but I would look at using a slightly higher level toolset, its not worth it and its usually slower (the library will tell the graphics card to do it, your hand rolled code will likely be on the CPU ).

[mbozzi]

Are you a Windows user?

To address your question, you can use a flood-fill algorithm. No need to think in terms of polygons or anything.

[mbozzi]

I got tired of waiting for a reply, so I wrote a simple clone of the game for Windows. I must split the source file into two posts because otherwise it is slightly too long. Here is the interesting part of the code:

#include <chrono>
#include <cstdint>
#include <cstring>
#include <random>
#include <thread>
#include <utility>

using namespace std::literals;

using u8 = unsigned char;
using u32 = std::uint32_t;
using my_clock = std::chrono::steady_clock;
using microseconds = std::chrono::microseconds;

microseconds constexpr period = 30ms;
int constexpr board_w  = 75, board_h = 75, bytes_per_px = 4;
bool running = true;

unsigned board[board_w * board_h];
unsigned constexpr claim_bit = 0b001, trail_bit = 0b010, mark_bit  = 0b100;
static unsigned& get(int x, int y) { return ::board[y * board_w + x]; }

std::default_random_engine rng(
  static_cast<unsigned>(std::chrono::system_clock::now().time_since_epoch().count()));

unsigned constexpr border_width = 2;
unsigned constexpr l_bit = 0b0001, r_bit = 0b0010, t_bit = 0b0100, b_bit = 0b1000;
static constexpr unsigned border_collision(int x, int y)
{
  return
    ((x <= 0) << 0) | ((x >= (board_w  - 1)) << 1) | // screen x
    ((y <= 0) << 2) | ((y >= (board_h - 1)) << 3);  // screen y
}

struct keyboard { bool w, a, s, d; };

struct enemy
{
  int x, y, dx, dy;
  bool within_claim;

  enemy() : within_claim{false}
  {
    static std::uniform_int_distribution<> random_x{ 1, board_w - 1 };
    static std::uniform_int_distribution<> random_y{ 1, board_h - 1 };
    static std::bernoulli_distribution random_dxdy;

    do x = random_x(::rng); while (border_collision(x, 0) & (r_bit | l_bit));
    do y = random_y(::rng); while (border_collision(0, y) & (b_bit | t_bit));
    dx = random_dxdy(::rng)? 1: -1;
    dy = random_dxdy(::rng)? 1: -1;
  }
};

struct game_state
{
  enum direction { up, left, down, right, stopped } dir = stopped;

  int player_x = 0;
  int player_y = 0;

  enemy enemies[4];
};

enum class color: u32
{
  background = 0x00000000,
  claim      = 0x000040ff,
  trail      = 0x00303030,
  enemy      = 0x00ff0000,
  player     = 0x0000ff40,
};

static_assert(sizeof(color) == bytes_per_px);

static void set_color(u8* buf, unsigned off, color c)
{
  std::memcpy(buf + off, &c, sizeof c);
}

static void fill(int x, int y)
{
  auto& tile = get(x, y);
  if (tile || border_collision(x, y)) return;

  tile |= mark_bit;
  fill(x + 1, y);
  fill(x, y + 1);
  fill(x - 1, y);
  fill(x, y - 1);
}

// Returns time until the next update.
// Everything interesting happens here.
static microseconds update(u8* buf, keyboard kbd, microseconds delta)
{
  static game_state state;
  static microseconds elapsed;

  if (elapsed += delta; period >= elapsed)
    return period - elapsed;
  else elapsed = 0us;

  { // Decide the player's current direction based on the last key pressed.
    static keyboard old_kbd = kbd;
    if (!old_kbd.w && kbd.w) state.dir = state.up;
    if (!old_kbd.a && kbd.a) state.dir = state.left;
    if (!old_kbd.s && kbd.s) state.dir = state.down;
    if (!old_kbd.d && kbd.d) state.dir = state.right;
    old_kbd = kbd;
  }

  { // Claim borders.
    for (int x = 0; x < board_w; ++x)
      for (int i = 0; i < border_width; ++i)
      {
        get(x, i) |= claim_bit;
        get(x, board_h - 1 - i) |= claim_bit;
      }
    for (int y = 2; y < board_h - 2; ++y)
      for (int i = 0; i < border_width; ++i)
      {
        get(i, y) |= claim_bit;
        get(board_w - 1 - i, y) |= claim_bit;
      }
  }
  
  auto const orig_x = state.player_x;
  auto const orig_y = state.player_y;
  auto& orig_tile = get(orig_x, orig_y);
  
  // If the current tile is not claimed, make it part of the trail.
  if (! (orig_tile & claim_bit)) orig_tile |= trail_bit;

  // Move all the enemies:
  for (auto& enemy: state.enemies)
  {
    auto& [x, y, dx, dy, in_claim] = enemy;
    in_claim = get(x, y) & claim_bit;

    x += dx;
    if ((get(x, y) & claim_bit) != in_claim || border_collision(x, y) & (l_bit | r_bit))
    { dx *= -1; x += dx * 2; }
    if (get(x, y) & trail_bit) ::running = false;

    y += dy;
    if ((get(x, y) & claim_bit) != in_claim || border_collision(x, y) & (t_bit | b_bit))
    { dy *= -1; y += dy * 2; }
    if (get(x, y) & trail_bit) ::running = false;
  }

  // Move the player.
  auto const cs = border_collision(state.player_x, state.player_y);
  if (state.dir == state.right && !(cs & r_bit)) ++state.player_x;
  if (state.dir == state.left  && !(cs & l_bit)) --state.player_x;
  if (state.dir == state.down  && !(cs & b_bit)) ++state.player_y;
  if (state.dir == state.up    && !(cs & t_bit)) --state.player_y;

  // If the player has moved into their own trail, they lose:
  if (state.dir != state.stopped && get(state.player_x, state.player_y) & trail_bit)
    ::running = false;
  
  // If the player's entering a claimed area from an unclaimed area, stop
  // moving, then reset the trail and claim the new tiles.
  if (!(orig_tile & claim_bit) && (get(state.player_x, state.player_y) & claim_bit))
  {
    state.dir = state.stopped;

    for (auto const& enemy : state.enemies)
      fill(enemy.x, enemy.y);

    for (int x = 0; x < board_w; ++x)
      for (int y = 0; y < board_h; ++y)
      {
        auto& tile = get(x, y);
        if (! (tile & mark_bit)) tile |= claim_bit;
        tile &= ~(trail_bit | mark_bit);
      }
  }

  { // Draw the representation of the board.
    auto const xy = [](int x, int y)
    { return (y * bytes_per_px * board_w) + (x * bytes_per_px); };

    for (int x = 0; x < board_w; ++x)
      for (int y = 0; y < board_h; ++y)
      {
        auto& tile = get(x, y);

        if (tile & claim_bit)
          set_color(buf, xy(x, y), color::claim);
        else
          set_color(buf, xy(x, y), (tile & trail_bit)? color::trail: color::background);
      }

    set_color(buf, xy(state.player_x, state.player_y), color::player);
    for (auto const& enemy: state.enemies)
      set_color(buf, xy(enemy.x, enemy.y), color::enemy);
  }

  return 0us;
}

[mbozzi]

Here is the uninteresting, platform-specific part of the code. Please note the two posts should be combined into one source file.

#define _UNICODE 1
#define UNICODE 1
#include <windows.h>

constexpr int size_bytes = board_w * board_h * bytes_per_px;
u8 data [size_bytes];
BITMAPINFO info;

static void present(HDC dc, HWND w)
{
  RECT w_dimensions;
  GetClientRect(w, &w_dimensions);
  auto const w_width = w_dimensions.right - w_dimensions.left;
  auto const w_height = w_dimensions.bottom - w_dimensions.top;
  StretchDIBits(dc, 0, 0, w_width, w_height, 0, 0, board_w,
                board_h, data, &info, DIB_RGB_COLORS, SRCCOPY);
}

static LRESULT CALLBACK my_wndproc(HWND w, UINT m, WPARAM wp, LPARAM lp)
{
  switch (m)
  {
  case WM_DESTROY:
  case WM_CLOSE:
    ::running = false;
    return 0;
  case WM_PAINT:
  {
    PAINTSTRUCT ps;
    HDC dc = BeginPaint(w, &ps);
    present(dc, w);
    EndPaint(w, &ps);
    return 0;
  }
  default:
    return DefWindowProc(w, m, wp, lp);
  }
}

int WINAPI wWinMain(HINSTANCE inst, HINSTANCE, PWSTR, int)
{
  info.bmiHeader.biWidth = board_w;
  info.bmiHeader.biBitCount = 8 * bytes_per_px;
  info.bmiHeader.biSize = sizeof (BITMAPINFOHEADER);
  info.bmiHeader.biHeight = -board_h;
  info.bmiHeader.biPlanes = 1;
  info.bmiHeader.biCompression = BI_RGB;

  LPCWSTR class_name = L"xonix";
  WNDCLASSW wc {};
  wc.lpszClassName = class_name;
  wc.lpfnWndProc = my_wndproc;
  wc.hInstance = inst;
  wc.hCursor = LoadCursor(nullptr, IDC_ARROW);
  RegisterClass(&wc);
  
  HWND window =
    CreateWindow(wc.lpszClassName, L"Xonix", WS_OVERLAPPED | WS_CAPTION | WS_VISIBLE | WS_SYSMENU,
                  CW_USEDEFAULT, CW_USEDEFAULT, board_w * 12, board_w * 12, 0, 0, 0, 0);
  if (! window) return 1;

  my_clock::time_point t0 = my_clock::now(), t1;
  
  HDC dc = GetDC(window);
  MSG message {};
  while (::running)
  {
    while (PeekMessage(&message, nullptr, 0, 0, PM_REMOVE))
    {
      if (message.message == WM_QUIT) ::running = false;
      else DispatchMessage(&message);
    }

    keyboard kbd;

    {
      BYTE ks[256];
      GetKeyboardState(ks);
      auto& [w,a,s,d] = kbd;
      w = ks['W'] & 0x80;
      a = ks['A'] & 0x80;
      s = ks['S'] & 0x80;
      d = ks['D'] & 0x80;
    }

    t0 = std::exchange(t1, my_clock::now());
    microseconds time_until_next_update
      = update(data, kbd, std::chrono::duration_cast<microseconds>(t1 - t0));
    present(dc, window);

    if (time_until_next_update > 1ms)
      std::this_thread::sleep_for(1ms);
  }
  return 0;
}