GTG Safe Zone

Points to polygon

The zone has no model and no collider. Its shape is a list of positions that somebody placed, and everything else – protection, alarm, ring – is a question asked of that list.

Corner points are plain entities

A corner point is an entity that does nothing but exist. It adds itself to a static list when it initialises and removes itself when it is deleted. The zone later asks that list for the corners that belong to it. Because the points are ordinary world entities, they can be placed in the World Editor, or by a Game Master while the session runs, and moved afterwards.

[EntityEditorProps(category: "GameScripted/MyAD", description: "Corner point of a zone")]
class MyAD_ZonePointClass : GenericEntityClass
{
}

class MyAD_ZonePoint : GenericEntity
{
	[Attribute("Zone1", desc: "Name of the zone this corner belongs to")]
	protected string m_sZoneId;

	protected static ref array<MyAD_ZonePoint> s_aPoints = {};

	static array<MyAD_ZonePoint> GetAll() { return s_aPoints; }
	string GetZoneId() { return m_sZoneId; }

	void MyAD_ZonePoint(IEntitySource src, IEntity parent)
	{
		SetEventMask(EntityEvent.INIT);
	}

	override protected void EOnInit(IEntity owner)
	{
		if (!s_aPoints.Contains(this))
			s_aPoints.Insert(this);
	}

	void ~MyAD_ZonePoint()
	{
		if (s_aPoints)
			s_aPoints.RemoveItem(this);
	}
}

Which points belong to which zone

Master and points share a zone name. All points with the master's name form its outline. Compare the names without regard to case, and mind what ToLower() does: it changes the string you call it on, in place. Copy first.

// Collect the corners of one zone as world positions.
static array<vector> CollectOutline(string zoneId)
{
	string wanted = zoneId;
	wanted.ToLower();				// ToLower() changes the string itself - so only ever on a copy

	array<vector> outline = {};
	foreach (MyAD_ZonePoint point : MyAD_ZonePoint.GetAll())
	{
		string id = point.GetZoneId();	// also a copy
		id.ToLower();
		if (id != wanted)
			continue;

		outline.Insert(MyAD_Zone.WorldPos(point));
	}

	return outline;
}

The position comes from the world transform, not from GetOrigin(). For an entity without a parent they are the same. For anything that sits inside a vehicle, GetOrigin() is relative to that vehicle – a mistake you only notice when a player in a turret is treated as standing at the world origin.

static vector WorldPos(notnull IEntity entity)
{
	vector mat[4];
	entity.GetWorldTransform(mat);
	return mat[3];		// the translation row
}

Build one step later

The points register themselves in their own EOnInit, and the engine does not promise an order between entities. A master that builds its outline in its own EOnInit sees none of its points, or some of them, differently from one start to the next. Hand the work to the call queue and it runs when everything exists.

override protected void EOnInit(IEntity owner)
{
	if (!s_aZones.Contains(this))
		s_aZones.Insert(this);

	GetGame().GetCallqueue().CallLater(DeferredStart, 0, false);	// one step later: the points exist by then
}

protected void DeferredStart()
{
	if (!Replication.IsServer())
		return;						// only the server builds the outline - see "Alarm and replication"

	m_aOutline = MyAD_ZonePoint.CollectOutline(m_sZoneId);
	MyAD_Geometry.OrderByAngleXZ(m_aOutline);
}

Inside or outside: a ray

The usual shortcut – a position is inside when it lies on the same side of every edge – is correct only for convex shapes. A notch around a hillside, a wall to follow, a corridor left open on purpose: all of those are concave, and the shortcut gets them wrong. Ray casting does not care. Send a ray from the position in one direction and count how many edges it crosses. An odd number means inside.

