C++

Forum

 
Xonix mechanics

Geckoo (362)
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
Last edited on
jonnin (11437)
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 (3932)
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.
Last edited on
mbozzi (3932)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
#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;
}



Last edited on
mbozzi (3932)
Here is the uninteresting, platform-specific part of the code. Please note the two posts should be combined into one source file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
#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;
}

Last edited on
Topic archived. No new replies allowed.