// This code was used in We're in the Same Boat.
// It is a C# class that implements the A* algorithmon for a puzzle game that's built using the command pattern.
// It can find the optimal set of movements to solve a river crossing puzzle. The logic of the game is completely
// decoupled from the solver, making it much easier to maintain.

namespace Tools
{
    public class Solver
    {
        public static State SolveWidth(GameLogic game, bool useHeuristic = false)
        {
            List openList = new List(); // List of states to explore 
            List closedList = new List(); // List of states that have already been explored

            State current = game.GetCurrentState();

            openList.Add(current); // Exploration starts with current state

            while (openList.Count > 0)
            {
                if (useHeuristic)
                    openList = openList.OrderByDescending(t => t.F).ToList();

                // Sets game state
                State previous = current;
                current = openList[0];

                SetState(current, previous, game);

                openList.Remove(current);
                closedList.Add(current);

                // Checks win and brakes loop if true
                if (game.Win) break;

                // Adds to the open list all of the new possible states derived from the current state
                ExpandNeighbours(current, game, openList, closedList);
            }

            if (!game.Win)
            {
                return null;
            }

            // Reset game to initial state
            State aux = current;
            while (aux.PreviousState != null)
            {
                aux = aux.PreviousState;
                game.Undo(true);
            }

            return current;
        }

        private static void SetState(State newState, State current, GameLogic game)
        {
            // Retrieve all the states previous to the new one
            List states = new List();
            State aux = newState;
            while (aux != null)
            {
                states.Add(aux);
                aux = aux.PreviousState;
            }

            // Reverse order
            states.Reverse();

            // Undo game until it reaches a state contained in the previous list
            int numberOfUndos = 0;
            aux = current;
            while (aux != null && !states.Contains(aux))
            {
                game.Undo(true);
                aux = aux.PreviousState;
                numberOfUndos++;
            }

            // The fisrt state found in the previous loop becomes the initial index of the next loop
            int startingPoint = aux == null ? 0 : states.IndexOf(aux);

            // Execute every command from every state to obtain the same state in the game
            for (int i = startingPoint + 1; i < states.Count; i++)
            {
                game.AddCommand(states[i].Command, true);
            }
        }

        private static void ExpandNeighbours(State current, GameLogic game, List openList, List closedList)
        {
            //If boat has transportables it will try to unload in current island
            if (current.BoatOccupiedSeats > 0)
            {
                for (int i = 0; i < current.BoatTransportables.Length; i++)
                {
                    Transportable transportable = current.BoatTransportables[i];
                    // Game logic is completely decoupled. The solver doesn't need to know how does the game work in order to work.
                    // It just tries to make every possible move and asks if it was valid.
                    if (transportable == null || !game.UnloadFromBoat(transportable, true))
                    {
                        continue;
                    }

                    TryAddNewState(current, game, openList, closedList);

                    if (game.Win)
                    {
                        openList.Insert(0, openList[openList.Count - 1]);
                    }

                    game.Undo(true);
                }
            }

            //If boat has empty seats it will load new transportables
            if (current.BoatOccupiedSeats < current.BoatCapacity)
            {
                for (int i = 0; i < current.CurrentIsland.Transportables.Count; i++)
                {
                    Transportable transportable = current.CurrentIsland.Transportables[i];
                    if (transportable == null || !game.LoadOnBoat(transportable, true))
                    {
                        continue;
                    }

                    TryAddNewState(current, game, openList, closedList);

                    game.Undo(true);
                }
            }

            //Boat will traver to another island if possible
            for (int i = current.Islands.Count - 1; i >= 0; i--)
            {
                State.IslandState island = current.Islands[i];
                if (island.islandRef == current.CurrentIsland || !game.MoveBoatToIsland(island.islandRef, true))
                    continue;

                TryAddNewState(current, game, openList, closedList);

                game.Undo(true);
            }
        }

        private static void TryAddNewState(State current, GameLogic game, List openList, List closedList)
        {
            State newState = game.GetCurrentState();

            // If the state is considered a fail or has already been explored, it gets omitted
            if (!(game.Fail || openList.Contains(newState) || closedList.Contains(newState)))
            {
                newState.PreviousState = current;
                openList.Add(newState);
            }
        }
    }
}