使用raylib
代码来源
https://github.com/seyhajin/flux-samples/blob/master/raylib/quadtree/quadtree.c
原来是视锥碰撞四叉树,经过一周开发变成碰撞检测四叉树可视化
后经过改写
绿色检测
灰色检测
//https://github.com/seyhajin/flux-samples/blob/master/raylib/quadtree/quadtree.c/********************************************************************************************* raylib: quadtree (adapted for HTML5 platform)** This example is prepared to compile for PLATFORM_WEB, PLATFORM_DESKTOP and PLATFORM_RPI* As you will notice, code structure is slightly diferent to the other examples...* To compile it for PLATFORM_WEB just uncomment #define PLATFORM_WEB at beginning** This example has been created using raylib 3.7 (www.raylib.com)* raylib is licensed under an unmodified zlib/libpng license (View raylib.h for details)** Copyright (c) 2015 Ramon Santamaria (@raysan5)* Copyright (c) 2021 Christophe TES (@seyhajin)*********************************************************************************************/#include <stdio.h>
#include <math.h>#include "raylib.h"
#include "raymath.h"//----------------------------------------------------------------------------------
// Types and Structures Definition
//----------------------------------------------------------------------------------//----- Frustumstatic Vector2 fl, fr; // left/right planes//----- Cameratypedef struct camera_s {Vector2 pos;float fov;int num; // 记录编号,解决自己碰撞自己问题
} camera_t;camera_t create_camera(float x, float y, float fov) {return (camera_t) {.pos = (Vector2) {x, y},.fov = fov};
}typedef struct target {int targeti;int targetj;int targetwidth;int targetheight;RenderTexture2D pic;
// RenderTexture* pic;target* linknext; // 这是四叉树里增加敌人,发现要增加好几个敌人时,追加在敌人后面,最简单修改就是增加一行,于是反过来修改敌人数据int number; // 记录敌人编号int islive;
} target;//----- Quadtreetypedef enum quad_child_e {CHILD_TL, // top-leftCHILD_BL, // bottom-leftCHILD_BR, // bottom-rightCHILD_TR, // top-rightCHILD_COUNT
} quad_child_t;typedef struct quadtree_s {Vector2 min;Vector2 max;struct quadtree_s *childs[CHILD_COUNT];target* enemy; // 绑定的数据
} quadtree_t;quadtree_t *create_quadtree(float xmin, float ymin, float xmax, float ymax, int depth) {quadtree_t *qt = (quadtree_t*)MemAlloc(sizeof(quadtree_t));qt->min = (Vector2) {xmin, ymin};qt->max = (Vector2) {xmax, ymax};// 追加空记录qt->enemy = NULL;if (depth > 0) {float xavg = (xmin + xmax) * 0.5f;float yavg = (ymin + ymax) * 0.5f;depth--;qt->childs[CHILD_TL] = create_quadtree(xmin, ymin, xavg, yavg, depth);qt->childs[CHILD_BL] = create_quadtree(xmin, yavg, xavg, ymax, depth);qt->childs[CHILD_BR] = create_quadtree(xavg, yavg, xmax, ymax, depth);qt->childs[CHILD_TR] = create_quadtree(xavg, ymin, xmax, yavg, depth);}return qt;
}void free_quadtree(quadtree_t *qt) {for (int i = 0; i < CHILD_COUNT; i++)MemFree(qt->childs[i]);MemFree(qt);
}int check(quadtree_t* qt, camera_t cam) {if (cam.pos.x > qt->min.x && cam.pos.x < qt->max.x && cam.pos.y > qt->min.y && cam.pos.y < qt->max.y) {return 1;}// 不加return 0 不出格子return 0;
}// 修改为查找数据并记录
void render_quadtree(quadtree_t *qt, camera_t cam, int depth) {if (check(qt, cam)) {if (qt->enemy == NULL) {qt->enemy = new target;qt->enemy->targetj = cam.pos.x;qt->enemy->targeti = cam.pos.y;qt->enemy->number = cam.num;} else if (qt->enemy->number == -1) {qt->enemy->targetj = cam.pos.x;qt->enemy->targeti = cam.pos.y;qt->enemy->number = cam.num;}// printf("%d\n", qt->enemy->number);if (depth > 1) {float xavg = (qt->min.x + qt->max.x) * 0.5f;float yavg = (qt->min.y + qt->max.y) * 0.5f;
// DrawLine(xavg, qt->min.y, xavg, qt->max.y, GRAY);DrawLine(xavg, qt->min.y, xavg, qt->max.y, GREEN);
// DrawLine(qt->min.x, yavg, qt->max.x, yavg, GRAY);DrawLine(qt->min.x, yavg, qt->max.x, yavg, GREEN);// 记录本层区域有敌人depth--;render_quadtree(qt->childs[CHILD_TL], cam, depth);render_quadtree(qt->childs[CHILD_BL], cam, depth);render_quadtree(qt->childs[CHILD_BR], cam, depth);render_quadtree(qt->childs[CHILD_TR], cam, depth);}}
}// 修改为查找数据并记录为已标记为“无” -1 表示没有敌人
// 修改自刚刚实现的查找记录功能数据void render_quadtreev3_delete(quadtree_t *qt, camera_t cam, int depth) {// 注释check 后清空数据未果if (check(qt, cam)) {if (qt->enemy == NULL) {qt->enemy = new target;}qt->enemy->targetj = -1;qt->enemy->targeti = -1;qt->enemy->number = -1;if (depth > 1) {float xavg = (qt->min.x + qt->max.x) * 0.5f;float yavg = (qt->min.y + qt->max.y) * 0.5f;// 记录本层区域有敌人depth--;// 注释掉render_quadtree 发现报错,原来是没有改旧函数导致直接重新标记 -_-|render_quadtreev3_delete(qt->childs[CHILD_TL], cam, depth);render_quadtreev3_delete(qt->childs[CHILD_BL], cam, depth);render_quadtreev3_delete(qt->childs[CHILD_BR], cam, depth);render_quadtreev3_delete(qt->childs[CHILD_TR], cam, depth);}}
}// 检测最小一个格子检测
// 追加返回值
//void render_quadtreev4_only_one(quadtree_t *qt, camera_t cam, int depth) {
int render_quadtreev4_only_one(quadtree_t *qt, camera_t cam, int depth) {// 原来禁用check可以打印全部记录数据// 这是对比12.绑定敌人数据与四叉树 对应名称的代码得知的// 不禁用,就是开始检测碰撞// 追加检测碰撞if (check(qt, cam)) {if (depth > 1) {float xavg = (qt->min.x + qt->max.x) * 0.5f;float yavg = (qt->min.y + qt->max.y) * 0.5f;DrawLine(xavg, qt->min.y, xavg, qt->max.y, GRAY);DrawLine(qt->min.x, yavg, qt->max.x, yavg, GRAY);// 先检测空if (qt->enemy != NULL) {if (cam.num != qt->enemy->number && qt->enemy->number != -1) {depth--;int a = 0;a += render_quadtreev4_only_one(qt->childs[CHILD_TL], cam, depth);if (a > 0) {return 1;}a += render_quadtreev4_only_one(qt->childs[CHILD_BL], cam, depth);if (a > 0) {return 1;}a += render_quadtreev4_only_one(qt->childs[CHILD_BR], cam, depth);if (a > 0) {return 1;}a += render_quadtreev4_only_one(qt->childs[CHILD_TR], cam, depth);if (a > 0) {return 1;}}}} else {// 最小格子记录// v4_only_one 绘制颜色仅绘制一格if (qt->enemy != NULL) {if (qt->enemy->number != cam.num && qt->enemy->number != -1) {
// printf("%d\n",qt->enemy->number);
// if (cam.pos.x > qt->enemy->targetj && cam.pos.x < qt->enemy->targetj + 30 && cam.pos.y > qt->enemy->targeti && cam.pos.y < qt->enemy->targeti + 30 ) {
// if (cam.pos.x > qt->enemy->targetj && cam.pos.x < qt->enemy->targetj + 130 && cam.pos.y > qt->enemy->targeti && cam.pos.y < qt->enemy->targeti + 130 ) {
// if (cam.pos.x > qt->enemy->targetj-10 && cam.pos.x < qt->enemy->targetj + 130 && cam.pos.y > qt->enemy->targeti-10 && cam.pos.y < qt->enemy->targeti + 130 ) {
// if (cam.pos.x >= qt->enemy->targetj && cam.pos.x < qt->enemy->targetj + 130 && cam.pos.y >= qt->enemy->targeti && cam.pos.y < qt->enemy->targeti + 130 ) {
// if ( cam.pos.x < qt->enemy->targetj + 130 && cam.pos.y < qt->enemy->targeti + 130 ) {
// if ( cam.pos.x < qt->enemy->targetj + 100 && cam.pos.y < qt->enemy->targeti + 100 ) {
// if ( cam.pos.x < qt->enemy->targetj + 10 && cam.pos.y < qt->enemy->targeti + 10 ) {// 复制粘贴自47.发现实现碰撞检测
// if (cam.pos.x > qt->enemy->targetj + 1 && cam.pos.x < qt->enemy->targetj + 10 && cam.pos.y + 1 > qt->enemy->targeti && cam.pos.y < qt->enemy->targeti + 10) {// 自100 进行对照移植
// if (cam.pos.x > qt->enemy->targetj + 1 && cam.pos.x < qt->enemy->targetj + 10 && cam.pos.y + 1 > qt->enemy->targeti && cam.pos.y < qt->enemy->targeti + 10) {
// if (cam.pos.x > qt->enemy->targetj && cam.pos.x < qt->enemy->targetj + 10 && cam.pos.y+1 > qt->enemy->targeti && cam.pos.y < qt->enemy->targeti + 10) {if (qt->enemy->number != cam.num && qt->enemy->number != -1) {printf("%d\n", qt->enemy->number);
// 测试之后,反而是黑色比红色准确
// DrawRectangle(qt->min.x, qt->min.y, qt->max.x - qt->min.x, qt->max.y - qt->min.y, RED);DrawRectangle(qt->enemy->targetj, qt->enemy->targeti, 10, 10, BLUE);return 1; // 碰撞上了}
// DrawRectangle(qt->enemy->targetj, qt->enemy->targeti, 100, 100,BLUE);}}}}// 没有碰撞就返回0return 0;
}//----------------------------------------------------------------------------------
// Global Variables Definition
//----------------------------------------------------------------------------------
static int screen_width = 1012;
static int screen_height = 1012;// Quadtree
static int quad_depth = 8; // depth
static int quad_size = 1012; // size
static quadtree_t *root;// Camera
static float cam_speed = 2; // speed
static float cam_fov = 60.0f; // field of view
static float view_line = 300; // frustum plane
static camera_t camera;//int enemysum = 100;
int enemysum = 10;
target* enemy;//----------------------------------------------------------------------------------
// Module Functions Declaration
//----------------------------------------------------------------------------------
void UpdateDrawFrame(void); // Update and Draw one frame//----------------------------------------------------------------------------------
// Main Enry Point
//----------------------------------------------------------------------------------
int main() {// Initialization//--------------------------------------------------------------------------------------InitWindow(screen_width, screen_height, "raylib: quadtree");// Create camera & quadtreefl = Vector2Zero();fr = Vector2Zero();camera = create_camera(quad_size / 2, quad_size / 2, cam_fov);root = create_quadtree(0, 0, quad_size, quad_size, quad_depth);SetTargetFPS(60); // Set our game to run at 60 frames-per-second//--------------------------------------------------------------------------------------target* enemyv2 = new target[enemysum];for (int n = 0; n < enemysum; n++) {enemyv2[n].targetj = rand() % 1000;enemyv2[n].targeti = rand() % 1000;enemyv2[n].targetwidth = rand() % 100;enemyv2[n].targetheight = rand() % 200;enemyv2[n].pic = LoadRenderTexture(enemyv2[n].targetwidth, enemyv2[n].targetheight);enemyv2[n].islive = 1;enemyv2[n].number = n;printf("%d %d\n", enemyv2[n].targetj, enemyv2[n].targeti);}enemy = enemyv2;for (int n = 0; n < enemysum; n++) {BeginTextureMode(enemy[n].pic);for (int i = 0; i < enemy[n].targetheight; i++) {for (int j = 0; j < enemy[n].targetwidth; j++) {DrawPixel(j, i, {n * 20 % 255, n * 20 % 255, n * 20 % 255 % 255, 255});}}EndTextureMode();}// Main game loopwhile (!WindowShouldClose()) { // Detect window close button or ESC keyUpdateDrawFrame();}// De-Initializationfree_quadtree(root);//--------------------------------------------------------------------------------------CloseWindow(); // Close window and OpenGL context//--------------------------------------------------------------------------------------return 0;
}//----------------------------------------------------------------------------------
// Module Functions Definition
//----------------------------------------------------------------------------------
void UpdateDrawFrame(void) {// Update//----------------------------------------------------------------------------------// TODO: Update your variables here//----------------------------------------------------------------------------------//Vector2 mouse_pos = GetMousePosition();// update camera positionif (IsKeyDown(KEY_LEFT)) {camera.pos.x -= cam_speed;} else if (IsKeyDown(KEY_RIGHT)) {camera.pos.x += cam_speed;}if (IsKeyDown(KEY_UP)) {camera.pos.y -= cam_speed;} else if (IsKeyDown(KEY_DOWN)) {camera.pos.y += cam_speed;}// camera anglefloat px = (float)GetMouseX() - camera.pos.x;float py = (float)GetMouseY() - camera.pos.y;float angle = atan2f(py, px);float cam_fov_rad = (camera.fov / 2.0f) * DEG2RAD;Vector2 cam_dir = (Vector2) {.x = camera.pos.x + (view_line * 0.5f) * cosf(angle),.y = camera.pos.y + (view_line * 0.5f) * sinf(angle)};// update frustum left positionfl.x = camera.pos.x + view_line * cosf(angle - cam_fov_rad);fl.y = camera.pos.y + view_line * sinf(angle - cam_fov_rad);// update frustum right positionfr.x = camera.pos.x + view_line * cosf(angle + cam_fov_rad);fr.y = camera.pos.y + view_line * sinf(angle + cam_fov_rad);// Draw//----------------------------------------------------------------------------------BeginDrawing();ClearBackground(WHITE);// 记录旧数据static camera_t oldcamera;// draw quadtreefor (int n = 0; n < enemysum; n++) {
// 不能相同名称的 static, 原来版本仅有一个static camera_t b 所以能跑
// static camera_t b;camera_t b;// 测试半天,发现没有加入标号b.num = enemy[n].number;for (int i = 0; i < enemy[n].targetheight ; i++) {b.pos.x = enemy[n].targetj + 0;b.pos.y = enemy[n].targeti + i;render_quadtree(root, b, quad_depth);}for (int i = 0; i < enemy[n].targetheight ; i++) {b.pos.x = enemy[n].targetj + enemy[n].targetwidth;b.pos.y = enemy[n].targeti + i;render_quadtree(root, b, quad_depth);}for (int j = 0; j < enemy[n].targetwidth ; j++) {b.pos.x = enemy[n].targetj + j;b.pos.y = enemy[n].targeti + 0;render_quadtree(root, b, quad_depth);}for (int j = 0; j < enemy[n].targetwidth ; j++) {b.pos.x = enemy[n].targetj + j;b.pos.y = enemy[n].targeti + enemy[n].targetheight ;render_quadtree(root, b, quad_depth);}}int playerj = camera.pos.x;int playeri = camera.pos.y;// 测试碰撞敌群for (int n = 0; n < enemysum; n++) {// 一个点camera_t b;// 自100追加numb.num = enemy[n].number;int a = 0;for (int i = 0; i < enemy[n].targetheight ; i ++) {b.pos.x = enemy[n].targetj + 0;b.pos.y = enemy[n].targeti + i;a += render_quadtreev4_only_one(root, b, quad_depth);if (a > 0) {break;}}for (int i = 0; i < enemy[n].targetheight ; i ++) {b.pos.x = enemy[n].targetj + enemy[n].targetwidth - 1;b.pos.y = enemy[n].targeti + i;a += render_quadtreev4_only_one(root, b, quad_depth);if (a > 0) {break;}}for (int j = 0; j < enemy[n].targetwidth ; j ++) {b.pos.x = enemy[n].targetj + j;b.pos.y = enemy[n].targeti + 0;a += render_quadtreev4_only_one(root, b, quad_depth);if (a > 0) {break;}}for (int j = 0; j < enemy[n].targetwidth ; j ++) {b.pos.x = enemy[n].targetj + j;b.pos.y = enemy[n].targeti + enemy[n].targetheight - 1 ;a += render_quadtreev4_only_one(root, b, quad_depth);if (a > 0) {break;}}// 随机倒退,减少重叠if (a > 0) {if (enemy[n].islive == 1) {if (enemy[n].targetj < playerj) {
// enemy[n].targetj += -1 - rand() % 30;enemy[n].targetj += -1 - rand() % 10;} else if (enemy[n].targetj > playerj) {
// enemy[n].targetj -= -1 - rand() % 30;enemy[n].targetj -= -1 - rand() % 10;}if (enemy[n].targeti > playeri) {
// enemy[n].targeti -= -1 - rand() % 30;enemy[n].targeti -= -1 - rand() % 10;} else if (enemy[n].targeti < playeri) {
// enemy[n].targeti += -1 - rand() % 30;enemy[n].targeti += -1 - rand() % 10;}}}}// 启用成功,没有旧标记了// 改颜色禁用测试碰撞效果// 删除旧数据,在敌人移动之前for (int n = 0; n < enemysum; n++) {camera_t b;// 测试批量网格// 自100追加numb.num = enemy[n].number;// 在发现进检测周围一周格子,于是原样删除,就仅删除四周一环格子,for (int i = 0; i < enemy[n].targetheight ; i++) {b.pos.x = enemy[n].targetj + 0;b.pos.y = enemy[n].targeti + i;render_quadtreev3_delete(root, b, quad_depth);}for (int i = 0; i < enemy[n].targetheight ; i++) {b.pos.x = enemy[n].targetj + enemy[n].targetwidth;b.pos.y = enemy[n].targeti + i;render_quadtreev3_delete(root, b, quad_depth);}for (int j = 0; j < enemy[n].targetwidth ; j++) {b.pos.x = enemy[n].targetj + j;b.pos.y = enemy[n].targeti + 0;render_quadtreev3_delete(root, b, quad_depth);}for (int j = 0; j < enemy[n].targetwidth ; j++) {b.pos.x = enemy[n].targetj + j;b.pos.y = enemy[n].targeti + enemy[n].targetheight ;render_quadtreev3_delete(root, b, quad_depth);}}DrawRectangleLines(root->min.x, root->min.y, root->max.x - root->min.x, root->max.y - root->min.y, RED);// 绘制敌人for (int n = 0; n < enemysum; n++) {DrawTexturePro(enemy[n].pic.texture,{0, 0, enemy[n].targetwidth, enemy[n].targetheight},{enemy[n].targetj, enemy[n].targeti, enemy[n].targetwidth, enemy[n].targetheight},{0, 0}, 0, WHITE);}// 敌人移动for (int n = 0; n < enemysum; n++) {if (enemy[n].islive == 1) {if (enemy[n].targetj < playerj) {enemy[n].targetj += 1;} else if (enemy[n].targetj > playerj) {enemy[n].targetj -= 1;}if (enemy[n].targeti > playeri) {enemy[n].targeti -= 1;} else if (enemy[n].targeti < playeri) {enemy[n].targeti += 1;}}}// draw frustum left planeDrawLine(camera.pos.x, camera.pos.y, fl.x, fl.y, GREEN);// draw frustum right planeDrawLine(camera.pos.x, camera.pos.y, fr.x, fr.y, RED);// draw cameraDrawLine(camera.pos.x, camera.pos.y, cam_dir.x, cam_dir.y, YELLOW);DrawCircle(camera.pos.x, camera.pos.y, 10, BLUE);// draw texts//DrawText(TextFormat("mouse.pos: (%f, %f)", px, py), 0, 0, 20, DARKGRAY);//DrawText(TextFormat("camera.pos: (%f, %f)", camera.pos.x, camera.pos.y), 0, 25, 20, DARKGRAY);DrawText(TextFormat("FPS %d", GetFPS()), 0, 0, 30, BLACK);EndDrawing();//----------------------------------------------------------------------------------
}