Skip to content

Zero Hour rebuilt from EA's source: x64, Direct3D 11, VS2022/CMake, ~60 original bugs fixed, an AI that builds a base. Bring your own game.

40.2 KB
Raw Blame
// The ground a defence can hit, worked out with the logic's own tests and handed to the renderer
// as a signed distance field (ReachOverlay.h).  Client side: it reads the logic and writes nothing
// back, and it draws no logic random number.  ReachOverlay_prove is the check that the picture
// does not lie; a scenario's reachproof line runs it.
// Distributed under the repository's GPL-3.0 terms; see LICENSE.md.

#include "PreRTS.h"	// This must go first in EVERY cpp file int the GameEngine

#include "GameClient/ReachOverlay.h"

#include "Common/GlobalData.h"
#include "Common/LogicThread.h"
#include "Common/Player.h"
#include "Common/PlayerList.h"
#include "Common/ThingFactory.h"
#include "Common/ThingTemplate.h"
#include "GameClient/Drawable.h"
#include "GameClient/GameClient.h"
#include "GameClient/InGameUI.h"
#include "GameClient/PlayerColorScheme.h"
#include "GameLogic/AI.h"
#include "GameLogic/AIPathfind.h"
#include "GameLogic/GameLogic.h"
#include "GameLogic/Module/AIUpdate.h"
#include "GameLogic/Object.h"
#include "GameLogic/PartitionManager.h"
#include "GameLogic/TerrainLogic.h"
#include "GameLogic/Weapon.h"
#include "GameLogic/WeaponSet.h"

#include <chrono>
#include <map>
#include <random>

//-------------------------------------------------------------------------------------------------
// What is shown, and why it can be trusted.
//
// A ground cell is lit for a defence only if every test the logic puts an idle defence through
// before it fires at a ground target there passes, asked of the same functions with the defence's
// own Object:
//
//   - getNextMoodTarget's search: the defence's adjusted vision range (TheAI's, with the mood and
//     owner factors), stretched by the high ground the way PartitionFilterElevatedReach stretches it;
//   - its line of sight, for a defence the INI marks ATTACK_NEEDS_LINE_OF_SIGHT: the terrain line
//     from the top of the defence to the top of the target (isClearLineOfSightTerrain), and the
//     structure walk of Pathfinder::isAttackViewBlockedByObstacle;
//   - the fog: the target's cell has to be clear for the defence's player (PartitionFilterFreeOfFog);
//   - the weapon: the set's chooser (WeaponSet::chooseBestWeaponForTarget) may pick any slot whose
//     AutoChooseSources lets an AI-picked target choose it and that hits ground, and the turret fires
//     only once the chosen one is in range (TurretAIAimTurretState), so EVERY such slot has to have
//     the point inside Weapon::isWithinAttackRange.  A Patriot's ground missile qualifies; its 450
//     assist missile (AutoChooseSources NONE, fired only when another Patriot asks) and its anti-air
//     missile do not, so the Patriot shows the ground it hits on its own.  Air targets are not shown;
//   - a pitch band (the Fire Base's howitzer): only the ground within the height Weapon::isWithinTargetPitch
//     waves through whatever the band.
//
// The target is the worst one of its kind, test by test: a range is measured to its centre (a wider
// target is reached sooner), a minimum range to the edge of the widest ground unit the game can build,
// and a sight line to the top of the lowest one.  A cell under a building or a bridge deck, where no
// ground unit stands, is left out.
//
// The tests are taken on a grid, a quarter of a pathfind cell apart, and a grid point is lit only if
// it and its eight neighbours all pass.  The renderer paints where the field, taken bilinearly, is
// above nought, which needs one lit corner (shadeField smooths the field but holds every unlit point
// below nought), so every painted spot lies in a grid cell whose four corners all passed.
// ReachOverlay_prove measures what is left: points between the grid points.
//-------------------------------------------------------------------------------------------------

static const Real LIVE_STEP = PATHFIND_CELL_SIZE_F * 0.25f;		///< a standing defence's grid
static const Real GHOST_STEP = PATHFIND_CELL_SIZE_F * 0.5f;		///< the placement cursor's, worked out as it moves
static const Real DISTANCE_LIMIT = 16.0f;											///< the field is clamped to this either side
static const UnsignedInt FOG_REFRESH_FRAMES = 15;							///< client frames between two looks at the fog
static const UnsignedInt FORGET_FRAMES = 300;									///< a field not wanted this long is dropped
static const Real BUILD_BUDGET_MS = 4.0f;											///< grids worked out in one frame, past the first

//-------------------------------------------------------------------------------------------------
/** The worst ground target the game can field: the lowest top and the widest body of every unit a
	* player can build that drives or walks. */
//-------------------------------------------------------------------------------------------------
struct GroundProbe
{
	Real lowestTop;
	Real widestRadius;
};

static GroundProbe theProbe = { 0.0f, 0.0f };
static const ThingTemplate *theProbeFrom = NULL;

static const GroundProbe &groundProbe( void )
{
	const ThingTemplate *first = TheThingFactory ? TheThingFactory->firstTemplate() : NULL;
	if( first == theProbeFrom )
		return theProbe;
	theProbeFrom = first;

	theProbe.lowestTop = FLT_MAX;
	theProbe.widestRadius = 0.0f;
	for( const ThingTemplate *tmpl = first; tmpl; tmpl = tmpl->friend_getNextTemplate() )
	{
		if( !tmpl->isKindOf( KINDOF_VEHICLE ) && !tmpl->isKindOf( KINDOF_INFANTRY ) )
			continue;
		// a player's: it costs something.  Ships, trains and film props cost nothing
		// and something to see on the ground: an angry mob's nexus is the mob's invisible one-unit-high
		// leader, and the mob itself is what gets shot
		if( tmpl->isKindOf( KINDOF_AIRCRAFT ) || tmpl->isKindOf( KINDOF_PROJECTILE ) || tmpl->isKindOf( KINDOF_MOB_NEXUS )
				|| tmpl->getBuildable() != BSTATUS_YES || tmpl->friend_getBuildCost() <= 0 )
			continue;
		// no Geometry of its own (ThingTemplate's default, a sphere of one): it never stands on the field
		// as itself, the way a Technical comes out as one of its chassis
		const GeometryInfo &geom = tmpl->getTemplateGeometryInfo();
		if( geom.getGeomType() == GEOMETRY_SPHERE && geom.getMajorRadius() == 1.0f && geom.getMaxHeightAbovePosition() <= 1.0f )
			continue;
		theProbe.lowestTop = min( theProbe.lowestTop, geom.getMaxHeightAbovePosition() );
		theProbe.widestRadius = max( theProbe.widestRadius, geom.getBoundingCircleRadius() );
	}
	if( theProbe.lowestTop == FLT_MAX )
		theProbe.lowestTop = 0.0f;
	theProbe.lowestTop = max( theProbe.lowestTop, 0.0f );
	DEBUG_LOG(( "REACHOVERLAY: ground targets judged by a top %.2f high and a body %.2f wide\n",
		theProbe.lowestTop, theProbe.widestRadius ));
	return theProbe;
}

