/*
 * Almost all of the following lines were taken from "cave.c", and then
 * modified as described below.  See "cave.c" for actual algorithm details.
 *
 * First, we removed all calls to "note_spot()" and "lite_spot()", and any
 * "if" and/or "loop" code which was thus rendered pointless.
 *
 * Then, we performed the following 'regexp' substitutions:
 *
 *   p_ptr->blind ==> borg_base_is_blind
 *
 *   p_ptr ==> b_ptr
 *
 *   \<cave_info\> ==> borg_cave_info
 *
 *   \<temp_g\> ==> borg_temp_g
 *   \<view_n\> ==> borg_view_n
 *   \<view_g\> ==> borg_view_g
 *
 *   forget_view ==> borg_forget_view
 *   update_view ==> borg_update_view
 *
 * Last adaptation performed on 1997-12-03
 *
 *
 * Old comments follow XXX XXX XXX XXX XXX
 *
 * The following functions are taken from "cave.c", and then modified for
 * the use of the Borg.  See "cave.c" for more complete documentation.
 *
 * First, some of the code is not needed by the Borg and must be removed.
 * This includes and code dealing with the variables "temp_n", "temp_y",
 * or "temp_x", the constants "CAVE_TEMP" or "CAVE_GLOW", or the functions
 * "lite_spot()" or "note_spot()".  Note that almost all of the "complete
 * the algorithm" code is thus removed (except for the code to clear the
 * "BORG_XTRA" flags).
 *
 * Then, make the following substitutions (in order).  XXX XXX XXX
 *
 *   CAVE_ -> BORG_
 *
 *   p_ptr -> b_ptr
 *
 *   cave_ -> db_ptr->cave_
 *
 *   lite_ -> borg_lite_
 *   view_ -> borg_view_
 *
 *   forget_ -> borg_forget_
 *   update_ -> borg_update_
 *
 *   update_borg_aux -> update_aux
 *
 *   borg_view_reduce_view -> view_reduce_view
 *
 *   db_ptr->cave_lite_hack -> borg_cave_lite_hack
 *   db_ptr->cave_view_hack -> borg_cave_view_hack
 *
 *   db_ptr->cave_floor_bold -> borg_cave_floor_bold
 *
 *   los -> borg_los
 *
 *
 * Last adaptation: 1997-05-04
 */



/*
 * Forget the "BORG_LITE" grids, redrawing as needed.
 */
void borg_forget_lite(void)
{
	int i, x, y;

	/* None to forget */
	if (!borg_lite_n) return;

	/* Clear them all */
	for (i = 0; i < borg_lite_n; i++)
	{
		y = borg_lite_y[i];
		x = borg_lite_x[i];

		/* Forget "LITE" flag */
		db_ptr->cave_info[y][x] &= ~(BORG_LITE);
	}

	/* None left */
	borg_lite_n = 0;
}


/*
 * Simplify the "borg_update_lite()" function XXX XXX XXX
 *
 * This macro allows us to efficiently add a grid to the "lite" array,
 * note that we are never called for illegal grids, or for grids which
 * have already been placed into the "lite" array, and we are never
 * called when the "lite" array is full.
 */
#define borg_cave_lite_hack(Y,X) \
	do { \
		db_ptr->cave_info[Y][X] |= (BORG_LITE); \
		borg_lite_y[borg_lite_n] = (Y); \
		borg_lite_x[borg_lite_n] = (X); \
		borg_lite_n++; \
	} while (0)


/*
 * Update the "BORG_LITE" grids, redrawing as needed.
 */
