Cesarus85--mjolnir-vr/source/ai/path_structure_bsp.c

/*
PATH_STRUCTURE_BSP.C

symbols in this file:
00051D80 01e0:
	_structure_test_ray2d (0000)
00051F60 0080:
	_structure_surfaces_are_equivalent (0000)
00051FE0 0070:
	_clip_empty_interval_by_solid_interval (0000)
00052050 0450:
	_structure_test_line2d (0000)
000524A0 0060:
	_structure_surface_index_from_point (0000)
00052500 0270:
	_structure_test_pill2d (0000)
0024EC0C 0020:
	_quantized_pathfinding_surface_widths (0000)
0024EC2C 0020:
	_quantized_pathfinding_surface_heights (0000)
0024EC4C 0027:
	??_C@_0CH@JLKIDLBA@c?3?2halo?2SOURCE?2ai?2path_structure@ (0000)
0024EC78 0008:
	__real@3fa99999a0000000 (0000)
0024EC80 0004:
	__real@3c000000 (0000)
0024EC88 0048:
	??_C@_0EI@IFBLLPMB@surface_index?$DO?$DN0?5?$CG?$CG?5surface_inde@ (0000)
0024ECD0 0007:
	??_C@_06KJFADLGN@result?$AA@ (0000)
*/

/* ---------- headers */

#include "cseries.h"
#include "cseries/errors.h"
#include "path_structure_bsp.h"

#include "math/real_math.h"
#include "physics/breakable_surfaces.h"
#include "physics/collision_bsp.h"
#include "physics/collision_bsp_definitions.h"
#include "structures/structure_bsp_definitions.h"

/* ---------- constants */

enum
{
	_pathfinding_surface_walkable_bit = 6,
	_pathfinding_surface_breakable_bit = 7,
};

enum
{
	_collision_surface_breakable_bit = 3,
};

enum
{
	_path_test_pill_endpoint_near_wall_ok_bit = 0,
};

/* ---------- macros */

/* ---------- structures */

/* ---------- prototypes */

static byte path_pathfinding_surface(
	struct structure_bsp const *structure,
	long surface_index);
static boolean path_collision_edge_vertices_valid(
	struct collision_bsp const *bsp,
	long edge_index);

/* ---------- globals */

/* port: whether a map's malformed pathfinding surfaces or collision edges
were reported (once each) */
static boolean warned_about_pathfinding_surface_index;
static boolean warned_about_collision_edge_vertices;

static real const quantized_pathfinding_surface_widths[8] =
{
	0.2f, 0.4f, 0.6f, 0.8f, 1.0f, 1.5f, 2.0f, 4.0f
};

static real const quantized_pathfinding_surface_heights[8] =
{
	0.25f, 0.5f, 0.75f, 1.0f, 1.5f, 2.0f, 4.0f, 8.0f
};

/* ---------- public code */

boolean structure_test_ray2d(
	struct structure_bsp const *structure,
	boolean ignore_broken_surfaces,
	real_point2d const *point,
	long surface_index,
	real_vector2d const *direction,
	real distance,
	struct structure_test_ray2d_result *result)
{
	struct collision_surface_test_line2d_result surface_result;
	struct collision_bsp const *bsp;
	byte *breakable_surface_flags;
	long surface_step_count = 0;

	bsp = TAG_BLOCK_GET_ELEMENT(&structure->collision_bsp, 0, struct collision_bsp);
	breakable_surface_flags = breakable_surface_flags_get();

	collision_surface_test_line2d(
		bsp,
		surface_index,
		_z,
		TRUE,
		point,
		direction,
		&surface_result);

