path: root/src/ch/epfl/xblast/server/GameState.java

package ch.epfl.xblast.server;

import ch.epfl.cs108.Sq;
import ch.epfl.xblast.*;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;


/**
 * GameState representing the current game state.
 *
 * @author Pacien TRAN-GIRARD (261948)
 * @author Timothée FLOURE (257420)
 */
public final class GameState {

    /**
     * The list of player priority order permutations.
     */
    private static final List<List<PlayerID>> PLAYER_PRIORITY_ORDERS = GameState.buildPlayerPriorityOrderList();

    /**
     * The list of bonuses to choose randomly from.
     */
    private static final Block[] RANDOM_BONUSES = new Block[]{Block.BONUS_BOMB, Block.BONUS_RANGE, Block.FREE};

    /**
     * The seed used for random value generation.
     * Constant between executions to make tests reproducible.
     */
    private static final int RANDOM_SEED = 2016;

    /**
     * Pseudo-random source for randomized behaviours.
     */
    private static final Random RANDOM_SOURCE = new Random(GameState.RANDOM_SEED);

    /**
     * Builds and returns the player priority order permutations.
     *
     * @return the list of player priority orders
     */
    private static List<List<PlayerID>> buildPlayerPriorityOrderList() {
        return Lists.permutations(Arrays.asList(PlayerID.values()));
    }

    /**
     * Returns a randomly chosen bonus Block with an equal probability distribution.
     *
     * @return a random bonus block
     */
    private static Block randomBonus() {
        int randomIndex = RANDOM_SOURCE.nextInt(GameState.RANDOM_BONUSES.length);
        return GameState.RANDOM_BONUSES[randomIndex];
    }

    /**
     * Filters the given list of players and returns the lively ones.
     *
     * @param players a list of players
     * @return the list of alive players
     */
    private static List<Player> alivePlayers(List<Player> players) {
        return players.stream()
                .filter(Player::isAlive)
                .collect(Collectors.toList());
    }

    /**
     * Maps the given bombs to their position.
     *
     * @param bombs a list of bombs
     * @return a map of positions and their bombs
     */
    private static Map<Cell, Bomb> bombedCells(List<Bomb> bombs) {
        return bombs.stream()
                .collect(Collectors.toMap(Bomb::position, Function.identity()));
    }

    /**
     * Maps bombs to their owning player ID.
     *
     * @param b the list of bombs
     * @return the mapping
     */
    private static Map<PlayerID, List<Bomb>> mapBombsToPlayers(List<Bomb> b) {
        return b.stream().collect(Collectors.groupingBy(Bomb::ownerId));
    }

    /**
     * Returns a set of cells that contains at least one blast in the given blasts sequences.
     *
     * @param blasts the list of blast sequences
     * @return the set of blasted cells
     */
    private static Set<Cell> blastedCells(List<Sq<Cell>> blasts) {
        return blasts.stream()
                .map(Sq::head)
                .collect(Collectors.toSet());
    }

    /**
     * Computes the next state of a blast.
     *
     * @param blasts0     existing particles
     * @param board0      the game's board
     * @param explosions0 active explosions
     * @return the position of the explosion's particles for the next state.
     */
    private static List<Sq<Cell>> nextBlasts(List<Sq<Cell>> blasts0, Board board0, List<Sq<Sq<Cell>>> explosions0) {
        return Stream.concat(
                blasts0.stream()
                        .filter(b -> board0.blockAt(b.head()).isFree())
                        .map(Sq::tail),
                explosions0.stream()
                        .filter(e -> !e.isEmpty())
                        .map(Sq::head))
                .filter(b -> !b.isEmpty())
                .filter(b -> board0.blockAt(b.head()).isDestructible())
                .collect(Collectors.toList());
    }

    /**
     * Computes and returns the next board state of the given board according to the given events.
     *
     * @param board0          the previous board
     * @param consumedBonuses the set of consumed bonuses
     * @param blastedCells1   the set of newly blasted cells
     * @return the next board
     */
    private static Board nextBoard(Board board0, Set<Cell> consumedBonuses, Set<Cell> blastedCells1) {
        return new Board(Cell.ROW_MAJOR_ORDER.stream()
                .map(c -> GameState.nextBlockSeq(c, board0.blocksAt(c), consumedBonuses, blastedCells1))
                .collect(Collectors.toList()));
    }