//-------------------------------------------------------------------------------------------------
/** A defence as the tests below see it: a standing one through its Object, or one on the
	* placement cursor through its template. */
//-------------------------------------------------------------------------------------------------
struct ReachGun
{
	const Weapon *live;						///< the standing defence's weapon, NULL for the cursor's
	const WeaponTemplate *tmpl;
};

struct ReachShooter
{
	const Object *obj;						///< NULL on the placement cursor
	const ThingTemplate *tmpl;
	Coord3D center;
	Real radius;
	Real eyeZ;
	Real acquireRange;						///< getNextMoodTarget's rangeToFindWithin before the high ground
	Bool lineOfSight;
	Int playerIndex;
	const Player *owner;
	std::vector< ReachGun > guns;
	Real reachBound;							///< nothing further than this from the centre passes
	ObjectID standingIn;					///< the cursor's twin in the proof stands in this building's cells
};

/// a slot the weapon set's chooser can pick for a ground target the defence found itself
static Bool picksGround( UnsignedInt sources, Int antiMask )
{
	if( ( antiMask & WEAPON_ANTI_GROUND ) == 0 )
		return FALSE;
	return ( sources & ( 1 << CMD_FROM_AI ) ) != 0 || ( sources & CMD_DEFAULT_SWITCH_WEAPON ) != 0;
}

/// a weapon that refuses targets outside a pitch band, the Fire Base's howitzer (-15 to 15 degrees)
static Bool pitchLimited( const WeaponTemplate *wt )
{
	return wt->getMinTargetPitch() > -PI || wt->getMaxTargetPitch() < PI;
}

/// Weapon::isWithinTargetPitch lets anything through whose height is within this of the shooter's,
/// whatever the band; past it the answer turns on the target's own shape, so the overlay stops there
static const Real PITCH_FREE_HEIGHT = 10.0f;

static void boundShooter( ReachShooter &s, const WeaponBonus *bonusless )
{
	Real bound = s.acquireRange + Weapon_elevationRangeBonus( s.acquireRange, FLT_MAX );
	for( size_t g = 0; g < s.guns.size(); ++g )
	{
		const Real range = s.guns[ g ].live ? s.guns[ g ].live->getAttackRange( s.obj ) : s.guns[ g ].tmpl->getAttackRange( *bonusless );
		bound = min( bound, range + Weapon_elevationRangeBonus( range, FLT_MAX ) );
	}
	s.reachBound = bound + s.radius;
}

static const char *theRefusal = NULL;		///< why liveShooter last said no, for the proof's log

static Bool refuse( const char *why )
{
	theRefusal = why;
	return FALSE;
}

static Bool liveShooter( const Object *obj, ReachShooter &s )
{
	if( obj == NULL || obj->isEffectivelyDead() || !obj->isKindOf( KINDOF_STRUCTURE ) )
		return refuse( "not a standing structure" );
	if( obj->testStatus( OBJECT_STATUS_UNDER_CONSTRUCTION ) || obj->testStatus( OBJECT_STATUS_SOLD ) )
		return refuse( "under construction or sold" );
	// unpowered, hacked, EMP'd: it fires at nothing, so it shows nothing
	if( obj->isDisabled() || !obj->isAbleToAttack() )
		return refuse( "disabled or unable to attack" );
	// a jammed defence's sight shrinks on a clock the drawing does not follow.  A Stinger Site's
	// shots come from soldiers who walk about it, and it has no gun of its own to show; a Fire Base
	// carries the same SPAWNS_ARE_THE_WEAPONS kind and its own howitzer, which is what is shown
	if( obj->getContainedBy() != NULL || obj->isSightJammed() )
		return refuse( "contained or jammed" );

	const AIUpdateInterface *ai = obj->getAI();
	if( ai == NULL || !ai->canAutoAcquire() )
		return refuse( "no idle auto-acquire" );
	if( ai->getMoodMatrixActionAdjustment( MM_Action_Idle ) & MAA_Affect_Range_IgnoreAll )
		return refuse( "mood ignores all" );
	if( obj->testStatus( OBJECT_STATUS_STEALTHED ) && !ai->canAutoAcquireWhileStealthed() )
		return refuse( "stealthed" );

	s.guns.clear();
	if( obj->isCurWeaponLocked() )
	{
		const Weapon *w = obj->getCurrentWeapon();
		if( w && ( w->getAntiMask() & WEAPON_ANTI_GROUND ) )
		{
			ReachGun gun = { w, w->getTemplate() };
			s.guns.push_back( gun );
		}
	}
	else
	{
		for( Int slot = PRIMARY_WEAPON; slot < WEAPONSLOT_COUNT; ++slot )
		{
			const Weapon *w = obj->getWeaponInWeaponSlot( (WeaponSlotType)slot );
			if( w == NULL || !picksGround( obj->getWeaponInWeaponSlotCommandSourceMask( (WeaponSlotType)slot ), w->getAntiMask() ) )
				continue;
			ReachGun gun = { w, w->getTemplate() };
			s.guns.push_back( gun );
		}
	}
	if( s.guns.empty() )
		return refuse( "no gun an idle scan picks for the ground" );
	for( size_t g = 0; g < s.guns.size(); ++g )
	{
		if( s.guns[ g ].live->isContactWeapon() )
			return refuse( "contact weapon" );
	}

	s.obj = obj;
	s.tmpl = obj->getTemplate();
	s.center = *obj->getPosition();
	s.radius = obj->getGeometryInfo().getBoundingCircleRadius();
	s.eyeZ = s.center.z + obj->getGeometryInfo().getMaxHeightAbovePosition();
	s.acquireRange = TheAI->getAdjustedVisionRangeForObject( obj, AI_VISIONFACTOR_OWNERTYPE | AI_VISIONFACTOR_MOOD );
	if( s.tmpl->acquiresBeyondVision() )
		s.acquireRange = max( s.acquireRange, obj->getLargestWeaponRange() );
	s.lineOfSight = TheAI->getAiData()->m_attackUsesLineOfSight && obj->isKindOf( KINDOF_ATTACK_NEEDS_LINE_OF_SIGHT );
	s.owner = obj->getControllingPlayer();
	s.playerIndex = s.owner ? s.owner->getPlayerIndex() : 0;
	s.standingIn = INVALID_ID;
	boundShooter( s, NULL );
	return s.acquireRange > 0.0f;
}