	/* port: the pathfinding surfaces' flags are read through
	path_pathfinding_surface, which keeps the read below for NONE and gives
	no walkable surface for any other index past them (a map's index) */
	/* (an open edge, with no surface beyond it, is in no shipped map) */
	while (TRUE)
	{
		long next_surface_index = NONE;

		if (distance < surface_result.enter_t &&
			path_pathfinding_surface(structure, surface_result.enter_surface_index))
		{
			boolean surface_passable = TRUE;

			if (!ignore_broken_surfaces &&
				TEST_FLAG(
					path_pathfinding_surface(structure, surface_result.enter_surface_index),
					_pathfinding_surface_breakable_bit))
			{
				struct collision_surface const *collision_surface;

				collision_surface = TAG_BLOCK_GET_ELEMENT(
					&bsp->surfaces,
					surface_result.enter_surface_index,
					struct collision_surface);
				match_assert(
					"c:\\halo\\SOURCE\\ai\\path_structure_bsp.c",
					105,
					TEST_FLAG(collision_surface->flags, _collision_surface_breakable_bit));
				surface_passable = BIT_VECTOR_TEST_FLAG(
					(long *)breakable_surface_flags,
					collision_surface->breakable_surface_index);
			}

			if (surface_passable)
			{
				next_surface_index = surface_result.enter_surface_index;
			}
		}

		if (next_surface_index == NONE &&
			distance > surface_result.exit_t &&
			path_pathfinding_surface(structure, surface_result.exit_surface_index))
		{
			boolean surface_passable = TRUE;

			if (!ignore_broken_surfaces &&
				TEST_FLAG(
					path_pathfinding_surface(structure, surface_result.exit_surface_index),
					_pathfinding_surface_breakable_bit))
			{
				struct collision_surface const *collision_surface;

				collision_surface = TAG_BLOCK_GET_ELEMENT(
					&bsp->surfaces,
					surface_result.exit_surface_index,
					struct collision_surface);
				match_assert(
					"c:\\halo\\SOURCE\\ai\\path_structure_bsp.c",
					126,
					TEST_FLAG(collision_surface->flags, _collision_surface_breakable_bit));
				surface_passable = BIT_VECTOR_TEST_FLAG(
					(long *)breakable_surface_flags,
					collision_surface->breakable_surface_index);
			}

			if (surface_passable)
			{
				next_surface_index = surface_result.exit_surface_index;
			}
		}

		if (next_surface_index == NONE)
		{
			break;
		}

		/* port: the ray crosses no more surfaces than the bsp has (each step
		depends on the surface alone, so a walk that ends never meets one
		twice; a map's surfaces that loop would walk forever): it stops at
		this surface's edge */
		surface_step_count++;
		if (surface_step_count > bsp->surfaces.count)
		{
			break;
		}

		surface_index = next_surface_index;
		collision_surface_test_line2d(
			bsp,
			surface_index,
			_z,
			TRUE,
			point,
			direction,
			&surface_result);
	}

	if (distance < surface_result.enter_t)
	{
		result->distance = surface_result.enter_t;
		result->surface_index = surface_index;
		result->edge_index = surface_result.enter_edge_index;
		return TRUE;
	}

	if (distance > surface_result.exit_t)
	{
		result->distance = surface_result.exit_t;
		result->surface_index = surface_index;
		result->edge_index = surface_result.exit_edge_index;
		return TRUE;
	}

	result->distance = distance;
	result->surface_index = surface_index;
	result->edge_index = NONE;

	return FALSE;
}

boolean structure_surfaces_are_equivalent(
	struct structure_bsp const *structure,
	real_point2d const *destination_point,
	long destination_surface_index,
	long test_surface_index)
{
	struct collision_bsp const *bsp;
	real_point3d destination_point3d;
	real_point3d test_point3d;
	boolean result;

	bsp = TAG_BLOCK_GET_ELEMENT(&structure->collision_bsp, 0, struct collision_bsp);
	result = FALSE;

	if (destination_surface_index != NONE && test_surface_index != NONE)
	{
		collision_surface_project_point2d(
			bsp,
			destination_surface_index,
			_z,
			TRUE,
			destination_point,
			&destination_point3d);
		collision_surface_project_point2d(
			bsp,
			test_surface_index,
			_z,
			TRUE,
			destination_point,
			&test_point3d);
		result = fabs(destination_point3d.z - test_point3d.z) < 0.05f;
	}

	return result;
}