    /**
     * Returns the next Block sequence for the given cell according to the current state and given events.
     *
     * @param c               the Cell
     * @param bs0             the previous Block sequence
     * @param consumedBonuses the bonus consumption event
     * @param blastedCells1   the new Cell blast events
     * @return the new Block sequence
     */
    private static Sq<Block> nextBlockSeq(Cell c, Sq<Block> bs0, Set<Cell> consumedBonuses, Set<Cell> blastedCells1) {
        Block b = bs0.head();

        if (consumedBonuses.contains(c) && b.isBonus())
            return Sq.constant(Block.FREE);

        if (blastedCells1.contains(c))
            if (b == Block.DESTRUCTIBLE_WALL)
                return Sq.repeat(Ticks.WALL_CRUMBLING_TICKS, Block.CRUMBLING_WALL)
                        .concat(Sq.constant(GameState.randomBonus()));

            else if (b.isBonus())
                return Sq.repeat(Ticks.BONUS_DISAPPEARING_TICKS, b)
                        .concat(Sq.constant(Block.FREE));

        return bs0.tail();
    }

    /**
     * Computes and returns the next player list given the current one and the given events and states.
     *
     * @param players0          the previous player list
     * @param playerBonuses     the map of player bonuses
     * @param bombedCells1      the set of newly bombed cells
     * @param board1            the newly updated board
     * @param blastedCells1     the set of newly blasted cells
     * @param speedChangeEvents the speed change events
     * @return the next player list
     */
    private static List<Player> nextPlayers(List<Player> players0, Map<PlayerID, Bonus> playerBonuses,
                                            Set<Cell> bombedCells1, Board board1, Set<Cell> blastedCells1,
                                            Map<PlayerID, Optional<Direction>> speedChangeEvents) {

        return players0.stream()
                .map(p -> {
                    Optional<Direction> speedChangeEvent = speedChangeEvents.get(p.id());
                    Direction requestedDirection = speedChangeEvent != null ? speedChangeEvent.orElse(null) : null;
                    return GameState.nextPlayer(p, playerBonuses.get(p.id()), bombedCells1, board1, blastedCells1, requestedDirection);
                })
                .collect(Collectors.toList());
    }

    /**
     * Computes and returns the next State of a Player from the given events.
     *
     * @param player0            the Player
     * @param playerBonus        the optional Bonus to apply to the Player
     * @param bombedCells1       the Set of bombed Cells
     * @param board1             the updated Board
     * @param blastedCells1      the Set of blasted Cells
     * @param requestedDirection the Player's new requested Direction
     * @return the next state of the Player
     */
    private static Player nextPlayer(Player player0, Bonus playerBonus,
                                     Set<Cell> bombedCells1, Board board1, Set<Cell> blastedCells1,
                                     Direction requestedDirection) {

        // 1. Compute the new path
        Sq<Player.DirectedPosition> path1 = GameState.nextPath(player0, requestedDirection);

        // 2. Check possible collisions and update the Sequence if necessary
        Sq<Player.DirectedPosition> directedPos1 = GameState.handleCollisions(player0, path1, board1, bombedCells1);

        // 3. Apply damages and generate a new LifeState Sequence
        Sq<Player.LifeState> lifeStates1 = GameState.nextLifeState(player0, directedPos1, blastedCells1);

        // 4. Create the new player given the new parameters
        Player p1 = new Player(player0.id(), lifeStates1, directedPos1, player0.maxBombs(), player0.bombRange());

        // 5. Update the capacities of the player given the possible bonus
        if (!Objects.isNull(playerBonus))
            p1 = playerBonus.applyTo(p1);

        return p1;
    }

    /**
     * Returns the next Direction of the Player according to the constraints.
     *
     * @param p0           the Player
     * @param requestedDir the requested new Direction
     * @return the next Direction
     */
    private static Direction nextDirection(Player p0, Direction requestedDir) {
        return !Objects.isNull(requestedDir) ? requestedDir : p0.direction();
    }