/// the defence on the placement cursor, as it will stand there: its template's default weapon set,
/// no bonus, the sight a human player's turret gets (the cursor is always the local player's)
static Bool ghostShooter( const ThingTemplate *tmpl, Real x, Real y, const Player *owner, ReachShooter &s )
{
	if( tmpl == NULL || owner == NULL || !tmpl->isKindOf( KINDOF_STRUCTURE ) )
		return FALSE;
	const WeaponTemplateSet *set = tmpl->findWeaponTemplateSet( WeaponSetFlags() );
	if( set == NULL )
		return FALSE;

	s.guns.clear();
	Real longest = 0.0f;
	const WeaponBonus bonusless;
	for( Int slot = PRIMARY_WEAPON; slot < WEAPONSLOT_COUNT; ++slot )
	{
		const WeaponTemplate *wt = set->getNth( (WeaponSlotType)slot );
		if( wt == NULL )
			continue;
		longest = max( longest, wt->getAttackRange( bonusless ) );
		if( !picksGround( set->getNthCommandSourceMask( (WeaponSlotType)slot ), wt->getAntiMask() ) )
			continue;
		if( wt->isContactWeapon() )
			return FALSE;
		ReachGun gun = { NULL, wt };
		s.guns.push_back( gun );
	}
	if( s.guns.empty() )
		return FALSE;

	s.obj = NULL;
	s.tmpl = tmpl;
	s.center.x = x;
	s.center.y = y;
	s.center.z = TheTerrainLogic->getGroundHeight( x, y );
	s.radius = tmpl->getTemplateGeometryInfo().getBoundingCircleRadius();
	s.eyeZ = s.center.z + tmpl->getTemplateGeometryInfo().getMaxHeightAbovePosition();
	s.acquireRange = tmpl->friend_calcVisionRange() * TheAI->getAiData()->m_guardOuterModifierHuman;
	if( tmpl->acquiresBeyondVision() )
		s.acquireRange = max( s.acquireRange, longest );
	s.lineOfSight = TheAI->getAiData()->m_attackUsesLineOfSight && tmpl->isKindOf( KINDOF_ATTACK_NEEDS_LINE_OF_SIGHT );
	s.owner = owner;
	s.playerIndex = owner->getPlayerIndex();
	s.standingIn = INVALID_ID;
	boundShooter( s, &bonusless );
	return s.acquireRange > 0.0f;
}

/// where a ground unit at (x, y) stands: on the ground, or on the water over it
static Real standHeight( Real x, Real y )
{
	Real z = TheTerrainLogic->getGroundHeight( x, y );
	Real waterZ = 0.0f;
	if( TheTerrainLogic->isUnderwater( x, y, &waterZ ) )
		z = max( z, waterZ );
	return z;
}

/// what a grid point's tests said: out of the guns' reach (a range edge, drawn as a line), passed, or
/// in reach but blocked (a cliff, a building, the sight line, the fog: an edge that fades in)
enum { REACH_OUT = 0, REACH_PASS = 1, REACH_BLOCKED = 2 };