boolean structure_test_line2d(
	struct structure_bsp const *structure,
	boolean ignore_broken_surfaces,
	real_point2d const *p0,
	long p0_surface_index,
	real_point2d const *p1,
	long p1_surface_index,
	struct path_collision_result *result)
{
	struct collision_bsp const *bsp = TAG_BLOCK_GET_ELEMENT(&structure->collision_bsp, 0, struct collision_bsp);
	long const *breakable_surface_flags = (long const *)breakable_surface_flags_get();
	long surface_index = p0_surface_index;
	boolean recursed = FALSE;
	real_vector2d p0p1;
	long surface_step_count = 0;

	match_assert("c:\\halo\\SOURCE\\ai\\path_structure_bsp.c", 217, result);

	vector_from_points2d(p0, p1, &p0p1);

	while (TRUE)
	{
		struct collision_surface const *surface;
		long edge_index;
		real_point3d point_in_surface = *global_origin3d;
		short edge_count = 0;
		boolean crossed_any = FALSE;
		boolean reached_target = FALSE;

		/* port: the line crosses no more surfaces than the bsp has, twice
		over for the one restart below (each step depends on the surface
		alone, so a walk that ends never meets one twice; a map's surfaces
		that loop would walk forever): past that it is blocked, as when it
		can't get back to p0. So is it at a surface that is not the bsp's (a
		map's index across an edge) */
		surface_step_count++;
		if (surface_step_count > 2 * bsp->surfaces.count ||
			!collision_bsp_valid_surface_index(bsp, surface_index))
		{
			collision_surface_project_point2d(
				bsp,
				p0_surface_index,
				_z,
				TRUE,
				p0,
				&result->point);
			result->surface_index = NONE;
			result->edge_index = NONE;
			result->collision = TRUE;
			result->t = 0.0f;
			return TRUE;
		}
		surface = TAG_BLOCK_GET_ELEMENT(&bsp->surfaces, surface_index, struct collision_surface);
		edge_index = surface->first_edge_index;

		while (TRUE)
		{
			struct collision_edge const *edge;
			boolean on_right_side;
			struct collision_vertex const *vertex0;
			struct collision_vertex const *vertex1;
			real_vector2d e0e1;
			real_vector2d e0p1;
			real_vector2d p0e0;
			real_vector2d p0e1;

			/* port: a surface's edges ring as
			collision_surface_edge_ring_continues says (within
			MAXIMUM_EDGES_PER_COLLISION_SURFACE of the bsp's edges), with
			vertices that are the bsp's (a map's indices; the retail rings
			all close within 3 to 8 edges): a ring that doesn't blocks it,
			as when it can't get back to p0 */
			if (!collision_surface_edge_ring_continues(bsp, edge_index, edge_count) ||
				!path_collision_edge_vertices_valid(bsp, edge_index))
			{
				collision_surface_project_point2d(
					bsp,
					p0_surface_index,
					_z,
					TRUE,
					p0,
					&result->point);
				result->surface_index = NONE;
				result->edge_index = NONE;
				result->collision = TRUE;
				result->t = 0.0f;
				return TRUE;
			}
			edge = TAG_BLOCK_GET_ELEMENT(&bsp->edges, edge_index, struct collision_edge);
			on_right_side = surface_index == edge->surface_indices[1];
			vertex0 = TAG_BLOCK_GET_ELEMENT(
				&bsp->vertices,
				edge->vertex_indices[!on_right_side],
				struct collision_vertex);
			vertex1 = TAG_BLOCK_GET_ELEMENT(
				&bsp->vertices,
				edge->vertex_indices[on_right_side],
				struct collision_vertex);

			vector_from_points2d((real_point2d const *)&vertex0->point, (real_point2d const *)&vertex1->point, &e0e1);
			vector_from_points2d((real_point2d const *)&vertex0->point, p1, &e0p1);
			vector_from_points2d(p0, (real_point2d const *)&vertex0->point, &p0e0);
			vector_from_points2d(p0, (real_point2d const *)&vertex1->point, &p0e1);

			if (edge->surface_indices[!on_right_side] == p1_surface_index)
			{
				reached_target = TRUE;
			}

			point_in_surface.x += vertex0->point.x;
			point_in_surface.y += vertex0->point.y;
			point_in_surface.z += vertex0->point.z;
			edge_count++;

			if (cross_product2d(&e0e1, &e0p1) > 0.0f)
			{
				crossed_any = TRUE;
				if (cross_product2d(&p0p1, &p0e0) > 0.0f &&
					cross_product2d(&p0e1, &p0p1) > 0.0f)
				{
					/* (an open edge, with no surface beyond it, is in no shipped map) */
					long next_surface_index = edge->surface_indices[!on_right_side];
					/* port: (path_pathfinding_surface: a map's index past
					the pathfinding surfaces is no walkable one) */
					byte next_pathfinding_surface = path_pathfinding_surface(
						structure,
						next_surface_index);
					boolean passable = TEST_FLAG(
						next_pathfinding_surface,
						_pathfinding_surface_walkable_bit);

					if (!ignore_broken_surfaces &&
						passable &&
						TEST_FLAG(
							next_pathfinding_surface,
							_pathfinding_surface_breakable_bit))
					{
						struct collision_surface const *collision_surface = TAG_BLOCK_GET_ELEMENT(
							&bsp->surfaces,
							next_surface_index,
							struct collision_surface);

						match_assert(
							"c:\\halo\\SOURCE\\ai\\path_structure_bsp.c",
							274,
							TEST_FLAG(collision_surface->flags, _collision_surface_breakable_bit));
						passable = BIT_VECTOR_TEST_FLAG(
							breakable_surface_flags,
							collision_surface->breakable_surface_index);
					}

					if (passable)
					{
						surface_index = next_surface_index;
						break;
					}
					else
					{
						real t = (cross_product2d(&e0e1, &p0e0) - magnitude2d(&e0e1) * (1.0f / 128.0f)) /
							cross_product2d(&e0e1, &p0p1);
						real_point2d p2d;

						point_from_line2d(p0, &p0p1, t, &p2d);
						collision_surface_project_point2d(
							bsp,
							surface_index,
							_z,
							TRUE,
							&p2d,
							&result->point);
						result->surface_index = surface_index;
						result->edge_index = edge_index;
						result->collision = TRUE;
						result->t = t;
						return TRUE;
					}
				}
			}

			edge_index = edge->edge_indices[on_right_side];
			if (edge_index == surface->first_edge_index)
			{
				if (crossed_any)
				{
					struct path_collision_result p0_result;

					match_assert(
						"c:\\halo\\SOURCE\\ai\\path_structure_bsp.c",
						316,
						surface_index>=0 && surface_index<structure->pathfinding_surfaces.count);
					point_in_surface.x /= edge_count;
					point_in_surface.y /= edge_count;

					if (!recursed &&
						path_pathfinding_surface(structure, surface_index) &&
						!structure_test_line2d(
							structure,
							ignore_broken_surfaces,
							(real_point2d const *)&point_in_surface,
							surface_index,
							p0,
							NONE,
							&p0_result))
					{
						recursed = TRUE;
						surface_index = p0_result.surface_index;
						break;
					}
					else
					{
						collision_surface_project_point2d(
							bsp,
							p0_surface_index,
							_z,
							TRUE,
							p0,
							&result->point);
						result->surface_index = NONE;
						result->edge_index = NONE;
						result->collision = TRUE;
						result->t = 0.0f;
						return TRUE;
					}
				}
				else
				{
					if (surface_index == p1_surface_index || reached_target || p1_surface_index == NONE)
					{
						collision_surface_project_point2d(
							bsp,
							surface_index,
							_z,
							TRUE,
							p1,
							&result->point);
						result->surface_index = surface_index;
						result->edge_index = NONE;
						result->collision = FALSE;
						result->t = 1.0f;
						return FALSE;
					}
					else
					{
						collision_surface_project_point2d(
							bsp,
							p0_surface_index,
							_z,
							TRUE,
							p0,
							&result->point);
						result->surface_index = NONE;
						result->edge_index = NONE;
						result->collision = TRUE;
						result->t = 0.0f;
						return TRUE;
					}
				}
			}
		}
	}
}

