# HG changeset patch
# User Mike Pavone <pavone@retrodev.com>
# Date 1389575153 28800
# Node ID c0bb53eaa6f4c11efd95074ea3fe7af1446cebde
# Parent  5ec4707a3fd13d0ad5a35f2d967635a169d0f96c
Calculate distances from goal for all passible points for pathfinding purposes

diff -r 5ec4707a3fd1 -r c0bb53eaa6f4 src/creep.c
--- a/src/creep.c	Sun Jan 12 16:03:33 2014 -0800
+++ b/src/creep.c	Sun Jan 12 17:05:53 2014 -0800
@@ -5,6 +5,8 @@
 u16 cur_creeps;
 extern u16 tilemap[40*28];
 
+u16 distances[20*14];
+
 u16 spawn_creep(u8 species, s16 x, s16 y)
 {
 	u16 index;
@@ -26,3 +28,101 @@
 	creeps[cur_creeps].direction = 0;
 	return cur_creeps++;
 }
+
+typedef struct {
+	u16 index;
+	u16 x;
+	u16 y;
+} mpoint;
+
+s16 explore(mpoint * points, s16 num_points, u16 src, u16 srcx, u16 srcy)
+{
+	u16 x,y,index,cindex,xmax,ymax,ystrt,dist;
+	dist = distances[src]+1;
+	xmax = srcx < 19 ? srcx+1 : srcx;
+	ymax = srcy < 13 ? srcy+1 : srcy;
+	if (srcy)
+	{
+		ystrt = srcy-1;
+		cindex = srcx ? src - 21 : src - 20;
+	} else {
+		ystrt = srcy;
+		cindex = srcx ? src - 1 : src;
+	}
+	for (x = srcx ? srcx-1 : srcx; x <= xmax; x++, cindex++)
+	{
+		for (y = ystrt, index=cindex; y<=ymax; y++,index+=20)
+		{
+			if (distances[index] > dist && !tilemap[x*2+y*2*40])
+			{
+				distances[index] = dist;
+				if (dist == 0xFFFF)
+				{
+					tilemap[x*2 + y*2*40] = TILE_ATTR_FULL(2, 0, 0, 0, 'E' - 32 + TILE_FONTINDEX);
+				}
+				points[num_points].index = index;
+				points[num_points].x = x;
+				points[num_points++].y = y;
+			}
+		}
+	}
+	return num_points;
+}
+
+void gen_distances(u16 x, u16 y)
+{
+	//TODO: Figure out the actual maximum number of candidate points that can exist
+	mpoint pointsa[20*14];
+	mpoint pointsb[20*14];
+	mpoint *points=pointsa;
+	mpoint *new_points;
+	s16 num_points = 0, old_points;
+	x /= 2;
+	y /= 2;
+	memset(distances, 0xFF, sizeof(distances));
+
+	distances[x + y*20] = 0;
+	num_points = explore(points, num_points, x + y*20, x, y);
+
+	while (num_points)
+	{
+		new_points = points == pointsa ? pointsb : pointsa;
+		old_points = num_points;
+		for (num_points = 0, old_points--; old_points >= 0; old_points--)
+		{
+			num_points = explore(new_points, num_points, points[old_points].index, points[old_points].x, points[old_points].y);
+		}
+		points = new_points;
+	}
+}
+
+void print_distances()
+{
+	u16 x,y,tindex,dindex,dist;
+	for (y = 0; y < 14; y++)
+	{
+		dindex = y * 20;
+		tindex = y * 2 * 40;
+		for (x = 0; x < 20; x++, dindex++, tindex += 2)
+		{
+			dist = distances[dindex];
+			if (dist < 10000)
+			{
+				tilemap[tindex+41] = TILE_ATTR_FULL(3, 0, 0, 0, '0' - 32 + dist % 10 + TILE_FONTINDEX);
+				dist /= 10;
+				if (dist)
+				{
+					tilemap[tindex+40] = TILE_ATTR_FULL(3, 0, 0, 0, '0' - 32 + dist % 10 + TILE_FONTINDEX);
+					dist /= 10;
+					if (dist)
+					{
+						tilemap[tindex+1] = TILE_ATTR_FULL(3, 0, 0, 0, '0' - 32 + dist % 10 + TILE_FONTINDEX);
+						dist /= 10;
+						if (dist)
+							tilemap[tindex] = TILE_ATTR_FULL(3, 0, 0, 0, '0' - 32 + dist % 10 + TILE_FONTINDEX);
+					}
+				}
+			}
+		}
+	}
+}
diff -r 5ec4707a3fd1 -r c0bb53eaa6f4 src/creep.h
--- a/src/creep.h	Sun Jan 12 16:03:33 2014 -0800
+++ b/src/creep.h	Sun Jan 12 17:05:53 2014 -0800
@@ -8,6 +8,7 @@
 typedef struct {
 	u16  index;
 	u16  health;
+	u16  waypoint;
 	u8   species;
 	u8   direction;
 } creep;
diff -r 5ec4707a3fd1 -r c0bb53eaa6f4 src/main.c
--- a/src/main.c	Sun Jan 12 16:03:33 2014 -0800
+++ b/src/main.c	Sun Jan 12 17:05:53 2014 -0800
@@ -15,10 +15,12 @@
 			tilemap[i+1] = 'O' + TILE_FONTINDEX;
 		}
 
-	tilemap[38 + 13*40] = TILE_ATTR_FULL(1, 0, 0, 0, 'G' + TILE_FONTINDEX);
-	tilemap[39 + 13*40] = TILE_ATTR_FULL(1, 0, 0, 0, 'G' + TILE_FONTINDEX);
 	tilemap[38 + 14*40] = TILE_ATTR_FULL(1, 0, 0, 0, 'G' + TILE_FONTINDEX);
 	tilemap[39 + 14*40] = TILE_ATTR_FULL(1, 0, 0, 0, 'G' + TILE_FONTINDEX);
+	tilemap[38 + 15*40] = TILE_ATTR_FULL(1, 0, 0, 0, 'G' + TILE_FONTINDEX);
+	tilemap[39 + 15*40] = TILE_ATTR_FULL(1, 0, 0, 0, 'G' + TILE_FONTINDEX);
+	gen_distances(38, 14);
+	//print_distances();
 	for (;;)
 	{
 		VDP_waitVSync();