Implement auto mic assignment algorithm with distance-based cost optimization

[Tim020]

Overview

Implement an intelligent auto-assignment algorithm for theatrical microphones that minimizes the cost of mic swaps between scenes, with a distance-based cost function where adjacent scenes have higher swap costs than distant scenes.

User Requirements

1. Distance-based cost: Swapping mics between adjacent scenes (S1→S2) is MORE expensive than distant scenes (S1→S3)
2. Over-allocation: When scenes have more speaking characters than mics, prioritize by line count
3. Mic sharing: Optimize for characters with few lines to share mics across non-overlapping scenes
4. Character groups: Treat each group member individually (not as a single allocation)
5. Intervals: Scene groups separated by intervals are independent - reassignment at intervals is free

Algorithm Design (Character-First Holistic Approach)

Core Principle

CRITICAL: This is a "fill in the blanks" algorithm, NOT "regenerate everything"

• Existing manual allocations are PRESERVED (immutable constraints)
• Algorithm only suggests allocations for unassigned (character, scene) pairs
• Existing allocations influence new assignments (e.g., continuity, swap costs)

Cost Function

def swap_cost(scene_index_1: int, scene_index_2: int) -> float:
    """
    Inverted distance cost: closer scenes = HIGHER cost.
    Encourages mic sharing across non-adjacent scenes.
    """
    distance = abs(scene_index_1 - scene_index_2)
    if distance == 0:
        return 0.0  # Same scene
    return 100.0 / distance  # Adjacent (d=1) = 100, distant (d=5) = 20

Why Character-First (Not Scene-First)?

Problem with scene-by-scene greedy:

• Character has 1 line in Scene 1, 20 lines in Scene 2
• Scene 1 is over-allocated → character doesn't get mic
• Scene 2 arrives → forced high-cost swap (distance=1, cost=100)
• Short-sighted: doesn't see character's importance globally

Character-first solution:

• Sort characters by TOTAL line count across all scenes
• High-priority characters (more total lines) get first pick of mics
• Character with "1 line in S1, 20 in S2" = 21 total lines → high priority
• They'll get a mic assigned for both scenes before low-priority characters

Implementation Phases

Phase 1: Load Existing Allocations

Load all existing manual allocations from database and mark them as immutable constraints.

Phase 2: Build Unallocated Character-Scene Pairs

Query database for character appearances, EXCLUDING pairs with existing allocations. Calculate total line count per character across all unallocated scenes.

Phase 3: Character Priority Ordering

Sort characters by total line count (descending). Characters with more total lines get first pick of microphones.

Phase 4: Assign Mics Per Character

For each character in priority order, get all scenes where they need a mic (chronological order) and assign the best mic for each scene.

Phase 5: Optimal Mic Selection

For each (character, scene) pair needing assignment, score all available mics using:

Scoring criteria (lower score = better):

• ✅ Manual allocation continuity: Mic manually assigned to this character elsewhere (-100)
• ✅ Auto-assignment continuity: Mic auto-assigned to this character earlier (-50)
• ❌ Swap cost penalty: Sum of swap_cost() for each use by different character

Phase 6: Return Suggestions (NOT Persist)

CRITICAL: This is a /suggest endpoint - it returns proposals, doesn't modify the database.

Return format matches the PATCH /show/microphones/allocations payload structure.

Frontend workflow:

1. User clicks "Auto-Allocate" in UI
2. POST /show/microphones/suggest → returns suggestions + hints
3. UI displays suggestions (highlighted as "new" vs "existing")
4. User reviews, can manually tweak
5. User clicks "Accept" → PATCH /show/microphones/allocations with the suggested payload
6. DB is updated only when user accepts

Response Format

Success Response (Always 200 - Best Effort)

{
  "allocations": {
    "1": {  // mic_id
      "5": 12,  // scene_id: character_id
      "6": 12,
      "7": 15
    },
    "2": {
      "5": 15,
      "6": 18,
      "7": 18
    }
  },
  "new_suggestions_count": 42,
  "existing_allocations_count": 18,
  "hints": [
    {
      "character_id": 22,
      "character_name": "Ensemble Member 3",
      "scene_id": 8,
      "scene_name": "Finale",
      "reason": "No available microphones in this scene"
    }
  ]
}

Notes:

• allocations format matches PATCH /show/microphones/allocations payload (can be directly sent to update endpoint)
• Includes BOTH existing allocations AND new suggestions (complete picture)
• hints array lists characters that couldn't be assigned
• Always returns 200 (even if some characters unassigned) - this is a suggestion system

File Modifications

Primary Implementation

File: server/controllers/api/show/microphones.py

Changes needed (starting at line 312):

1. Import additional models: Script, ScriptRevision, ScriptLine, ScriptLinePart, CharacterGroup, ScriptCuts
2. Implement helper functions:
   • collect_character_appearances() - Query DB for character/scene/line count data
   • assign_microphones_to_scene_group() - Character-first assignment algorithm
   • find_best_mic() - Optimal mic selection with cost function
   • calculate_mic_score() - Scoring logic
   • swap_cost() - Distance-based cost function
3. Update MicrophoneAutoAssignmentController.post() method

Edge Cases & Validation

Pre-flight Validation

• No microphones in show → Return 400 error
• No script or revision → Return 400 error
• No acts/scenes in show → Return 400 error

Best-Effort Handling

Algorithm makes best-effort suggestions. If some characters can't be assigned (over-capacity), they're listed in hints/warnings.

Testing Considerations

1. Test holistic prioritization: Character with 1 line in S1, 20 in S2 gets mic in both scenes before character with 10 total lines
2. Test existing allocation preservation: Create manual allocations → run algorithm → verify manual allocations unchanged
3. Test existing allocation influence: Manual allocation of Mic1 to CharA in S1 → algorithm prefers Mic1 for CharA in S2 (continuity bonus)
4. Test distance cost: Verify scenes 1↔3 swap costs less than 1↔2
5. Test character groups: Each member gets individual assignment
6. Test script cuts: Cut lines not counted in line totals
7. Test intervals: Assignments independent across interval boundaries

Algorithm Complexity

• Time: O(G × S × C × M) where G=scene groups, S=scenes, C=characters, M=mics
• Typical runtime: <100ms for standard shows
• Space: O(S × C) for appearance data

Key Reference Files

• server/controllers/api/show/cast.py:186-205 - Line counting pattern with cuts
• server/models/mics.py - MicrophoneAllocation model
• server/models/script.py - ScriptLine, ScriptLinePart, ScriptCuts
• server/controllers/api/show/microphones.py:268-316 - Existing controller skeleton