//-------------------------------------------------------------------------------------------------
/** Every test but the fog, for the worst ground target standing at (x, y). */
//-------------------------------------------------------------------------------------------------
static UnsignedByte hitsGroundAt( const ReachShooter &s, const GroundProbe &probe, Real x, Real y )
{
	const Real dx = x - s.center.x;
	const Real dy = y - s.center.y;
	if( dx * dx + dy * dy > s.reachBound * s.reachBound )
		return REACH_OUT;

	Coord3D at;
	at.set( x, y, standHeight( x, y ) );

	const PathfindCell *cell = TheAI->pathfinder()->getCell( LAYER_GROUND, &at );
	if( cell == NULL || cell->getType() == PathfindCell::CELL_OBSTACLE )
		return REACH_BLOCKED;
	if( TheTerrainLogic->findBridgeAt( &at ) != NULL )
		return REACH_BLOCKED;

	// FROM_BOUNDINGSPHERE_2D from the defence's edge to the target's middle
	Real distSqr;
	if( s.obj )
		distSqr = ThePartitionManager->getDistanceSquared( s.obj, &at, FROM_BOUNDINGSPHERE_2D );
	else
	{
		const Real d = sqrtf( dx * dx + dy * dy ) - s.radius;
		distSqr = d > 0.0f ? d * d : 0.0f;
	}

	// getNextMoodTarget's search and PartitionFilterElevatedReach
	const Real look = s.obj ? Weapon_elevatedRange( s.obj, s.acquireRange, at.z )
		: s.acquireRange + Weapon_elevationRangeBonus( s.acquireRange, s.center.z - at.z );
	if( distSqr > look * look )
		return REACH_OUT;

	// the widest target's edge is this much nearer than its middle (distCalcProc_BoundaryAndBoundary_2D)
	const Real edge = max( 0.0f, sqrtf( distSqr ) - probe.widestRadius );
	const WeaponBonus bonusless;
	for( size_t g = 0; g < s.guns.size(); ++g )
	{
		const ReachGun &gun = s.guns[ g ];
		if( gun.live )
		{
			if( !gun.live->isWithinAttackRange( s.obj, &at ) )
				return REACH_OUT;
		}
		else
		{
			const Real range = gun.tmpl->getAttackRange( bonusless );
			const Real reach = range + Weapon_elevationRangeBonus( range, s.center.z - at.z );
			const Real minimum = gun.tmpl->getMinimumAttackRange();
			if( distSqr > reach * reach || distSqr < minimum * minimum )
				return REACH_OUT;
		}
		const Real minimum = gun.tmpl->getMinimumAttackRange();
		if( minimum > 0.0f && edge * edge < minimum * minimum )
			return REACH_OUT;
		if( pitchLimited( gun.tmpl ) && fabs( at.z - s.center.z ) >= PITCH_FREE_HEIGHT )
			return REACH_BLOCKED;
	}

	if( s.lineOfSight )
	{
		Coord3D top = at;
		top.z += probe.lowestTop;
		if( s.obj )
		{
			if( !ThePartitionManager->isClearLineOfSightTerrain( s.obj, *s.obj->getPosition(), NULL, top ) )
				return REACH_BLOCKED;
			if( TheAI->pathfinder()->isAttackViewBlockedByObstacle( s.obj, *s.obj->getPosition(), NULL, at ) )
				return REACH_BLOCKED;
		}
		else
		{
			Coord3D eye = s.center;
			eye.z = s.eyeZ;
			if( !ThePartitionManager->isClearLineOfSightTerrain( NULL, eye, NULL, top ) )
				return REACH_BLOCKED;
			if( TheAI->pathfinder()->isGroundViewBlockedByObstacle( s.center, at, s.standingIn ) )
				return REACH_BLOCKED;
		}
	}
	return REACH_PASS;
}

//-------------------------------------------------------------------------------------------------
// One defence's field and the grid behind it.
//-------------------------------------------------------------------------------------------------
struct ReachEntry
{
	ReachOverlayField field;
	std::vector< UnsignedByte > geometry;		///< REACH_PASS where every test but the fog passed at this grid point
	UnsignedInt signature;
	UnsignedInt fogFrame;
	UnsignedInt lastWanted;
	Int playerIndex;
	Bool built;
	Bool regridded;		///< the grid moved or changed size since the last field, so the version must change
};

static UnsignedInt theVersion = 0;

static void layGrid( ReachOverlayField &field, const ReachShooter &s, Real step )
{
	field.step = step;
	field.originX = floorf( ( s.center.x - s.reachBound ) / step ) * step - step;
	field.originY = floorf( ( s.center.y - s.reachBound ) / step ) * step - step;
	field.width = (Int)ceilf( ( s.center.x + s.reachBound - field.originX ) / step ) + 2;
	field.height = (Int)ceilf( ( s.center.y + s.reachBound - field.originY ) / step ) + 2;
	field.distanceLimit = DISTANCE_LIMIT;
	field.color = clientPlayerColor( s.owner );
	field.opacity = 1.0f;
}

static void traceGeometry( ReachEntry &entry, const ReachShooter &s, Real step )
{
	layGrid( entry.field, s, step );
	const GroundProbe &probe = groundProbe();
	const Int w = entry.field.width;
	const Int h = entry.field.height;
	entry.geometry.assign( w * h, 0 );
	for( Int j = 0; j < h; ++j )
	{
		const Real y = entry.field.originY + j * step;
		for( Int i = 0; i < w; ++i )
			entry.geometry[ j * w + i ] = hitsGroundAt( s, probe, entry.field.originX + i * step, y );
	}

	// the bound allows for all the high ground a range can gain; cut the grid down to what passed,
	// two points of nothing round it, so the fog pass, the field and the texture stay small
	Int loI = w, hiI = -1, loJ = h, hiJ = -1;
	for( Int j = 0; j < h; ++j )
	{
		for( Int i = 0; i < w; ++i )
		{
			if( entry.geometry[ j * w + i ] != REACH_PASS )
				continue;
			loI = min( loI, i );
			hiI = max( hiI, i );
			loJ = min( loJ, j );
			hiJ = max( hiJ, j );
		}
	}
	if( hiI < 0 )
	{
		loI = loJ = 0;
		hiI = hiJ = 1;
	}
	loI = max( loI - 2, 0 );
	loJ = max( loJ - 2, 0 );
	hiI = min( hiI + 2, w - 1 );
	hiJ = min( hiJ + 2, h - 1 );
	const Int cw = hiI - loI + 1;
	const Int ch = hiJ - loJ + 1;
	std::vector< UnsignedByte > cropped( cw * ch );
	for( Int j = 0; j < ch; ++j )
		memcpy( &cropped[ j * cw ], &entry.geometry[ ( j + loJ ) * w + loI ], cw );
	entry.geometry.swap( cropped );
	entry.field.originX += loI * step;
	entry.field.originY += loJ * step;
	entry.field.width = cw;
	entry.field.height = ch;

	entry.playerIndex = s.playerIndex;
	entry.built = TRUE;
	entry.regridded = TRUE;
	entry.fogFrame = 0;
}

/// a separable Gaussian over the grid, sigma in grid steps; past the border the edge sample holds,
/// and the border is two points of nothing (traceGeometry's crop)
static void blurGrid( std::vector< Real > &v, Int w, Int h, Real sigma )
{
	const Int radius = (Int)ceilf( 2.5f * sigma );
	std::vector< Real > weight( radius + 1 );
	Real sum = 0.0f;
	for( Int r = 0; r <= radius; ++r )
	{
		weight[ r ] = expf( -0.5f * (Real)( r * r ) / ( sigma * sigma ) );
		sum += r == 0 ? weight[ r ] : 2.0f * weight[ r ];
	}
	for( Int r = 0; r <= radius; ++r )
		weight[ r ] /= sum;

	// one line of samples, stride apart, through a padded copy so the inner loop has no clamp
	std::vector< Real > line( max( w, h ) + 2 * radius );
	auto pass = [ & ]( Real *first, Int count, Int stride )
	{
		for( Int n = 0; n < count; ++n )
			line[ radius + n ] = first[ n * stride ];
		for( Int r = 0; r < radius; ++r )
		{
			line[ r ] = first[ 0 ];
			line[ radius + count + r ] = first[ ( count - 1 ) * stride ];
		}
		for( Int n = 0; n < count; ++n )
		{
			const Real *at = &line[ radius + n ];
			Real total = weight[ 0 ] * at[ 0 ];
			for( Int r = 1; r <= radius; ++r )
				total += weight[ r ] * ( at[ -r ] + at[ r ] );
			first[ n * stride ] = total;
		}
	};
	for( Int j = 0; j < h; ++j )
		pass( &v[ j * w ], w, 1 );
	for( Int i = 0; i < w; ++i )
		pass( &v[ i ], h, w );
}

