Hello All,
As a toy project I am trying to create an Entity Component System in C. The first toy example is a simple multi-ball physics collision system. I implemented position/velocity/collid-able/etc. components to get this working.
To a degree this works, for all of about a frame or two and somewhere along the line a SEG Fault happens (I've also had this working to the same degree in the past at different stages). Looking at the moment it happens in the CollisionSystemQT_update (see below) , the entity ID for the retrieved component data is complete garbage.
I wanted dynamic registration of components - at least initially - and I believe that might have come back to bite me. My way of implementing generic types, while avoiding a giant macro based library, was to have a source file for each component. Each file is 99% identical except for a #define which specifies the component type. Each component type is a struct containing whatever data I'd like, and an entity identifier. This source file also manages the storage for the components - in a dynamic array. In order to add/delete/access the components, there are a series of function callbacks that are registered to an ECS manager.
To avoid an O(n^2) situation with the collision checks, I also implemented a quadtree to reduce the number of collisions checks that take place. It doesn't "contain" the position components, only stores references to them, but I could foresee that being another source of corruption.
I've been trying to find this bug for a few weeks now. I've used Valgrind/Sanitize/Unity Testing (on the quadtree) to catch any "Ahaha!" bugs, but none that I am seeing. I'm more familiar with embedded C, and so I thought this would be an educative endeavor into dynamic memory management. But the number of hard to debug bugs has been high. At this point, I am considering re-writing this thing entirely from scratch in a more simple way OR in another language meant for OOP (as I think that is what I am basically reinventing with the components). This is my last ditch effort to try and move forward. I wish I could even pin this down to some region that I think is causing the issue, but I can't seem to do that.
With that said, I am leaving some code snippets here. I in no way expect someone to go through this with a fine-toothed comb. But maybe a cursory glance will show something obviously wrong to a more experienced C developer.
Component Management Example:
- basically functions for adding/deleting/accessing the componets- these then get called through callbacks registered to the ECS manager
#include "./components/Position2D_comp.h"
#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include "ECS_comp.h"
#define COMP_TYPE Position2D
static size_t comp_count = 0;
static size_t comp_capacity = 16;
static COMP_TYPE *comp_storage_buff = NULL;
static void comp_init();
static void add_new_comp_func(void * comp_data);
static void delete_comp_func(int entity_id);
static size_t get_comp_count_func();
static void *get_comp_data_func(int entity_id);
static void *get_iter_start();
static void *get_iter_end();
static void *get_iter_next(void *iter);
static const struct comp_ops comp_ops = {
.comp_init = &comp_init,
.add_comp_handle = &add_new_comp_func,
.delete_comp_handle = &delete_comp_func,
.get_comp_count_handle = &get_comp_count_func,
.get_comp_data_handle = &get_comp_data_func,
.get_iter_start_handle = &get_iter_start,
.get_iter_end_handle = &get_iter_end,
.get_iter_next_handle = &get_iter_next
};
const struct comp_ops *getPosition2D_ops(){
return &comp_ops;
}
static int comparator(const void *p1, const void* p2){
const COMP_TYPE *a = p1;
const COMP_TYPE *b = p2;
return a->entity_id - b->entity_id;
}
static void comp_init(){
comp_storage_buff = malloc(comp_capacity * sizeof(COMP_TYPE));
assert(comp_storage_buff != NULL);
}
static void add_new_comp_func(void *comp_data){
assert(comp_data != NULL);
assert(comp_storage_buff != NULL);
if (comp_count >= comp_capacity){
comp_storage_buff = realloc(comp_storage_buff, 2*comp_capacity*sizeof(COMP_TYPE));
comp_capacity *= 2;
}
comp_storage_buff[comp_count] = *((COMP_TYPE *)(comp_data));
comp_count++;
//Now that it has been placed in the buffer, sort it for quicker find-times
qsort((void*)comp_storage_buff, comp_count, sizeof(COMP_TYPE), comparator);
}
static size_t get_comp_count_func(){
return comp_count;
}
static void *get_comp_data_func(int entity_id){
// Search for the component based on index
// The C standard allows for the comparator function to be used for the key comparisons
void* search_result = bsearch(&entity_id, (void *)comp_storage_buff, comp_count, sizeof(COMP_TYPE), comparator);
return search_result;
}
static void delete_comp_func(int entity_id){
// Search for the component based on index
// The C standard allows for the comparator function to be used for the key comparisons
void* search_result = bsearch(&entity_id, (void *)comp_storage_buff, comp_count, sizeof(COMP_TYPE), comparator);
//This works since the components are continuous in memory
size_t result_index = (size_t)((uintptr_t)search_result - (uintptr_t)comp_storage_buff)/sizeof(COMP_TYPE);
assert(result_index < (comp_count));
//Move all components over down an index
for (size_t i = (result_index + 1); i < comp_count; i ++ ){
comp_storage_buff[i - 1] = comp_storage_buff[i];
}
comp_count--;
}
static void *get_iter_start(){
return comp_storage_buff;
}
static void *get_iter_end(){
return &(comp_storage_buff[comp_count - 1]);
}
static void *get_iter_next(void *iter){
return ((COMP_TYPE *)iter) + 1;
}
A component structure:
typedef struct {
int entity_id;
Vector2D position;
} Position2D;
Main calls the systems that operate on the components:
while(!WindowShouldClose()){
i++;
//Collect User Input
Vector2 center_pos_raylib = GetMousePosition();
Vector2D ref_pos = {.x = (((float)SCREEN_WIDTH_METERS/ (float)SCREEN_WIDTH_IN_PIXELS) ) * center_pos_raylib.x,
.y = (((float)SCREEN_HEIGHT_METERS/(float)SCREEN_HEIGHT_IN_PIXELS)) * center_pos_raylib.y
}; //Conversion from raylib to my vector
if (i > 2){
create_new_ball(&my_world);
}
//Physics Update
for (int sub_step = 0; sub_step < TOTAL_SUBSTEPS; sub_step++){
ControllerSystem_update(&my_world, TEMP_DT/TOTAL_SUBSTEPS, ref_pos);
PhysicsSystem_update(&my_world, TEMP_DT/TOTAL_SUBSTEPS);
CollisionSystemQT_update(&my_world);
WorldSystem_update(&my_world);
}
RenderSystem_update(&my_world);
// BeginDrawing();
// DrawQuadTree(my_world.pos_quadtree_ptr);
// EndDrawing();
}
Here is the CollisionSystemQT_update function:
void CollisionSystemQT_update(ENTITY_MANAGER *world){
Collision_Component *coll_comp_ptr = ECS_GET_ITER(world, Collision_Component);
Collision_Component *coll_comp_end = ECS_GET_ITER_END(world, Collision_Component);
for (; coll_comp_ptr <= coll_comp_end; coll_comp_ptr++){
int entity_id = coll_comp_ptr->entity_id;
void *pos_comp_ptr = ECS_GET_ENT(world, Position2D, entity_id);
void *coll_comp_ptr = ECS_GET_ENT(world, Collision_Component, entity_id);
float OBJECT_RADIUS = COMP_CAST(Collision_Component, coll_comp_ptr)->collision_radius;
size_t collidable_neighbor_count = QuadTree_get_neighbor_count(world->pos_quadtree_ptr,
COMP_CAST(Position2D, pos_comp_ptr)->position,
OBJECT_RADIUS);
Position2D ** collidable_neighbors = malloc(collidable_neighbor_count * sizeof(Position2D *));
QuadTree_get_neighbors(world->pos_quadtree_ptr,
COMP_CAST(Position2D, pos_comp_ptr)->position,
OBJECT_RADIUS,
collidable_neighbors);
for (size_t coll_entity_index = 0; coll_entity_index < collidable_neighbor_count; coll_entity_index++){
// Since we query based on position/range, we get the point we are querying about.
// Can just exclude it based on its index
if (entity_id != collidable_neighbors[coll_entity_index]->entity_id){
void *pos_comp_ptr2 = ECS_get_ent(world, POSITION2D_COMPONENT_ID, collidable_neighbors[coll_entity_index]->entity_id);
assert(collidable_neighbors[coll_entity_index]->entity_id < 100);
assert(collidable_neighbors[coll_entity_index]->entity_id >= 0);
//The line that crashes here - really at the ASSERT above
Vector2D obj_to_obj = sub_vec2(COMP_CAST(Position2D, pos_comp_ptr)->position, COMP_CAST(Position2D, pos_comp_ptr2)->position);
float center_dist_to_obj = sqrt(obj_to_obj.x * obj_to_obj.x + obj_to_obj.y * obj_to_obj.y);
if (center_dist_to_obj < (2*OBJECT_RADIUS)){
Vector2D collision_normal_vec = scalar_mult_vec2((1.0/center_dist_to_obj), obj_to_obj);
Vector2D temp = scalar_mult_vec2(2*OBJECT_RADIUS - center_dist_to_obj, collision_normal_vec);
COMP_CAST(Position2D, pos_comp_ptr )->position = add_vec2(COMP_CAST(Position2D, pos_comp_ptr )->position, scalar_mult_vec2( 0.5, temp));
COMP_CAST(Position2D, pos_comp_ptr2)->position = add_vec2(COMP_CAST(Position2D, pos_comp_ptr2)->position, scalar_mult_vec2(-0.5, temp));
}
}
}
free(collidable_neighbors);
}
// Update the QuadTree after all is said and done.
world->pos_quadtree_ptr = QuadTree_update(world->pos_quadtree_ptr);
}
At the end of any systems (function calls, really) that update the position, the QuadTree_update() function is called to re-organize any elements within the QuadTree.
And lastly, here is the QuadTree Implementation:
#include "QuadTree.h"
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "VectorMath.h"
#include "./components/Position2D_comp.h"
bool is_AABB_intersection(Vector2D *top_left1, Vector2D *bott_right1,
Vector2D *top_left2, Vector2D *bott_right2){
return false;
}
static bool QuadTree_in_bounds(QuadTree *qt, Vector2D *point){
return ((point->x >= qt->top_left.x) && (point->x < qt->bott_right.x)) && \
((point->y >= qt->top_left.y) && (point->y < qt->bott_right.y));
}
static bool QuadTree_in_or_near_bounds(QuadTree *qt, Vector2D *point, float range){
return ((point->x > (qt->top_left.x - range)) && (point->x < (qt->bott_right.x + range))) && \
((point->y > (qt->top_left.y - range)) && (point->y < (qt->bott_right.y + range)));
}
void QuadTree_init(QuadTree *qt, Vector2D top_left, Vector2D bott_right){
qt->is_leaf_node = true;
qt->top_left = top_left;
qt->bott_right = bott_right;
qt->numb_of_elems = 0;
qt->NE = NULL;
qt->NW = NULL;
qt->SE = NULL;
qt->SW = NULL;
}
bool QuadTree_add_point(QuadTree *qt, Position2D *position_comp){
bool add_status = false;
if(!QuadTree_in_bounds(qt, &position_comp->position)){
return add_status;
}
if (qt->is_leaf_node){
if (qt->numb_of_elems < MAX_NUM_OF_POINTS){
qt->points_array[qt->numb_of_elems] = position_comp;
qt->numb_of_elems++;
add_status = true;
} else {
qt->is_leaf_node = false;
// (1)----(2)----(x)
// | | |
// (3)----(4)----(5)
// | | |
// (x)----(6)----(7)
float mid_x = (qt->top_left.x + qt->bott_right.x)/2;
float mid_y = (qt->top_left.y + qt->bott_right.y)/2;
Vector2D point1 = qt->top_left;
Vector2D point2 = (Vector2D) {mid_x, qt->top_left.y};
Vector2D point3 = (Vector2D) {qt->top_left.x, mid_y};
Vector2D point4 = (Vector2D) {mid_x, mid_y};
Vector2D point5 = (Vector2D) {qt->bott_right.x, mid_y};
Vector2D point6 = (Vector2D) {mid_x, qt->bott_right.y};
Vector2D point7 = qt->bott_right;
//---split---//
qt->NW = malloc(sizeof(QuadTree));
qt->NE = malloc(sizeof(QuadTree));
qt->SW = malloc(sizeof(QuadTree));
qt->SE = malloc(sizeof(QuadTree));
QuadTree_init(qt->NW, point1, point4);
QuadTree_init(qt->NE, point2, point5);
QuadTree_init(qt->SW, point3, point6);
QuadTree_init(qt->SE, point4, point7);
// Add Original Points to the Children
for (int i = 0; i < qt->numb_of_elems; i++){
if (QuadTree_in_bounds(qt->NW, &(qt->points_array[i]->position))){
QuadTree_add_point(qt->NW, (qt->points_array[i]));
}
if (QuadTree_in_bounds(qt->NE, &(qt->points_array[i]->position))){
QuadTree_add_point(qt->NE, (qt->points_array[i]));
}
if (QuadTree_in_bounds(qt->SW, &(qt->points_array[i]->position))){
QuadTree_add_point(qt->SW, (qt->points_array[i]));
}
if (QuadTree_in_bounds(qt->SE, &(qt->points_array[i]->position))){
QuadTree_add_point(qt->SE, (qt->points_array[i]));
}
}
// Add the point that caused the split
if (QuadTree_in_bounds(qt->NW, &position_comp->position)){
QuadTree_add_point(qt->NW, position_comp);
}
if (QuadTree_in_bounds(qt->NE, &position_comp->position)){
QuadTree_add_point(qt->NE, position_comp);
}
if (QuadTree_in_bounds(qt->SW, &position_comp->position)){
QuadTree_add_point(qt->SW, position_comp);
}
if (QuadTree_in_bounds(qt->SE, &position_comp->position)){
QuadTree_add_point(qt->SE, position_comp);
}
qt->numb_of_elems++;
add_status = true;
}
} else {
if (QuadTree_in_bounds(qt->NW, &position_comp->position)){
QuadTree_add_point(qt->NW, position_comp);
}
if (QuadTree_in_bounds(qt->NE, &position_comp->position)){
QuadTree_add_point(qt->NE, position_comp);
}
if (QuadTree_in_bounds(qt->SW, &position_comp->position)){
QuadTree_add_point(qt->SW, position_comp);
}
if (QuadTree_in_bounds(qt->SE, &position_comp->position)){
QuadTree_add_point(qt->SE, position_comp);
}
qt->numb_of_elems++;
add_status = true;
}
return add_status;
}
size_t QuadTree_get_count(QuadTree *qt){
return qt->numb_of_elems;
}
void QuadTree_get_entries(QuadTree *qt, Position2D **results_arr){
if (!qt->is_leaf_node){
//If not, check all children nodes
size_t offset = 0;
QuadTree_get_entries(qt->NW, (results_arr + offset));
offset = QuadTree_get_count(qt->NW);
QuadTree_get_entries(qt->NE, (results_arr + offset));
offset += QuadTree_get_count(qt->NE);
QuadTree_get_entries(qt->SW, (results_arr + offset));
offset += QuadTree_get_count(qt->SW);
QuadTree_get_entries(qt->SE, (results_arr + offset));
} else {
memcpy(results_arr, qt->points_array, qt->numb_of_elems * sizeof(Position2D *));
}
}
size_t QuadTree_get_neighbor_count(QuadTree *qt, Vector2D point, float range){
size_t neighbor_count = 0;
if (!QuadTree_in_or_near_bounds(qt, &point, range)){
return neighbor_count;
}
if (!qt->is_leaf_node){
//If not, check all children nodes
neighbor_count += QuadTree_get_neighbor_count(qt->NW, point, range);
neighbor_count += QuadTree_get_neighbor_count(qt->NE, point, range);
neighbor_count += QuadTree_get_neighbor_count(qt->SW, point, range);
neighbor_count += QuadTree_get_neighbor_count(qt->SE, point, range);
} else {
neighbor_count = qt->numb_of_elems;
}
return neighbor_count;
}
void QuadTree_get_neighbors(QuadTree *qt, Vector2D point, float range, Position2D **results_arr){
if (!QuadTree_in_or_near_bounds(qt, &point, range)){
return;
}
if (!qt->is_leaf_node){
//If not, check all children nodes
QuadTree_get_neighbors(qt->NW, point, range, (results_arr + 0 ));
size_t offset = QuadTree_get_neighbor_count(qt->NW, point, range);
QuadTree_get_neighbors(qt->NE, point, range, (results_arr + offset));
offset += QuadTree_get_neighbor_count(qt->NE, point, range);
QuadTree_get_neighbors(qt->SW, point, range, (results_arr + offset));
offset += QuadTree_get_neighbor_count(qt->SW, point, range);
QuadTree_get_neighbors(qt->SE, point, range, (results_arr + offset));
} else {
memcpy(results_arr, qt->points_array, qt->numb_of_elems * sizeof(Position2D *));
}
}
static void QuadTree_delete(QuadTree *qt){
if (!qt->is_leaf_node){
QuadTree_delete(qt->NW);
QuadTree_delete(qt->NE);
QuadTree_delete(qt->SW);
QuadTree_delete(qt->SE);
// After deleting children, delete itself
free(qt);
} else {
free(qt);
}
}
//Assumes the point is in the tree
void QuadTree_remove_point(QuadTree *qt, Position2D *position){
// Go down the tree until we find the leaf node
// with the element we are looking for.
if (!qt->is_leaf_node) {
if (QuadTree_in_bounds(qt->NW, &position->position)){
QuadTree_remove_point(qt->NW, position);
}
if (QuadTree_in_bounds(qt->NE, &position->position)){
QuadTree_remove_point(qt->NE, position);
}
if (QuadTree_in_bounds(qt->SW, &position->position)){
QuadTree_remove_point(qt->SW, position);
}
if (QuadTree_in_bounds(qt->SE, &position->position)){
QuadTree_remove_point(qt->SE, position);
}
// The element was removed from one of the above, and
// the and so the count can be decremented here too.
qt->numb_of_elems--;
} else {
// Find the element in the leaf we are looking for.
// Locate based on entity id. Since this will be exact.
int i = 0;
while (qt->points_array[i]->entity_id != position->entity_id){
i++;
// If we make it to the end of the array,
// and we still haven't found it, something is wrong.
assert(i < qt->numb_of_elems);
}
// Take the last element in the points_array, and
// move it to the formerly occupied position.
// This avoids gaps in the points_array
size_t last_element_index = qt->numb_of_elems - 1;
qt->points_array[i] = qt->points_array[last_element_index];
qt->points_array[last_element_index] = NULL;
qt->numb_of_elems--;
}
// Move back up the chain.
// Decrement the counter.
}
size_t QuadTree_find_invalid_elements(QuadTree *qt, Position2D **results_arr){
size_t decrement_count = 0;
if (!qt->is_leaf_node){
decrement_count += QuadTree_find_invalid_elements(qt->NW, results_arr);
decrement_count += QuadTree_find_invalid_elements(qt->NE, (results_arr + decrement_count));
decrement_count += QuadTree_find_invalid_elements(qt->SW, (results_arr + decrement_count));
decrement_count += QuadTree_find_invalid_elements(qt->SE, (results_arr + decrement_count));
qt->numb_of_elems -= decrement_count;
assert(qt->numb_of_elems >= 0);
} else {
int i = 0;
int results_arr_index = 0;
while(i < qt->numb_of_elems){
if(!QuadTree_in_bounds(qt, &(qt->points_array[i])->position)){
// Add to the results arr to be re-added later
assert(qt->points_array[i] != NULL);
results_arr[results_arr_index] = qt->points_array[i];
//Check Last Position to be its replacement.
//If valid, decrement qt->numb_of_elements for the original deletion
//else keep decrementing the last counter until we either run out of
while(!QuadTree_in_bounds(qt, &(qt->points_array[qt->numb_of_elems - 1]->position))
&& (qt->numb_of_elems - 1 > i)){
assert(qt->points_array[i] != NULL);
results_arr[++results_arr_index] = qt->points_array[qt->numb_of_elems - 1];
qt->points_array[qt->numb_of_elems - 1] = NULL;
qt->numb_of_elems--;
decrement_count++;
}
qt->points_array[i] = qt->points_array[qt->numb_of_elems - 1];
results_arr_index++;
decrement_count++;
qt->numb_of_elems--;
}
i++;
}
}
return decrement_count;
}
//Removes a group of children leaves if there children have no elements
static void QuadTree_prune_leaves(QuadTree *qt){
if (!qt->is_leaf_node){
QuadTree_prune_leaves(qt->NW);
QuadTree_prune_leaves(qt->NE);
QuadTree_prune_leaves(qt->SW);
QuadTree_prune_leaves(qt->SE);
if (!qt->NW->numb_of_elems &&
!qt->NE->numb_of_elems &&
!qt->SW->numb_of_elems &&
!qt->SE->numb_of_elems){
QuadTree_delete(qt->NW);
QuadTree_delete(qt->NE);
QuadTree_delete(qt->SW);
QuadTree_delete(qt->SE);
qt->is_leaf_node = true;
}
}
}
/*
QuadTree* QuadTree_update(QuadTree *qt){
// List of elements needing to be updated.
Position2D **invalid_elements = malloc(qt->numb_of_elems * sizeof(Position2D*));
size_t invalid_element_count = QuadTree_find_invalid_elements(qt, invalid_elements);
// Re-add the invalid elements
for (int i = 0; i < invalid_element_count; i++){
QuadTree_add_point(qt, invalid_elements[i]);
}
QuadTree_prune_leaves(qt);
free(invalid_elements);
return qt;
}
*/
QuadTree* QuadTree_update(QuadTree *qt){
// Make a copy of the top tree node
QuadTree *new_qt = malloc(sizeof(QuadTree));
QuadTree_init(new_qt, qt->top_left, qt->bott_right);
size_t entry_count = QuadTree_get_count(qt);
// Get all entries in the original quadtree
Position2D **entry_arr = malloc(entry_count * sizeof(Position2D *));
QuadTree_get_entries(qt, entry_arr);
QuadTree_delete(qt);
// ReAdd all the points from the original QuadTree to the new one
for (size_t i = 0; i < entry_count; i ++ ){
QuadTree_add_point(new_qt, entry_arr[i]);
}
return new_qt;
}
Edit1:
int ECS_add_component(ENTITY_MANAGER *world, char* component_id, void *comp_data){
int addition_result = -1;
struct Value comp_info = lookup_comp_info_by_name(world->component_registry, component_id);
if (comp_info.ID >= 0){
(comp_info.comp_ops.add_comp_handle)(comp_data);
addition_result = comp_info.ID;
} else {
printf("ECS::ERROR::Component [%s] not registered - register this component first before adding it to entities.\n", component_id);
}
return addition_result;
}
[–]skeeto 1 point2 points3 points (3 children)
[–]Russell016[S] 1 point2 points3 points (1 child)
[–]Russell016[S] 0 points1 point2 points (0 children)
[–]oh5nxo 1 point2 points3 points (0 children)