    /**
     * Generates the new Sequence of DirectedPositions.
     *
     * @param p0           the Player
     * @param requestedDir the new requested Direction
     * @return the next path
     */
    private static Sq<Player.DirectedPosition> nextPath(Player p0, Direction requestedDir) {
        Sq<Player.DirectedPosition> path1 = GameState.newPath(
                Player.DirectedPosition.moving(p0.directedPositions().head()),
                GameState.nextDirection(p0, requestedDir));

        return p0.lifeState().canMove() ? path1.tail() : path1;
    }

    /**
     * Computes the new path to follow according to the Player's wishes and the Board constraints.
     *
     * @param p0     the current path
     * @param newDir the new requested Direction
     * @return the new path
     */
    private static Sq<Player.DirectedPosition> newPath(Sq<Player.DirectedPosition> p0, Direction newDir) {
        if (p0.head().direction().isPerpendicularTo(newDir))
            return GameState.pivotPath(p0, newDir);
        else
            return Player.DirectedPosition.moving(new Player.DirectedPosition(p0.head().position(), newDir));
    }

    /**
     * Builds and returns a pivot path reaching the next pivot SubCell and then rotating to the given Direction.
     *
     * @param p0     the initial path
     * @param newDir the new Direction to follow when possible
     * @return the pivot path
     */
    private static Sq<Player.DirectedPosition> pivotPath(Sq<Player.DirectedPosition> p0, Direction newDir) {
        SubCell nextCentral = GameState.nextCentralPosition(p0);

        return GameState
                .pathToNextCentralPosition(p0)
                .concat(Player.DirectedPosition.moving(new Player.DirectedPosition(nextCentral, newDir)));
    }

    /**
     * Returns the path to the next central SubCell.
     *
     * @param p the path to follow
     * @return the truncated path
     */
    private static Sq<Player.DirectedPosition> pathToNextCentralPosition(Sq<Player.DirectedPosition> p) {
        return p.tail()
                .takeWhile(dp -> dp.position().isCentral());
    }

    /**
     * Searches for and returns the next central SubCell reachable following the given path.
     *
     * @param p the path to follow
     * @return the next central SubCell
     */
    private static SubCell nextCentralPosition(Sq<Player.DirectedPosition> p) {
        return p.tail()
                .findFirst(dp -> dp.position().isCentral())
                .position();
    }

    /**
     * Checks for possible collisions and update the path if necessary.
     *
     * @param player0       the Player
     * @param projectedPath the current path projection
     * @param board1        the updated Board
     * @param bombedCells1  the Set of bombed Cell-s
     * @return the corrected path
     */
    private static Sq<Player.DirectedPosition> handleCollisions(Player player0,
                                                                Sq<Player.DirectedPosition> projectedPath,
                                                                Board board1, Set<Cell> bombedCells1) {

        Cell projectedCell = GameState.nextCentralPosition(projectedPath).containingCell();
        if (GameState.isColliding(player0, projectedCell, board1, bombedCells1))
            return Sq.repeat(1, player0.directedPositions().head())
                    .concat(projectedPath);

        return projectedPath;
    }

    /**
     * Returns T(the player is colliding with an object).
     *
     * @param player0       the Player
     * @param projectedCell the projected next Cell
     * @param board1        the updated Board
     * @param bombedCells1  the Set of bombed Cell-s
     * @return T(the player is colliding with an object)
     */
    private static boolean isColliding(Player player0, Cell projectedCell, Board board1, Set<Cell> bombedCells1) {
        if (!board1.blockAt(projectedCell).canHostPlayer())
            return true;

        if (bombedCells1.contains(projectedCell) && projectedCell.equals(player0.position().containingCell()))
            if (player0.position().distanceToCentral() <= Board.BOMB_BLOCKING_DISTANCE)
                return true;

        return false;
    }

    /**
     * Applies damages and generate a new LifeState sequence.
     *
     * @param player0            the Player
     * @param directedPositions1 the DirectedPosition sequence
     * @param blastedCells1      the Set of blasted Cell-s
     * @return the next LifeState sequence
     */
    private static Sq<Player.LifeState> nextLifeState(Player player0, Sq<Player.DirectedPosition> directedPositions1,
                                                      Set<Cell> blastedCells1) {

        Cell currentCell = directedPositions1.head().position().containingCell();

        if (player0.isVulnerable() && blastedCells1.contains(currentCell))
            return player0.statesForNextLife();
        else
            return player0.lifeStates().tail();
    }

