From 24af775b5041cbed67dfc84f3a0d67850a4b6a1b Mon Sep 17 00:00:00 2001
From: Aldrik Ramaekers <aldrik@amftech.nl>
Date: Sun, 11 Dec 2022 16:14:54 +0100
Subject: pathfinding

---
 build/zombies.exe           | Bin 1662213 -> 1679328 bytes
 bullets.c                   |  19 ++-
 include/bullets.h           |   2 +
 include/list.h              |  27 ++++
 include/map.h               |   2 +-
 include/objects.h           |   4 +-
 include/pathfinding.h       |  23 ++++
 include/players.h           |  25 ++--
 include/zombies.h           |  10 +-
 list.c                      | 127 ++++++++++++++++++
 main.c                      |  10 ++
 map.c                       |  14 +-
 math_helper.c               |   3 +-
 objects.c                   |  37 ++++--
 pathfinding.c               | 308 ++++++++++++++++++++++++++++++++++++++++++++
 players.c                   | 158 +++++++++++++++--------
 project-base.code-workspace |   6 +-
 zombies.c                   | 114 ++++++++++++++--
 18 files changed, 778 insertions(+), 111 deletions(-)
 create mode 100644 include/list.h
 create mode 100644 include/pathfinding.h
 create mode 100644 list.c
 create mode 100644 pathfinding.c

diff --git a/build/zombies.exe b/build/zombies.exe
index 072f96c..6c42ba3 100644
Binary files a/build/zombies.exe and b/build/zombies.exe differ
diff --git a/bullets.c b/bullets.c
index 9475729..1c8f8b0 100644
--- a/bullets.c
+++ b/bullets.c
@@ -1,10 +1,10 @@
 #include "include/bullets.h"
 
