UMassBattleFormationAlgorithms

线程安全分配核心:无 ECS 访问,操作预捕获数据。先按飞行状态(AgentCanFly,缺失条目默认非飞行)把 agent 索引分成地面/飞行两组;若任一组为空走单组快速路径。双组路径下每组在完整槽位列表上独立调用 AssignPositionsSingleGroup 分配——飞行与非飞行组的 XY 结果可能重合,因运行时它们处于不同 Z 层。单组内部按 AssignmentMode 分派:KeepFormation 用「理想位置贪心(大半径优先)+ 阻挡网格 + 局部成对交换修复」;ReformTheLine 用「稀疏混合候选拍卖(KNear 局部 + KStrat 错位步长覆盖,保证全槽位可竞价)+ 气泡压缩(空位逐环向外冒)+ 跨阵型成对交换 + 链式位移半径修复」。确定性:排序键含 AgentUniqueIDs,候选与堆操作带确定性 tie-break。

Thread-safe assignment core: no ECS access, operates on pre-captured data. First partitions agent indices by flying status (AgentCanFly; missing entries default to non-flying) into ground/flying groups; either group empty takes the single-group fast path. On the two-group path each group runs AssignPositionsSingleGroup independently over the full slot list — flying and ground results may coincide in XY because they occupy different Z layers at runtime. Within a group the AssignmentMode dispatches: KeepFormation uses "ideal-position greedy (largest radius first) + blocker grid + localized pairwise swap repair"; ReformTheLine uses "sparse hybrid-candidate auction (KNear locality + KStrat stride-sampled coverage so every slot is biddable) + bubble compaction (holes ripple outward ring by ring) + cross-formation pairwise swap + chain-displacement radius repair". Determinism: sort keys include AgentUniqueIDs; candidates and heap operations carry deterministic tie-breaks.

ECS 读取包装:逐 agent 读取 FLocating.Location(缺失回退 AgentCentroid)、FDeterminism.UniqueID(缺失回退索引 i)、FMove.Z.bCanFly,然后委托给线程安全核心 AssignPositionsFromData。

ECS-reading wrapper: per agent reads FLocating.Location (fallback AgentCentroid), FDeterminism.UniqueID (fallback index i), and FMove.Z.bCanFly, then delegates to the thread-safe core AssignPositionsFromData.

计算单个 agent 的阵型半径。基准为胶囊体投影到 XY 平面的包围圆半径:轴长 FCollider.Height * Scale 按上方向(FRotating.RotationQuat * FCollider.RelativeRotation)投影,端盖半径 FCollider.Radius * Scale * ColliderMult(ColliderMult 来自 FPhysicsShared,放大端盖不放大轴高,与 PBD 行为一致)。FromAvoidance 模式下再乘避障椭圆长轴系数 max(AvoidDistMult.X, AvoidDistMult.Y);最后乘以 SizeMultiplier。无 FCollider 时默认 34 * Scale。

Computes an agent's formation radius. The baseline is the capsule's bounding-circle radius projected onto the XY plane: the shaft FCollider.Height * Scale is projected along the up vector (FRotating.RotationQuat * FCollider.RelativeRotation), and the cap radius is FCollider.Radius * Scale * ColliderMult (ColliderMult from FPhysicsShared, inflating caps not the shaft, matching PBD behavior). In FromAvoidance mode the result is scaled by the avoidance ellipse's long axis max(AvoidDistMult.X, AvoidDistMult.Y); finally multiplied by SizeMultiplier. Defaults to 34 * Scale without an FCollider.

阵型槽位资格判定:句柄必须是存活实体(有效——未销毁/移除)、未濒死(死亡动画/待清除窗口;DyingFlag 在死亡入口就地置位,同帧可见),且能移动到槽位——缺 FMove / FMove.bEnable=false(静态道具、建筑、炮塔)或运行时 bStopActiveMovement 锁存都意味着永远走不到目标,占槽只会烂掉。战斗减员后 RTS 陈旧选集仍带着死亡句柄——幽灵不得占槽或让防线围着缺席单位重排。同步 Impl 与异步 BPTask 共用;各 Impl 在任何计数之前用它过滤输入,输出保持输入长度(1:1 契约),被剔除项散射回中心。

