From 5f6c4b946aaa4da8668ea153f2fef2dde91b8e58 Mon Sep 17 00:00:00 2001 From: "Juan J. Martinez" Date: Tue, 11 Jul 2023 12:20:35 +0100 Subject: Use insertion sort --- src/entities.c | 39 ++++++++++++++++++++++++++------------- 1 file changed, 26 insertions(+), 13 deletions(-) diff --git a/src/entities.c b/src/entities.c index fe05ef8..a1aa9db 100644 --- a/src/entities.c +++ b/src/entities.c @@ -1,6 +1,5 @@ #include #include -#include #include "vga.h" #include "map.h" @@ -59,17 +58,6 @@ void entities_update() } } -static int cmp_entities(const void *a, const void *b) -{ - const Entity **ea = (const Entity **)a; - const Entity **eb = (const Entity **)b; - - if (((*ea)->y >> 4) == ((*eb)->y >> 4)) - return (*ea)->used - (*eb)->used; - else - return (*ea)->y - (*eb)->y; -} - void entities_sort() { sort_cnt = 0; @@ -81,7 +69,32 @@ void entities_sort() player_ent.y = player_y(); sort[sort_cnt++] = &player_ent; - qsort(sort, sort_cnt, sizeof(Entity *), cmp_entities); + /* using insertion sort; + * + * The sorting criteria is the y coordinate unless the entities + * share a 16px area in which we check the value of used that defines 3 + * layers: bg, fb and player. + * */ + + Entity *t; + uint8_t i = 1; + + while (i < sort_cnt) + { + uint8_t j = i; + while (j > 0 && ( + sort[j - 1]->y > sort[j]->y + || ((sort[j - 1]->y >> 4) == (sort[j]->y >> 4) + && sort[j - 1]->used > sort[j]->used) + )) + { + t = sort[j]; + sort[j] = sort[j - 1]; + sort[j - 1] = t; + j--; + } + i++; + } } void entities_draw() -- cgit v1.2.3