void borg_update_lite(void)
{
	int py = b_ptr->py;
	int px = b_ptr->px;

	int r = b_ptr->cur_lite;

	int i, y, x;


	/*** Special case ***/

	/* Hack -- Player has no lite */
	if (r <= 0)
	{
		/* Forget the old lite */
		borg_forget_lite();

		/* All done */
		return;
	}


	/*** Save the old "lite" grids for later ***/

	/* Clear them all */
	for (i = 0; i < borg_lite_n; i++)
	{
		y = borg_lite_y[i];
		x = borg_lite_x[i];

		/* Mark the grid as not "lite" */
		db_ptr->cave_info[y][x] &= ~(BORG_LITE);
	}

	/* None left */
	borg_lite_n = 0;


	/*** Collect the new "lite" grids ***/

	/* Player grid */
	borg_cave_lite_hack(py, px);

	/* Radius 1 -- torch radius */
	if (r >= 1)
	{
		/* Adjacent grid */
		borg_cave_lite_hack(py+1, px);
		borg_cave_lite_hack(py-1, px);
		borg_cave_lite_hack(py, px+1);
		borg_cave_lite_hack(py, px-1);

		/* Diagonal grids */
		borg_cave_lite_hack(py+1, px+1);
		borg_cave_lite_hack(py+1, px-1);
		borg_cave_lite_hack(py-1, px+1);
		borg_cave_lite_hack(py-1, px-1);
	}

	/* Radius 2 -- lantern radius */
	if (r >= 2)
	{
		/* South of the player */
		if (borg_cave_floor_bold(py+1, px))
		{
			borg_cave_lite_hack(py+2, px);
			borg_cave_lite_hack(py+2, px+1);
			borg_cave_lite_hack(py+2, px-1);
		}

		/* North of the player */
		if (borg_cave_floor_bold(py-1, px))
		{
			borg_cave_lite_hack(py-2, px);
			borg_cave_lite_hack(py-2, px+1);
			borg_cave_lite_hack(py-2, px-1);
		}

		/* East of the player */
		if (borg_cave_floor_bold(py, px+1))
		{
			borg_cave_lite_hack(py, px+2);
			borg_cave_lite_hack(py+1, px+2);
			borg_cave_lite_hack(py-1, px+2);
		}

		/* West of the player */
		if (borg_cave_floor_bold(py, px-1))
		{
			borg_cave_lite_hack(py, px-2);
			borg_cave_lite_hack(py+1, px-2);
			borg_cave_lite_hack(py-1, px-2);
		}
	}

	/* Radius 3+ -- artifact radius */
	if (r >= 3)
	{
		int y1, y2, x1, x2;

		/* Paranoia */
		if (r > 5) r = 5;

		/* South-East of the player */
		if (borg_cave_floor_bold(py+1, px+1))
		{
			borg_cave_lite_hack(py+2, px+2);
		}

		/* South-West of the player */
		if (borg_cave_floor_bold(py+1, px-1))
		{
			borg_cave_lite_hack(py+2, px-2);
		}

		/* North-East of the player */
		if (borg_cave_floor_bold(py-1, px+1))
		{
			borg_cave_lite_hack(py-2, px+2);
		}

		/* North-West of the player */
		if (borg_cave_floor_bold(py-1, px-1))
		{
			borg_cave_lite_hack(py-2, px-2);
		}

		/* Maximal north */
		y1 = py - r;
		if (y1 < 0) y1 = 0;

		/* Maximal south */
		y2 = py + r;
		if (y2 > DUNGEON_HGT-1) y2 = DUNGEON_HGT-1;

		/* Maximal west */
		x1 = px - r;
		if (x1 < 0) x1 = 0;

		/* Maximal east */
		x2 = px + r;
		if (x2 > DUNGEON_WID-1) x2 = DUNGEON_WID-1;

		/* Scan the maximal box */
		for (y = y1; y <= y2; y++)
		{
			for (x = x1; x <= x2; x++)
			{
				int d;

				int dy = (py > y) ? (py - y) : (y - py);
				int dx = (px > x) ? (px - x) : (x - px);

				/* Skip the "central" grids (above) */
				if ((dy <= 2) && (dx <= 2)) continue;

				/* Hack -- approximate the distance */
				d = (dy > dx) ? (dy + (dx>>1)) : (dx + (dy>>1));

				/* Skip distant grids */
				if (d > r) continue;

				/* Viewable grids get "torch lit" */
				if (db_ptr->cave_info[y][x] & (BORG_VIEW))
				{
					/* This grid is "torch lit" */
					borg_cave_lite_hack(y, x);
				}
			}
		}
	}
}




/*
 * Forget the "BORG_VIEW" grids, redrawing as needed
 */
