diff options
| -rw-r--r-- | main.c | 147 |
1 files changed, 131 insertions, 16 deletions
@@ -2,6 +2,7 @@ #include <string.h> #include <stdlib.h> +#include <stdbit.h> #include <time.h> #include "wrmr.h" @@ -109,25 +110,125 @@ typedef struct { SnkSeg seg[SNK_SEG_MAX]; } Snake; -Snake snk = { 0 }; +Snake snk = { + .len = 1 +}; typedef struct { i16 x, y; } Apple; -#define APPLE_MAX 32 +#define APPLE_MAX ((WIDTH * HEIGHT) / 10 + 1) +u32 napple = APPLE_MAX; Apple apple[APPLE_MAX]; +typedef struct { + u64 len; + u64 data[(WIDTH * HEIGHT + 63) / 64]; +} BitBoard; + +static inline int bitb_has(BitBoard *b, i16 x, i16 y) { + u32 i = y * WIDTH + x; + return !!(b->data[i / 64] & (1ULL << (i & 63))); +} + +static inline void bitb_del(BitBoard *b, i16 x, i16 y) { + if (bitb_has(b, x, y)) { + u32 i = y * WIDTH + x; + b->data[i / 64] &= ~(1ULL << (i & 63)); + b->len--; + } +} + +static inline void bitb_add(BitBoard *b, i16 x, i16 y) { + if (!bitb_has(b, x, y)) { + u32 i = y * WIDTH + x; + b->data[i / 64] |= 1ULL << (i & 63); + b->len++; + } +} + +static inline int bitb_nth(BitBoard *b, u32 nth, i16 *x, i16 *y) { + for (u32 i = 0; i < sizeof b->data * sizeof(u64); i++) { + u64 d = b->data[i]; + u32 j = i * 64; + while (d) { + u32 z = stdc_trailing_zeros(d); + j += z; + if (!nth--) { + *x = j % WIDTH; + *y = j / WIDTH; + return 1; + } + d >>= z + 1; + j += 1; + } + } + + /* + while (i < WIDTH * HEIGHT) { + if (b->data[i / 64] & (1ULL << (i & 63))) { + nth--; + if (!nth) { + *x = i % WIDTH; + *y = i / WIDTH; + return 1; + } + } + i++; + } + */ + return 0; +} + +static inline void bitb_fill(BitBoard *b, int v) { + u64 val = v ? (u64)-1 : 0; + for (u32 i = 0; i < sizeof b->data / sizeof *b->data; i++) { + b->data[i] = val; + } + b->len = v ? WIDTH * HEIGHT : 0; +} + +#include <assert.h> + +void apple_bitboard(BitBoard *b) { + bitb_fill(b, 1); + for (u32 j = 0; j < snk.len; j++) { + bitb_del(b, snk.seg[j].x, snk.seg[j].y); + } + for (u32 j = 0; j < napple; j++) { + bitb_del(b, apple[j].x, apple[j].y); + } +} + +u32 last_apple_bb_len = 0; +u32 last_apple_pos = 0; void replace_apple(u32 i) { - Apple *a = &apple[i]; - do { - a->x = rand() % WIDTH; - a->y = rand() % HEIGHT; - } while (board[a->y][a->x] != TILE_FLOOR); + BitBoard bb; + //printf("%u after apple removal\n\r", bb.len); + //assert(bb.len < WIDTH * HEIGHT); + //bitb_del(&bb, WIDTH - 1, HEIGHT - 1); + apple_bitboard(&bb); + last_apple_bb_len = bb.len; + if (bb.len > 0) { + Apple *a = &apple[i]; + bitb_nth(&bb, rand() % bb.len, &a->x, &a->y); + for (u32 j = 0; j < napple; j++) { + if (j != i) { + //assert(!(apple[j].x == a->x && apple[j].y == a->y)); + } + } + last_apple_pos = a->y * WIDTH + a->x; + } else { + if (i + 1 < napple) { + apple[i] = apple[napple - 1]; + } + napple--; + } } void place_apple(void) { - for (u32 i = 0; i < APPLE_MAX; i++) { + for (u32 i = 0; i < napple; i++) { replace_apple(i); } } @@ -141,12 +242,12 @@ void brd_clear(void) { } void brd_draw(void) { - /* u32 left = COLS / 2 - WIDTH; u32 top = LINES / 2 - HEIGHT / 2; - */ + /* u32 left = COLS / 2 - snk.seg->x * 2; u32 top = LINES / 2 - snk.seg->y; + */ u32 right = left + WIDTH * 2; u32 bottom = top + HEIGHT; @@ -194,7 +295,7 @@ void snk_draw(Snake *s) { } void apple_draw(void) { - for (u32 i = 0; i < APPLE_MAX; i++) { + for (u32 i = 0; i < napple; i++) { board[apple[i].y][apple[i].x] = TILE_APPLE; } } @@ -206,18 +307,31 @@ void draw(void *ctx) { vui_clear(); brd_clear(); - snk_draw(&snk); apple_draw(); + snk_draw(&snk); brd_draw(); if (!alive) { vui_puts(COLS/2 - 4, LINES/2, "YOU DIED!"); } vui_printf(0, 0, "input polling iterations: %u", poll_input_iter); + vui_printf(0, 1, "apples: %u", napple); + vui_printf(0, 2, "last apple bitboard len: %u", last_apple_bb_len); + vui_printf(0, 3, "last apple position: %u", last_apple_pos % WIDTH, last_apple_pos / WIDTH); + vui_printf(-1, 0, "snake pos: %hd, %hd ", snk.seg->x, snk.seg->y); + + BitBoard bb; + apple_bitboard(&bb); + i16 x, y; + int r = bitb_nth(&bb, 0, &x, &y); + vui_printf(0, 4, "0th bitboard free space (%d): %hd, %hd / %u", r, x, y, bb.len); + for (u32 i = 0; i < sizeof bb.data / sizeof *bb.data; i++) { + vui_printf(0, 6 + i, "%016lX", bb.data[i]); + } } void update(void) { - for (u32 i = 0; i < APPLE_MAX; i++) { + for (u32 i = 0; i < napple; i++) { if (snk.seg[0].x == apple[i].x && snk.seg[0].y == apple[i].y) { replace_apple(i); snk.len++; @@ -244,7 +358,7 @@ void update(void) { snk.seg[0].x = x; snk.seg[0].y = y; - vui_scroll(-DIR_DX(snk.dir) * 2, -DIR_DY(snk.dir)); + //vui_scroll(-DIR_DX(snk.dir) * 2, -DIR_DY(snk.dir)); } void snk_chg_dir(Snake *s, Dir d) { @@ -258,14 +372,15 @@ void snk_chg_dir(Snake *s, Dir d) { int main(void) { srand(time(NULL)); vui_init(); + vui_redraw_fn(draw); snk.dir = DIR_RIGHT; snk.seg[snk.len++] = (SnkSeg) { 0, 0 }; alive = 1; paused = 0; - vui_redraw_fn(draw); + napple = APPLE_MAX; place_apple(); while (alive) { - poll_input(30); + poll_input(33); draw(NULL); vui_blit(); switch (pop_input()) { |