--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

function widget:GetInfo()
	return {
		name    = "Auto Retreat Plus",
		desc    = "Extends the built-in auto retreat: retreating units path around enemy reach, stop when a constructor repairs them, " ..
		          "can skip the walk back afterwards, resume their patrol, and idle engineers in retreat zones repair whoever is nearby.",
		author  = "Thomas",
		date    = "2026-10-21",
		license = "GNU GPL, v2 or later",
		layer   = 0,
		enabled = true,
	}
end

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-- How it works
--
-- Auto retreat is the synced gadget LuaRules/Gadgets/cmd_retreat.lua, not a
-- widget, and a widget cannot replace a gadget. This widget leaves the gadget
-- in charge of when a unit retreats (the Retreat 30/65/99% button, the retreat
-- zones, start states) and takes over how it gets there.
--
-- When the gadget starts a retreat it puts [RAW_MOVE to a point in the zone,
-- WAIT] at the front of the queue, and if the unit was idle it appends a
-- RAW_MOVE back to where the unit stood. It clears the WAIT at full health.
-- The gadget checks every 20 frames at frame % 20 == 10, and this widget looks
-- in the same frame, right after it, so it sees those orders the moment they
-- are given:
--
--   * Enemy avoidance. Each visible enemy gets a danger disk of radius
--     weapon range + speed * reach time + margin: where it could shoot us
--     within that many seconds. A* over a coarse grid, with danger as extra
--     cost, gives a route; it is pulled tight into a few waypoints and inserted
--     in front of the gadget's WAIT. Replanned while the enemies move, three
--     times a second while the unit is taking damage. Enemies that drop out
--     of sight are remembered: structures until their spot is seen empty,
--     mobile units for ten seconds.
--   * Stop for repair. If an allied constructor is repairing the unit and the
--     unit is out of every danger disk and not taking damage, its moves are
--     removed so it halts on the gadget's WAIT. They come back when the repair
--     stops.
--   * No walk back. The return RAW_MOVE is removed.
--   * Patrol. The unit's patrol points are recorded when the retreat starts. If
--     none are left in the queue when it ends, the unit walks to the first one
--     and patrols the same loop again.
--   * Retreat zone engineers. Constructors that are idle inside a zone, or
--     sitting on the retreat WAIT there, repair damaged allies in reach,
--     retreating units first.
--
-- Our moves are recognised by their coordinates, as the Lotus widget does
-- with its aim points: an order we send has no tag until it arrives.
--------------------------------------------------------------------------------

local spGetUnitPosition       = Spring.GetUnitPosition
local spGetUnitDefID          = Spring.GetUnitDefID
local spGetUnitCommands       = Spring.GetUnitCommands
local spGetUnitCommandCount   = Spring.GetUnitCommandCount
local spGetUnitRulesParam     = Spring.GetUnitRulesParam
local spGetUnitsInCylinder    = Spring.GetUnitsInCylinder
local spGetUnitsInRectangle   = Spring.GetUnitsInRectangle
local spGetUnitIsBuilding     = Spring.GetUnitIsBuilding
local spGetUnitIsBeingBuilt   = Spring.GetUnitIsBeingBuilt
local spGetUnitIsStunned      = Spring.GetUnitIsStunned
local spGetUnitHealth         = Spring.GetUnitHealth
local spGetUnitRadius         = Spring.GetUnitRadius
local spGetGroundHeight       = Spring.GetGroundHeight
local spGetGroundNormal       = Spring.GetGroundNormal
local spGetTeamRulesParam     = Spring.GetTeamRulesParam
local spGetGameRulesParam     = Spring.GetGameRulesParam
local spGetTeamList           = Spring.GetTeamList
local spGetTeamUnits          = Spring.GetTeamUnits
local spGiveOrderToUnit       = Spring.GiveOrderToUnit
local spGiveOrderArrayToUnitArray = Spring.GiveOrderArrayToUnitArray
local spValidUnitID           = Spring.ValidUnitID
local spIsUnitSelected        = Spring.IsUnitSelected
local spGetGameFrame          = Spring.GetGameFrame
local spIsPosInLos           = Spring.IsPosInLos

local sqrt, floor, ceil, min, max, abs = math.sqrt, math.floor, math.ceil, math.min, math.max, math.abs
local cos, rad = math.cos, math.rad

local CUSTOM = (Spring.Utilities and Spring.Utilities.CMD) or {}
local CMD_RAW_MOVE  = CUSTOM.RAW_MOVE or 31109
local CMD_REARM     = CUSTOM.REARM or 33410
local CMD_WAIT      = CMD.WAIT
local CMD_PATROL    = CMD.PATROL
local CMD_REPAIR    = CMD.REPAIR
local CMD_INSERT    = CMD.INSERT
local CMD_REMOVE    = CMD.REMOVE
local CMD_OPT_SHIFT = CMD.OPT_SHIFT
local ENEMY_UNITS   = Spring.ENEMY_UNITS
local ALLY_UNITS    = Spring.ALLY_UNITS

local MAP_X, MAP_Z = Game.mapSizeX, Game.mapSizeZ

-- Danger grid. Coarse on purpose: it only decides the waypoints, and the
-- engine pathfinder still walks between them.
local CELL = max(96, ceil(max(MAP_X, MAP_Z) / 72))
local NX, NZ = ceil(MAP_X / CELL), ceil(MAP_Z / CELL)

local MAX_CHASE        = 600   -- elmos; caps speed * reach time for fast raiders and bombers
-- A* costs about 10 us a node in plain Lua 5.1. Plans run in a coroutine that
-- stops for the frame once it has spent NODES_PER_FRAME, so one plan may span
-- several frames but no frame pays more than a millisecond or two. A plan that
-- hits MAX_EXPAND heads for the explored cell nearest the zone, and the next
-- replan carries on from there.
local MAX_EXPAND       = 1500  -- A* nodes per plan
local NODES_PER_FRAME  = 150
local HEURISTIC_WEIGHT = 1.6
local MAX_WAYPOINTS  = 10
local RADAR_THREAT   = {range = 300, speed = 60, w = 0.6}
local MOBILE_MEMORY  = 300   -- frames a mobile enemy is still avoided after it leaves sight
local RETREAT_RADIUS = 160   -- read from the gadget in Initialize

--------------------------------------------------------------------------------
-- Options

options_path = 'Settings/Unit Behaviour/Auto Retreat Plus'

local function V(key)
	return options[key].value
end

options_order = {
	'lbl_avoid',
	'avoidEnemies', 'reachTime', 'safetyMargin', 'avoidStrength', 'maxThreatRange', 'avoidRadar', 'replanInterval',

	'lbl_repair',
	'stopForRepair', 'repairResumeDelay', 'havenEngineers', 'engineerReach',

	'lbl_after',
	'returnToPosition', 'resumePatrol',

	'lbl_draw',
	'drawRoutes', 'drawThreats',
}