static const Real SMOOTH_SIGMA = 4.0f;		///< world units the edge is smoothed over, at least a grid step
static const Real SMOOTH_MARGIN = 0.6f;		///< grid steps the smoothed edge is pulled in, past the steps' corners
static const Real UNLIT_HOLD = 0.05f;			///< grid steps an unlit point is held under nought whatever the blur says

//-------------------------------------------------------------------------------------------------
/** The fog on top of the geometry, then the erosion, then the signed distance (a chamfer walk, a
	* grid step straight and step root two across), smoothed.  Only the sign is load-bearing; the size
	* shapes the border the renderer draws.
	*
	* The lit points are the grid's own staircase, and so is a field taken straight from them: a range
	* ring drawn in steps of a grid point, a cliff's edge in steps of a pathfind cell.  The distance is
	* blurred, which lays the edge along the middle of the steps, and pulled in by a margin so it passes
	* inside their corners.  Whatever the blur did, an unlit point is then held below nought, so the
	* edge the renderer draws still lies only in grid cells with a lit corner, whose four corners all
	* passed: the area can shrink by the margin, never grow.
	*
	* The hardness is what the nearest failed point failed on, out of reach (a ring, hard) or blocked
	* (soft), blurred as the distance is so a ring meeting a cliff turns from line to fade smoothly. */
//-------------------------------------------------------------------------------------------------
static void shadeField( ReachEntry &entry )
{
	ReachOverlayField &field = entry.field;
	const Int w = field.width;
	const Int h = field.height;
	const Real step = field.step;

	// hard: what the nearest failed point failed on, 1 out of reach, 0 blocked (a point in reach that
	// the fog hides counts as blocked); gap: how far that point is, in grid steps, a city-block walk
	std::vector< UnsignedByte > seen( w * h, 0 );
	std::vector< Real > hard( w * h, 1.0f );
	std::vector< Int > gap( w * h, w + h );
	for( Int j = 0; j < h; ++j )
	{
		for( Int i = 0; i < w; ++i )
		{
			const Int k = j * w + i;
			if( entry.geometry[ k ] == REACH_PASS )
			{
				Coord3D at;
				at.set( field.originX + i * step, field.originY + j * step, 0.0f );
				seen[ k ] = ThePartitionManager->getShroudStatusForPlayer( entry.playerIndex, &at ) == CELLSHROUD_CLEAR ? 1 : 0;
			}
			if( !seen[ k ] )
			{
				gap[ k ] = 0;
				hard[ k ] = entry.geometry[ k ] == REACH_OUT ? 1.0f : 0.0f;
			}
		}
	}
	auto take = [ & ]( Int k, Int from )
	{
		if( gap[ from ] + 1 < gap[ k ] )
		{
			gap[ k ] = gap[ from ] + 1;
			hard[ k ] = hard[ from ];
		}
	};
	for( Int j = 0; j < h; ++j )
		for( Int i = 0; i < w; ++i )
		{
			if( i > 0 ) take( j * w + i, j * w + i - 1 );
			if( j > 0 ) take( j * w + i, ( j - 1 ) * w + i );
		}
	for( Int j = h - 1; j >= 0; --j )
		for( Int i = w - 1; i >= 0; --i )
		{
			if( i < w - 1 ) take( j * w + i, j * w + i + 1 );
			if( j < h - 1 ) take( j * w + i, ( j + 1 ) * w + i );
		}

	// lit: it and its eight neighbours passed
	std::vector< UnsignedByte > lit( w * h, 0 );
	for( Int j = 1; j < h - 1; ++j )
	{
		for( Int i = 1; i < w - 1; ++i )
		{
			Bool all = TRUE;
			for( Int dj = -1; dj <= 1 && all; ++dj )
				for( Int di = -1; di <= 1 && all; ++di )
					all = seen[ ( j + dj ) * w + i + di ] != 0;
			lit[ j * w + i ] = all ? 1 : 0;
		}
	}

	const Real across = step * 1.41421356f;
	const Real outOfReach = DISTANCE_LIMIT + step;
	std::vector< Real > d( w * h, outOfReach );
	for( Int j = 0; j < h; ++j )
	{
		for( Int i = 0; i < w; ++i )
		{
			const UnsignedByte mine = lit[ j * w + i ];
			for( Int dj = -1; dj <= 1; ++dj )
			{
				for( Int di = -1; di <= 1; ++di )
				{
					const Int ni = i + di;
					const Int nj = j + dj;
					if( ( di == 0 && dj == 0 ) || ni < 0 || nj < 0 || ni >= w || nj >= h || lit[ nj * w + ni ] == mine )
						continue;
					d[ j * w + i ] = min( d[ j * w + i ], ( di != 0 && dj != 0 ) ? across : step );
				}
			}
		}
	}
	for( Int j = 0; j < h; ++j )
	{
		for( Int i = 0; i < w; ++i )
		{
			Real &here = d[ j * w + i ];
			if( i > 0 ) here = min( here, d[ j * w + i - 1 ] + step );
			if( j > 0 ) here = min( here, d[ ( j - 1 ) * w + i ] + step );
			if( i > 0 && j > 0 ) here = min( here, d[ ( j - 1 ) * w + i - 1 ] + across );
			if( i < w - 1 && j > 0 ) here = min( here, d[ ( j - 1 ) * w + i + 1 ] + across );
		}
	}
	for( Int j = h - 1; j >= 0; --j )
	{
		for( Int i = w - 1; i >= 0; --i )
		{
			Real &here = d[ j * w + i ];
			if( i < w - 1 ) here = min( here, d[ j * w + i + 1 ] + step );
			if( j < h - 1 ) here = min( here, d[ ( j + 1 ) * w + i ] + step );
			if( i < w - 1 && j < h - 1 ) here = min( here, d[ ( j + 1 ) * w + i + 1 ] + across );
			if( i > 0 && j < h - 1 ) here = min( here, d[ ( j + 1 ) * w + i - 1 ] + across );
		}
	}

	for( Int k = 0; k < w * h; ++k )
	{
		const Real magnitude = min( d[ k ] - 0.5f * step, DISTANCE_LIMIT );
		d[ k ] = lit[ k ] ? magnitude : -magnitude;
	}
	const Real sigma = max( SMOOTH_SIGMA / step, 1.0f );
	blurGrid( d, w, h, sigma );
	blurGrid( hard, w, h, sigma );

	// a fog refresh that changed nothing keeps the version, so the renderer keeps its texture
	Bool changed = (Int)field.distance.size() != w * h || (Int)field.hardness.size() != w * h;
	field.distance.resize( w * h );
	field.hardness.resize( w * h );
	for( Int k = 0; k < w * h; ++k )
	{
		Real value = d[ k ] - SMOOTH_MARGIN * step;
		if( !lit[ k ] )
			value = min( value, -UNLIT_HOLD * step );
		value = max( -DISTANCE_LIMIT, min( value, DISTANCE_LIMIT ) );
		const Real hardness = hard[ k ];
		changed = changed || field.distance[ k ] != value || field.hardness[ k ] != hardness;
		field.distance[ k ] = value;
		field.hardness[ k ] = hardness;
	}
	if( changed || entry.regridded )
		field.version = ++theVersion;
	entry.regridded = FALSE;
}