    /**
     * Computes and returns the next state of the given explosion list.
     *
     * @param explosions0 the previous explosion state
     * @return the next explosion state
     */
    private static List<Sq<Sq<Cell>>> nextExplosions(List<Sq<Sq<Cell>>> explosions0) {
        return explosions0.stream()
                .map(Sq::tail)
                .filter(s -> !s.isEmpty())
                .collect(Collectors.toList());
    }

    /**
     * Returns a list of exploding bombs (reached by a blast or consumed fuse).
     *
     * @param bombs        the list of bombs
     * @param blastedCells the set of blasted cells
     * @return the list of exploding bombs
     */
    private static List<Bomb> explodingBombs(List<Bomb> bombs, Set<Cell> blastedCells) {
        return bombs.stream()
                .filter(b -> blastedCells.contains(b.position()) || b.fuseLength() <= 1)
                .collect(Collectors.toList());
    }

    /**
     * Computes the consumption of the bombs.
     *
     * @param bombs0         the list of bombs
     * @param explodingBombs the list of exploding bombs
     * @return the new bombs states
     */
    private static List<Bomb> nextBombs(List<Bomb> bombs0, List<Bomb> explodingBombs) {
        return bombs0.stream()
                .filter(b -> !explodingBombs.contains(b))
                .map(b -> new Bomb(b.ownerId(), b.position(), b.fuseLengths().tail(), b.range()))
                .collect(Collectors.toList());
    }

    /**
     * Computes and returns the list of newly dropped bombs by players according to the given player states and events.
     * Given bomb drop events must be conflict-free.
     *
     * @param players0       the previous player states
     * @param bombDropEvents the bomb drop events
     * @param bombs0         the previous bomb state
     * @return the newly dropped bombs
     */
    private static List<Bomb> newlyDroppedBombs(List<Player> players0, Set<PlayerID> bombDropEvents, List<Bomb> bombs0) {
        HashSet<Cell> bombedCells = new HashSet<>(GameState.bombedCells(bombs0).keySet());
        Map<PlayerID, List<Bomb>> bombOwnerMap = GameState.mapBombsToPlayers(bombs0);
        List<Bomb> bombs1 = new ArrayList<>(bombs0);

        for (Player p : GameState.alivePlayers(players0)) {
            if (!bombDropEvents.contains(p.id())) continue;
            if (bombedCells.contains(p.position().containingCell())) continue;

            List<Bomb> ownedBombs = bombOwnerMap.get(p.id());
            if (ownedBombs != null && ownedBombs.size() >= p.maxBombs()) continue;

            Bomb b = new Bomb(p.id(), p.position().containingCell(), Ticks.BOMB_FUSE_TICKS - 1, p.bombRange());
            bombedCells.add(b.position());
            bombs1.add(b);
        }

        return bombs1;
    }

    private final int ticks;
    private final Board board;
    private final List<Player> players;
    private final List<Bomb> bombs;
    private final List<Sq<Sq<Cell>>> explosions;
    private final List<Sq<Cell>> blasts;

    /**
     * Instantiates a new GameState.
     *
     * @param ticks      the tick corresponding to the state
     * @param board      the game's board
     * @param players    list of the players
     * @param bombs      list of the bombs
     * @param explosions list of the explosions
     * @param blasts     list of particle blasts
     * @throws IllegalArgumentException if ticks is negative or players does not contains 4 players.
     * @throws NullPointerException     if any element except ticks is null.
     */
    public GameState(int ticks, Board board, List<Player> players, List<Bomb> bombs, List<Sq<Sq<Cell>>> explosions, List<Sq<Cell>> blasts) {
        this.ticks = ArgumentChecker.requireNonNegative(ticks);
        this.board = Objects.requireNonNull(board);

        if (players.size() != PlayerID.values().length) throw new IllegalArgumentException();
        this.players = new ArrayList<>(players);

        this.bombs = new ArrayList<>(Objects.requireNonNull(bombs));
        this.explosions = new ArrayList<>(Objects.requireNonNull(explosions));
        this.blasts = new ArrayList<>(Objects.requireNonNull(blasts));
    }