-void shoot(platform_window* window) {
+void shoot(platform_window* window, player p) {
 	map_info info = get_map_info(window);
 	float bullet_range = 100.0f;
 
-	float hh = get_height_of_tile_under_coords(window, playerx, playery);
+	float hh = get_height_of_tile_under_coords(window, p.playerx, p.playery);
 
 	float dirx = (_global_mouse.x - (window->width/2));
 	float diry = (_global_mouse.y - (window->height/2));
@@ -16,8 +16,8 @@ void shoot(platform_window* window) {
 	dirx += ((float)rand()/(float)(RAND_MAX/SPRAY_BOUNDS)-(SPRAY_BOUNDS/2));
 	diry += ((float)rand()/(float)(RAND_MAX/SPRAY_BOUNDS)-(SPRAY_BOUNDS/2));
 
-	float bulletx = gunx;
-	float bullety = guny;
+	float bulletx = p.gunx;
+	float bullety = p.guny;
 	float bullet_end_point_x = bulletx+dirx*bullet_range;
 	float bullet_end_point_y = bullety+diry*bullet_range;
 
@@ -25,7 +25,7 @@ void shoot(platform_window* window) {
 		bullet b = bullets[i];
 		if (b.active) continue;
 
-		bullets[i] = (bullet){true, bulletx, bullety, hh + 0.5, bullet_end_point_x, bullet_end_point_y};
+		bullets[i] = (bullet){p.id, true, bulletx, bullety, hh + 0.5, bullet_end_point_x, bullet_end_point_y};
 		break;
 	}
 }
@@ -167,13 +167,12 @@ void draw_bullets(platform_window* window) {
 	map_info info = get_map_info(window);
 
 	for (int i = 0; i < max_bullets; i++) {
-		bullets[i].position.x = gunx;
-		bullets[i].position.y = guny;
-		bullets[i].position.z = gun_height;
 		bullet b = bullets[i];
 		if (!b.active) continue;
-
-		
+		player p = get_player_by_id(b.player_id);
+		bullets[i].position.x = p.gunx;
+		bullets[i].position.y = p.guny;
+		bullets[i].position.z = p.gun_height;
 		
 		if (check_if_bullet_collided_with_ground(&b, window)) {
 			bullets[i].endy = b.endy;
diff --git a/include/bullets.h b/include/bullets.h
index e8ddb86..ed64333 100644
--- a/include/bullets.h
+++ b/include/bullets.h
@@ -8,6 +8,7 @@
 #include "map.h"
 
 typedef struct t_bullet {
+	int player_id;
 	bool active;
 	vec3f position;
 	float endx;
@@ -18,6 +19,7 @@ typedef struct t_bullet {
 bullet bullets[500] = {0};
 int max_bullets = 500;
 
+void shoot(platform_window* window, player p);
 void draw_bullets(platform_window* window);
 
 #endif
\ No newline at end of file
diff --git a/include/list.h b/include/list.h
new file mode 100644
index 0000000..d4809de
--- /dev/null
+++ b/include/list.h
@@ -0,0 +1,27 @@
+
+#ifndef INCLUDE_LIST
+#define INCLUDE_LIST
+
+#include <projectbase/project_base.h>
+
+typedef struct t_list_item
+{
+	void *next;
+	void *data;
+} list_item;
+
+typedef struct t_list
+{
+	list_item *start;
+	u32 count;
+	u16 size;
+} list;
+
+void list_destroy(list* list);
+list list_create(u16 size);
+list_item *list_push(list *list, void *data);
+void* list_at(list *list, u32 index);
+void list_remove_at(list *list, u32 index);
+void list_debug_print(list *list);
+
+#endif
\ No newline at end of file
diff --git a/include/map.h b/include/map.h
index 82584e9..3bc8273 100644
--- a/include/map.h
+++ b/include/map.h
@@ -49,7 +49,7 @@ int map[MAP_SIZE_Y][MAP_SIZE_X] = {
 	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
-	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
+	{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0},
 	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
 	{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
diff --git a/include/objects.h b/include/objects.h
index c4bb689..b7c14b3 100644
--- a/include/objects.h
+++ b/include/objects.h
@@ -28,8 +28,8 @@ typedef struct t_box {
 	vec2f br_u;
 } box;
 
-object objects[50];
-int max_objects = 50;
+int max_objects = 150;
+object objects[150];
 
 void create_objects();
 void draw_objects_at_row(platform_window* window, int row);
diff --git a/include/pathfinding.h b/include/pathfinding.h
new file mode 100644
index 0000000..2b38766
--- /dev/null
+++ b/include/pathfinding.h
@@ -0,0 +1,23 @@
+#ifndef INCLUDE_PATHFINDING
+#define INCLUDE_PATHFINDING
+
+#include <projectbase/project_base.h>
+
+#include "players.h"
+#include "objects.h"
+#include "list.h"
+
+typedef struct t_pathfinding_request
+{
+	vec2f start;
+	vec2f end;
+	array *to_fill;
+	bool cancelled;
+	bool done;
+} pathfinding_request;
+
+array global_pathfinding_queue;
+
+void make_pathfinding_request(vec2f start, vec2f end, array *to_fill, pathfinding_request *request);
+
+#endif
\ No newline at end of file
diff --git a/include/players.h b/include/players.h
index 7107797..cd7560f 100644
--- a/include/players.h
+++ b/include/players.h
@@ -8,15 +8,24 @@
 #include "zombies.h"
 #include "math_helper.h"
 
-float sec_since_last_shot = 10.0f;
-float playerx = 3;
-float playery = 3;
-float gunx = 0.0f;
-float guny = 0.0f;
-float gun_height = 0.0f;
+typedef struct t_player {
+	int id;
+	bool active;
+	float sec_since_last_shot;
+	float playerx;
+	float playery;
+	float gunx;
+	float guny;
+	float gun_height;
+} player;
 
-void shoot(platform_window* window);
-void draw_player(platform_window* window);
+int my_id = 1;
+
+int max_players = 10;
+player players[10] = {0};
+
+player get_player_by_id(int id);
+void draw_players_at_tile(platform_window* window, int x, int y);
 void draw_bullets(platform_window* window);
 float get_player_size(platform_window* window);
 
diff --git a/include/zombies.h b/include/zombies.h
index 44b2956..a8a58fe 100644
--- a/include/zombies.h
+++ b/include/zombies.h
@@ -5,12 +5,17 @@
 
 #include "players.h"
 #include "objects.h"
+#include "pathfinding.h"
 
 typedef struct t_zombie {
 	bool alive;
 	float health;
 	vec3f position;
 	vec3f size;
+	array path;
+	array next_path;
+	float time_since_last_path;
+	pathfinding_request request;
 } zombie;
 
 typedef struct t_spawner {
@@ -20,11 +25,10 @@ typedef struct t_spawner {
 
 // data data that is stored on disk
 spawner spawner_tiles[2] = {
-	{9, 0, 0},
-	{1, 8, 0},
+	{15, 5, 999},
+	{3, 8, 999},
 };
 
-
 zombie zombies[50] = {0};
 int max_zombies = 50;
 
diff --git a/list.c b/list.c
new file mode 100644
index 0000000..35c41eb
--- /dev/null
+++ b/list.c
@@ -0,0 +1,127 @@
+/* 
+*  Copyright 2019 Aldrik Ramaekers
+*
+*  This program is free software: you can redistribute it and/or modify
+*  it under the terms of the GNU General Public License as published by
+*  the Free Software Foundation, either version 3 of the License, or
+*  (at your option) any later version.
+
+*  This program is distributed in the hope that it will be useful,
+*  but WITHOUT ANY WARRANTY; without even the implied warranty of
+*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+*  GNU General Public License for more details.
+
+*  You should have received a copy of the GNU General Public License
+*  along with this program.  If not, see <https://www.gnu.org/licenses/>.
+*/
+
+#include "include/list.h"
+
+list list_create(u16 size)
+{
+	list l;
+	l.size = size;
+	l.count = 0;
+	l.start = 0;
+	
+	return l;
+}
+
+void list_destroy(list* list) {
+	list_item *prev = 0;
+	list_item *current_item = list->start;
+	while(current_item)
+	{
+		prev = current_item;
+		current_item = current_item->next;
+		mem_free(prev);
+	}
+	
+	list->count = 0;
+}
+
+list_item *list_push(list *list, void *data)
+{
+	list_item *item = mem_alloc(sizeof(list_item));
+	item->next = 0;
+	item->data = data;
+	
+	if (list->count == 0)
+	{
+		list->start = item;
+	}
+	else
+	{
+		list_item *current_item = list->start;
+		while(current_item)
+		{
+			if (!current_item->next)
+			{
+				current_item->next = item;
+				goto done;
+			}
+			else
+			{
+				current_item = current_item->next;
+			}
+		}
+	}
+	
+	done:
+	list->count++;
+	return item;
+}
+
+void* list_at(list *list, u32 index)
+{
+	list_item *current_item = list->start;
+	s32 count = 0;
+	while(current_item)
+	{
+		if (count == index)
+			return current_item->data;
+		count++;
+		current_item = current_item->next;
+	}
+	return 0;
+}
+
+void list_remove_at(list *list, u32 index)
+{
+	list_item *prev = 0;
+	list_item *current_item = list->start;
+	s32 count = 0;
+	while(current_item)
+	{
+		if (count == index)
+		{
+			if (prev)
+				prev->next = current_item->next;
+			else
+				list->start = current_item->next;
+			
+			mem_free(current_item);
+			goto done;
+		}
+		
+		count++;
+		prev = current_item;
+		current_item = current_item->next;
+	}
+	
+	done:
+	list->count--;
+}
+
+void list_debug_print(list *list)
+{
+	list_item *current_item = list->start;
+	s32 count = 0;
+	while(current_item)
+	{
+		printf("%d %p\n", count, current_item->data);
+		
+		count++;
+		current_item = current_item->next;
+	}
+}
\ No newline at end of file
diff --git a/main.c b/main.c
index ea17371..ccdfc91 100644
--- a/main.c
+++ b/main.c
@@ -6,6 +6,8 @@
 #include "include/zombies.h"
 #include "include/math_helper.h"
 #include "include/bullets.h"
+#include "include/pathfinding.h"
+#include "include/list.h"
 
 #include "map.c"
 #include "players.c"
@@ -13,6 +15,8 @@
 #include "zombies.c"
 #include "bullets.c"
 #include "math_helper.c"
+#include "pathfinding.c"
+#include "list.c"
 
 #define CONFIG_DIRECTORY "zombieshooter"
 
@@ -43,12 +47,18 @@ int main(int argc, char **argv)
 	load_map_from_data();
 	create_objects();
 
+	pathfinding_init();
+
+	thread t = thread_start(pathfinding_thread, 0);
+	thread_detach(&t);
+
     while(platform_keep_running(window)) {
         platform_handle_events();
     }
 
     settings_write_to_file();
     platform_destroy();
+	pathfinding_destroy();
 
 	memory_print_leaks();
 
diff --git a/map.c b/map.c
index e6f7fd5..15a7c70 100644
--- a/map.c
+++ b/map.c
@@ -26,19 +26,19 @@ static int get_height_of_tile_tl(int current_height, int x, int y) {
 
 static int get_height_of_tile_br(int current_height, int x, int y) {
 	int highest_point = current_height;
-	if (x < 9) {
+	if (x < MAP_SIZE_X-1) {
 		int tile_right = map[y][x+1];
 		if (tile_right > highest_point) {
 			highest_point = tile_right;
 		}
 	}
-	if (y < 9 && x < 9) {
+	if (y < MAP_SIZE_Y-1 && x < MAP_SIZE_X-1) {
 		int tile_bottom_right = map[y+1][x+1];
 		if (tile_bottom_right > highest_point) {
 			highest_point = tile_bottom_right;
 		}
 	}
-	if (y < 9) {
+	if (y < MAP_SIZE_Y-1) {
 		int tile_bottom = map[y+1][x];
 		if (tile_bottom > highest_point) {
 			highest_point = tile_bottom;
@@ -55,13 +55,13 @@ static int get_height_of_tile_bl(int current_height, int x, int y) {
 			highest_point = tile_left;
 		}
 	}
-	if (y < 9 && x > 0) {
+	if (y < MAP_SIZE_Y-1 && x > 0) {
 		int tile_bottom_left = map[y+1][x-1];
 		if (tile_bottom_left > highest_point) {
 			highest_point = tile_bottom_left;
 		}
 	}
-	if (y < 9) {
+	if (y < MAP_SIZE_Y-1) {
 		int tile_bottom = map[y+1][x];
 		if (tile_bottom > highest_point) {
 			highest_point = tile_bottom;
@@ -78,13 +78,13 @@ static int get_height_of_tile_tr(int current_height, int x, int y) {
 			highest_point = tile_above;
 		}
 	}
-	if (y > 0 && x < 9) {
+	if (y > 0 && x < MAP_SIZE_X-1) {
 		int tile_above_right = map[y-1][x+1];
 		if (tile_above_right > highest_point) {
 			highest_point = tile_above_right;
 		}
 	}
-	if (x < 9) {
+	if (x < MAP_SIZE_X-1) {
 		int tile_right = map[y][x+1];
 		if (tile_right > highest_point) {
 			highest_point = tile_right;
diff --git a/math_helper.c b/math_helper.c
index 782599d..648fbd2 100644
--- a/math_helper.c
+++ b/math_helper.c
@@ -49,7 +49,8 @@ bool lines_intersect(vec2f p1, vec2f q1, vec2f p2, vec2f q2)
     if (o1 != o2 && o3 != o4) {
 		vec2f bdir = get_dir_of_line(p1, q1);
 		vec2f pdir = get_dir_of_line(p1, p2);
-		if ((neg2(bdir.x, pdir.x) || pos2(bdir.x, pdir.x)) && (neg2(bdir.y, pdir.y) || pos2(bdir.y, pdir.y))) return true; // going down
+		if (((p1.x <= p2.x && q1.x >= p2.x) || (p1.x >= p2.x && q1.x <= p2.x)) || ((p1.y <= p2.y && q1.y >= p2.y) || (p1.y >= p2.y && q1.y <= p2.y)))
+		if ((neg2(bdir.x, pdir.x) || pos2(bdir.x, pdir.x)) && (neg2(bdir.y, pdir.y) || pos2(bdir.y, pdir.y))) return true;
 	}
   
     // Special Cases
diff --git a/objects.c b/objects.c
index 39e0f30..72af5a5 100644
--- a/objects.c
+++ b/objects.c
@@ -30,17 +30,11 @@ object get_object_at_tile(int x, int y) {
 void draw_objects_at_row(platform_window* window, int row) {
 	map_info info = get_map_info(window);
 
-	bool did_player_draw = false;
-	int x_of_player = playerx;
-	int y_of_player = playery+get_player_size_in_tile();
-
 	for (int i = MAP_SIZE_X-1; i >= 0; i--) {
 		object o = get_object_at_tile(i, row);
 	
-		if (row == y_of_player && x_of_player == i) {
-			OBJECT_RENDER_DEPTH(o.h);
-			draw_player(window);
-		}
+		OBJECT_RENDER_DEPTH(o.h);
+		draw_players_at_tile(window, i, row);
 
 		draw_zombies_at_tile(window, i, row);
 
@@ -71,12 +65,27 @@ void create_box(float x, float y, float h) {
 
 void create_objects() {
 	// rechts naar links op map.
-	create_box(4, 0, 0);
-	create_box(1, 0, 0);
-	create_box(0, 0, 0);
 
-	create_box(0, 1, 0);
-	create_box(3, 5, 0);
+	for (int i = MAP_SIZE_X-1; i >= 0; i--) {
+		create_box(i, 0, 0);
+		create_box(i, MAP_SIZE_Y-1, 0);
+	}
+
+	for (int i = MAP_SIZE_Y-1; i >= 0; i--) {
+		create_box(0, i, 0);
+		create_box(MAP_SIZE_Y-1, i, 0);
+	}
+
+	create_box(16, 8, 0);
+	create_box(14, 8, 0);
+	create_box(11, 8, 0);
+	create_box(10, 8, 0);
 
-	spawn_zombie(2, 7);
+	create_box(15, 10, 0);
+	create_box(14, 10, 0);
+	create_box(13, 10, 0);
+	create_box(11, 10, 0);
+	
+	spawn_player(my_id);
+	spawn_player(my_id+1);
 }
\ No newline at end of file
diff --git a/pathfinding.c b/pathfinding.c
new file mode 100644
index 0000000..b69d420
--- /dev/null
+++ b/pathfinding.c
@@ -0,0 +1,308 @@
+#include "include/pathfinding.h"
+
+static float distance_between(vec2f v1, vec2f v2)
+{
+	return ((v1.x-v2.x)*(v1.x-v2.x)+(v1.y-v2.y)*(v1.y-v2.y));
+}
+
+bool can_walk_at(float x, float y)
+{
+	for (int i = 0; i < max_objects; i++) {
+		object o = objects[i];
+		if (!o.active) continue;
+		if (x >= o.position.x && x < o.position.x + o.size.x && y >= o.position.y && y < o.position.y + o.size.y) return false;
+	}
+	return true;
+}
+
+bool find_path_to(vec2f start_pos, vec2f end_pos, array *to_fill, pathfinding_request* request)
+{
+	struct path_node {
+		struct path_node *parent;
+		vec2f position;
+		s32 g;
+		s32 h;
+		s32 f;
+	};
+	
+	list open_array = list_create(sizeof(struct path_node));
+	list closed_array = list_create(sizeof(struct path_node));
+	
+	struct path_node *start_node = mem_alloc(sizeof(struct path_node));
+	start_node->g = 0;
+	start_node->h = 0;
+	start_node->f = 0;
+	start_node->parent = 0;
+	start_node->position = start_pos;
+	
+	list_push(&open_array, (uint8_t*)start_node);
+	
+	struct path_node *current_node = 0;
+	while(open_array.count > 0 && !request->cancelled)
+	{
+		// Get the current node
+		current_node = list_at(&open_array, 0);
+		s32 current_index = 0;
+		
+		for (s32 i = 0; i < open_array.count; i++)
+		{
+			struct path_node *item = list_at(&open_array, i);
+			if (item->f < current_node->f)
+			{
+				current_node = item;
+				current_index = i;
+			}
+		}
+		
+		//Pop current off open array, add to closed array
+		list_push(&closed_array, (uint8_t*)current_node);
+		
+		if (closed_array.count > 1000) return false;
+		if (open_array.count > 1000) return false;
+		
+		// Found the goal
+		if (distance_between(current_node->position, end_pos) <= 0)
+		{
+			if (to_fill)
+				to_fill->length = 0;
+			struct path_node *current = current_node;
+			
+			while(current != 0)
+			{
+				if (to_fill)
+				{
+					vec2f v;
+					v.x = current->position.x + 0.5;
+					v.y = current->position.y + 0.5;
+					array_push(to_fill, (uint8_t*)&v);
+				}
+				
+				struct path_node *prev = current;
+				current = current->parent;
+				mem_free(prev);
+			}
+			
+			if (to_fill) {
+				array_remove_at(to_fill, to_fill->length-1);
+				request->done = true;
+			}
+
+			list_destroy(&open_array);
+			list_destroy(&closed_array);
+			
+			return true;
+		}
+		
+		vec2 adjecent[8] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };
+		
+		list children = list_create(sizeof(struct path_node));
+		
+		// Generate children
+		for (s32 i = 0; i < 8; i++)
+		{
+			//Get node position
+			vec2f node_position;
+			node_position.x = current_node->position.x + adjecent[i].x;
+			node_position.y = current_node->position.y + adjecent[i].y;
+			
+			//Make sure within range
+			if (!is_in_bounds(node_position.x, node_position.y) || !can_walk_at(node_position.x, node_position.y)) continue;
+			
+			// if diagonal move, check if not cutting off building
+			if (i >= 4) {
+				if (i == 4) // top left
+				{
+					if (!can_walk_at(node_position.x+1, node_position.y)) continue;
+					if (!can_walk_at(node_position.x, node_position.y+1)) continue;
+				}
+				if (i == 5) // down left
+				{
+					if (!can_walk_at(node_position.x+1, node_position.y)) continue;
+					if (!can_walk_at(node_position.x, node_position.y-1)) continue;
+				}
+				if (i == 6) // top right
+				{
+					if (!can_walk_at(node_position.x-1, node_position.y)) continue;
+					if (!can_walk_at(node_position.x, node_position.y+1)) continue;
+				}
+				if (i == 7) // down right
+				{
+					if (!can_walk_at(node_position.x-1, node_position.y)) continue;
+					if (!can_walk_at(node_position.x, node_position.y-1)) continue;
+				}
+			}
+			
+			// Create new node
+			struct path_node *new_node = mem_alloc(sizeof(struct path_node));
+			new_node->g = 0;
+			new_node->h = 0;
+			new_node->f = 0;
+			new_node->parent = current_node;
+			new_node->position = node_position;
+			
+			if (node_position.x == current_node->position.x &&
+				node_position.y == current_node->position.y)
+				continue;
+			
+			// Child is on the closed array
+			for (s32 c = 0; c < closed_array.count; c++)
+			{
+				struct path_node *closed_child = list_at(&closed_array, c);
+				
+				if (closed_child->position.x == new_node->position.x &&
+					closed_child->position.y == new_node->position.y)
+				{
+					goto skip_adjecent;
+				}
+			}
+			
+			list_push(&children,(uint8_t*)new_node);
+			
+			skip_adjecent:;
+		}
+		
+		// Loop through children
+		for (s32 i = 0; i < children.count; i++)
+		{
+			struct path_node *child = list_at(&children, i);
+			
+			// Child is on the closed array
+			for (s32 c = 0; c < closed_array.count; c++)
+			{
+				struct path_node *closed_child = list_at(&closed_array, c);
+				
+				if (closed_child->position.x == child->position.x &&
+					closed_child->position.y == child->position.y)
+				{
+					goto skip_child;
+				}
+			}
+			
+			// Create the f, g, and h values
+			child->g = current_node->g + 1;
+			child->h = distance_between(child->position, end_pos);
+			child->f = child->g + child->h;
+			
+			// Child is already in the open array
+			for (s32 c = 0; c < open_array.count; c++)
+			{
+				struct path_node *open_child = list_at(&open_array, c);
+				
+				if ((open_child->position.x == child->position.x &&
+					 open_child->position.y == child->position.y) && 
+					child->g >= open_child->g)
+				{
+					goto skip_child;
+				}
+			}
+			
+			// Add the child to the open array
+			list_push(&open_array, (uint8_t*)child);
+			
+			skip_child:;
+		}
+		
+		list_remove_at(&open_array, current_index);
+	}
+	
+	return false;
+}
+
+vec2f get_open_tile_next_to_target(float x, float y)
+{
+	vec2f adjecent[8] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} };
+	
+	vec2f v_s;
+	v_s.x = x;
+	v_s.y = y;
+	
+	s32 closest_index = -1;
+	s32 closest_dist = 999999;
+	vec2f v;
+	for (s32 i = 0; i < 8; i++)
+	{
+		if (can_walk_at(x + adjecent[i].x, y + adjecent[i].y))
+		{
+			vec2f vv;
+			vv.x = x + adjecent[i].x;
+			vv.y = y + adjecent[i].y;
+			
+			s32 dist = distance_between(v_s, vv);
+			if (dist < closest_dist)
+			{
+				v = vv;
+				closest_dist = dist;
+				closest_index = i;
+			}
+		}
+	}
+	
+	if (closest_index != -1)
+	{
+		return v;
+	}
+	
+	v.x = -1;
+	v.y = -1;
+	return v;
+}
+
+void pathfinding_init()
+{
+	global_pathfinding_queue = array_create(sizeof(pathfinding_request));
+	array_reserve(&global_pathfinding_queue, 1000);
+}
+
+void pathfinding_destroy()
+{
+	array_destroy(&global_pathfinding_queue);
+}
+
+void* pathfinding_thread(void *args)
+{
+	while(1)
+	{
+		pathfinding_request request;
+		
+		mutex_lock(&global_pathfinding_queue.mutex);
+		if (global_pathfinding_queue.length)
+		{
+			pathfinding_request* request = *(pathfinding_request**)array_at(&global_pathfinding_queue, 0);
+			array_remove_at(&global_pathfinding_queue, 0);
+			mutex_unlock(&global_pathfinding_queue.mutex);
+
+			request->cancelled = false;
+			find_path_to(request->start, request->end, request->to_fill, request);
+			
+			continue;
+		}
+		else
+		{
+			mutex_unlock(&global_pathfinding_queue.mutex);
+			continue;
+		}
+		
+		thread_sleep(100);
+	}
+	
+	return 0;
+}
+
+void make_pathfinding_request(vec2f start, vec2f end, array *to_fill, pathfinding_request *request)
+{
+	mutex_lock(&global_pathfinding_queue.mutex);
+
+	request->cancelled = true;
+
+	start.x = (int)start.x;
+	start.y = (int)start.y;
+	end.x = (int)end.x;
+	end.y = (int)end.y;
+	
+	request->start = start;
+	request->end = end;
+	request->to_fill = to_fill;
+	request->done = false;
+	array_push(&global_pathfinding_queue, (uint8_t*)&request);
+	mutex_unlock(&global_pathfinding_queue.mutex);
+}
\ No newline at end of file
diff --git a/players.c b/players.c
index 40b2de3..f6719b5 100644
--- a/players.c
+++ b/players.c
@@ -16,7 +16,30 @@ float get_player_size(platform_window* window) {
 	int player_size = get_tile_width(window) * get_player_size_in_tile();
 }
 
-object check_if_player_collided_with_object(platform_window* window) {
+void spawn_player(int id) {
+	for (int i = 0; i < max_players; i++) {
+		if (players[i].active) continue;
+		players[i].active = true;
+		players[i].sec_since_last_shot = 10.0f;
+		players[i].playerx = 3;
+		players[i].playery = 3;
+		players[i].gunx = 0.0f;
+		players[i].guny = 0.0f;
+		players[i].gun_height = 0.0f;
+		players[i].id = id;
+		return;
+	}
+}
+
+player get_player_by_id(int id) {
+	for (int i = 0; i < max_players; i++) {
+		if (!players[i].active) continue;
+		if (players[i].id == id) return players[i];
+	}
+	return (player){-1};
+}
+
+object check_if_player_collided_with_object(platform_window* window, player p) {
 	map_info info = get_map_info(window);
 	float player_size = get_player_size(window);
 
@@ -25,9 +48,9 @@ object check_if_player_collided_with_object(platform_window* window) {
 		if (!o.active) continue;
 
 		box box = get_box_of_object(window, o);
-		float x_to_check = playerx;
+		float x_to_check = p.playerx;
 		float player_size_in_tile_px = player_size / (float)info.tile_width;
-		float y_to_check = playery + player_size_in_tile_px;
+		float y_to_check = p.playery + player_size_in_tile_px;
 
 		if (x_to_check+player_size_in_tile_px >= o.position.x && x_to_check <= o.position.x+o.size.x
 		 && y_to_check >= o.position.y && y_to_check <= o.position.y+o.size.y) {
@@ -38,85 +61,108 @@ object check_if_player_collided_with_object(platform_window* window) {
 	return (object){0};
 }
 
+int get_my_player_index() {
+	for (int i = 0; i < max_players; i++) {
+		if (!players[i].active) continue;
+		if (players[i].id == my_id) return i;
+	}
+	return -1;
+}
+
 void take_player_input(platform_window* window) {
 	float speed = 0.1f;
 	float pad_between_player_and_obj = 0.01f;
 
-	float old_x = playerx;
-	float old_y = playery;
+	int my_index = get_my_player_index();
+	if (my_index == -1) return;
+
+	float old_x = players[my_index].playerx;
+	float old_y = players[my_index].playery;
 
 	if (keyboard_is_key_down(KEY_W)) {
-		float newy = playery - speed;
-		if (is_in_bounds(playerx, newy)) {
-			playery = newy;
-			object o = check_if_player_collided_with_object(window);
-			if (o.active) playery = o.position.y+o.size.y - get_player_size_in_tile() + pad_between_player_and_obj;
+		float newy = players[my_index].playery - speed;
+		if (is_in_bounds(players[my_index].playerx, newy)) {
+			players[my_index].playery = newy;
+			object o = check_if_player_collided_with_object(window, players[my_index]);
+			if (o.active) players[my_index].playery = o.position.y+o.size.y - get_player_size_in_tile() + pad_between_player_and_obj;
 		}
 	}
 
 	if (keyboard_is_key_down(KEY_S)) {
-		float newy = playery + speed;
-		if (is_in_bounds(playerx, newy)) {
-			playery = newy;
-			object o = check_if_player_collided_with_object(window);
-			if (o.active) playery = o.position.y - get_player_size_in_tile() - pad_between_player_and_obj;
+		float newy = players[my_index].playery + speed;
+		if (is_in_bounds(players[my_index].playerx, newy)) {
+			players[my_index].playery = newy;
+			object o = check_if_player_collided_with_object(window, players[my_index]);
+			if (o.active) players[my_index].playery = o.position.y - get_player_size_in_tile() - pad_between_player_and_obj;
 		}
 	}
 
 	if (keyboard_is_key_down(KEY_A)) {
-		float newx = playerx - speed;
-		if (is_in_bounds(newx, playery)) {
-			playerx = newx;
-			object o = check_if_player_collided_with_object(window);
-			if (o.active) playerx = o.position.x+o.size.x + pad_between_player_and_obj;
+		float newx = players[my_index].playerx - speed;
+		if (is_in_bounds(newx, players[my_index].playery)) {
+			players[my_index].playerx = newx;
+			object o = check_if_player_collided_with_object(window, players[my_index]);
+			if (o.active) players[my_index].playerx = o.position.x+o.size.x + pad_between_player_and_obj;
 		}
 	}
 
 	if (keyboard_is_key_down(KEY_D)) {
-		float newx = playerx + speed;
-		if (is_in_bounds(newx, playery)) {
-			playerx = newx;
-			object o = check_if_player_collided_with_object(window);
-			if (o.active) playerx = o.position.x-get_player_size_in_tile() - pad_between_player_and_obj;
+		float newx = players[my_index].playerx + speed;
+		if (is_in_bounds(newx, players[my_index].playery)) {
+			players[my_index].playerx = newx;
+			object o = check_if_player_collided_with_object(window, players[my_index]);
+			if (o.active) players[my_index].playerx = o.position.x-get_player_size_in_tile() - pad_between_player_and_obj;
 		}
 	}
 }
 
-void draw_player(platform_window* window) {
-	int size = get_tile_width(window) / 2;
-	map_info info = get_map_info(window);
-	float height = get_height_of_tile_under_coords(window, playerx, playery);
-
-	take_player_input(window);
-
-	sec_since_last_shot += update_delta;
-	float bullets_per_sec = 10;
-	float time_between_bullets = 1.0f/bullets_per_sec;
-	if (is_left_down()) {
-		if (sec_since_last_shot > time_between_bullets) {
-			for (int i = 0; i < 3; i++) shoot(window);
-			sec_since_last_shot = 0.0f;
+void draw_players_at_tile(platform_window* window, int x, int y) {
+	for (int i = 0; i < max_players; i++) {
+		if (!players[i].active) continue;
+		if ((int)players[i].playerx != x || (int)(players[i].playery+get_player_size_in_tile()) != y) continue;
+
+		int size = get_tile_width(window) / 2;
+		map_info info = get_map_info(window);
+		float height = get_height_of_tile_under_coords(window, players[i].playerx, players[i].playery);
+
+		take_player_input(window);
+
+		players[i].sec_since_last_shot += update_delta;
+		float bullets_per_sec = 10;
+		float time_between_bullets = 1.0f/bullets_per_sec;
+		if (is_left_down()) {
+			if (players[i].sec_since_last_shot > time_between_bullets) {
+				int ix = get_my_player_index();
+				if (ix != -1) {
+					for (int i = 0; i < 3; i++) {
+						shoot(window, players[ix]);
+						players[i].sec_since_last_shot = 0.0f;
+					}
+				}
+			}
 		}
-	}
 
-	float player_render_x = playerx*info.tile_width + (playery*info.px_incline);
-	float player_render_y = playery*info.tile_height - (height*info.px_raised_per_h);
-	renderer->render_rectangle(player_render_x, player_render_y, size, size, rgb(200,150,120));
+		float player_render_x = players[i].playerx*info.tile_width + (players[i].playery*info.px_incline);
+		float player_render_y = players[i].playery*info.tile_height - (height*info.px_raised_per_h);
+		renderer->render_rectangle(player_render_x, player_render_y, size, size, rgb(200,150,120));
 
-	float dirx = (_global_mouse.x - (window->width/2));
-	float diry = (_global_mouse.y - (window->height/2));
-	double length = sqrt(dirx * dirx + diry * diry);
-	dirx /= length;
-	diry /= length;
+		float dirx = (_global_mouse.x - (window->width/2));
+		float diry = (_global_mouse.y - (window->height/2));
+		double length = sqrt(dirx * dirx + diry * diry);
+		dirx /= length;
+		diry /= length;
 
-	gunx = playerx + (get_player_size_in_tile()/2) + dirx/2;
-	guny = playery + (get_player_size_in_tile()/2) + diry/2;
-	gun_height = height+0.5;
-	float gun_render_x = gunx*info.tile_width + (guny*info.px_incline);
-	float gun_render_y = guny*info.tile_height - (gun_height*info.px_raised_per_h);
+		players[i].gunx = players[i].playerx + (get_player_size_in_tile()/2) + dirx/2;
+		players[i].guny = players[i].playery + (get_player_size_in_tile()/2) + diry/2;
+		players[i].gun_height = height+0.5;
+		float gun_render_x = players[i].gunx*info.tile_width + (players[i].guny*info.px_incline);
+		float gun_render_y = players[i].guny*info.tile_height - (players[i].gun_height*info.px_raised_per_h);
 
-	renderer->render_rectangle(gun_render_x, gun_render_y, size/4, size/4, rgb(20,255,20));
+		renderer->render_rectangle(gun_render_x, gun_render_y, size/4, size/4, rgb(20,255,20));
 
-	_global_camera.x = -(window->width / 2) + player_render_x;
-	_global_camera.y = -(window->height / 2) + player_render_y;
+		if (players[i].id == my_id) {
+			_global_camera.x = -(window->width / 2) + player_render_x;
+			_global_camera.y = -(window->height / 2) + player_render_y;
+		}
+	}
 }
diff --git a/project-base.code-workspace b/project-base.code-workspace
index 45b030e..be07839 100644
--- a/project-base.code-workspace
+++ b/project-base.code-workspace
@@ -53,7 +53,11 @@
 			"map.h": "c",
 			"zombies.h": "c",
 			"math.h": "c",
-			"math_helper.h": "c"
+			"math_helper.h": "c",
+			"xiosbase": "c",
+			"pathfinding.h": "c",
+			"unordered_map": "c",
+			"players.h": "c"
 		}
 	}
 }
\ No newline at end of file
diff --git a/zombies.c b/zombies.c
index 80a34ad..85dea2d 100644
--- a/zombies.c
+++ b/zombies.c
@@ -1,14 +1,44 @@
 #include "include/zombies.h"
 
+static player get_closest_player_to_tile(int x, int y) {
+	float best_length = 99999;
+	int best_index = -1;
+
+	for (int i = 0; i < max_players; i++) {
+		if (!players[i].active) continue;
+		float dirx = (players[i].playerx - x);
+		float diry = (players[i].playery - y);
+		double length = sqrt(dirx * dirx + diry * diry);
+
+		if (length < best_length) {
+			best_length = length;
+			best_index = i;
+		}
+	}
+	if (best_index == -1) {
+		return (player){-1};
+	}
+	else {
+		return players[best_index];
+	}
+}
+
 void spawn_zombie(int x, int y) {
 	for (int i = 0; i < max_zombies; i++) {
 		zombie o = zombies[i];
 		if (o.alive) continue;
 
+		zombies[i].path = array_create(sizeof(vec2f));
+		zombies[i].next_path = array_create(sizeof(vec2f));
 		zombies[i].alive = true;
 		zombies[i].health = 100.0f;
 		zombies[i].position = (vec3f){x,y, 0};
 		zombies[i].size = (vec3f){0.4, 0.4, 1};
+		zombies[i].time_since_last_path = 0.0f;
+
+		player closest_player = get_closest_player_to_tile(x, y);
+
+		make_pathfinding_request((vec2f){x,y}, (vec2f){closest_player.playerx, closest_player.playery}, &zombies[i].path, &zombies[i].request);
 		break;
 	}
 }
@@ -30,7 +60,7 @@ void draw_spawners(platform_window* window) {
 				rgb(100, 150, 50));	
 
 		spawner_tiles[x].sec_since_last_spawn += update_delta;
-		if (spawner_tiles[x].sec_since_last_spawn >= 1.0f) {
+		if (spawner_tiles[x].sec_since_last_spawn >= 3.0f) {
 			spawn_zombie(spawner.position.x, spawner.position.y);
 			spawner_tiles[x].sec_since_last_spawn = 0;
 		}
@@ -42,6 +72,55 @@ void draw_spawners(platform_window* window) {
 	}
 }
 
+static void draw_path_of_zombie(platform_window* window, zombie o) {
+	map_info info = get_map_info(window);
+	vec2f prev_pos = (vec2f){o.position.x, o.position.y};
+
+	for (int i = 0; i < o.path.length; i++) {
+		vec2f* pos = array_at(&o.path, o.path.length-1-i);
+
+		int render_x = (info.tile_width * prev_pos.x) + (info.px_incline * prev_pos.y);
+		int render_y = info.tile_height * prev_pos.y;
+
+		int render_x2 = (info.tile_width * pos->x) + (info.px_incline * pos->y);
+		int render_y2 = info.tile_height * pos->y;
+
+		prev_pos = *pos;
+		if (i == 0) {
+			renderer->render_line(render_x, render_y, render_x2, render_y2, 2, rgb(0,255,255));
+			continue;
+		}
+	
+		renderer->render_line(render_x, render_y, render_x2, render_y2, 2, rgb(0,0,255));
+	}
+}
+
+static vec2f get_direction_to_next_tile(zombie o) {
+	vec2f dest = (vec2f){o.position.x, o.position.y};
+	if (o.path.length > 0) {
+		dest = *(vec2f*)array_at(&o.path, o.path.length-1);
+	}
+
+	float dirx = (dest.x - o.position.x);
+	float diry = (dest.y - o.position.y);
+	if (dirx == 0 && diry == 0) return (vec2f){0,0};
+	double length = sqrt(dirx * dirx + diry * diry);
+	dirx /= length;
+	diry /= length;
+	return (vec2f){dirx, diry};
+}
+
+static bool is_within_next_tile(zombie o) {
+	if (o.path.length > 0) {
+		vec2f dest = *(vec2f*)array_at(&o.path, o.path.length-1);
+		if (fabs(o.position.x - dest.x) < 0.05f && fabs(o.position.y - dest.y) < 0.05f) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
 void draw_zombies_at_tile(platform_window* window, int x, int y) {
 	map_info info = get_map_info(window);
 	float speed = 0.05f;
@@ -49,24 +128,43 @@ void draw_zombies_at_tile(platform_window* window, int x, int y) {
 	for (int i = 0; i < max_zombies; i++) {
 		zombie o = zombies[i];
 		if (!o.alive) continue;
+
 		if ((int)o.position.x != x || (int)ceil(o.position.y) != y) continue;
 
-		float dirx = (playerx - o.position.x);
-		float diry = (playery - o.position.y);
-		double length = sqrt(dirx * dirx + diry * diry);
-		dirx /= length;
-		diry /= length;
+		zombies[i].time_since_last_path += update_delta;
+		if (zombies[i].time_since_last_path > 0.1f) {
+			player closest_player = get_closest_player_to_tile(x, y);
+			make_pathfinding_request((vec2f){o.position.x,o.position.y}, 
+				(vec2f){closest_player.playerx, closest_player.playery + get_player_size_in_tile()}, 
+				&zombies[i].next_path, &zombies[i].request);
+			zombies[i].time_since_last_path = 0;
+		}
+		else {
+			if (zombies[i].request.done) {
+				zombies[i].path = zombies[i].next_path;
+				array_clear(&zombies[i].next_path);
+				zombies[i].request.done = false;
+			}
+		}
+
+		vec2f dir = get_direction_to_next_tile(o);
 
 		float height = get_height_of_tile_under_coords(window, zombies[i].position.x, zombies[i].position.y);
-		zombies[i].position.x += dirx*speed;
-		zombies[i].position.y += diry*speed;
+		zombies[i].position.x += dir.x*speed;
+		zombies[i].position.y += dir.y*speed;
 		zombies[i].position.z = height;
 
+		if (is_within_next_tile(zombies[i])) {
+			array_remove_at(&zombies[i].path, zombies[i].path.length-1);
+		}
+
 		box box = get_render_box_of_square(window, (vec3f){o.position.x, o.position.y, height}, o.size);
 		render_quad_with_outline(box.tl_b, box.tr_b, box.bl_b, box.br_b);
 		render_quad_with_outline(box.tl_u, box.tr_u, box.bl_u, box.br_u);
 		render_quad_with_outline(box.tl_u, box.tl_b, box.bl_u, box.bl_b);
 		render_quad_with_outline(box.bl_u, box.br_u, box.bl_b, box.br_b);
+
+		draw_path_of_zombie(window, o);
 	}
 }
 
-- 
cgit v1.2.3-70-g09d2