options = {
	lbl_avoid = {name = 'Enemy avoidance', type = 'label', noSave = true},

	avoidEnemies = {
		name = 'Path around enemies while retreating',
		desc = 'Retreating units take a route around the estimated reach of visible enemies instead of the straight line to the retreat zone.',
		type = 'bool', value = true,
	},
	reachTime = {
		name = 'Enemy reach time (s)',
		desc = 'Each enemy is avoided by its weapon range plus how far it can move in this many seconds. ' ..
		       'Higher keeps a wider berth from fast units. Static defences only count their range.',
		type = 'number', value = 2, min = 0, max = 6, step = 0.5,
	},
	safetyMargin = {
		name = 'Extra safety margin (elmos)',
		type = 'number', value = 60, min = 0, max = 300, step = 10,
	},
	avoidStrength = {
		name = 'Detour willingness',
		desc = 'How much longer a route may be to stay out of danger. At 6, an elmo inside the deepest part of an enemy zone costs as much as about seven elmos of safe ground.',
		type = 'number', value = 6, min = 1, max = 20, step = 1,
	},
	maxThreatRange = {
		name = 'Ignore enemies with more range than',
		desc = 'Long-range artillery and superweapons cannot be walked around. They are left out so they do not cover the whole map.',
		type = 'number', value = 1400, min = 400, max = 4000, step = 100,
	},
	avoidRadar = {
		name = 'Avoid unidentified radar dots',
		desc = 'Treat radar contacts as a small generic threat.',
		type = 'bool', value = true,
	},
	replanInterval = {
		name = 'Replan every (s)',
		type = 'number', value = 1.5, min = 0.5, max = 5, step = 0.5,
	},

	lbl_repair = {name = 'Repair', type = 'label', noSave = true},

	stopForRepair = {
		name = 'Stop retreating while being repaired',
		desc = 'A retreating unit that an allied constructor is repairing waits where it is, unless it is inside enemy reach or taking damage. It moves on if the repair stops.',
		type = 'bool', value = true,
	},
	repairResumeDelay = {
		name = 'Move on after repair stops for (s)',
		type = 'number', value = 1.5, min = 0.5, max = 6, step = 0.5,
	},
	havenEngineers = {
		name = 'Engineers in retreat zones repair nearby units',
		desc = 'Idle constructors inside a retreat zone, including ones that retreated there, repair damaged allied units in reach. Retreating units go first, then the most damaged.',
		type = 'bool', value = true,
	},
	engineerReach = {
		name = 'Engineers walk up to (elmos)',
		desc = 'How far past its build range a zone engineer may walk to reach a damaged unit. It walks back afterwards.',
		type = 'number', value = 150, min = 0, max = 500, step = 25,
	},

	lbl_after = {name = 'After the retreat', type = 'label', noSave = true},

	returnToPosition = {
		name = 'Go back to where it was',
		desc = 'At full health, a unit that was idle when it retreated walks back to where it stood (the built-in behaviour). Turn off to leave it in the retreat zone.',
		type = 'bool', value = true,
	},
	resumePatrol = {
		name = 'Return to patrol route',
		desc = 'A unit that was patrolling when it retreated goes back to the same patrol loop at full health, if its patrol orders were lost.',
		type = 'bool', value = true,
	},

	lbl_draw = {name = 'Display', type = 'label', noSave = true},

	drawRoutes = {
		name = 'Draw retreat routes of selected units',
		type = 'bool', value = true,
	},
	drawThreats = {
		name = 'Draw enemy reach estimates near selected retreating units',
		type = 'bool', value = false,
	},
}

--------------------------------------------------------------------------------
-- Unit data

local function Truthy(v)
	return v and v ~= "0" and v ~= "false" and v ~= 0 and v ~= false
end

local moverDef     = {} -- defID -> true: has the retreat command
local builderDef   = {} -- defID -> build distance, for anything that can repair
local mobileDef    = {} -- defID -> true for builders that can walk to a target
local ignoreDef    = {} -- terraform markers and the like
local defCats      = {} -- defID -> {set = {cat = true}, key = "a b c"}
local defMove      = {} -- defID -> passability key, false for flyers
local maxBuildDist = 0

for defID = 1, #UnitDefs do
	local ud = UnitDefs[defID]
	local cp = ud.customParams or {}
	if Truthy(cp.dontcount) then
		ignoreDef[defID] = true
	end
	if ud.canMove and (ud.speed or 0) > 0 then
		moverDef[defID] = true
	end
	local bd = ud.buildDistance or 0
	if ud.isBuilder and ud.canRepair and not ud.isFactory and bd > 0 then
		builderDef[defID] = bd
		maxBuildDist = max(maxBuildDist, bd)
		if ud.canMove and (ud.speed or 0) > 0 then
			mobileDef[defID] = true
		end
	end
end
maxBuildDist = min(maxBuildDist, 1000)

