diff options
| -rw-r--r-- | Makefile | 15 | ||||
| -rw-r--r-- | README.md | 8 | ||||
| -rwxr-xr-x | rectangles.c | 148 |
3 files changed, 171 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b894e43 --- /dev/null +++ b/Makefile @@ -0,0 +1,15 @@ +PROG=rectangles +CC=gcc +FLAGS=-lm -lraylib + +.DEFAULT_GOAL := build + +install: ${PROG} + cp ${PROG} ${PREFIX}/bin/ + +build: ${PROG}.c + ${CC} ${PROG}.c -o ${PROG} ${FLAGS} + +clean: ${PROG} + rm ${PROG} + diff --git a/README.md b/README.md new file mode 100644 index 0000000..65ece48 --- /dev/null +++ b/README.md @@ -0,0 +1,8 @@ +# Rectangles + +A simple proof of concept algorithm to combine multiple tiled rectangles into a smaller number. This can be used to optimise the number of rectangles to check for collision in a game. + +## Requirements + +- C Compiler +- raylib diff --git a/rectangles.c b/rectangles.c new file mode 100755 index 0000000..ded41bd --- /dev/null +++ b/rectangles.c @@ -0,0 +1,148 @@ +#include <complex.h> +#include <raylib.h> +#include <stdlib.h> +#include <stdio.h> +#include <math.h> + +#define TILESIZE 50 + +#define SCREEN_W 800 +#define SCREEN_H 600 +#define RECT_COUNT (SCREEN_H / TILESIZE) * (SCREEN_W / TILESIZE) +#define GRID_H (int) (SCREEN_W / TILESIZE); +#define GRID_W (int) (SCREEN_H / TILESIZE); + +Rectangle rectangles[RECT_COUNT]; + +int draw_grid() { + // vertical lines + for (int x = 0; x < SCREEN_W; x += TILESIZE) { + DrawLine(x, 0, x, SCREEN_H, DARKGRAY); + } + // vertical lines + for (int y = 0; y < SCREEN_H; y += TILESIZE) { + DrawLine(0, y, SCREEN_W, y, DARKGRAY); + } +} + +int rect_valid(Rectangle rect) { + return rect.width || rect.height; +} + + +int draw_rectangles() { + for (int i = 0; i < RECT_COUNT; i++) { + Rectangle rectangle = rectangles[i]; + if (rect_valid(rectangle)) { + DrawRectangleRec(rectangle, DARKGRAY); + } + } +} + +int rects_touch_y(Rectangle rect_a, Rectangle rect_b) { + return rect_a.x == rect_b.x && rect_a.width == rect_b.width && + (rect_a.y == rect_b.y + rect_b.height || + rect_b.y == rect_a.y + rect_a.height); +} + +int rects_touch_x(Rectangle rect_a, Rectangle rect_b) { + return rect_a.y == rect_b.y && rect_a.height == rect_b.height && + (rect_a.x == rect_b.x + rect_b.width || + rect_b.x == rect_a.x + rect_a.width); +} + + +int draw_optimised_rectangles() { + Rectangle *optimised = malloc(sizeof(Rectangle) * RECT_COUNT); + int index = 0; + + // copy rectangles to optimised + + for (int i = 0; i < RECT_COUNT; i++) { + Rectangle rectangle = rectangles[i]; + if (rect_valid(rectangle)) { + optimised[i] = rectangle; + } + } + + Rectangle rect_a, rect_b; + + // merge rectangles in x direction + + for (int i = 0; i < RECT_COUNT; i++) { + if (rect_valid(rect_a = optimised[i])) + for (int j = 0; j < RECT_COUNT; j++) { + if (i != j && rect_valid(rect_b = optimised[j]) + && rects_touch_x(rect_a, rect_b)) { + optimised[i].x = rect_a.x < rect_b.x ? rect_a.x : rect_b.x; + optimised[i].width = rect_a.width + rect_b.width; + rect_a = optimised[i]; + // delete j + optimised[j].width = 0; + } + } + } + + // merge rectangles in y direction + + for (int i = 0; i < RECT_COUNT; i++) { + if (rect_valid(rect_a = optimised[i])) + for (int j = 0; j < RECT_COUNT; j++) { + if (i != j && rect_valid(rect_b = optimised[j]) + && rects_touch_y(rect_a, rect_b)) { + + optimised[i].y = rect_a.y < rect_b.y ? rect_a.y : rect_b.y; + optimised[i].height = rect_a.height + rect_b.height; + rect_a = optimised[i]; + // delete j + optimised[j].width = 0; + } + } + } + + Rectangle rectangle; + for (int i = 0; i < RECT_COUNT; i++) { + if (rect_valid(rectangle = optimised[i])) + DrawRectangleLinesEx(rectangle, 2, GREEN); + } + free(optimised); +} + +int draw() { + BeginDrawing(); + ClearBackground(LIGHTGRAY); + + draw_grid(); + draw_rectangles(); + draw_optimised_rectangles(); + + if (IsMouseButtonDown(MOUSE_BUTTON_LEFT)) { + int gridx = (int) floor(GetMouseX() / TILESIZE); + int gridy = (int) floor(GetMouseY() / TILESIZE); + + Rectangle rectangle = (Rectangle){gridx * TILESIZE, gridy * TILESIZE, TILESIZE, TILESIZE}; + + // keep rectangles in order so that larger y and x are more right / left + int rect_index = gridx + gridy*GRID_H; + rectangles[rect_index] = rectangle; + } + + EndDrawing(); +} + +int main() { + SetTargetFPS(60); + InitWindow(SCREEN_W, SCREEN_H, "Rectangles"); + + for (int i = 0; i < RECT_COUNT; i++) { + rectangles[i] = (Rectangle){0, 0, 0, 0}; + } + + while(!WindowShouldClose()) { + draw(); + } + + CloseWindow(); + + return 0; +} |