Formation-slot eligibility: the handle must be a live entity (valid — not destroyed/removed), not dying (death-animation / pre-despawn window; DyingFlag is set in-place at death entry, same-frame visible), AND able to move to a slot at all — missing FMove / FMove.bEnable=false (static props, buildings, turrets) or the runtime bStopActiveMovement latch mean the agent can never walk to the goal, so a slot would rot. Stale RTS selections keep dead handles after combat losses — ghosts must not reserve slots or reshape the line around missing units. Shared by the sync Impls and the async BPTask; each Impl filters its input with it before any count is taken, keeping the output at input length (1:1 contract) with dropped entries scattered to the center.

位置验证与偏移:① 若配置了地面/障碍物对象类型,做向下线追踪(LineTraceMultiByObjectType,起点 = 位置 + max(Y),终点 = 位置 + min(Y));障碍物命中判无效;地面命中做坡度检查(法线 Z < cos(MaxSlope) 判为障碍);通过后位置吸附到撞击点。② 随机偏移:种子由位置内容 FNV-1a 哈希派生(相同内容不同阵型得到不同种子),每个点加随机角度 × Offset 的平面位移;偏移后重新追踪验证。无效点直接从数组中移除。注意:验证失败的点会被删除——仅对晶格槽位安全(生长补足会补),绝不可用于逐 agent 目标数组(索引映射会错位)。

Position validation and offset: ① when ground/obstacle object types are configured, runs a downward line trace (LineTraceMultiByObjectType, start = position + max(Y), end = position + min(Y)); obstacle hits invalidate the point; ground hits run the slope check (normal Z < cos(MaxSlope) treated as obstacle); on success the position snaps to the impact point. ② Random offset: the seed derives from an FNV-1a hash of the position content (different formations with the same count get different seeds); each point gets a planar displacement of random angle × Offset; points are re-traced and re-validated after offsetting. Invalid points are removed from the array. Note: points that fail validation are dropped — only safe for lattice slots (the repair loop regrows them), NEVER for per-agent goal arrays (index mapping).

KeepFormation 平移目标解析器:逐点贴地 + 障碍/坡度校验(与 TraceAndValidate 同语义)。trace 柱内无合法地面的点(在可行走世界之外——刚体平移把它带出了平台边沿)走折返带:向锚点行进至边界后再向内一格(离边沿留余量),占用 SearchStep 大小格网上最近的空闲格——占用集预置全部原位有效目标;格心逐一地面探测,虚空格被拒,补充带沿墙/墙角自然弯折而不是堆在边沿。空间不足降级阶梯:带区搜索(折返格周围,半径随 agent 数缩放——保证能越过阵型自身已占用的侧翼)→ 锚点格周围同样搜索(有间距收拢)→ 锚点本身。有地面但被障碍/陡坡挡住的点走 ① 确定性环形搜索(MaxSearchRings 圈、SearchStep 步长、8 方向、隔圈半步偏移)——绕障碍局部变形;② 保证收敛的向心拉回——沿目标→锚点方向逐步步进探测至首个有效落点。绝不删点(每 agent 恰一个目标)。未配置地面/障碍类型则不动作。