local function Cats(defID)
	local c = defCats[defID]
	if c then
		return c
	end
	local set, list = {}, {}
	local mc = UnitDefs[defID].modCategories or {}
	for cat in pairs(mc) do
		local lc = string.lower(cat)
		set[lc] = true
		list[#list + 1] = lc
	end
	table.sort(list)
	c = {set = set, key = table.concat(list, " "), fly = UnitDefs[defID].canFly and true or false}
	defCats[defID] = c
	return c
end

-- What one enemy type can do to one kind of target. Same reading of the weapon
-- tables as the Combat Advisor: stats_damage, and mount-level onlyTargets keyed
-- by lowercase category, where an empty table hits everything.
local profiles = {} -- catKey -> defID -> profile or false

local function Profile(defID, cats)
	local byKey = profiles[cats.key]
	if not byKey then
		byKey = {}
		profiles[cats.key] = byKey
	end
	local p = byKey[defID]
	if p ~= nil then
		return p
	end
	local ud = UnitDefs[defID]
	local range, dps = 0, 0
	local weapons = ud.weapons or {}
	for i = 1, #weapons do
		local wpn = weapons[i]
		local wd = wpn.weaponDef and WeaponDefs[wpn.weaponDef]
		if wd and not wd.isShield and not (cats.fly and wd.type == "TorpedoLauncher") then
			local wcp = wd.customParams or {}
			local dmg = tonumber(wcp.stats_damage) or (wd.damages and wd.damages[0]) or 0
			if wd.paralyzer then
				dmg = dmg * 0.5
			end
			local reload = wd.reload or 0
			if reload <= 0 then
				reload = 1
			end
			local wdps = dmg * (wd.salvoSize or 1) * (wd.projectiles or 1) / reload
			if wdps > 1 then
				local ot = wpn.onlyTargets
				local hits = (not ot) or (next(ot) == nil)
				if not hits then
					for cat in pairs(ot) do
						if cats.set[string.lower(cat)] then
							hits = true
							break
						end
					end
				end
				if hits then
					range = max(range, wd.range or 0)
					dps = dps + wdps
				end
			end
		end
	end
	if range <= 0 then
		p = false
	else
		p = {range = range, speed = ud.speed or 0, w = min(max(sqrt(dps / 150), 0.5), 3)}
	end
	byKey[defID] = p
	return p
end

--------------------------------------------------------------------------------
-- State

local retreaters  = {} -- unitID -> retreat record, while the gadget has it retreating
local myMovers    = {} -- unitID -> defID
local myBuilders  = {} -- unitID -> defID
local patrolJobs  = {} -- unitID -> patrol restore in progress
local havens      = {} -- {x, z} of every allied retreat zone
local myHavens    = {} -- own team's only, where our units retreat to

local myTeam, myAllyTeam, spectating

local threatList, threatFrame = {}, -1000
local enemyMemory = {} -- unitID -> {x, z, defID, frame}: last sighting, kept after the enemy leaves sight
local fields = {} -- catKey -> {frame, d = {cell = danger}, threats = {...}}
local passCache = {} -- move key -> {cell = bool}

local planQueue = {} -- unitIDs waiting for the planner, most urgent first
local planner        -- the planning coroutine
local planSpent = 0  -- work units spent this frame (one per A* node)

-- Called from inside planning work: pauses the planner until next frame once
-- the frame's budget is gone. Outside the coroutine it only counts.
local function Spend(k)
	planSpent = planSpent + k
	if planSpent >= NODES_PER_FRAME and coroutine.running() then
		coroutine.yield()
	end
end

--------------------------------------------------------------------------------
-- Grid helpers

local INV_CELL = 1 / CELL

local function CellOf(x, z)
	local cx, cz = floor(x * INV_CELL), floor(z * INV_CELL)
	if cx < 0 then cx = 0 elseif cx >= NX then cx = NX - 1 end
	if cz < 0 then cz = 0 elseif cz >= NZ then cz = NZ - 1 end
	return cz * NX + cx + 1, cx, cz
end

local function CellCenter(i)
	local j = i - 1
	local cx = j % NX
	local cz = (j - cx) / NX
	return (cx + 0.5) * CELL, (cz + 0.5) * CELL
end

local function MoveKey(defID)
	local k = defMove[defID]
	if k ~= nil then
		return k
	end
	local ud = UnitDefs[defID]
	if ud.canFly or not ud.moveDef then
		k = false
	else
		k = tostring(ud.moveDef.name or ud.moveDef.id or defID)
	end
	defMove[defID] = k
	return k
end

-- moveDef.maxSlope is stored as 1 - cos(angle), the same scale as 1 - normal.y.
local function SlopeLimit(md)
	local s = md.maxSlope
	if not s then
		return 1
	end
	if s > 1 then -- degrees, if an engine ever hands those out
		return 1 - cos(rad(s))
	end
	return s
end

local function PointPassable(ud, md, family, x, z)
	local h = spGetGroundHeight(x, z)
	if family == "ship" or (ud.minWaterDepth or 0) > 0 then
		return h < -(ud.minWaterDepth or 5)
	end
	if h < 0 then
		if family == "hover" then
			return true
		end
		local depth = md.depth or ud.maxWaterDepth or 22
		if -h > depth then
			return false
		end
	end
	local _, ny = spGetGroundNormal(x, z)
	if ny and (1 - ny) > SlopeLimit(md) then
		return false
	end
	return true
end

-- The per-cell cache for this unit's movement class, nil for flyers.
local function PassTable(defID)
	local key = MoveKey(defID)
	if not key then
		return nil
	end
	local cache = passCache[key]
	if not cache then
		cache = {}
		passCache[key] = cache
	end
	return cache
end

local function Passable(defID, i)
	local cache = PassTable(defID)
	if not cache then
		return true
	end
	local p = cache[i]
	if p == nil then
		local ud = UnitDefs[defID]
		local md = ud.moveDef
		local family = md.family or md.type
		local x, z = CellCenter(i)
		local o = CELL * 0.3
		local ok = 0
		if PointPassable(ud, md, family, x, z) then ok = ok + 1 end
		if PointPassable(ud, md, family, x - o, z - o) then ok = ok + 1 end
		if PointPassable(ud, md, family, x + o, z - o) then ok = ok + 1 end
		if PointPassable(ud, md, family, x - o, z + o) then ok = ok + 1 end
		if PointPassable(ud, md, family, x + o, z + o) then ok = ok + 1 end
		p = ok >= 3
		cache[i] = p
	end
	return p
end

--------------------------------------------------------------------------------
-- Enemy reach estimate

-- Enemies that left sight are still avoided: a structure until the spot is back
-- in LOS without it, a mobile unit for MOBILE_MEMORY frames, its reach growing
-- with the time since it was seen. Without this a unit that retreats out of
-- sight forgets the turrets it just ran from and plans straight back past them.
local function CollectThreats(frame)
	if frame - threatFrame < 15 then
		return threatList
	end
	threatFrame = frame
	local units = spGetUnitsInRectangle(0, 0, MAP_X, MAP_Z, ENEMY_UNITS) or {}
	for k = 1, #units do
		local u = units[k]
		local x, _, z = spGetUnitPosition(u)
		if x then
			local m = enemyMemory[u]
			local defID = spGetUnitDefID(u) or (m and m.defID) -- a radar dot keeps its identity
			if defID and (ignoreDef[defID] or (spGetUnitIsBeingBuilt and spGetUnitIsBeingBuilt(u))) then
				enemyMemory[u] = nil
			elseif m then
				m.x, m.z, m.defID, m.frame = x, z, defID, frame
			else
				enemyMemory[u] = {x = x, z = z, defID = defID, frame = frame}
			end
		end
	end
	local list = {}
	local radar = V('avoidRadar')
	for u, m in pairs(enemyMemory) do
		local age = frame - m.frame
		local keep = true
		if age > 0 then
			local static = m.defID and not moverDef[m.defID]
			if not static then
				keep = age <= MOBILE_MEMORY and m.defID ~= nil
			elseif spIsPosInLos and spIsPosInLos(m.x, spGetGroundHeight(m.x, m.z), m.z, myAllyTeam) then
				keep = false -- we can see the spot and it is not there
			end
		end
		if not keep then
			enemyMemory[u] = nil
		elseif m.defID or radar then
			list[#list + 1] = {x = m.x, z = m.z, defID = m.defID, age = age}
		end
	end
	threatList = list
	return list
end

local function Stamp(d, x, z, R, w)
	local cx0, cx1 = max(floor((x - R) / CELL), 0), min(floor((x + R) / CELL), NX - 1)
	local cz0, cz1 = max(floor((z - R) / CELL), 0), min(floor((z + R) / CELL), NZ - 1)
	for cz = cz0, cz1 do
		local pz = (cz + 0.5) * CELL - z
		for cx = cx0, cx1 do
			local px = (cx + 0.5) * CELL - x
			local dd = sqrt(px*px + pz*pz)
			if dd < R then
				local i = cz * NX + cx + 1
				d[i] = (d[i] or 0) + w * (0.4 + 0.6 * (1 - dd / R))
			end
		end
	end
end

local function GetField(defID, frame)
	local cats = Cats(defID)
	local f = fields[cats.key]
	if f and frame - f.frame < 30 then
		return f
	end
	local d, drawn = {}, {}
	local T, margin, maxRange = V('reachTime'), V('safetyMargin'), V('maxThreatRange')
	local list = CollectThreats(frame)
	for k = 1, #list do
		local t = list[k]
		local p
		if t.defID then
			p = Profile(t.defID, cats)
		else
			p = RADAR_THREAT
		end
		if p and p.range <= maxRange then
			local R = p.range + min(p.speed * (T + t.age / 30), MAX_CHASE) + margin
			Stamp(d, t.x, t.z, R, p.w)
			drawn[#drawn + 1] = {t.x, t.z, R}
		end
	end
	f = {frame = frame, d = d, threats = drawn}
	fields[cats.key] = f
	return f
end

local function DangerAt(f, x, z)
	return f.d[(CellOf(x, z))] or 0
end

--------------------------------------------------------------------------------
-- Route planning

-- Binary heap on parallel arrays.
local function HeapPush(hf, hi, n, f, i)
	n = n + 1
	local c = n
	while c > 1 do
		local p = floor(c / 2)
		if hf[p] <= f then
			break
		end
		hf[c], hi[c] = hf[p], hi[p]
		c = p
	end
	hf[c], hi[c] = f, i
	return n
end

local function HeapPop(hf, hi, n)
	local topI = hi[1]
	local lf, li = hf[n], hi[n]
	hf[n], hi[n] = nil, nil
	n = n - 1
	if n > 0 then
		local c = 1
		while true do
			local l = c * 2
			if l > n then
				break
			end
			if l < n and hf[l + 1] < hf[l] then
				l = l + 1
			end
			if hf[l] >= lf then
				break
			end
			hf[c], hi[c] = hf[l], hi[l]
			c = l
		end
		hf[c], hi[c] = lf, li
	end
	return topI, n
end

local NB_DX  = {1, -1, 0, 0, 1, 1, -1, -1}
local NB_DZ  = {0, 0, 1, -1, 1, -1, 1, -1}
local NB_LEN = {1, 1, 1, 1, 1.41421, 1.41421, 1.41421, 1.41421}

-- Returns the cell path, whether it stops short of the goal, and the nodes spent.
-- The inner loop is inlined by hand: this runs in plain Lua 5.1.
local function AStar(defID, f, sx, sz, gx, gz, budget)
	local d = f.d
	local halfK = V('avoidStrength') * 0.5
	local s, scx, scz = CellOf(sx, sz)
	local g, gcx, gcz = CellOf(gx, gz)
	if s == g then
		return {s}, false, 0
	end
	local span = max(abs(gcx - scx), abs(gcz - scz))
	local pad = max(12, floor(span * 0.5))
	local bx0, bx1 = max(min(scx, gcx) - pad, 0), min(max(scx, gcx) + pad, NX - 1)
	local bz0, bz1 = max(min(scz, gcz) - pad, 0), min(max(scz, gcz) + pad, NZ - 1)
	local pt = PassTable(defID) -- nil for flyers

	-- Octile distance, inflated: a slightly longer route is fine, and a greedier
	-- search expands a fraction of the nodes when danger covers much of the map.
	local hw = CELL * HEURISTIC_WEIGHT
	local hf, hi, n = {}, {}, 0
	local gScore, came, closed = {[s] = 0}, {}, {}

	local function PathTo(i)
		local path = {i}
		while came[path[1]] do
			table.insert(path, 1, came[path[1]])
		end
		return path
	end

	local dx0, dz0 = abs(scx - gcx), abs(scz - gcz)
	local bestI = s
	local bestH = hw * (max(dx0, dz0) + 0.41421 * min(dx0, dz0))
	n = HeapPush(hf, hi, n, bestH, s)
	local expanded = 0
	while n > 0 do
		local cur
		cur, n = HeapPop(hf, hi, n)
		if cur == g then
			return PathTo(g), false, expanded
		end
		if not closed[cur] then
			closed[cur] = true
			expanded = expanded + 1
			if expanded % 25 == 0 then
				Spend(25)
			end
			if expanded > budget then
				-- Out of budget: head for the explored cell nearest the goal.
				if bestI ~= s then
					return PathTo(bestI), true, expanded
				end
				return nil, false, expanded
			end
			local j = cur - 1
			local cx = j % NX
			local cz = (j - cx) / NX
			local dCur = d[cur] or 0
			local gCur = gScore[cur]
			for k = 1, 8 do
				local nx, nz = cx + NB_DX[k], cz + NB_DZ[k]
				if nx >= bx0 and nx <= bx1 and nz >= bz0 and nz <= bz1 then
					local ni = nz * NX + nx + 1
					if not closed[ni] then
						local ok = true
						if pt and ni ~= g then
							ok = pt[ni]
							if ok == nil then
								ok = Passable(defID, ni)
							end
						end
						if ok then
							local ng = gCur + CELL * NB_LEN[k] * (1 + halfK * (dCur + (d[ni] or 0)))
							local old = gScore[ni]
							if not old or ng < old then
								gScore[ni] = ng
								came[ni] = cur
								local hx, hz = nx - gcx, nz - gcz
								if hx < 0 then hx = -hx end
								if hz < 0 then hz = -hz end
								local h
								if hx > hz then
									h = hw * (hx + 0.41421 * hz)
								else
									h = hw * (hz + 0.41421 * hx)
								end
								if h < bestH then
									bestI, bestH = ni, h
								end
								n = HeapPush(hf, hi, n, ng + h, ni)
							end
						end
					end
				end
			end
		end
	end
	return nil, false, expanded
end

-- Can the unit walk straight from cell a to cell b without more danger than the
-- grid path between them had?
local function SegmentClear(defID, f, ax, az, bx, bz, limit)
	local d = f.d
	local pt = PassTable(defID)
	local dx, dz = bx - ax, bz - az
	local len = sqrt(dx*dx + dz*dz)
	local steps = max(1, ceil(len / (CELL * 0.5)))
	Spend(steps * 0.1)
	limit = limit + 0.01
	for k = 1, steps - 1 do
		local t = k / steps
		local i = CellOf(ax + dx * t, az + dz * t)
		if (d[i] or 0) > limit then
			return false
		end
		if pt then
			local p = pt[i]
			if p == nil then
				p = Passable(defID, i)
			end
			if not p then
				return false
			end
		end
	end
	return true
end

-- Danger-weighted length of a straight segment.
local function SegCost(f, ax, az, bx, bz, K)
	local d = f.d
	local dx, dz = bx - ax, bz - az
	local len = sqrt(dx*dx + dz*dz)
	local steps = max(1, ceil(len / (CELL * 0.5)))
	Spend(steps * 0.1)
	local step, cost = len / steps, 0
	for s = 1, steps do
		local t = (s - 0.5) / steps
		cost = cost + step * (1 + K * (d[(CellOf(ax + dx * t, az + dz * t))] or 0))
	end
	return cost
end

-- Pull the grid path tight. Only the cells where the path turns are candidate
-- waypoints, and a shortcut must not cost more, danger included, than the
-- stretch of grid path it replaces. Comparing only the worst cell let a unit
-- starting deep in enemy reach cut diagonally across it instead of backing out
-- the way the grid path did.
local function Smooth(defID, f, path, sx, sz)
	local K = V('avoidStrength')
	local m = #path
	local corners = {1}
	for k = 2, m - 1 do
		if path[k] - path[k - 1] ~= path[k + 1] - path[k] then
			corners[#corners + 1] = k
		end
	end
	if m > 1 then
		corners[#corners + 1] = m
	end
	local out = {}
	local a = 1 -- index into corners
	local ax, az = sx, sz
	local nc = #corners
	while a < nc do
		local b = a + 1
		-- Cost of following the grid from the anchor to corner b.
		local px, pz = ax, az
		local grid = 0
		for k = corners[a] + 1, corners[b] do
			local cx, cz = CellCenter(path[k])
			grid = grid + SegCost(f, px, pz, cx, cz, K)
			px, pz = cx, cz
		end
		while b < nc do
			local nextGrid = grid
			for k = corners[b] + 1, corners[b + 1] do
				local cx, cz = CellCenter(path[k])
				nextGrid = nextGrid + SegCost(f, px, pz, cx, cz, K)
				px, pz = cx, cz
			end
			local qx, qz = CellCenter(path[corners[b + 1]])
			if SegCost(f, ax, az, qx, qz, K) <= nextGrid + 1 and SegmentClear(defID, f, ax, az, qx, qz, math.huge) then
				b = b + 1
				grid = nextGrid
			else
				break
			end
		end
		ax, az = CellCenter(path[corners[b]])
		out[#out + 1] = {ax, az}
		a = b
	end
	return out
end

local function RoundPoint(x, z)
	x = floor(min(max(x, 8), MAP_X - 8) + 0.5)
	z = floor(min(max(z, 8), MAP_Z - 8) + 0.5)
	return {x, spGetGroundHeight(x, z), z}
end

-- Waypoints to dest, ending with dest itself, and the A* nodes spent. nil if no
-- plan could be made.
local function PlanRoute(unitID, r, frame, budget)
	local x, _, z = spGetUnitPosition(unitID)
	if not x then
		return nil, 0
	end
	local dest = r.dest
	if not V('avoidEnemies') then
		return {dest}, 0
	end
	local f = GetField(r.defID, frame)
	local path, partial, used = AStar(r.defID, f, x, z, dest[1], dest[3], budget or MAX_EXPAND)
	if not path then
		return nil, used
	end
	local pts = {}
	local smooth = Smooth(r.defID, f, path, x, z)
	-- The last cell is dest's own, unless the search stopped short of it.
	for k = 1, #smooth - (partial and 0 or 1) do
		local p = smooth[k]
		local dx, dz = p[1] - x, p[2] - z
		if dx*dx + dz*dz > (CELL * 0.75)^2 then
			pts[#pts + 1] = RoundPoint(p[1], p[2])
		end
	end
	while #pts > MAX_WAYPOINTS - 1 do
		table.remove(pts, #pts)
	end
	pts[#pts + 1] = dest
	return pts, used
end

-- Danger-weighted length of a polyline, and whether any of it is in danger.
local function PolyCost(f, x, z, pts)
	local K = V('avoidStrength')
	local cost, risky = 0, false
	local px, pz = x, z
	for k = 1, #pts do
		local qx, qz = pts[k][1], pts[k][3]
		local dx, dz = qx - px, qz - pz
		local len = sqrt(dx*dx + dz*dz)
		local steps = max(1, ceil(len / (CELL * 0.5)))
		local step = len / steps
		for s = 1, steps do
			local t = (s - 0.5) / steps
			local danger = DangerAt(f, px + dx * t, pz + dz * t)
			if danger > 0 then
				risky = true
			end
			cost = cost + step * (1 + K * danger)
		end
		px, pz = qx, qz
	end
	return cost, risky
end

--------------------------------------------------------------------------------
-- Queue helpers

local function Near(p, x, z, tol)
	return p and abs(p[1] - x) < tol and abs(p[3] - z) < tol
end

local function HasTag(unitID, tag)
	if not tag then
		return false
	end
	local q = spGetUnitCommands(unitID, -1) or {}
	for k = 1, #q do
		if q[k].tag == tag then
			return true
		end
	end
	return false
end

-- Tags and points of the route moves still queued in front of the WAIT.
local function RouteInQueue(unitID, r)
	local tags, pts = {}, {}
	local q = spGetUnitCommands(unitID, 16) or {}
	for k = 1, #q do
		local c = q[k]
		if c.tag == r.waitTag then
			break
		end
		if c.id == CMD_RAW_MOVE and c.params then
			local cx, cz = c.params[1], c.params[3]
			for j = 1, #r.route do
				if Near(r.route[j], cx, cz, 1.5) then
					tags[#tags + 1] = c.tag
					pts[#pts + 1] = r.route[j]
					break
				end
			end
		end
	end
	return tags, pts
end

local function Give(unitID, orders, r, frame)
	if #orders > 0 then
		spGiveOrderArrayToUnitArray({unitID}, orders)
		if r then
			r.pendingUntil = frame + 12
		end
	end
end

local function InsertRouteOrders(orders, pts, skipLast)
	local last = skipLast and (#pts - 1) or #pts
	for k = 1, last do
		local p = pts[k]
		orders[#orders + 1] = {CMD_INSERT, {k - 1, CMD_RAW_MOVE, CMD_OPT_SHIFT, p[1], p[2], p[3]}, {"alt"}}
	end
end

--------------------------------------------------------------------------------
-- Repair detection

local function IsBeingRepaired(unitID, x, z)
	if not spGetUnitIsBuilding then
		return false
	end
	local near = spGetUnitsInCylinder(x, z, maxBuildDist + 60, ALLY_UNITS) or {}
	for k = 1, #near do
		local b = near[k]
		if b ~= unitID then
			local defID = spGetUnitDefID(b)
			if defID and builderDef[defID] and spGetUnitIsBuilding(b) == unitID then
				return true
			end
		end
	end
	return false
end

local function IsSafe(unitID, r, frame, x, z)
	if frame - (r.lastDamage or -1000) < 45 then
		return false
	end
	return DangerAt(GetField(r.defID, frame), x, z) <= 0
end

--------------------------------------------------------------------------------
-- Retreat lifecycle

local function Adopt(unitID, defID, frame)
	local q = spGetUnitCommands(unitID, 4) or {}
	local w
	for k = 2, min(3, #q) do
		if q[k].id == CMD_WAIT then
			w = k
			break
		end
	end
	if not w or q[w - 1].id ~= CMD_RAW_MOVE then
		return -- not the gadget's move-and-wait: planes rearming, units already in a zone
	end
	local hasRearm = (w == 3)
	if hasRearm and q[1].id ~= CMD_REARM then
		return
	end
	local mp = q[w - 1].params
	local r = {
		defID = defID,
		dest = {mp[1], mp[2], mp[3]},
		waitTag = q[w].tag,
		hasRearm = hasRearm,
		state = 'moving',
		pendingUntil = 0,
		nextPlan = frame,
	}
	-- Gunships heading for an airpad keep the gadget's REARM; we only add waypoints.
	r.route = hasRearm and {} or {r.dest}

	-- The gadget's walk back: a RAW_MOVE to where the unit stood, last in the queue.
	local ret = q[w + 1]
	if ret and ret.id == CMD_RAW_MOVE and spGetUnitCommandCount(unitID) == w + 1 then
		local x, _, z = spGetUnitPosition(unitID)
		local tol = 24 + (UnitDefs[defID].speed or 0) * 0.75
		if x and Near(ret.params, x, z, tol) then
			r.returnTag = ret.tag
		end
	end

	local full = spGetUnitCommands(unitID, -1) or {}
	for k = 1, #full do
		local c = full[k]
		if c.id == CMD_PATROL and c.params and c.params[3] then
			r.patrol = r.patrol or {}
			r.patrol[#r.patrol + 1] = {c.params[1], c.params[2], c.params[3]}
		end
	end

	retreaters[unitID] = r
	patrolJobs[unitID] = nil

	if r.returnTag and not V('returnToPosition') then
		Give(unitID, {{CMD_REMOVE, {r.returnTag}, 0}}, r, frame)
		r.returnTag = nil
	end
end

local function Finish(unitID, r, frame)
	retreaters[unitID] = nil
	local orders = {}
	local tags = RouteInQueue(unitID, r)
	if #tags > 0 then
		orders[#orders + 1] = {CMD_REMOVE, tags, 0}
	end
	if r.returnTag and not V('returnToPosition') and HasTag(unitID, r.returnTag) then
		orders[#orders + 1] = {CMD_REMOVE, {r.returnTag}, 0}
	end
	Give(unitID, orders, nil, frame)
	if r.patrol and V('resumePatrol') then
		patrolJobs[unitID] = {pts = r.patrol, phase = 0, checkAt = frame + 10, giveUpAt = frame + 30 * 90}
	end
end

local function CheckRetreaters(frame)
	for unitID, defID in pairs(myMovers) do
		local want = spGetUnitRulesParam(unitID, "retreat") == 1
		local r = retreaters[unitID]
		if r then
			if not want then
				Finish(unitID, r, frame)
			elseif not HasTag(unitID, r.waitTag) then
				-- A new order replaced the retreat. The gadget sends the unit
				-- again once it goes idle, and we pick it up then.
				retreaters[unitID] = nil
			end
		elseif want then
			Adopt(unitID, defID, frame)
		end
	end
end

-- What is left of the current route, ending at dest.
local function RemainingRoute(r, remaining)
	local old = {}
	for k = 1, #remaining do
		old[k] = remaining[k]
	end
	if #old == 0 or old[#old] ~= r.dest then
		old[#old + 1] = r.dest
	end
	return old
end

-- A finished plan replaces the queued route if it is clearly safer. The queue is
-- read again here because the plan may have taken a few frames.
local function ApplyPlan(unitID, r, pts)
	local frame = spGetGameFrame()
	if retreaters[unitID] ~= r or r.state ~= 'moving' then
		return
	end
	if frame < r.pendingUntil then
		r.nextPlan = r.pendingUntil
		return
	end
	r.planned = true
	if not pts then
		return
	end
	local tags, remaining = RouteInQueue(unitID, r)
	if #tags == 0 and not r.hasRearm then
		return -- arrived meanwhile
	end
	local x, _, z = spGetUnitPosition(unitID)
	local f = GetField(r.defID, frame)
	local oldCost = PolyCost(f, x, z, RemainingRoute(r, remaining))
	local newCost = PolyCost(f, x, z, pts)
	if newCost >= oldCost * 0.85 - 1 then
		return
	end
	local orders = {}
	if #tags > 0 then
		orders[1] = {CMD_REMOVE, tags, 0}
	end
	InsertRouteOrders(orders, pts, r.hasRearm)
	if r.hasRearm then
		pts[#pts] = nil
	end
	r.route = pts
	Give(unitID, orders, r, frame)
end

local function PlannerLoop()
	while true do
		local unitID = table.remove(planQueue, 1)
		if not unitID then
			coroutine.yield()
		else
			local r = retreaters[unitID]
			if r then
				r.planQueued = nil
				if r.state == 'moving' and spValidUnitID(unitID) then
					-- GetGameFrame returns a second value (days), which would land in budget.
					local pts = PlanRoute(unitID, r, (spGetGameFrame()))
					ApplyPlan(unitID, r, pts)
				end
			end
		end
	end
end

local function RequestPlan(unitID, r)
	if r.planQueued then
		return
	end
	r.planQueued = true
	if r.planned then
		planQueue[#planQueue + 1] = unitID
	else
		-- Units still on the gadget's straight line go first.
		local k = 1
		while planQueue[k] and retreaters[planQueue[k]] and not retreaters[planQueue[k]].planned do
			k = k + 1
		end
		table.insert(planQueue, k, unitID)
	end
end

local function RunPlanner()
	if #planQueue == 0 then
		return
	end
	if not planner or coroutine.status(planner) == "dead" then
		planner = coroutine.create(PlannerLoop)
	end
	planSpent = 0
	local ok, err = coroutine.resume(planner)
	if not ok then
		Spring.Echo("Auto Retreat Plus: planner error: " .. tostring(err))
		planner = nil
	end
end

-- Back on the move after a repair: straight to the zone at once, and a proper
-- plan as soon as the planner gets to it.
local function Resume(unitID, r, frame)
	local orders = {}
	InsertRouteOrders(orders, {r.dest}, false)
	r.route = {r.dest}
	r.state = 'moving'
	r.planned = false
	Give(unitID, orders, r, frame)
	r.nextPlan = r.pendingUntil
end

local function UpdateRetreater(unitID, r, frame)
	if frame < r.pendingUntil then
		return
	end
	local x, _, z = spGetUnitPosition(unitID)
	if not x then
		return
	end
	if r.state == 'moving' then
		local tags, remaining = RouteInQueue(unitID, r)
		-- A gunship bound for an airpad starts with no moves of ours, so it has
		-- not arrived until it had its chance at a plan.
		if #tags == 0 and (not r.hasRearm or r.planned or not V('avoidEnemies')) then
			r.state = 'arrived'
			return
		end
		if V('stopForRepair') and not r.hasRearm and IsBeingRepaired(unitID, x, z) and IsSafe(unitID, r, frame, x, z) then
			r.state = 'held'
			r.lastRepair = frame
			Give(unitID, {{CMD_REMOVE, tags, 0}}, r, frame)
			return
		end
		if V('avoidEnemies') and frame >= r.nextPlan then
			-- A route that touches no enemy reach cannot be improved on. Most
			-- checks end here, which keeps the A* cost to units actually at risk.
			-- Under fire, every second counts: replan about three times a second.
			if frame - (r.lastDamage or -1000) < 30 then
				r.nextPlan = frame + 9
			else
				r.nextPlan = frame + V('replanInterval') * 30
			end
			if r.planned then
				local _, risky = PolyCost(GetField(r.defID, frame), x, z, RemainingRoute(r, remaining))
				if not risky then
					return
				end
			end
			RequestPlan(unitID, r)
		end
	elseif r.state == 'held' then
		if IsBeingRepaired(unitID, x, z) then
			r.lastRepair = frame
		end
		if not V('stopForRepair') or not IsSafe(unitID, r, frame, x, z)
		or frame - r.lastRepair >= V('repairResumeDelay') * 30 then
			Resume(unitID, r, frame)
		end
	end
end

--------------------------------------------------------------------------------
-- Patrol restore

local function UpdatePatrolJob(unitID, job, frame)
	if frame < job.checkAt then
		return
	end
	job.checkAt = frame + 15
	if frame > job.giveUpAt or not spValidUnitID(unitID) then
		patrolJobs[unitID] = nil
		return
	end
	local pts = job.pts
	local q = spGetUnitCommands(unitID, -1) or {}
	if job.phase == 0 then
		for k = 1, #q do
			if q[k].id == CMD_PATROL then
				patrolJobs[unitID] = nil -- the loop survived the retreat
				return
			end
		end
		local p = pts[1]
		local opts = (#q > 0) and CMD_OPT_SHIFT or 0
		if #pts == 1 then
			spGiveOrderToUnit(unitID, CMD_PATROL, p, opts)
			patrolJobs[unitID] = nil
			return
		end
		-- Walk onto the loop first. A patrol order starts from where the unit
		-- stands, so ordering it from the retreat zone would add the zone to it.
		spGiveOrderToUnit(unitID, CMD_RAW_MOVE, p, opts)
		job.phase = 1
		job.checkAt = frame + 30
		return
	end
	local p = pts[1]
	if #q > 0 then
		for k = 1, #q do
			if q[k].id == CMD_RAW_MOVE and Near(q[k].params, p[1], p[3], 1.5) then
				return -- still walking there
			end
		end
		patrolJobs[unitID] = nil -- given other orders meanwhile
		return
	end
	-- Idle: arrived, or the move gave up short of the point. Either way patrol
	-- the loop from here; in the second case the loop gains this spot.
	local x, _, z = spGetUnitPosition(unitID)
	local first = (x and Near(p, x, z, 120)) and 2 or 1
	local orders = {}
	for k = first, #pts do
		orders[#orders + 1] = {CMD_PATROL, pts[k], (k > first) and CMD_OPT_SHIFT or 0}
	end
	spGiveOrderArrayToUnitArray({unitID}, orders)
	patrolJobs[unitID] = nil
end

--------------------------------------------------------------------------------
-- Retreat zone engineers

local function UpdateHavens()
	RETREAT_RADIUS = spGetGameRulesParam('retreatZoneRadius') or RETREAT_RADIUS
	havens, myHavens = {}, {}
	if not myAllyTeam then
		return
	end
	for _, teamID in ipairs(spGetTeamList(myAllyTeam) or {}) do
		local count = spGetTeamRulesParam(teamID, "haven_count") or 0
		for i = 1, count do
			local hx, hz = spGetTeamRulesParam(teamID, "haven_x" .. i), spGetTeamRulesParam(teamID, "haven_z" .. i)
			if hx and hz then
				havens[#havens + 1] = {hx, hz}
				if teamID == myTeam then
					myHavens[#myHavens + 1] = {hx, hz}
				end
			end
		end
	end
end

local function InHaven(x, z)
	local r2 = (RETREAT_RADIUS + 24)^2
	for k = 1, #havens do
		local h = havens[k]
		local dx, dz = x - h[1], z - h[2]
		if dx*dx + dz*dz <= r2 then
			return h
		end
	end
	return nil
end

local function IsBuilt(unitID)
	if spGetUnitIsBeingBuilt then
		return not spGetUnitIsBeingBuilt(unitID)
	end
	local _, _, _, _, bp = spGetUnitHealth(unitID)
	return bp and bp >= 1
end

local function PickRepairTarget(builderID, defID, x, z)
	local reach = builderDef[defID] + (mobileDef[defID] and V('engineerReach') or 0)
	local near = spGetUnitsInCylinder(x, z, reach + 60, ALLY_UNITS) or {}
	local best, bestRank, bestDist
	for k = 1, #near do
		local u = near[k]
		if u ~= builderID then
			local uDef = spGetUnitDefID(u)
			local hp, maxHp = spGetUnitHealth(u)
			if uDef and not ignoreDef[uDef] and hp and maxHp and hp < maxHp - 0.5 and IsBuilt(u) then
				local ux, _, uz = spGetUnitPosition(u)
				local dx, dz = ux - x, uz - z
				local dist = sqrt(dx*dx + dz*dz) - (spGetUnitRadius(u) or 0)
				if dist <= reach then
					-- Retreating units first, then by health fraction.
					local rank = hp / maxHp + ((spGetUnitRulesParam(u, "retreat") == 1) and 0 or 1)
					if not best or rank < bestRank - 0.001 or (abs(rank - bestRank) <= 0.001 and dist < bestDist) then
						best, bestRank, bestDist = u, rank, dist
					end
				end
			end
		end
	end
	return best, bestDist
end

local function RunEngineers(frame)
	if not V('havenEngineers') or #havens == 0 then
		return
	end
	for b, defID in pairs(myBuilders) do
		if IsBuilt(b) and not spGetUnitIsStunned(b) then
			local x, y, z = spGetUnitPosition(b)
			if x and InHaven(x, z) then
				local count = spGetUnitCommandCount(b) or 0
				local waiting = false
				if count > 0 and spGetUnitRulesParam(b, "retreat") == 1 then
					local q = spGetUnitCommands(b, 1)
					waiting = q and q[1] and q[1].id == CMD_WAIT
				end
				if count == 0 or waiting then
					local target, dist = PickRepairTarget(b, defID, x, z)
					if target then
						if waiting then
							spGiveOrderToUnit(b, CMD_INSERT, {0, CMD_REPAIR, 0, target}, {"alt"})
						else
							local orders = {{CMD_REPAIR, {target}, 0}}
							if mobileDef[defID] and dist > builderDef[defID] then
								local p = RoundPoint(x, z)
								orders[2] = {CMD_RAW_MOVE, p, CMD_OPT_SHIFT}
							end
							spGiveOrderArrayToUnitArray({b}, orders)
						end
					end
				end
			end
		end
	end
end

--------------------------------------------------------------------------------
-- Main loop

function widget:GameFrame(n)
	if spectating then
		return
	end
	if n % 15 == 0 then
		CollectThreats(n) -- keeps enemyMemory current while nothing is retreating
	end
	if n % 30 == 15 then
		UpdateHavens()
		RunEngineers(n)
	end
	-- The gadget checks at n % 20 == 10, so this sees its orders the frame they appear.
	if n % 20 == 10 then
		CheckRetreaters(n)
	end
	if n % 6 == 0 then
		for unitID, r in pairs(retreaters) do
			if spValidUnitID(unitID) then
				UpdateRetreater(unitID, r, n)
			else
				retreaters[unitID] = nil
			end
		end
		for unitID, job in pairs(patrolJobs) do
			UpdatePatrolJob(unitID, job, n)
		end
	end
	RunPlanner()
	if n % 1800 == 0 then
		passCache = {} -- terraform
	end
end

--------------------------------------------------------------------------------
-- Callins

local function AddUnit(unitID, unitDefID, unitTeam)
	if unitTeam ~= myTeam or not unitDefID then
		return
	end
	if moverDef[unitDefID] then
		myMovers[unitID] = unitDefID
	end
	if builderDef[unitDefID] then
		myBuilders[unitID] = unitDefID
	end
end

local function RemoveUnit(unitID)
	myMovers[unitID] = nil
	myBuilders[unitID] = nil
	retreaters[unitID] = nil
	patrolJobs[unitID] = nil
end

function widget:UnitCreated(unitID, unitDefID, unitTeam)
	AddUnit(unitID, unitDefID, unitTeam)
end

function widget:UnitGiven(unitID, unitDefID, newTeam)
	AddUnit(unitID, unitDefID, newTeam)
end

function widget:UnitTaken(unitID, unitDefID, oldTeam, newTeam)
	if newTeam ~= myTeam then
		RemoveUnit(unitID)
	end
end

function widget:UnitDestroyed(unitID)
	RemoveUnit(unitID)
	enemyMemory[unitID] = nil
end

function widget:UnitDamaged(unitID, unitDefID, unitTeam, damage)
	local r = retreaters[unitID]
	if r and (damage or 0) > 0 then
		r.lastDamage = spGetGameFrame()
	end
end

local function Reinitialize()
	retreaters, myMovers, myBuilders, patrolJobs = {}, {}, {}, {}
	fields, threatList, threatFrame, enemyMemory = {}, {}, -1000, {}
	planQueue, planner = {}, nil
	myTeam = Spring.GetMyTeamID()
	myAllyTeam = Spring.GetMyAllyTeamID()
	spectating = Spring.GetSpectatingState()
	if spectating then
		return
	end
	for _, unitID in ipairs(spGetTeamUnits(myTeam) or {}) do
		AddUnit(unitID, spGetUnitDefID(unitID), myTeam)
	end
	UpdateHavens()
end

function widget:PlayerChanged()
	if Spring.GetMyTeamID() ~= myTeam or Spring.GetSpectatingState() ~= spectating then
		Reinitialize()
	end
end

function widget:Initialize()
	Reinitialize()
end

--------------------------------------------------------------------------------
-- Drawing

local glColor, glVertex, glLineWidth = gl.Color, gl.Vertex, gl.LineWidth
local glBeginEnd, glDrawGroundCircle, glDepthTest = gl.BeginEnd, gl.DrawGroundCircle, gl.DepthTest
local GL_LINE_STRIP = GL.LINE_STRIP

local stripPts, stripN = {}, 0
local function DrawStrip()
	for k = 1, stripN do
		local p = stripPts[k]
		glVertex(p[1], p[2], p[3])
	end
end

function widget:DrawWorld()
	if spectating or not next(retreaters) then
		return
	end
	local routes, threats = V('drawRoutes'), V('drawThreats')
	if not routes and not threats then
		return
	end
	glDepthTest(true)
	glLineWidth(2)
	local frame = spGetGameFrame()
	local shown = {}
	for unitID, r in pairs(retreaters) do
		if spIsUnitSelected(unitID) then
			local x, y, z = spGetUnitPosition(unitID)
			if x then
				if routes then
					if r.state == 'held' then
						glColor(0.3, 1, 0.4, 0.8)
						glDrawGroundCircle(x, y, z, 40, 20)
					elseif r.state == 'moving' then
						local _, remaining = RouteInQueue(unitID, r)
						stripN = 1
						stripPts[1] = {x, y + 6, z}
						for k = 1, #remaining do
							local p = remaining[k]
							stripN = stripN + 1
							stripPts[stripN] = {p[1], spGetGroundHeight(p[1], p[3]) + 6, p[3]}
						end
						glColor(1, 0.8, 0.2, 0.8)
						glBeginEnd(GL_LINE_STRIP, DrawStrip)
					end
				end
				if threats then
					local f = fields[Cats(r.defID).key]
					if f and not shown[f] then
						shown[f] = true
						glColor(1, 0.25, 0.2, 0.35)
						for k = 1, #f.threats do
							local t = f.threats[k]
							local dx, dz = t[1] - x, t[2] - z
							if dx*dx + dz*dz < (t[3] + 1500)^2 then
								glDrawGroundCircle(t[1], spGetGroundHeight(t[1], t[2]), t[2], t[3], 40)
							end
						end
					end
				end
			end
		end
	end
	glColor(1, 1, 1, 1)
	glLineWidth(1)
	glDepthTest(false)
end