void borg_forget_view(void)
{
	int i;

	/* None to forget */
	if (!borg_view_n) return;

	/* Clear them all */
	for (i = 0; i < borg_view_n; i++)
	{
		int y = borg_view_y[i];
		int x = borg_view_x[i];

		/* Forget that the grid is viewable */
		db_ptr->cave_info[y][x] &= ~(BORG_VIEW);
	}

	/* None left */
	borg_view_n = 0;
}


/*
 * Simplify the "borg_update_view()" function XXX XXX XXX
 *
 * This macro allows us to efficiently add a grid to the "view" array,
 * note that we are never called for illegal grids, or for grids which
 * have already been placed into the "view" array, and we are never
 * called when the "view" array is full.
 */
#define borg_cave_view_hack(Y,X) \
	do { \
		db_ptr->cave_info[Y][X] |= (BORG_VIEW); \
		borg_view_y[borg_view_n] = (Y); \
		borg_view_x[borg_view_n] = (X); \
		borg_view_n++; \
	} while (0)


/*
 * Helper function for "borg_update_view()" below
 *
 * This function processes the "viewability" of the grid (y,x).
 *
 * Grid (y1,x1) is on the "diagonal" between (py,px) and (y,x)
 * Grid (y2,x2) is "adjacent", also between (py,px) and (y,x).
 *
 * This function returns "TRUE" if vision is "blocked" by grid (y,x).
 */
static bool borg_update_view_aux(int y, int x, int y1, int x1, int y2, int x2)
{
	bool f1, f2, v1, v2, z1, z2, wall;


	/* Check for walls */
	f1 = (borg_cave_floor_bold(y1, x1));
	f2 = (borg_cave_floor_bold(y2, x2));

	/* Totally blocked by physical walls */
	if (!f1 && !f2) return (TRUE);


	/* Check for visibility */
	v1 = (f1 && (db_ptr->cave_info[y1][x1] & (BORG_VIEW)));
	v2 = (f2 && (db_ptr->cave_info[y2][x2] & (BORG_VIEW)));

	/* Totally blocked by "unviewable neighbors" */
	if (!v1 && !v2) return (TRUE);


	/* Check for walls */
	wall = (!borg_cave_floor_bold(y, x));


	/* Check the "ease" of visibility */
	z1 = (v1 && (db_ptr->cave_info[y1][x1] & (BORG_XTRA)));
	z2 = (v2 && (db_ptr->cave_info[y2][x2] & (BORG_XTRA)));

	/* Hack -- "easy" plus "easy" yields "easy" */
	if (z1 && z2)
	{
		db_ptr->cave_info[y][x] |= (BORG_XTRA);

		borg_cave_view_hack(y, x);

		return (wall);
	}

	/* Hack -- primary "easy" yields "viewed" */
	if (z1)
	{
		borg_cave_view_hack(y, x);

		return (wall);
	}


	/* Hack -- "view" plus "view" yields "view" */
	if (v1 && v2)
	{
		/* db_ptr->cave_info[y][x] |= (BORG_XTRA); */

		borg_cave_view_hack(y, x);

		return (wall);
	}


	/* Mega-Hack -- the "borg_los()" function works poorly on walls */
	if (wall)
	{
		borg_cave_view_hack(y, x);

		return (wall);
	}


	/* Actual line of sight test */
	if (TRUE)
	{
		int py = b_ptr->py;
		int px = b_ptr->px;

		/* Hack -- check line of sight */
		if (borg_los(py, px, y, x))
		{
			borg_cave_view_hack(y, x);

			return (wall);
		}
	}


	/* Assume no line of sight. */
	return (TRUE);
}


/*
 * Hack -- keep the code below simple
 */
#define DY1 0
#define DY2 (DUNGEON_HGT-1)
#define DX1 0
#define DX2 (DUNGEON_WID-1)


/*
 * Update the "BORG_VIEW" grids, redrawing as needed
 */