boolean clip_empty_interval_by_solid_interval(
	real *empty_t0,
	real *empty_t1,
	real solid_t0,
	real solid_t1)
{
	real clipped_solid_t0;
	real clipped_solid_t1;

	if (*empty_t0 > solid_t1)
		clipped_solid_t1 = *empty_t0;
	else
		clipped_solid_t1 = solid_t1;
	solid_t1 = clipped_solid_t1;

	clipped_solid_t0 = MIN(solid_t0, *empty_t1);

	if (*empty_t1 - solid_t1 > clipped_solid_t0 - *empty_t0)
		*empty_t0 = solid_t1;
	else
		*empty_t1 = clipped_solid_t0;

	return *empty_t0 > *empty_t1;
}

long structure_surface_index_from_point(
	struct structure_bsp const *structure,
	boolean ignore_broken_surfaces,
	real_point2d const *known_point,
	long known_surface_index,
	real_point2d *point)
{
	struct path_collision_result result;

	if (known_surface_index != NONE)
	{
		structure_test_line2d(
			structure,
			ignore_broken_surfaces,
			known_point,
			known_surface_index,
			point,
			NONE,
			&result);

		point->x = result.point.x;
		point->y = result.point.y;

		if (result.surface_index == NONE)
			return known_surface_index;

		return result.surface_index;
	}

	return NONE;
}

