Troop collision separation & bridge pathfinding

Clash Royale Simulator — technical writeup for engine fixes in combat.rs

This is a deterministic multi-agent combat simulator written in Rust — tick-level precision, integer arithmetic, fully reproducible. Built as practice for autonomous systems work: the collision steering and graph-based pathfinding directly mirror challenges in multi-agent coordination and swarm navigation. The following documents two engine-level bugs I diagnosed and fixed in the collision and pathfinding systems.

1. The collision stacking problem bug

Two same-team troops spawned at the same position remain permanently stacked at distance = 0, walking in perfect lockstep. This violates real Clash Royale behavior where same-team troops form side-by-side clusters.

Figure 1 — The tick-ordering trap: collision pushes are undone by identical movement vectors every tick.

Why post-movement collision can't fix this

After the collision push separates them by 998 units on X, both troops compute direction toward the same bridge waypoint w ~5000 units away. The angular difference between their movement vectors is only:

Δθ ≈ arctan(998 / 5000) ≈ 11°

This produces ~1 unit/tick of divergence — but each troop takes a full 30 unit step toward w, reconverging by ~29 units. Movement overwhelms collision separation.

2. The bridge selection problem bug

The old bridge selection used nearest_bridge_x(entity.x) — choosing the bridge closest to the troop's current X position. This ignores the target entirely.

Figure 2 — Bridge selection: nearest-to-self (red dashed) picks the wrong bridge. Shortest-path-to-target (green solid) picks correctly.

3. Solution: ally-avoidance steering fix

Instead of bolting collision onto movement as a post-hoc correction, we integrate ally-awareness directly into the velocity computation. Each tick, every troop computes a combined velocity:

Figure 3 — Avoidance steering pipeline: preferred velocity + lateral separation + symmetry break + capped residual collision.

The math

Preferred velocity: direction from troop position p to waypoint w:

v̂_pref = (w − p) / ‖w − p‖

Avoidance: for each of the 2 nearest same-team allies within radius r_s = 1.2 × (r_i + r_j):

â = (p_i − p_j) / ‖p_i − p_j‖ (away from ally)

s = max(0, 1 − ‖p_i − p_j‖ / r_s) (penetration strength)

Decompose into lateral and forward using perpendicular n̂_⊥ = (−v̂_pref_y, v̂_pref_x):

a_lat = (â · n̂_⊥) · s a_fwd = (â · v̂_pref) · s · 0.3

Symmetry break for exact overlap (‖p_i − p_j‖ < 1):

a_lat += { +1.0 if id mod 2 = 0, −1.0 if id mod 2 = 1 }

Magnitude clamp: ‖(a_lat, a_fwd)‖ ≤ 1.0 (caps deflection to ~22°)

Final velocity:

v_final = normalize(v̂_pref + α · (a_lat · n̂_⊥ + a_fwd · v̂_pref)) · speed

where α = 0.4.

Demo Two Knights spawned at the same position separate via ally-avoidance steering. Entity ID parity drives the symmetry break — even ID goes right, odd goes left.

tick A_x     A_y     B_x     B_y     dist
1      0 −5000      0 −5000       0
10      0 −5000      0 −5000       0 ← deploy timer
20    322 −4607 −363 −5355    1014 ← separation starts
40    802 −4267 −806 −4977    1757
60 1282 −3927 −1246 −4597    2615
80 1762 −3587 −1686 −4217    3505 ← ~5.8 tiles apart

PASS — final distance = 3,505 units. Monotonically increasing: avoidance is persistent, not a one-tick collision push that gets undone.

4. Solution: waypoint lane graph fix

Bridge selection was rewritten to use a 10-node navigation graph. All node positions derive from arena constants — no hardcoded heuristics.

Figure 4 — 10-node waypoint lane graph. Within each side, nodes are fully connected (open ground). Cross-river only via bridge pairs.

How a troop uses the graph each tick

The graph defines the arena's walkable topology. Each tick, every troop runs a 3-step decision:

Figure 5 — Per-tick pathing decision: choose target → find shortest path on the lane graph → walk toward the next waypoint node.

The key: step ② doesn't compute raw point-to-point distances. It walks the graph, summing leg distances through actual nodes — the same nodes from Figure 4. Here's a concrete trace:

Figure 6 — Graph traversal trace: each route sums 3 legs through explicit graph nodes. The left route wins; the knight walks toward BRIDGE_L_P1 this tick.

The troop doesn't see raw distances — it walks the graph. Each candidate route is a sequence of nodes:

