Theta*

Theta* Search is Informed for the same reason as A* Search: expand by cost-so-far plus distance-to-exit. The extra knowledge is geometry — if a neighbour can see an ancestor, parent it there and skip intermediate waypoints.

Any-phase death cells join the obstacle set for line-of-sight checks, so shortcuts cannot cut through known kill tiles.

Run an A* Search-like loop on the spatial grid. When expanding a neighbour, try parenting it to the current node's parent if line of sight is clear; otherwise parent to the current node. Reconstruct the waypoint chain when the exit pops.

Rasterise each waypoint segment with line cells, expand any diagonal Bresenham steps into orthogonal neighbours, then walk that list with rising ticks while obeying "x,y,phase" bans.

Cone cells become "x,y,phase" bans. The next Theta* Search rebuilds spatial walls from those bans and replans shortcuts around them.

Because rasterisation re-checks the calendar tick by tick, a waypoint chain that looked clear in space can still fail if a phase lands wrong — then the space-time repair between waypoints has to snake around.