boolean structure_test_pill2d(
	struct structure_bsp const *structure,
	boolean ignore_broken_surfaces,
	real_point2d const *p0,
	long p0_surface_index,
	real_point2d const *p1,
	long p1_surface_index,
	real radius,
	unsigned long flags,
	struct path_collision_result *result)
{
	boolean collision = FALSE;
	real_vector2d direction;
	real_vector2d perpendicular;

	vector_from_points2d(p0, p1, &direction);
	set_real_vector2d(&perpendicular, -direction.j, direction.i);
	if (normalize2d(&perpendicular) > 0.0f)
	{
		real_point2d left_p0;
		real_point2d left_p1;
		real_point2d right_p0;
		real_point2d right_p1;
		long left_p0_surface_index;
		long left_p1_surface_index;
		long right_p0_surface_index;
		long right_p1_surface_index;
		struct path_collision_result left_result;
		struct path_collision_result right_result;
		struct path_collision_result endpoint_result;
		struct path_collision_result *best_result;

		left_p0_surface_index = structure_surface_index_from_point(
			structure,
			ignore_broken_surfaces,
			p0,
			p0_surface_index,
			point_from_line2d(p0, &perpendicular, radius, &left_p0));
		left_p1_surface_index = structure_surface_index_from_point(
			structure,
			ignore_broken_surfaces,
			p1,
			p1_surface_index,
			point_from_line2d(p1, &perpendicular, radius, &left_p1));
		right_p0_surface_index = structure_surface_index_from_point(
			structure,
			ignore_broken_surfaces,
			p0,
			p0_surface_index,
			point_from_line2d(p0, &perpendicular, -radius, &right_p0));
		right_p1_surface_index = structure_surface_index_from_point(
			structure,
			ignore_broken_surfaces,
			p1,
			p1_surface_index,
			point_from_line2d(p1, &perpendicular, -radius, &right_p1));

		if (left_p0_surface_index == NONE)
		{
			left_result.collision = FALSE;
		}
		else if (structure_test_line2d(
				structure,
				ignore_broken_surfaces,
				&left_p0,
				left_p0_surface_index,
				&left_p1,
				left_p1_surface_index,
				&left_result) &&
			left_result.surface_index != NONE &&
			!TEST_FLAG(flags, _path_test_pill_endpoint_near_wall_ok_bit) &&
			!structure_test_line2d(
				structure,
				ignore_broken_surfaces,
				(real_point2d const *)&left_result.point,
				left_result.surface_index,
				p1,
				p1_surface_index,
				&endpoint_result))
		{
			left_result.collision = FALSE;
		}

		if (right_p0_surface_index == NONE)
		{
			right_result.collision = FALSE;
		}
		else if (structure_test_line2d(
				structure,
				ignore_broken_surfaces,
				&right_p0,
				right_p0_surface_index,
				&right_p1,
				right_p1_surface_index,
				&right_result) &&
			right_result.surface_index != NONE &&
			!TEST_FLAG(flags, _path_test_pill_endpoint_near_wall_ok_bit) &&
			!structure_test_line2d(
				structure,
				ignore_broken_surfaces,
				(real_point2d const *)&right_result.point,
				right_result.surface_index,
				p1,
				p1_surface_index,
				&endpoint_result))
		{
			right_result.collision = FALSE;
		}

		if (left_result.collision && right_result.collision)
		{
			if (left_result.t < right_result.t)
			{
				best_result = &left_result;
			}
			else
			{
				best_result = &right_result;
			}
		}
		else if (left_result.collision)
		{
			best_result = &left_result;
		}
		else if (right_result.collision)
		{
			best_result = &right_result;
		}
		else
		{
			best_result = NULL;
		}

		/* (as the original game, kept: a side whose first surface is NONE leaves the rest of its
		result unset) */
		if (!best_result ||
			distance_squared2d((real_point2d const *)&best_result->point, p1) < radius * radius)
		{
			*result = left_result;
		}
		else
		{
			*result = *best_result;
			collision = TRUE;
		}
	}