KeepFormation translation-goal resolver: per point, ground-snap + obstacle/slope validation (same per-point semantics as TraceAndValidate). A point whose trace column has NO legal ground (outside the walkable world — the rigid translation carried it past a platform edge) relocates via the FOLD-BACK BAND: march toward the anchor to the boundary, one more cell inward (margin from the rim), then claim the nearest free cell of a SearchStep-sized occupancy grid seeded with every in-place-valid goal; cell centers are ground-probed, so void cells are rejected and the band wraps along walls and corners instead of piling on the rim. Space-insufficiency ladder: band search (size-scaled rings around the fold-back cell — the radius grows with agent count so the search can reach past the formation's own occupied flanks) → the same search around the anchor cell (center collapse WITH spacing) → the anchor itself. A point that HAS ground but is blocked by an obstacle/steep slope relocates via ① a deterministic ring search (MaxSearchRings rings of SearchStep radius, 8 directions, alternating half-step offset) — local deformation around obstacles; then ② a GUARANTEED center pull-back — marching toward the anchor in SearchStep increments until a valid spot is found. No point is ever removed (exactly one goal per agent). No ground/obstacle types configured = no-op.

可视化阵型结果:逐 agent(有效且有 FLocating)按配置绘制起始圆圈、起始→终点箭头、终点圆圈(均抬高 ZOffset=5)。绘制请求推入 UMassBattleSubsystem 的 LineBatchCircleQueue / LineBatchArrowQueue MPSC 队列的线程本地槽,由 ProcessDrawDebugQueues 中心排空——保持 LineBatcher 后端以在 Shipping 构建中可见(DrawDebug* 会被剥离)。

Visualizes the formation result: per agent (valid with FLocating), draws the start circle, start→end arrow, and end circle (all raised by ZOffset=5) per config. Draw requests are pushed into the thread-local slots of UMassBattleSubsystem's LineBatchCircleQueue / LineBatchArrowQueue MPSC queues, drained centrally by ProcessDrawDebugQueues — keeping the LineBatcher backend visible in Shipping builds (DrawDebug* is stripped).

网格阵型实现(由 MassBattleFuncLib::GenerateGridFormation 调用):① IsFormationSlotEligible 在任何计数之前剔除陈旧选集幽灵(输出保持输入长度 1:1,被剔除项散射回中心);② 计算各 agent 半径(≥256 个 agent 时并行)与质心;③ KeepFormation = 纯刚体平移(goal = Center + R(KeepFormationRotateDeg)·(Loc − 质心),整个排列连同队间间隙作为刚体移动,不压缩到晶格),目标经 ResolveTranslatedGoalsOnGround 贴地解析,未配置地面类型则回退点击点 Z;④ ReformTheLine 走晶格重整:ComputeBlockerExtraSlotCount(Box 脚印)+ ComputeFitAgentsSlotTarget 推目标槽位数,GenerateGridSlotPositions 生成晶格并输出实际宽高比;⑤ ValidateAndOffsetPositions 验证偏移,点数不足目标时 AppendGridGrowth 四向生长补足(≤8 轮,只验证新点、已有点绝不二次偏移);⑥ AssignPositionsToAgents 分配(矩形环纵横比 = 实际晶格宽高比,Box 脚印);⑦ Z 冻结 agent(!Z.bEnable)保持自身平面;按需可视化。

Grid formation implementation (called from MassBattleFuncLib::GenerateGridFormation): ① IsFormationSlotEligible filters stale-selection ghosts before any count is taken (output keeps input length 1:1; dropped entries scatter to the center); ② computes per-agent radii (parallelized at ≥256 agents) and the centroid; ③ KeepFormation = pure rigid translation (goal = Center + R(KeepFormationRotateDeg)·(Loc − centroid); the whole arrangement including inter-squad gaps moves as one rigid body, nothing is compressed onto a lattice), goals ground-resolved via ResolveTranslatedGoalsOnGround, falling back to the click-point Z when no ground types are configured; ④ ReformTheLine reshapes onto the lattice: ComputeBlockerExtraSlotCount (Box footprint) + ComputeFitAgentsSlotTarget derive the target slot count, and GenerateGridSlotPositions emits the lattice with the realized aspect ratio; ⑤ ValidateAndOffsetPositions validates/offsets; shortfall vs. the target is regrown by AppendGridGrowth omnidirectional growth (≤8 retries, only new points validated — existing points are never offset twice); ⑥ assigns via AssignPositionsToAgents (rectangular ring aspect = realized lattice aspect, Box footprint); ⑦ Z-frozen agents (!Z.bEnable) keep their own plane; visualizes on demand.

圆形/多边形阵型实现(由 MassBattleFuncLib::GenerateCircularFormation 调用):① IsFormationSlotEligible 剔除幽灵(1:1 契约同网格实现);② 计算各 agent 半径(并行阈值同上);③ ComputeBlockerExtraSlotCount(Circle 脚印)+ ComputeFitAgentsSlotTarget 推目标槽位数,GenerateCircularSlotPositions 从 InnerRadius(下限 Spacing.Y/2)向外逐环生成——每环按弧长/Spacing.X 布点,多边形模式(Segments 3-32)逐角度收缩外半径,FitAgents 下环持续生长(忽略 OuterRadius,有安全上限)直到数量达标;④ 验证与偏移,不足时 AppendCircularGrowth 向外长环补足(≤8 轮,只验证新点);⑤ 质心采集;KeepFormation = 纯刚体平移(同网格实现,含 ResolveTranslatedGoalsOnGround 贴地解析);⑥ AssignPositionsToAgents 分配(环形度量 = 欧氏距离,即 RectRingAspectRatio = 0,Circle 脚印);⑦ Z 冻结处理与按需可视化。

Circular/polygon formation implementation (called from MassBattleFuncLib::GenerateCircularFormation): ① IsFormationSlotEligible filters ghosts (same 1:1 contract as the grid impl); ② computes radii (same parallel threshold); ③ ComputeBlockerExtraSlotCount (Circle footprint) + ComputeFitAgentsSlotTarget derive the target slot count, and GenerateCircularSlotPositions emits rings outward from InnerRadius (floored at Spacing.Y/2) — points per ring by arc length / Spacing.X; polygon mode (Segments 3-32) shrinks the outer radius per angle, and in FitAgents the rings keep growing (OuterRadius ignored, safety cap) until the count is met; ④ validation and offset; shortfall regrown by AppendCircularGrowth outer-ring growth (≤8 retries, only new points validated); ⑤ centroid gather; KeepFormation = pure rigid translation (same as the grid impl, including ResolveTranslatedGoalsOnGround ground resolution); ⑥ assigns via AssignPositionsToAgents (ring metric = Euclidean, i.e. RectRingAspectRatio = 0, Circle footprint); ⑦ Z-frozen handling and on-demand visualization.

三角(楔形)阵型实现(由 MassBattleFuncLib::GenerateTriangleFormation 调用;与异步 BPTask 三角分支一致——Hexagon 阻挡脚印、间距比例 Chebyshev 环):① IsFormationSlotEligible 剔除幽灵(1:1 契约);② 半径与质心;KeepFormation = 纯刚体平移(同网格实现,含 ResolveTranslatedGoalsOnGround);③ ComputeBlockerExtraSlotCount(Hexagon 脚印)+ ComputeFitAgentsSlotTarget 推目标槽位数,GenerateTriangleSlotPositions 生成楔形晶格(第 j 行 j+1 槽,顶点行朝 +ShapeDirection,包围盒居中);④ 验证与偏移,不足时 AppendTriangleGrowth 向底边长行补足(≤8 轮,只验证新点);⑤ 分配——环度量与脚印跟随阵型族:间距比例 Chebyshev 环(行 = 环,RectRingAspectRatio = Spacing.X / Spacing.Y)+ Hexagon 脚印;Spacing.Y 退化时回退圆形族默认(欧氏环 + Circle);⑥ Z 冻结处理与按需可视化。

Triangle (wedge) formation implementation (called from MassBattleFuncLib::GenerateTriangleFormation; mirrors the async BPTask triangle branch — Hexagon blocker footprint, spacing-ratio Chebyshev rings): ① IsFormationSlotEligible filters ghosts (1:1 contract); ② radii and centroid; KeepFormation = pure rigid translation (same as the grid impl, including ResolveTranslatedGoalsOnGround); ③ ComputeBlockerExtraSlotCount (Hexagon footprint) + ComputeFitAgentsSlotTarget derive the target slot count, and GenerateTriangleSlotPositions emits the wedge lattice (row j holds j+1 slots, apex row toward +ShapeDirection, bounding-box centered); ④ validation and offset; shortfall regrown by AppendTriangleGrowth base-row growth (≤8 retries, only new points validated); ⑤ assignment — ring metric and footprint follow the formation family: spacing-ratio Chebyshev rings (row = ring, RectRingAspectRatio = Spacing.X / Spacing.Y) + Hexagon footprint; degenerate Spacing.Y falls back to the circular-family defaults (Euclidean rings + Circle); ⑥ Z-frozen handling and on-demand visualization.

FitAgents 目标槽位数 = ceil(Agent 数 × SlotCountMargin) + ExtraBlockerSlots(见 ComputeBlockerExtraSlotCount);尺寸解析为(当前禁用的)Fixed 分支时返回 0。

FitAgents slot-count target = ceil(NumAgents × SlotCountMargin) + ExtraBlockerSlots (see ComputeBlockerExtraSlotCount); returns 0 when sizing resolves to the (currently disabled) Fixed branches.

大单位的额外槽位需求:半径超过半个最小槽距的 agent 是 blocker,其排除脚印覆盖多个格位(脚印族跟随阵型——网格 Box、圆形 Circle、三角 Hexagon)。故意按脚印不重叠高估——多余槽位在 ReformTheLine 中被压拢、在 KeepFormation 中闲置,而短缺会让被挤走的 agent 堆到阵型中心。纯数学,只依赖半径多重集。

Extra FitAgents slot demand from large agents: each agent whose radius exceeds half the minimum slot spacing becomes a blocker whose exclusion footprint covers multiple lattice cells (footprint family follows the formation — Box for grid, Circle for circular, Hexagon for triangle). Deliberately a disjoint-footprint OVERestimate: extra slots compact away in ReformTheLine and stay unused in KeepFormation, while a shortfall piles displaced agents at the formation center. Pure math on the radii multiset.

网格晶格生成(纯数学、线程安全):Fixed 模式 NumX/NumY = Floor(Region/Spacing),逐点复现旧版 authored 画布布局;FitAgents 模式按 authored 长宽比解出点数比 W/H(使 (W-1)·SX / ((H-1)·SY) ≈ Region.X/Region.Y),取最小 W×H ≥ 目标槽位数——authored 尺寸仅作长宽比,槽位始终够用。OutRealizedAspectRatio = NumX·SX / (NumY·SY)(退化时 1.f),喂给矩形环形压缩。

Grid lattice generation (pure math, thread-safe): Fixed mode NumX/NumY = Floor(Region/Spacing), reproducing the legacy authored-canvas layout exactly; FitAgents mode solves the point-count ratio W/H from the authored aspect so (W-1)·SX / ((H-1)·SY) ≈ Region.X/Region.Y with minimal W×H ≥ TargetSlotCount — the authored size only sets the aspect ratio, so slots always suffice. OutRealizedAspectRatio = NumX·SX / (NumY·SY) (1.f if degenerate), feeding rectangular ring compaction.

不发射晶格直接算实际物理宽高比 (NumX·SX)/(NumY·SY)——供只携带形状数据的路径(如异步任务的派发步骤)做环形压缩。AgentRadii 参与和生成器一致的 blocker 额外槽位目标,保证宽高比与发射晶格一致。退化时返回 1.f。

Realized physical aspect (NumX·SX)/(NumY·SY) without emitting the lattice — for ring compaction on paths that only carry the shape data (e.g. the async task's dispatch step). AgentRadii feed the same blocker-extra slot target the generators use, so the aspect matches the emitted lattice. Returns 1.f when degenerate.

三角(楔形)晶格生成:第 j 行 j+1 槽,行内间距 Spacing.X,行间距 Spacing.Y,顶点行(1 槽)朝 +ShapeDirection,包围盒居中。Fixed 模式行数受 Min(Floor(Region.X/SX), Floor(Region.Y/SY)) + 1 限制;FitAgents 模式取最小 Rows 使 Rows·(Rows+1)/2 ≥ 目标槽位数。

Triangle (wedge) lattice generation: row j holds j+1 slots, in-row pitch Spacing.X, row pitch Spacing.Y, apex row (1 slot) toward +ShapeDirection, bounding-box centered. Fixed mode caps rows at Min(Floor(Region.X/SX), Floor(Region.Y/SY)) + 1; FitAgents mode takes the smallest Rows with Rows·(Rows+1)/2 ≥ TargetSlotCount.

圆形/多边形环晶格生成:Fixed 模式环数受 OuterRadius 界定(含逐角度多边形裁剪);FitAgents 模式环持续生长(忽略 OuterRadius,有安全上限)直到数量 ≥ 目标槽位数。OutNextRingIdx = 首个未发射环——AppendCircularGrowth 的续接点。

Circular/polygon ring lattice generation: Fixed mode bounds rings by OuterRadius (including the per-angle polygon clip); FitAgents mode keeps growing rings (OuterRadius ignored, safety cap) until count ≥ TargetSlotCount. OutNextRingIdx = first unemitted ring — the resume point for AppendCircularGrowth.

FitAgents 的 trace 删点补足:追加晶格点且不移动已有点,发射直到 MinNewSlots 个新点就绪(或形状耗尽)。调用方单独验证新点并追加幸存者,因此任何点不会被偏移两次;返回 0 = 无可生长。网格生长是四向的:晶格边界(MinX..MaxX、MinY..MaxY)在四条边上轮转扩展,锚定在初始生成的行列数(OriginNumX/OriginNumY)上——中心贴墙角的阵型也能找到开阔侧,扎进墙里的发射点在调用方的 trace 中被丢弃,自由方向持续积累。三角生长向底边长行;圆形生长向外长环(经 InOutNextRingIdx 续接)。

FitAgents trace-shortfall repair: appends lattice points WITHOUT moving existing ones, emitting until MinNewSlots new points are available (or the shape is exhausted). Call sites validate the new points separately and append the survivors, so no point is ever offset twice; 0 = nothing left to grow. Grid growth is OMNIDIRECTIONAL: the lattice bounds (MinX..MaxX, MinY..MaxY) extend round-robin on all four edges, anchored at the ORIGINAL generation dims (OriginNumX/OriginNumY) — a formation pinned against a wall corner still finds the open side; emissions into the wall die at the call site's trace while the free directions accumulate. Triangle growth extends base rows; circular growth adds outer rings (resumed via InOutNextRingIdx).