Left route: Knight → BRIDGE_LEFT_P1 → BRIDGE_LEFT_P2 → target
Right route: Knight → BRIDGE_RIGHT_P1 → BRIDGE_RIGHT_P2 → target

The "shortest path" sums Euclidean distances along each route's edges. With only 2 candidate routes (one per bridge), this is equivalent to Dijkstra on the graph but runs in constant time — just two 3-leg sums.

Step ③ then takes the first node on the winning route (BRIDGE_LEFT_P1 in this example) as the movement waypoint for this tick. Once the troop reaches the bridge entry, the is_on_bridge() check passes, bridge routing turns off, and the troop walks directly toward the target.

The decision re-runs every tick. If the target changes (building dies, retarget to a closer enemy, building pull), the graph routes are re-evaluated and the troop may switch bridges. This is correct CR behavior — troops follow their current target, not a pre-committed lane. And because the calculation is self-reinforcing (each step toward a bridge makes that route shorter), troops don't zigzag between bridges (validated by test_bridge_commitment_no_zigzag).

Demo Giant spawned at x=2000 (right half) with only the left princess tower alive. A nearest-to-self heuristic would pick the right bridge — the lane graph picks the left bridge (shorter total path) and commits with zero direction reversals.

Setup: P2 right princess destroyed first. Giant spawned at (2000, −5000).
Left route: Giant → BRIDGE_L_P1 → BRIDGE_L_P2 → target = 19,453
Right route: Giant → BRIDGE_R_P1 → BRIDGE_R_P2 → target = 20,907
Nearest bridge to self: RIGHT (3,100 < 7,100) Graph: LEFT ✓ These disagree.

PASS — Giant walked from x=2000 to x=35 (← LEFT). Zero direction reversals. Graph overruled nearest-to-self by 1,454 units.

5. Swarm cohesion safeguards

Without caps, avoidance causes swarms (Skeleton Army, Barbarians) to fan out wider than real CR. Three safeguards prevent this:

Safeguard	Mechanism	Why needed
2-nearest-ally limit	Only the 2 closest same-team allies contribute to avoidance	Prevents O(N) accumulation in 15-skeleton clusters
Magnitude clamp	‖(a_lat, a_fwd)‖ ≤ 1.0	Caps deflection to ~22°; troops always advance toward target
Collision push cap	Per-entity push ≤ collision_radius per tick	Prevents edge troops in clusters from getting O(N) accumulated pushes

Validated by test: 5 barbarians spawned at the same position in the left lane spread to 3.8 tiles width at tick 40, then self-stabilize — contracting to 3.5 tiles by tick 60 as the shared bridge waypoint pulls them back together. The formation converges rather than diverging, confirming the safeguards work.

Demo 5 Barbarians spawned at (−3000, −6000) separate into a natural pack and converge on the left bridge. Spread peaks at 3.9 tiles then contracts — the safeguards prevent runaway fan-out.

tick width    avg_pair tiles
10       0          0    0.0 ← deploy timer
20     941        609    1.6
30    2329       1429    3.9 ← peak spread
40    2263       1416    3.8 ← contracting
50    2184       1396    3.6
60    2102       1375    3.5 ← self-stabilized

PASS — width < 5 tiles ✓ avg dist < 4.2 tiles ✓ 5/5 alive ✓ Spread decelerating, not exploding.

6. Design constraints data-driven

Constraint	How satisfied
No heuristics or magic numbers	`collision_radius`, `mass`, `speed` from JSON. α = 0.4 is the only tuning parameter.
Deterministic	Entity ID parity for symmetry break. No randomness. Reproducible.
Bridge routing preserved	Avoidance modifies velocity direction, not target. Lane graph is unaffected.
Swarm cohesion	2-nearest limit + magnitude clamp + collision cap.
No regressions	166 assertions across 87 tests pass: elixir, combat timing, towers, death spawns, etc.

7. Validation results

RESULTS: 166 passed, 0 failed out of 166 assertions

Key tests:
  ✓ Collision resolution (same-team troops separate)
  ✓ Swarm cohesion — width, depth, avg pairwise, growth ratio
  ✓ Bridge selection path-based
  ✓ Bridge commitment no zigzag
  ✓ Bridge retarget switches bridge
  ✓ Attack phase timing exact (Knight 14-tick windup)
  ✓ PEKKA windup is 26 ticks
  ✓ 20v20 mass battle (performance)
  + 78 more covering all engine systems