/// the field taken bilinearly, as the renderer takes it; outside the grid it is the limit below nought
static Real fieldAt( const ReachOverlayField &field, Real x, Real y )
{
	const Real fx = ( x - field.originX ) / field.step;
	const Real fy = ( y - field.originY ) / field.step;
	const Int i = (Int)floorf( fx );
	const Int j = (Int)floorf( fy );
	if( i < 0 || j < 0 || i + 1 >= field.width || j + 1 >= field.height )
		return -field.distanceLimit;
	const Real tx = fx - i;
	const Real ty = fy - j;
	const Real *row = &field.distance[ j * field.width + i ];
	const Real top = row[ 0 ] * ( 1.0f - tx ) + row[ 1 ] * tx;
	const Real bottom = row[ field.width ] * ( 1.0f - tx ) + row[ field.width + 1 ] * tx;
	return top * ( 1.0f - ty ) + bottom * ty;
}

//-------------------------------------------------------------------------------------------------
// What is on the map this frame, and which fields are wanted.
//-------------------------------------------------------------------------------------------------
struct StructureMark
{
	ObjectID id;
	Real x;
	Real y;
};

static std::vector< StructureMark > theStructures;
static std::map< ObjectID, ReachEntry > theEntries;
static ReachEntry theGhost;
static const ThingTemplate *theGhostTemplate = NULL;
static Coord3D theGhostAt;
static Bool theGhostShown = FALSE;
static std::vector< const ReachOverlayField * > theShown;

static UnsignedInt mix( UnsignedInt hash, UnsignedInt value )
{
	return ( hash ^ value ) * 16777619u;
}

static UnsignedInt mixReal( UnsignedInt hash, Real value )
{
	UnsignedInt bits;
	memcpy( &bits, &value, sizeof( bits ) );
	return mix( hash, bits );
}

/// what the grid depends on: the defence and its guns, and every structure standing near it
static UnsignedInt shooterSignature( const ReachShooter &s )
{
	UnsignedInt hash = 2166136261u;
	hash = mixReal( hash, s.center.x );
	hash = mixReal( hash, s.center.y );
	hash = mixReal( hash, s.center.z );
	hash = mixReal( hash, s.eyeZ );
	hash = mixReal( hash, s.acquireRange );
	hash = mix( hash, s.lineOfSight ? 1 : 0 );
	hash = mix( hash, (UnsignedInt)s.playerIndex );
	for( size_t g = 0; g < s.guns.size(); ++g )
	{
		hash = mix( hash, (UnsignedInt)(uintptr_t)s.guns[ g ].tmpl );
		if( s.guns[ g ].live )
			hash = mixReal( hash, s.guns[ g ].live->getAttackRange( s.obj ) );
	}
	const Real nearSqr = sqr( s.reachBound + PATHFIND_CELL_SIZE_F * 10.0f );
	for( size_t k = 0; k < theStructures.size(); ++k )
	{
		const StructureMark &mark = theStructures[ k ];
		if( sqr( mark.x - s.center.x ) + sqr( mark.y - s.center.y ) > nearSqr )
			continue;
		hash = mix( hash, mark.id );
		hash = mixReal( hash, mark.x );
		hash = mixReal( hash, mark.y );
	}
	return hash;
}

/// a defence whose reach the local player is shown: their own, an ally's, or any to an observer
static Bool revealedToLocal( const Object *obj )
{
	const Player *local = ThePlayerList->getLocalPlayer();
	if( local == NULL || obj == NULL )
		return FALSE;
	if( obj->getControllingPlayer() == local )
		return TRUE;
	if( !local->isPlayerObserver() && local->getRelationship( obj->getTeam() ) != ALLIES )
		return FALSE;
	return obj->getShroudedStatus( local->getPlayerIndex() ) < OBJECTSHROUD_FOGGED;
}

static void clearAll( void )
{
	theEntries.clear();
	theShown.clear();
	theGhostShown = FALSE;
	theGhostTemplate = NULL;
	theGhost.built = FALSE;
}

static Real millisecondsSince( const std::chrono::steady_clock::time_point &start )
{
	return std::chrono::duration< Real, std::milli >( std::chrono::steady_clock::now() - start ).count();
}