void borg_update_view(void)
{
	int py = b_ptr->py;
	int px = b_ptr->px;

	int n, m, d, k, y, x, z;

	int se, sw, ne, nw, es, en, ws, wn;

	int full, over;


	/*** Initialize ***/

	/* Optimize */
	if (view_reduce_view && !b_ptr->depth)
	{
		/* Full radius (10) */
		full = MAX_SIGHT / 2;

		/* Octagon factor (15) */
		over = MAX_SIGHT * 3 / 4;
	}

	/* Normal */
	else
	{
		/* Full radius (20) */
		full = MAX_SIGHT;

		/* Octagon factor (30) */
		over = MAX_SIGHT * 3 / 2;
	}


	/*** Step 0 -- Begin ***/

	/* Save the old "view" grids for later */
	for (n = 0; n < borg_view_n; n++)
	{
		y = borg_view_y[n];
		x = borg_view_x[n];

		/* Mark the grid as not in "view" */
		db_ptr->cave_info[y][x] &= ~(BORG_VIEW);
	}

	/* Start over with the "view" array */
	borg_view_n = 0;


	/*** Step 1 -- adjacent grids ***/

	/* Now start on the player */
	y = py;
	x = px;

	/* Assume the player grid is easily viewable */
	db_ptr->cave_info[y][x] |= (BORG_XTRA);

	/* Assume the player grid is viewable */
	borg_cave_view_hack(y, x);


	/*** Step 2 -- Major Diagonals ***/

	/* Hack -- Limit */
	z = full * 2 / 3;

	/* Scan south-east */
	for (d = 1; d <= z; d++)
	{
		db_ptr->cave_info[y+d][x+d] |= (BORG_XTRA);
		borg_cave_view_hack(y+d, x+d);
		if (!borg_cave_floor_bold(y+d, x+d)) break;
	}

	/* Scan south-west */
	for (d = 1; d <= z; d++)
	{
		db_ptr->cave_info[y+d][x-d] |= (BORG_XTRA);
		borg_cave_view_hack(y+d, x-d);
		if (!borg_cave_floor_bold(y+d, x-d)) break;
	}

	/* Scan north-east */
	for (d = 1; d <= z; d++)
	{
		db_ptr->cave_info[y-d][x+d] |= (BORG_XTRA);
		borg_cave_view_hack(y-d, x+d);
		if (!borg_cave_floor_bold(y-d, x+d)) break;
	}

	/* Scan north-west */
	for (d = 1; d <= z; d++)
	{
		db_ptr->cave_info[y-d][x-d] |= (BORG_XTRA);
		borg_cave_view_hack(y-d, x-d);
		if (!borg_cave_floor_bold(y-d, x-d)) break;
	}


	/*** Step 3 -- major axes ***/

	/* Scan south */
	for (d = 1; d <= full; d++)
	{
		db_ptr->cave_info[y+d][x] |= (BORG_XTRA);
		borg_cave_view_hack(y+d, x);
		if (!borg_cave_floor_bold(y+d, x)) break;
	}

	/* Initialize the "south strips" */
	se = sw = d;

	/* Scan north */
	for (d = 1; d <= full; d++)
	{
		db_ptr->cave_info[y-d][x] |= (BORG_XTRA);
		borg_cave_view_hack(y-d, x);
		if (!borg_cave_floor_bold(y-d, x)) break;
	}

	/* Initialize the "north strips" */
	ne = nw = d;

	/* Scan east */
	for (d = 1; d <= full; d++)
	{
		db_ptr->cave_info[y][x+d] |= (BORG_XTRA);
		borg_cave_view_hack(y, x+d);
		if (!borg_cave_floor_bold(y, x+d)) break;
	}

	/* Initialize the "east strips" */
	es = en = d;

	/* Scan west */
	for (d = 1; d <= full; d++)
	{
		db_ptr->cave_info[y][x-d] |= (BORG_XTRA);
		borg_cave_view_hack(y, x-d);
		if (!borg_cave_floor_bold(y, x-d)) break;
	}

	/* Initialize the "west strips" */
	ws = wn = d;


	/*** Step 4 -- Divide each "octant" into "strips" ***/

	/* Now check each "strip" */
	for (n = 1; n <= over / 2; n++)
	{
		int ypn, ymn, ypnpd, ymnmd;
		int xpn, xmn, xpnpd, xmnmd;


		/* Acquire the "bounds" of the maximal circle */
		z = over - n - n;
		if (z > full - n) z = full - n;
		while ((z + n + (n>>1)) > full) z--;


		/* Access the four diagonal grids */
		ypn = y + n;
		ymn = y - n;
		xpn = x + n;
		xmn = x - n;


		/* South strip */
		if (ypn < DY2)
		{
			/* Maximum distance */
			m = MIN(z, DY2 - ypn);

			/* East side */
			if (n < se)
			{
				/* Scan */
				for (k = n, ypnpd = ypn+1, d = 1; d <= m; d++, ypnpd++)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ypnpd, xpn, ypnpd-1, xpn-1, ypnpd-1, xpn))
					{
						if (n + d >= se) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				se = k + 1;
			}

			/* West side */
			if (n < sw)
			{
				/* Scan */
				for (k = n, ypnpd = ypn+1, d = 1; d <= m; d++, ypnpd++)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ypnpd, xmn, ypnpd-1, xmn+1, ypnpd-1, xmn))
					{
						if (n + d >= sw) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				sw = k + 1;
			}
		}


		/* North strip */
		if (ymn > DY1)
		{
			/* Maximum distance */
			m = MIN(z, ymn - DY1);

			/* East side */
			if (n < ne)
			{
				/* Scan */
				for (k = n, ymnmd = ymn-1, d = 1; d <= m; d++, ymnmd--)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ymnmd, xpn, ymnmd+1, xpn-1, ymnmd+1, xpn))
					{
						if (n + d >= ne) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				ne = k + 1;
			}

			/* West side */
			if (n < nw)
			{
				/* Scan */
				for (k = n, ymnmd = ymn-1, d = 1; d <= m; d++, ymnmd--)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ymnmd, xmn, ymnmd+1, xmn+1, ymnmd+1, xmn))
					{
						if (n + d >= nw) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				nw = k + 1;
			}
		}


		/* East strip */
		if (xpn < DX2)
		{
			/* Maximum distance */
			m = MIN(z, DX2 - xpn);

			/* South side */
			if (n < es)
			{
				/* Scan */
				for (k = n, xpnpd = xpn+1, d = 1; d <= m; d++, xpnpd++)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ypn, xpnpd, ypn-1, xpnpd-1, ypn, xpnpd-1))
					{
						if (n + d >= es) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				es = k + 1;
			}

			/* North side */
			if (n < en)
			{
				/* Scan */
				for (k = n, xpnpd = xpn+1, d = 1; d <= m; d++, xpnpd++)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ymn, xpnpd, ymn+1, xpnpd-1, ymn, xpnpd-1))
					{
						if (n + d >= en) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				en = k + 1;
			}
		}


		/* West strip */
		if (xmn > DX1)
		{
			/* Maximum distance */
			m = MIN(z, xmn - DX1);

			/* South side */
			if (n < ws)
			{
				/* Scan */
				for (k = n, xmnmd = xmn-1, d = 1; d <= m; d++, xmnmd--)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ypn, xmnmd, ypn-1, xmnmd+1, ypn, xmnmd+1))
					{
						if (n + d >= ws) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				ws = k + 1;
			}

			/* North side */
			if (n < wn)
			{
				/* Scan */
				for (k = n, xmnmd = xmn-1, d = 1; d <= m; d++, xmnmd--)
				{
					/* Check grid "d" in strip "n", notice "blockage" */
					if (borg_update_view_aux(ymn, xmnmd, ymn+1, xmnmd+1, ymn, xmnmd+1))
					{
						if (n + d >= wn) break;
					}

					/* Track most distant "non-blockage" */
					else
					{
						k = n + d;
					}
				}

				/* Limit the next strip */
				wn = k + 1;
			}
		}
	}


	/*** Step 5 -- Complete the algorithm ***/

	/* Process "new" grids */
	for (n = 0; n < borg_view_n; n++)
	{
		y = borg_view_y[n];
		x = borg_view_x[n];

		/* Clear the "BORG_XTRA" flag */
		db_ptr->cave_info[y][x] &= ~(BORG_XTRA);
	}
}



/*
 * Hack -- keep the code above simple
 */
#undef DY1
#undef DY2
#undef DX1
#undef DX2