diff options
| -rw-r--r-- | lib/algolib.c | 2 | ||||
| -rw-r--r-- | lib/init.c | 8 | ||||
| -rw-r--r-- | src/1-1-binary-search-tree.c | 4 | ||||
| -rw-r--r-- | src/1-2-binary-search-tree-visual.c | 17 | ||||
| -rw-r--r-- | src/3-1-a-star.c | 331 |
5 files changed, 343 insertions, 19 deletions
diff --git a/lib/algolib.c b/lib/algolib.c index 8d15782..dc2d890 100644 --- a/lib/algolib.c +++ b/lib/algolib.c @@ -7,6 +7,8 @@ #include <stdlib.h> #include <vectorlib.c> +// Everything needs rewritten. this is just for learning. + #define flaot float // Binary Search Tree @@ -28,7 +28,6 @@ int main(int argc, char *argv[]) } srand(time(NULL)); - OBJECT_INER obj_storage[obj_n]; STUFFS stuff = { startw, @@ -45,12 +44,7 @@ int main(int argc, char *argv[]) stuff.font = TTF_OpenFont("/usr/share/fonts/TTF/JetBrainsMono-Regular.ttf" , 10); - init_stuffs(startw,starth,obj_storage,&stuff); - - - - for (int i = 0; i < obj_n; i++) - stuff.obj.objs[i] = &obj_storage[i]; + init_stuffs(startw,starth,&stuff); SDL_SetRenderDrawBlendMode(renderer, SDL_BLENDMODE_BLEND); diff --git a/src/1-1-binary-search-tree.c b/src/1-1-binary-search-tree.c index cb5efc1..b6ff99e 100644 --- a/src/1-1-binary-search-tree.c +++ b/src/1-1-binary-search-tree.c @@ -4,6 +4,8 @@ #include <vectorlib.c> #include <time.h> +#define PROJECT_NAME "algorithms-binary search tree" + typedef struct TREE{ BS_Node *root; } TREE; @@ -30,4 +32,4 @@ int main(int argc, char **argv){ /* Challanges * * balance the tree - */
\ No newline at end of file + */ diff --git a/src/1-2-binary-search-tree-visual.c b/src/1-2-binary-search-tree-visual.c index 633dc7b..26b2990 100644 --- a/src/1-2-binary-search-tree-visual.c +++ b/src/1-2-binary-search-tree-visual.c @@ -10,15 +10,10 @@ #include <SDL2/SDL_ttf.h> #define PROJECT_NAME "algorithms-binary search tree visual" -#define obj_n 1 -typedef struct OBJECT_INER { +typedef struct OBJECT { BS_Node *root; BS_Node *found_node; -} OBJECT_INER; - -typedef struct OBJECT { - OBJECT_INER *objs[obj_n]; } OBJECT; #include <init.h> @@ -77,8 +72,8 @@ void add_text(BS_Node **node, STUFFS *stuff){ } } -void init_stuffs(int w, int h, OBJECT_INER *objs,STUFFS *stuff){ - OBJECT_INER *tree = &objs[0]; +void init_stuffs(int w, int h, STUFFS *stuff){ + OBJECT *tree = &stuff->obj; for(int i=0; i <100; i++){ BSAddValue(&tree->root,(int)RandomFloat(0,100)); } @@ -108,7 +103,7 @@ void draw_node(BS_Node **node, STUFFS *stuff){ } SDL_RenderCopy(stuff->renderer,(*node)->text->texture,NULL, &(*node)->text->textRect); circleRGBA(stuff->renderer,(*node)->pos.x,(*node)->pos.y,10,255,0,255,255); - if(stuff->obj.objs[0]->found_node != NULL && stuff->obj.objs[0]->found_node == *node){ + if(stuff->obj.found_node != NULL && stuff->obj.found_node == *node){ circleRGBA(stuff->renderer,(*node)->pos.x,(*node)->pos.y,10,0,255,255,255); SDL_SetRenderDrawColor(stuff->renderer,255,0,255,255); } @@ -128,7 +123,7 @@ void draw(SDL_Window* window, STUFFS *stuff){ //} SDL_SetRenderDrawColor(stuff->renderer,255,0,255,255); - draw_node(&stuff->obj.objs[0]->root,stuff); + draw_node(&stuff->obj.root,stuff); SDL_RenderPresent(stuff->renderer); } @@ -145,7 +140,7 @@ void BSFreeText(BS_Node **node){ } void on_end(STUFFS *stuff){ - OBJECT_INER *tree = stuff->obj.objs[0]; + OBJECT *tree = &stuff->obj; BSFreeText(&tree->root); BSFreeTree(&tree->root); } diff --git a/src/3-1-a-star.c b/src/3-1-a-star.c new file mode 100644 index 0000000..57a3ffd --- /dev/null +++ b/src/3-1-a-star.c @@ -0,0 +1,331 @@ +#include <algolib.c> +#include <math.h> +#include <stdbool.h> +#include <stdio.h> +#include <vectorlib.c> + +#include <SDL2/SDL.h> +#include <SDL2/SDL2_gfxPrimitives.h> +#include <SDL2/SDL_render.h> +#include <SDL2/SDL_ttf.h> +#include <SDL2/SDL_video.h> + +#define PROJECT_NAME "algorithms-a* 1" + +#define grid_cols 50 +#define grid_rows 50 + +#define obj_n grid_cols* grid_rows + +// im not moving these objects and functions out to algolib.c as its only used here. +// may move it later +typedef struct ITEM { + int i; + int j; + + int f; + int g; + int h; + + struct ITEM* neighbors[8]; + struct ITEM* previous; + + bool wall; +} ITEM; + +void removeFromArr(ITEM* arr[], ITEM* elt) +{ + for (int i = obj_n - 1; i >= 0; i--) { + if (arr[i] == elt) { + for (int j = i; j < obj_n; j++) { + if (arr[j + 1]) { + arr[j] = arr[j + 1]; + } else { + arr[j] = NULL; + break; + } + } + } + } +} + +void pushIntoArr(ITEM* arr[], ITEM* elt) +{ + for (int i = obj_n - 1; i >= 0; i--) { + if (arr[i]) { + arr[i + 1] = elt; + break; + } else if (i == 0) { + arr[i] = elt; + break; + } + } +} + +bool arrContains(ITEM* arr[], ITEM* node) +{ + for (int j = 0; j < obj_n; j++) { + if (node == arr[j]) + return true; + } + return false; +} + +void pushIntoArrNei(ITEM* arr[], ITEM* elt) +{ + for (int i = 8 - 1; i >= 0; i--) { + if (arr[i]) { + arr[i + 1] = elt; + break; + } else if (i == 0) { + arr[i] = elt; + break; + } + } +} + +void addNeighbors(ITEM* item, ITEM* items[]) +{ + int i = item->i; + int j = item->j; + for (int i = 0; i < 8; i++) { + item->neighbors[i] = NULL; + } + if (i < grid_cols - 1) { + pushIntoArrNei(item->neighbors, items[j * grid_cols + i + 1]); + } + if (i > 0) { + pushIntoArrNei(item->neighbors, items[j * grid_cols + i - 1]); + } + if (j < grid_rows - 1) { + pushIntoArrNei(item->neighbors, items[(j + 1) * grid_cols + i]); + } + if (j > 0) { + pushIntoArrNei(item->neighbors, items[(j - 1) * grid_cols + i]); + } + if (i > 0 && j > 0) { + pushIntoArrNei(item->neighbors, items[(j - 1) * grid_cols + (i - 1)]); + } + if (i < grid_cols - 1 && j > 0) { + pushIntoArrNei(item->neighbors, items[(j - 1) * grid_cols + (i + 1)]); + } + if (i > 0 && j < grid_rows - 1) { + pushIntoArrNei(item->neighbors, items[(j + 1) * grid_cols + (i - 1)]); + } + if (i < grid_cols - 1 && j < grid_rows - 1) { + pushIntoArrNei(item->neighbors, items[(j + 1) * grid_cols + (i + 1)]); + } +} + +typedef struct OBJECT { + ITEM* items[obj_n]; + ITEM* openSet[obj_n]; + ITEM* closedSet[obj_n]; + ITEM* start; + ITEM* end; + + int w; + int h; +} OBJECT; + +#include <init.h> + +void init_stuffs(int w, int h, STUFFS* stuff) +{ + stuff->obj.w = stuff->width / grid_cols; + stuff->obj.h = stuff->height / grid_rows; + + for (int j = 0; j < grid_rows; j++) { + for (int i = 0; i < grid_cols; i++) { + int index = j * grid_cols + i; + stuff->obj.items[index] = (ITEM*)malloc(sizeof(ITEM)); + stuff->obj.items[index]->i = i; + stuff->obj.items[index]->j = j; + stuff->obj.items[index]->f = 0; + stuff->obj.items[index]->g = 0; + stuff->obj.items[index]->h = 0; + stuff->obj.items[index]->previous = NULL; + stuff->obj.items[index]->wall = false; + + if (RandomFloat(0, 1) < 0.4) { + stuff->obj.items[index]->wall = true; + } + + stuff->obj.openSet[index] = NULL; + stuff->obj.closedSet[index] = NULL; + } + } + + for (int i = 0; i < obj_n; i++) { + addNeighbors(stuff->obj.items[i], stuff->obj.items); + } + + stuff->obj.start = stuff->obj.items[0]; + stuff->obj.end = stuff->obj.items[obj_n - 1]; + stuff->obj.start->wall = false; + stuff->obj.end->wall = false; + + stuff->obj.openSet[0] = stuff->obj.start; +} + +void draw_node(ITEM* node, STUFFS* stuff) +{ + SDL_RenderFillRect(stuff->renderer, &(SDL_Rect) { node->i * stuff->obj.w, node->j * stuff->obj.h, stuff->obj.w - 1, stuff->obj.h - 1 }); +} + +float dist(float x, float y, float x2, float y2) +{ + return sqrt((pow(x, 2) + pow(y, 2) + pow(x2, 2) + pow(y2, 2))); +} + +int heuristic(ITEM* a, ITEM* b) +{ + if (a && b) { + // really slow + // return (int)dist((float)a->i, (float)a->j, (float)b->i, (float)b->j); + + return fabsf((float)a->i - (float)b->i) + fabsf((float)a->j - (float)b->j); + } + return 0; +} + +void draw(SDL_Window* window, STUFFS* stuff) +{ + static bool done = false; + if (done == false) { + SDL_SetRenderDrawColor(stuff->renderer, 0, 0, 0, 255); + // SDL_RenderClear(renderer); + SDL_RenderFillRect(stuff->renderer, &(SDL_Rect) { 0, 0, stuff->width, stuff->height }); + // for (int i=0; i<obj_n; i++){ + // show(renderer,stuff,stuff->obj.objs[i]); + // } + + ITEM* path[obj_n] = { NULL }; + ITEM* temp = NULL; + + if (stuff->obj.openSet[0]) { + int winner = 0; + for (int i = 0; i < obj_n; i++) { + if (!stuff->obj.openSet[i]) + break; + + if (stuff->obj.openSet[i]->f < stuff->obj.openSet[winner]->f) { + winner = i; + } + } + + ITEM* current = stuff->obj.openSet[winner]; + + if (current == stuff->obj.end) { + SDL_Log("DONE!\n"); + done = true; + return; + } + + removeFromArr(stuff->obj.openSet, current); + pushIntoArr(stuff->obj.closedSet, current); + + // foreach neighbor + ITEM** neighbors = current->neighbors; + for (int i = 0; i < 8; i++) { + ITEM* neighbor = neighbors[i]; + + if (neighbor) { + if (!arrContains(stuff->obj.closedSet, neighbor) && !neighbor->wall) { + int tempG = current->g + 1; + + bool newPath = false; + if (arrContains(stuff->obj.openSet, neighbor)) { + if (tempG < neighbor->g) { + neighbor->g = tempG; + newPath = true; + } + } else { + neighbor->g = tempG; + newPath = true; + pushIntoArr(stuff->obj.openSet, neighbor); + } + + if (newPath) { + neighbor->h = heuristic(neighbor, stuff->obj.end); + neighbor->f = neighbor->g + neighbor->h; + neighbor->previous = current; + } + } + } + } + + temp = current; + } else { + SDL_Log("no solution\n"); + done = true; + return; + } + + SDL_SetRenderDrawColor(stuff->renderer, 255, 255, 255, 255); + for (int j = 0; j < grid_rows; j++) { + for (int i = 0; i < grid_cols; i++) { + draw_node((stuff->obj.items[j * grid_cols + i]), stuff); + } + } + + // debug + + SDL_SetRenderDrawColor(stuff->renderer, 255, 0, 0, 255); + for (int i = 0; i < obj_n; i++) { + if (stuff->obj.closedSet[i]) { + draw_node(stuff->obj.closedSet[i], stuff); + } + } + + SDL_SetRenderDrawColor(stuff->renderer, 0, 255, 0, 255); + for (int i = 0; i < obj_n; i++) { + if (stuff->obj.openSet[i]) { + draw_node(stuff->obj.openSet[i], stuff); + } + } + + if (temp) { + pushIntoArr(path, temp); + while (temp->previous) { + pushIntoArr(path, temp->previous); + temp = temp->previous; + } + } + + SDL_SetRenderDrawColor(stuff->renderer, 0, 0, 255, 255); + for (int i = 0; i < obj_n; i++) { + if (path[i]) { + draw_node(path[i], stuff); + } + } + + SDL_SetRenderDrawColor(stuff->renderer, 0, 0, 0, 255); + for (int j = 0; j < grid_rows; j++) { + for (int i = 0; i < grid_cols; i++) { + if (stuff->obj.items[j * grid_cols + i]->wall) + draw_node((stuff->obj.items[j * grid_cols + i]), stuff); + } + } + + SDL_RenderPresent(stuff->renderer); + } +} + +void on_end(STUFFS* stuff) +{ + for (int i = 0; i < obj_n; i++) { + free(stuff->obj.items[i]); + } +} + +#include <init.c> + +/* Challanges + * + * draw a line over the path + * + * make it so 2 sqares on either corner of a square is also a wall + * 0x + * x0 + */ |