    /**
     * Instantiates a new (clean) GameState.
     *
     * @param board   the board
     * @param players list of the players
     */
    public GameState(Board board, List<Player> players) {
        this(0, board, players, new ArrayList<>(), new ArrayList<>(), new ArrayList<>());
    }

    /**
     * @return the tick related to the state.
     */
    public int ticks() {
        return this.ticks;
    }

    /**
     * Returns T(the game is over).
     *
     * @return true if all the players are dead or if the game reached the time limit
     */
    public boolean isGameOver() {
        return this.alivePlayers().size() <= this.players().size() - 1 || this.ticks >= Ticks.TOTAL_TICKS;
    }

    /**
     * Return the remaining time.
     *
     * @return the remaining game time (in seconds)
     */
    public double remainingTime() {
        return ((double) (Ticks.TOTAL_TICKS - this.ticks)) / Ticks.TICKS_PER_SECOND;
    }

    /**
     * Returns the winner of the game.
     *
     * @return the ID of the player who won the game.
     */
    public Optional<PlayerID> winner() {
        if (this.alivePlayers().size() == 1)
            return Optional.of(this.alivePlayers().get(0).id());
        else
            return Optional.empty();
    }

    /**
     * @return the game board
     */
    public Board board() {
        return this.board;
    }

    /**
     * @return the players
     */
    public List<Player> players() {
        return this.players;
    }

    /**
     * Returns the alive players.
     *
     * @return a list of the alive players
     */
    public List<Player> alivePlayers() {
        return GameState.alivePlayers(this.players);
    }

    /**
     * Returns a mapping of Cells and their Bomb.
     *
     * @return the map of bombs
     */
    public Map<Cell, Bomb> bombedCells() {
        return GameState.bombedCells(this.bombs);
    }

    /**
     * Returns the set of cells which contains at least one explosion particle.
     *
     * @return the set of blasted cells
     */
    public Set<Cell> blastedCells() {
        return GameState.blastedCells(this.blasts);
    }

    /**
     * Computes and returns the game state for the next tick, given the current state and the given events.
     *
     * @param speedChangeEvents the speed change events
     * @param bombDropEvents    the bomb drop events
     * @return the next game state
     */
    public GameState next(Map<PlayerID, Optional<Direction>> speedChangeEvents, Set<PlayerID> bombDropEvents) {
        // 1. blasts evolution
        List<Sq<Cell>> blasts1 = GameState.nextBlasts(this.blasts, this.board, this.explosions);

        // 2. board evolution
        Set<Cell> blastedCells1 = GameState.blastedCells(blasts1);
        Map<Cell, PlayerID> consumedBonuses = this.consumedBonuses();
        Board board1 = GameState.nextBoard(this.board, consumedBonuses.keySet(), blastedCells1);

        // 3. existing explosions evolution
        List<Sq<Sq<Cell>>> explosions1 = GameState.nextExplosions(this.explosions);

        // 4.1. existing bombs evolution
        Set<Cell> blastedCells0 = this.blastedCells();
        List<Bomb> explodingBombs = GameState.explodingBombs(this.bombs, blastedCells0);
        List<Bomb> existingBombs = GameState.nextBombs(this.bombs, explodingBombs);

        // 4.2. subsequent explosions addition
        explodingBombs.forEach(b -> explosions1.addAll(b.explosion()));

        // 4.3. newly dropped bombs addition
        Set<PlayerID> topPriorityBombDropEvents = discardConflictingBombDropEvents(bombDropEvents);
        List<Bomb> bombs1 = GameState.newlyDroppedBombs(this.players, topPriorityBombDropEvents, existingBombs);

        // 5. players evolution
        Map<PlayerID, Bonus> playerBonuses = mapPlayersToBonuses(consumedBonuses);
        Set<Cell> bombedCells1 = GameState.bombedCells(bombs1).keySet();
        List<Player> players1 = GameState.nextPlayers(
                this.players, playerBonuses, bombedCells1, board1, blastedCells1, speedChangeEvents);

        return new GameState(this.ticks + 1, board1, players1, bombs1, explosions1, blasts1);
    }

