controllers/algorithms/budget_composer.py - master - Vibek/First_Game

controllers/algorithms/budget_composer.py
102 строки6 KB
Vibek
Реализован менеджер волн и новое состояние выбора улучшений
12 июн 2026, 20:36
12 июн 2026, 20:3652b2dcf
"""
Алгоритм 1: BudgetWaveComposer
Комбинаторная оптимизация с ограничениями, рандомизацией и откатом (backtracking).
Генерирует уникальный состав волны, не превышая заданный бюджет.
"""
import random
from typing import List, Dict, Any, Set
from core.config import Config

class BudgetWaveComposer:
    @staticmethod
    def generate_wave(budget: int, wave_index: int, forbidden_hashes: Set[str]) -> List[Dict[str, Any]]:
        """
        Генерирует состав волны.
        :param budget: Доступные очки сложности на текущую волну.
        :param wave_index: Номер текущей волны (для проверки unlock_wave).
        :param forbidden_hashes: Множество хешей уже использованных комбинаций врагов.
        :return: Список словарей вида [{"type": "scout", "count": 2}, ...]
        """
        # 1. Фильтрация доступных врагов для текущей волны
        available_enemies = [
            (enemy_type, stats) 
            for enemy_type, stats in Config.ENEMY_CONFIG.items() 
            if stats["unlock_wave"] <= wave_index
        ]

        if not available_enemies:
            raise ValueError(f"Нет доступных врагов для волны {wave_index}")

        # 2. Гарантированный минимум (обязательные враги)
        wave_composition = {}
        current_cost = 0

        for enemy_type, stats in available_enemies:
            min_req = stats["min_count"]
            if min_req > 0:
                cost = min_req * stats["cost"]
                current_cost += cost
                wave_composition[enemy_type] = min_req

        # Guard Clause: Если бюджет слишком мал даже для обязательных врагов
        if current_cost > budget:
            raise ValueError(f"Бюджет {budget} недостаточен для обязательных врагов волны {wave_index}")

        remaining_budget = budget - current_cost

        # 3. Жадное заполнение с рандомизацией и откатом (Backtracking)
        max_retries = 50  # Защита от бесконечного цикла
        retries = 0

        while remaining_budget > 0 and retries < max_retries:
            # Перемешиваем доступных врагов для рандомизации выбора
            random.shuffle(available_enemies)
            added_this_iteration = False

            for enemy_type, stats in available_enemies:
                cost = stats["cost"]
                max_allowed = stats["max_count"]
                current_count = wave_composition.get(enemy_type, 0)

                # Проверяем: влезает ли в бюджет и не превышен ли лимит
                if remaining_budget >= cost and current_count < max_allowed:
                    wave_composition[enemy_type] = current_count + 1
                    remaining_budget -= cost
                    added_this_iteration = True
                    break  # Переходим к следующей итерации внешнего цикла (снова перемешиваем)

            # Если ни одного врага добавить не удалось (бюджет есть, но лимиты исчерпаны или цены слишком высоки)
            if not added_this_iteration:
                break

            # 4. Проверка уникальности (Хеширование)
            # Сортируем ключи, чтобы ["scout", "storm"] и ["storm", "scout"] дали одинаковый хеш
            sorted_composition = tuple(sorted(wave_composition.items()))
            hash_str = ",".join([f"{etype}:{count}" for etype, count in sorted_composition])

            if hash_str in forbidden_hashes:
                # ОТКАТ (Backtracking): комбинация уже была.
                # Удаляем последнего добавленного врага (упрощенный откат на 1 шаг)
                # Находим врага с count > min_count и уменьшаем его
                rollback_done = False
                for enemy_type, stats in available_enemies:
                    if wave_composition.get(enemy_type, 0) > stats["min_count"]:
                        wave_composition[enemy_type] -= 1
                        remaining_budget += stats["cost"]
                        rollback_done = True
                        break
                
                if not rollback_done:
                    # Если откатить некого (все на минимуме), прерываем, чтобы не зациклиться
                    break
            
            retries += 1

        # Добавляем финальный (уникальный или лучший возможный) хеш в запрещенные
        final_sorted = tuple(sorted(wave_composition.items()))
        final_hash = ",".join([f"{etype}:{count}" for etype, count in final_sorted])
        forbidden_hashes.add(final_hash)

        # 5. Формирование итогового списка для EventBus
        result = [{"type": etype, "count": count} for etype, count in wave_composition.items() if count > 0]
        return result