class MyAD_Geometry
{
	// Top view: X and Z. Y is height and is a separate question.
	static bool IsPointInPolygonXZ(vector p, notnull array<vector> poly)
	{
		int count = poly.Count();
		if (count < 3)
			return false;

		bool inside = false;
		int j = count - 1;				// the previous corner; starting with (last, first) closes the polygon

		for (int i = 0; i < count; i++)
		{
			float zi = poly[i][2];
			float zj = poly[j][2];

			// Does the edge j->i cross the horizontal line z = p.z?
			// For a horizontal edge both sides of the comparison are equal, so it is skipped -
			// and that is exactly what makes the division below safe.
			if ((zi > p[2]) != (zj > p[2]))
			{
				float t = (p[2] - zi) / (zj - zi);
				float xCross = poly[i][0] + t * (poly[j][0] - poly[i][0]);

				if (p[0] < xCross)		// the ray runs towards -X
					inside = !inside;
			}

			j = i;
		}

		return inside;
	}
}

Height is its own condition

The polygon says nothing about height, and it should not. Floor and ceiling are two offsets from the average height of the placed points. Without a ceiling, an aircraft high above the zone would be protected as well, and could fire from it.

protected bool IsHeightInRange(vector pos)
{
	return pos[1] >= m_fBaseHeight + m_fFloorOffset		// e.g. -50
		&& pos[1] <= m_fBaseHeight + m_fCeilingOffset;	// e.g. +150
}

bool IsInside(vector pos)
{
	if (!m_bValid || !m_bEnabled)
		return false;

	return IsHeightInRange(pos) && MyAD_Geometry.IsPointInPolygonXZ(pos, m_aOutline);
}

A bounding sphere for the questions the world answers

The world can be asked for entities within a sphere. The zone needs one that holds the whole outline: the centre of the bounding box and the distance to the farthest corner. It does not have to be the smallest sphere – it is only a pre-selection, and every hit is afterwards tested exactly against the polygon. The same function gives the reference height for floor and ceiling: the average height of the corners.

static void ComputeBounds(notnull array<vector> poly, out vector centre, out float radius, out float baseHeight)
{
	float minX = poly[0][0];
	float maxX = minX;
	float minZ = poly[0][2];
	float maxZ = minZ;
	float sumY = 0;

	foreach (vector p : poly)
	{
		minX = Math.Min(minX, p[0]);
		maxX = Math.Max(maxX, p[0]);
		minZ = Math.Min(minZ, p[2]);
		maxZ = Math.Max(maxZ, p[2]);
		sumY += p[1];
	}

	baseHeight = sumY / poly.Count();
	centre = Vector((minX + maxX) * 0.5, baseHeight, (minZ + maxZ) * 0.5);

	radius = 0;
	foreach (vector q : poly)
	{
		float dx = q[0] - centre[0];
		float dz = q[2] - centre[2];
		radius = Math.Max(radius, Math.Sqrt(dx * dx + dz * dz));
	}
}

Putting the points in order

An outline is not a set of points but a path: the order decides which corner connects to which. The first version used the order in which the points had been created. That is not a property of the shape. It is the order in which their EOnInit happened to fire – the order of placing on the server, the order of delivery on a client, and anything at all after a restart with persistence.

A path that follows from the positions alone has none of those problems: sort the points by their angle around the centre of all of them, once around like a clock hand. Each edge then stays within its own wedge, and two wedges never overlap, so the outline cannot cross itself, however the points were placed.

static void OrderByAngleXZ(notnull array<vector> points)
{
	int count = points.Count();
	if (count < 3)
		return;

	float centreX = 0;
	float centreZ = 0;
	for (int k = 0; k < count; k++)
	{
		centreX += points[k][0];
		centreZ += points[k][2];
	}
	centreX /= count;
	centreZ /= count;

	// Work out each angle once - Atan2 costs more than the comparison that follows.
	array<float> angles = {};
	for (int m = 0; m < count; m++)
		angles.Insert(Math.Atan2(points[m][2] - centreZ, points[m][0] - centreX));

	// Insertion sort: for a handful of corners it beats anything fancier,
	// and both arrays move in step, so they cannot drift apart.
	for (int i = 1; i < count; i++)
	{
		vector point = points[i];
		float angle = angles[i];

		int j = i - 1;
		while (j >= 0 && angles[j] > angle)
		{
			points[j + 1] = points[j];
			angles[j + 1] = angles[j];
			j--;
		}

		points[j + 1] = point;
		angles[j + 1] = angle;
	}
}