	return collision;
}

/* ---------- private code */

/* port: a surface's pathfinding flags, for a surface index from the map.
NONE reads the byte before the array, as January does (the BUG notes
above); any other index past the pathfinding surfaces has none (0: not
walkable). The retail bsps have as many pathfinding surfaces as surfaces,
and every edge's surfaces are theirs */
static byte path_pathfinding_surface(
	struct structure_bsp const *structure,
	long surface_index)
{
	byte const *pathfinding_surfaces = structure->pathfinding_surfaces.address;

	if ((surface_index == NONE && structure->pathfinding_surfaces.count > 0) ||
		VALID_INDEX(surface_index, structure->pathfinding_surfaces.count))
	{
		return pathfinding_surfaces[surface_index];
	}
	/* (NONE of a bsp with no pathfinding surfaces has none: there is no
	array to read before) */
	if (surface_index == NONE)
		return 0;

	if (!warned_about_pathfinding_surface_index)
	{
		error(_error_silent, "pathfinding surface #%ld is not one of the bsp's %ld",
			surface_index,
			structure->pathfinding_surfaces.count);
		warned_about_pathfinding_surface_index = TRUE;
	}

	return 0;
}

/* port: whether an edge's vertices (from the map) are the bsp's (the
retail ones all are) */
static boolean path_collision_edge_vertices_valid(
	struct collision_bsp const *bsp,
	long edge_index)
{
	struct collision_edge const *edge = TAG_BLOCK_GET_ELEMENT(
		&bsp->edges,
		edge_index,
		struct collision_edge);

	if (VALID_INDEX(edge->vertex_indices[0], bsp->vertices.count) &&
		VALID_INDEX(edge->vertex_indices[1], bsp->vertices.count))
	{
		return TRUE;
	}

	if (!warned_about_collision_edge_vertices)
	{
		error(_error_silent, "collision edge #%ld's vertices are not the bsp's", edge_index);
		warned_about_collision_edge_vertices = TRUE;
	}

	return FALSE;
}