void ReachOverlay_update( void )
{
	if( TheGlobalData == NULL || TheGlobalData->m_headless || TheGameLogic == NULL || TheInGameUI == NULL
			|| !TheGameLogic->isInGame() || TheGameLogic->isInShellGame() || ThePlayerList == NULL
			|| ThePlayerList->getLocalPlayer() == NULL || TheAI == NULL || TheAI->pathfinder() == NULL )
	{
		clearAll();
		return;
	}

	// the tick may be running beside this frame: keep what was worked out at the last sync point
	if( LogicThread::isInsideWindow() )
		return;

	const std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
	const UnsignedInt now = TheGameClient ? TheGameClient->getFrame() : 0;

	theStructures.clear();
	for( Object *obj = TheGameLogic->getFirstObject(); obj; obj = obj->getNextObject() )
	{
		if( !obj->isKindOf( KINDOF_STRUCTURE ) || obj->isEffectivelyDead() )
			continue;
		StructureMark mark = { obj->getID(), obj->getPosition()->x, obj->getPosition()->y };
		theStructures.push_back( mark );
	}

	// which defences are wanted: the selected ones, or while a building is on the cursor none but
	// that one; every defence at once buries the ground in colour
	std::vector< const Object * > wanted;
	const ThingTemplate *pending = TheInGameUI->getPendingPlaceType();
	if( pending == NULL )
	{
		const DrawableList *selected = TheInGameUI->getAllSelectedDrawables();
		for( DrawableListCIt it = selected->begin(); it != selected->end(); ++it )
		{
			const Object *obj = (*it)->getObject();
			if( revealedToLocal( obj ) )
				wanted.push_back( obj );
		}
	}

	theShown.clear();
	Bool builtOne = FALSE;

	// the cursor's first: it is what the player is looking at
	theGhostShown = FALSE;
	const Drawable *icon = TheInGameUI->getPendingPlaceDrawable();
	ReachShooter ghost;
	if( pending != NULL && icon != NULL
			&& ghostShooter( pending, icon->getPosition()->x, icon->getPosition()->y, ThePlayerList->getLocalPlayer(), ghost ) )
	{
		const Bool moved = pending != theGhostTemplate || !theGhost.built
			|| sqr( ghost.center.x - theGhostAt.x ) + sqr( ghost.center.y - theGhostAt.y ) > sqr( 0.5f * GHOST_STEP );
		if( moved )
		{
			theGhostTemplate = pending;
			theGhostAt = ghost.center;
			traceGeometry( theGhost, ghost, GHOST_STEP );
			builtOne = TRUE;
		}
		if( moved || now - theGhost.fogFrame >= FOG_REFRESH_FRAMES )
		{
			shadeField( theGhost );
			theGhost.fogFrame = now;
		}
		theGhost.field.opacity = 1.0f;
		theShown.push_back( &theGhost.field );
		theGhostShown = TRUE;
	}

	for( size_t k = 0; k < wanted.size(); ++k )
	{
		ReachShooter s;
		if( !liveShooter( wanted[ k ], s ) )
			continue;

		ReachEntry &entry = theEntries[ s.obj->getID() ];
		entry.lastWanted = now;
		const UnsignedInt signature = shooterSignature( s );
		if( !entry.built || entry.signature != signature )
		{
			// a grid that no longer matches what stands round it is not drawn until it is worked out again
			if( builtOne && millisecondsSince( start ) > BUILD_BUDGET_MS )
			{
				entry.built = FALSE;
				continue;
			}
			traceGeometry( entry, s, LIVE_STEP );
			entry.signature = signature;
			shadeField( entry );
			entry.fogFrame = now;
			builtOne = TRUE;
		}
		else if( now - entry.fogFrame >= FOG_REFRESH_FRAMES )
		{
			shadeField( entry );
			entry.fogFrame = now;
		}
		entry.field.color = clientPlayerColor( s.owner );
		theShown.push_back( &entry.field );
	}

	for( std::map< ObjectID, ReachEntry >::iterator it = theEntries.begin(); it != theEntries.end(); )
	{
		if( now - it->second.lastWanted > FORGET_FRAMES )
			theEntries.erase( it++ );
		else
			++it;
	}
}

void ReachOverlay_getFields( std::vector< const ReachOverlayField * > &out )
{
	out = theShown;
}

//-------------------------------------------------------------------------------------------------
/** The check that the picture does not lie.  For a standing defence and a probe of the enemy's, a
	* real Object: the field the defence would show, and the one its template would show on the cursor
	* at the same spot, are sampled at random points, inside, outside and near the edge; the probe is
	* put on each point and the logic is asked itself, the way an idle defence asks it: getNextMoodTarget
	* as the turret's idle scan calls it, the fog filter it applies for this owner, then the weapon the
	* chooser takes and the range and attack tests the turret's aim state makes before it fires.  A lit
	* point the logic refuses is a lie; an unlit one it accepts is ground the picture leaves out.
	*
	* Diagnostic: it moves the probe, runs the partition and sets the defence's current weapon, so only
	* a scenario calls it.  The sample points come from a generator of their own, not the logic's. */
//-------------------------------------------------------------------------------------------------
static Bool logicHits( Object *defence, Object *probe )
{
	AIUpdateInterface *ai = defence->getAI();
	if( ai == NULL || ai->getNextMoodTarget( FALSE, TRUE, FALSE, TRUE ) != probe )
		return FALSE;

	const Player *owner = defence->getControllingPlayer();
	if( owner && ( owner->getPlayerType() == PLAYER_HUMAN || owner->isForkMapComputer() || defence->getTemplate()->acquiresBeyondVision() ) )
	{
		const ObjectShroudStatus status = probe->getShroudedStatus( owner->getPlayerIndex() );
		if( status != OBJECTSHROUD_CLEAR && status != OBJECTSHROUD_PARTIAL_CLEAR )
			return FALSE;
	}

	defence->chooseBestWeaponForTarget( probe, PREFER_MOST_DAMAGE, CMD_FROM_AI );
	const Weapon *weapon = defence->getCurrentWeapon();
	if( weapon == NULL || !weapon->isWithinAttackRange( defence, probe ) )
		return FALSE;
	const CanAttackResult result = defence->getAbleToAttackSpecificObject( ATTACK_CONTINUED_TARGET, probe, CMD_FROM_AI );
	return result == ATTACKRESULT_POSSIBLE || result == ATTACKRESULT_POSSIBLE_AFTER_MOVING;
}