    /**
     * Returns the current player priority order permutation.
     *
     * @return the player priority order
     */
    private List<PlayerID> currentPlayerPriorityOrder() {
        int priorityIndex = this.ticks % GameState.PLAYER_PRIORITY_ORDERS.size();
        return GameState.PLAYER_PRIORITY_ORDERS.get(priorityIndex);
    }

    /**
     * Resolves a conflict according to the current priority order.
     *
     * @param claimants the list of claimants
     * @return the highest priority player
     */
    private PlayerID resolveConflict(List<PlayerID> claimants) {
        if (claimants == null || claimants.isEmpty()) return null;

        return this.currentPlayerPriorityOrder().stream()
                .filter(claimants::contains)
                .findFirst().orElse(null);
    }

    /**
     * Resolves a conflict according to the current priority order.
     *
     * @param claimants the list of claimants
     * @return the highest priority player
     */
    public Player resolvePlayerConflict(List<Player> claimants) {
        if (claimants == null || claimants.isEmpty()) return null;

        Map<PlayerID, Player> claimantsMap = claimants.stream()
                .collect(Collectors.toMap(Player::id, Function.identity()));

        List<PlayerID> claimantsIDs = claimants.stream()
                .map(Player::id).collect(Collectors.toList());

        return claimantsMap.get(this.resolveConflict(claimantsIDs));
    }

    /**
     * Returns a mapping of players from their location.
     *
     * @param players a list of players to map
     * @return the location->player mapping
     */
    public Map<Cell, List<Player>> mapPlayersCells(List<Player> players) {
        return players.stream()
                .collect(
                        Collectors.groupingBy(p -> p.position().containingCell(),
                                Collectors.mapping(Function.identity(), Collectors.toList())));
    }

    /**
     * Returns a mapping of top-priority player from their location.
     * Conflicts are resolved using the current turn's players priority order.
     *
     * @param players a list of players to map
     * @return the location->top-priority player mapping
     */
    private Map<Cell, Player> mapTopPriorityPlayerCells(List<Player> players) {
        return this.mapPlayersCells(players).entrySet().stream()
                .collect(Collectors.toMap(
                        Map.Entry::getKey,
                        e -> resolvePlayerConflict(e.getValue())));
    }

    /**
     * Returns a mapping of location of consumed bonuses and their top-priority claimant.
     *
     * @return the bonus-location->player mapping
     */
    private Map<Cell, PlayerID> consumedBonuses() {
        return this.mapTopPriorityPlayerCells(
                this.alivePlayers().stream()
                        .filter(p -> p.position().isCentral())
                        .filter(p -> this.board.blockAt(p.position().containingCell()).isBonus())
                        .collect(Collectors.toList()))
                .entrySet().stream()
                .collect(Collectors.toMap(Map.Entry::getKey, e -> e.getValue().id()));
    }

    /**
     * Returns a mapping of players and their newly acquired bonus.
     *
     * @param consumedBonuses a mapping of bonus location and their claimants
     * @return the player->bonus mapping
     */
    private Map<PlayerID, Bonus> mapPlayersToBonuses(Map<Cell, PlayerID> consumedBonuses) {
        return consumedBonuses.entrySet().stream()
                .collect(Collectors.toMap(
                        Map.Entry::getValue,
                        e -> this.board.blockAt(e.getKey()).associatedBonus()));
    }

    /**
     * Returns a conflict-free set a player bomb dropping events.
     *
     * @param bombDropEvents the bomb drop events to filter
     * @return the conflict-free set of bomb drop events
     */
    private Set<PlayerID> discardConflictingBombDropEvents(Set<PlayerID> bombDropEvents) {
        return this.mapTopPriorityPlayerCells(
                this.alivePlayers().stream()
                        .filter(p -> bombDropEvents.contains(p.id()))
                        .collect(Collectors.toList()))
                .values().stream()
                .map(Player::id)
                .collect(Collectors.toSet());
    }

    @Override
    public String toString() {
        return "GameState{" +
                "ticks=" + ticks +
                ", board=" + board +
                ", players=" + players +
                ", bombs=" + bombs +
                ", explosions=" + explosions +
                ", blasts=" + blasts +
                '}';
    }

}