struct ProofCount
{
	Int drawn;
	Int drawnMissed;			///< lies
	Int undrawn;
	Int undrawnHit;				///< ground left out
};

static void tally( ProofCount &count, Bool drawn, Bool hit )
{
	if( drawn )
	{
		++count.drawn;
		if( !hit )
			++count.drawnMissed;
	}
	else
	{
		++count.undrawn;
		if( hit )
			++count.undrawnHit;
	}
}

Bool ReachOverlay_prove( Object *defence, Object *probe, Int samples )
{
	ReachShooter live;
	if( defence == NULL || probe == NULL || !liveShooter( defence, live ) )
	{
		DEBUG_LOG(( "HEADLESS REACHPROOF: no field for %s: %s\n", defence ? defence->getTemplate()->getName().str() : "(none)",
			theRefusal ? theRefusal : "no probe" ));
		return FALSE;
	}
	ReachShooter ghost;
	const Bool hasGhost = ghostShooter( defence->getTemplate(), live.center.x, live.center.y, live.owner, ghost );
	ghost.standingIn = defence->getID();

	const std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
	ReachEntry liveEntry;
	traceGeometry( liveEntry, live, LIVE_STEP );
	shadeField( liveEntry );
	const Real liveMS = millisecondsSince( start );
	ReachEntry ghostEntry;
	if( hasGhost )
	{
		traceGeometry( ghostEntry, ghost, GHOST_STEP );
		ghostEntry.playerIndex = live.playerIndex;
		shadeField( ghostEntry );
	}

	Int litPoints = 0;
	for( size_t k = 0; k < liveEntry.field.distance.size(); ++k )
		litPoints += liveEntry.field.distance[ k ] > 0.0f ? 1 : 0;

	const Coord3D home = *probe->getPosition();
	// mt19937's raw output is the same on every platform; its distributions are not
	std::mt19937 pick( (UnsignedInt)defence->getID() * 2654435761u + (UnsignedInt)samples );
	const Real span = live.reachBound + 10.0f;
	auto across = [ &pick, span ]( void ) { return ( (Real)( pick() >> 8 ) * ( 1.0f / 16777216.0f ) * 2.0f - 1.0f ) * span; };

	enum { ANYWHERE, INSIDE, EDGE, KINDS };
	static const char *const kindNames[ KINDS ] = { "anywhere", "inside", "edge" };
	ProofCount liveCount[ KINDS ];
	ProofCount ghostCount[ KINDS ];
	memset( liveCount, 0, sizeof( liveCount ) );
	memset( ghostCount, 0, sizeof( ghostCount ) );
	Int unstandable = 0;
	Real lowest = FLT_MAX;
	Real highest = -FLT_MAX;

	for( Int kind = 0; kind < KINDS; ++kind )
	{
		Int taken = 0;
		for( Int tries = 0; taken < samples && tries < samples * 200; ++tries )
		{
			const Real x = live.center.x + across();
			const Real y = live.center.y + across();
			const Real d = fieldAt( liveEntry.field, x, y );
			if( kind == INSIDE && d <= 0.0f )
				continue;
			if( kind == EDGE && fabs( d ) > 6.0f )
				continue;

			Coord3D at;
			at.set( x, y, standHeight( x, y ) );
			const PathfindCell *cell = TheAI->pathfinder()->getCell( LAYER_GROUND, &at );
			if( cell == NULL || cell->getType() == PathfindCell::CELL_OBSTACLE || TheTerrainLogic->findBridgeAt( &at ) != NULL )
			{
				++unstandable;
				continue;
			}
			++taken;
			lowest = min( lowest, at.z );
			highest = max( highest, at.z );

			probe->setPosition( &at );
			ThePartitionManager->update();
			const Bool hit = logicHits( defence, probe );
			tally( liveCount[ kind ], d > 0.0f, hit );
			if( hasGhost )
				tally( ghostCount[ kind ], fieldAt( ghostEntry.field, x, y ) > 0.0f, hit );
		}
	}

	probe->setPosition( &home );
	ThePartitionManager->update();

	const GroundProbe &worst = groundProbe();
	DEBUG_LOG(( "HEADLESS REACHPROOF: %s at (%.0f,%.0f,%.1f) against %s: reach bound %.1f, %d lit grid points, grid in %.1f ms, worst target top %.2f body %.2f, ground sampled from %.1f to %.1f high, %d unstandable points skipped\n",
		defence->getTemplate()->getName().str(), live.center.x, live.center.y, live.center.z,
		probe->getTemplate()->getName().str(), live.reachBound, litPoints, liveMS, worst.lowestTop, worst.widestRadius,
		lowest, highest, unstandable ));
	Int lies = 0;
	for( Int kind = 0; kind < KINDS; ++kind )
	{
		DEBUG_LOG(( "HEADLESS REACHPROOF:   %-8s live  drawn %d, %d not hit; undrawn %d, %d hit\n", kindNames[ kind ],
			liveCount[ kind ].drawn, liveCount[ kind ].drawnMissed, liveCount[ kind ].undrawn, liveCount[ kind ].undrawnHit ));
		if( hasGhost )
			DEBUG_LOG(( "HEADLESS REACHPROOF:   %-8s ghost drawn %d, %d not hit; undrawn %d, %d hit\n", kindNames[ kind ],
				ghostCount[ kind ].drawn, ghostCount[ kind ].drawnMissed, ghostCount[ kind ].undrawn, ghostCount[ kind ].undrawnHit ));
		lies += liveCount[ kind ].drawnMissed + ghostCount[ kind ].drawnMissed;
	}
	DEBUG_LOG(( "HEADLESS REACHPROOF: %s %s, %d lies\n", defence->getTemplate()->getName().str(), lies == 0 ? "PASS" : "FAIL", lies ));
	return lies == 0;
}