#include "GridNavigatorAutomatic.h"

GridNavigatorAutomatic::GridNavigatorAutomatic() : GridNavigator()
{
}
// A* Algorithm Probed
void GridNavigatorAutomatic::Navigate()
{
    const int SIZE = 20;
    const int INF = 1000000;

    // From the maze generation code:
    // player starts at (1, 18)
    // target starts at (18, 1)
    const int startX = 1;
    const int startY = 18;
    const int targetX = 18;
    const int targetY = 1;

    // Arrays hold the search state for A*
    int known[SIZE][SIZE]; //What has been discovered about the maze so far.

    int gScore[SIZE][SIZE]; // The movement cost from start
    int fScore[SIZE][SIZE]; // Estimate total cost 
	bool closed[SIZE][SIZE]; // Marks nodes that have been evaluated
	int prevX[SIZE][SIZE]; // Previous node tracking
	int prevY[SIZE][SIZE]; // Previous node tracking

    // Prepares the grid for probed A* search.
    // Marks walls immediately and resets so that search starts with no explored routes

    for (int y = 0; y < SIZE; y++)
    {
        for (int x = 0; x < SIZE; x++)
        {
            // Outer border is always wall
            if (x == 0 || x == SIZE - 1 || y == 0 || y == SIZE - 1)
            {
                known[y][x] = 1;
            }
            else
            {
                known[y][x] = 0;
            }

            gScore[y][x] = INF;
            fScore[y][x] = INF;
            closed[y][x] = false;
            prevX[y][x] = -1;
            prevY[y][x] = -1;
        }
    }

	// Start and target are definitely accessible squares.
    known[startY][startX] = 2;
    known[targetY][targetX] = 2;
	// Represents one node in the open list for A* search. Each node contains its coordinates and its fScore.
    struct Node
    {
        int x;
        int y;
        int f;
    };
	// The open list is a simple array of nodes. Implemented with a simple array.
    Node openList[SIZE * SIZE * 4];
    int openCount = 0;

	// Heuristic function for A* search. Uses Manhattan distance to estimate the cost from a node to the target.
    auto heuristic = [&](int x, int y)
        {
            return abs(targetX - x) + abs(targetY - y);
        };
	// Adds a node to the open list with its coordinates and fScore.
    auto pushNode = [&](int x, int y, int f)
        {
            openList[openCount].x = x;
            openList[openCount].y = y;
            openList[openCount].f = f;
            openCount++;
        };
	// Removes and returns the node with the lowest fScore from the open list. 
    // This is a linear search through the open list to find the node with the lowest fScore.
    auto popLowest = [&]() -> Node
        {
            int bestIndex = 0;

            for (int i = 1; i < openCount; i++)
            {
                if (openList[i].f < openList[bestIndex].f)
                {
                    bestIndex = i;
                }
            }

            Node best = openList[bestIndex];
            openCount--;
            openList[bestIndex] = openList[openCount];

            return best;
        };
    // This is the probed part of the A* search.
	// It checks if a square has been discovered yet. If not, it queries the grid to find out if it's a wall or a possible place to move to.
	// Once discovered, it marks the square as known.
    auto ensureKnown = [&](int x, int y)
        {
            if (known[y][x] != 0)
            {
                return;
            }

            griditem square = grid->GetGridSquare(x, y);

            if (square == griditem::wall)
            {
                known[y][x] = 1;
            }
            else
            {
                known[y][x] = 2;
            }
        };
	// Initialises the search from the start node.
    gScore[startY][startX] = 0;
    fScore[startY][startX] = heuristic(startX, startY);
    pushNode(startX, startY, fScore[startY][startX]);

    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };



	// Main A* search loop.
	// An iteration takes the node with the lowest fScore from the open list, skips if closed, marks it closed otherwise.
    // Then, it moves onto closest squares.
	// For each closest sqaure, A* checks if it is a wall, closed, or unknown. If unknown, it probes the grid to find out what it is.
    // The loop combines the path cost with the Manhattan estimate.
    while (openCount > 0)
    {
        Node current = popLowest();
        int x = current.x;
        int y = current.y;

        if (closed[y][x])
        {
            continue;
        }

        closed[y][x] = true;

        if (x == targetX && y == targetY)
        {
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= SIZE || ny < 0 || ny >= SIZE)
            {
                continue;
            }

            ensureKnown(nx, ny);

            if (known[ny][nx] == 1)
            {
                continue;
            }

            if (closed[ny][nx])
            {
                continue;
            }

            int tentativeG = gScore[y][x] + 1;

            if (tentativeG < gScore[ny][nx])
            {
                gScore[ny][nx] = tentativeG;
                fScore[ny][nx] = tentativeG + heuristic(nx, ny);
                prevX[ny][nx] = x;
                prevY[ny][nx] = y;
                pushNode(nx, ny, fScore[ny][nx]);
            }
        }
    }
    // If target has no gScore after search, then this algorithm did not find a path.
    if (gScore[targetY][targetX] == INF)
    {
        return;
    }

	// These variables are used to reconstruct the path from the target.
	// A* stores the previous node for each node in the prevX and prevY arrays. This loop traces back from the target to the start, building a path of move directions.
    movedirection path[SIZE * SIZE];
    int pathLength = 0;

    int currentX = targetX;
    int currentY = targetY;
    
    while (!(currentX == startX && currentY == startY))
    {
        int parentX = prevX[currentY][currentX];
        int parentY = prevY[currentY][currentX];

        if (parentX == -1 || parentY == -1)
        {
            return;
        }

        if (currentX == parentX && currentY == parentY - 1)
        {
            path[pathLength] = movedirection::up;
        }
        else if (currentX == parentX && currentY == parentY + 1)
        {
            path[pathLength] = movedirection::down;
        }
        else if (currentX == parentX - 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::left;
        }
        else if (currentX == parentX + 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::right;
        }

        pathLength++;
        currentX = parentX;
        currentY = parentY;
    }
	// This portion of code executes the moves in reverse order to navigate from the start to the target.
    for (int i = pathLength - 1; i >= 0; i--)
    {
        moveresults mr = grid->MovePlayer(path[i]);

        if (mr == moveresults::complete)
        {
            break;
        }
    }
}



////A* with Manhattan Distance
void GridNavigatorAutomatic::Navigate()
{
	// Fixed values for the grid size and a large number representing infinity.
    const int SIZE = 20;
    const int INF = 1000000;

    // Read the whole maze once
    griditem** maze = grid->GetGrid();
	// Stores the coordinates of the player and target. 
    int startX = -1, startY = -1;
    int targetX = -1, targetY = -1;

    // Find start and target positions
    for (int y = 0; y < SIZE; y++)
    {
        for (int x = 0; x < SIZE; x++)
        {
            if (maze[y][x] == griditem::player)
            {
                startX = x;
                startY = y;
            }
            else if (maze[y][x] == griditem::target)
            {
                targetX = x;
                targetY = y;
            }
        }
    }
    // Stops if code failed to find valid start or target.
    if (startX == -1 || targetX == -1)
    {
        return;
    }
    // As the second A* algorithm, this creates the main A* tracking arrays.
    int gScore[SIZE][SIZE];
    int fScore[SIZE][SIZE];
    bool closed[SIZE][SIZE];
    int prevX[SIZE][SIZE];
    int prevY[SIZE][SIZE];
    // Initialises the arrays.
    for (int y = 0; y < SIZE; y++)
    {
        for (int x = 0; x < SIZE; x++)
        {
            gScore[y][x] = INF;
            fScore[y][x] = INF;
            closed[y][x] = false;
            prevX[y][x] = -1;
            prevY[y][x] = -1;
        }
    }
    // Defines the node structure.
    struct Node
    {
        int x;
        int y;
        int f;
    };
	// Creates an openList for nodes. Tracks nodes that are yet to be evaluated.
    Node openList[SIZE * SIZE * 4];
    int openCount = 0;
	// Defines the heuristic function for A* search. Uses Manhattan distance to estimate the cost from a node to the target.
    auto heuristic = [&](int x, int y)
        {
            return abs(targetX - x) + abs(targetY - y);
        };
    // Creates an openList for future searches
    auto pushNode = [&](int x, int y, int f)
        {
            openList[openCount].x = x;
            openList[openCount].y = y;
            openList[openCount].f = f;
            openCount++;
        };
    // Selects and removes the node using the lowest fscore.
    auto popLowest = [&]() -> Node
        {
            int bestIndex = 0;

            for (int i = 1; i < openCount; i++)
            {
                if (openList[i].f < openList[bestIndex].f)
                {
                    bestIndex = i;
                }
            }

            Node best = openList[bestIndex];
            openCount--;

            openList[bestIndex] = openList[openCount];
            return best;
        };
    // Sets the start node cost to zero, finds total cost (Manhattan distance), places into openList.
    gScore[startY][startX] = 0;
    fScore[startY][startX] = heuristic(startX, startY);
    pushNode(startX, startY, fScore[startY][startX]);
    // Cardinal movements.
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
    // Main A* loop.
    // Takes lowest fscore from open list, skips if closed, marks closed otherwise, explores closest path, valid paths are updated if a shorter path have been found.
    while (openCount > 0)
    {
        Node current = popLowest();
        int x = current.x;
        int y = current.y;

        if (closed[y][x])
        {
            continue;
        }

        closed[y][x] = true;

        if (x == targetX && y == targetY)
        {
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= SIZE || ny < 0 || ny >= SIZE)
            {
                continue;
            }

            if (maze[ny][nx] == griditem::wall)
            {
                continue;
            }

            if (closed[ny][nx])
            {
                continue;
            }

            int tentativeG = gScore[y][x] + 1;

            if (tentativeG < gScore[ny][nx])
            {
                gScore[ny][nx] = tentativeG;
                fScore[ny][nx] = tentativeG + heuristic(nx, ny);
                prevX[ny][nx] = x;
                prevY[ny][nx] = y;
                pushNode(nx, ny, fScore[ny][nx]);
            }
        }
    }
	// If target has no gScore after search, then this alogorithm did not find a path. A* did not find a valid route.
    if (gScore[targetY][targetX] == INF)
    {
        return;
    }
    // Preparation to reconstruct the path.
    movedirection path[SIZE * SIZE];
    int pathLength = 0;

    int currentX = targetX;
    int currentY = targetY;
    // Build the shortest path backwards from the target.
    while (!(currentX == startX && currentY == startY))
    {
        int parentX = prevX[currentY][currentX];
        int parentY = prevY[currentY][currentX];

        if (parentX == -1 || parentY == -1)
        {
            return;
        }

        if (currentX == parentX && currentY == parentY - 1)
        {
            path[pathLength] = movedirection::up;
        }
        else if (currentX == parentX && currentY == parentY + 1)
        {
            path[pathLength] = movedirection::down;
        }
        else if (currentX == parentX - 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::left;
        }
        else if (currentX == parentX + 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::right;
        }

        pathLength++;
        currentX = parentX;
        currentY = parentY;
    }
    // Creates the path in the correct forward order. Moves player.
    for (int i = pathLength - 1; i >= 0; i--)
    {
        moveresults mr = grid->MovePlayer(path[i]);

        if (mr == moveresults::complete)
        {
            break;
        }
    }
}

//Dijkstra probed 
void GridNavigatorAutomatic::Navigate()
{
    const int SIZE = 20;
    const int INF = 1000000;

    // From the provided Grid code:
    // player starts at (1, 18)
    // target starts at (18, 1)
    const int startX = 1;
    const int startY = 18;
    const int targetX = 18;
    const int targetY = 1;

	// Arrays store the state of the probed Dijkstra's algorithm.
    int known[SIZE][SIZE];

    int dist[SIZE][SIZE];
    bool visited[SIZE][SIZE];
    int prevX[SIZE][SIZE];
    int prevY[SIZE][SIZE];
	// Initialises the arrays
    for (int y = 0; y < SIZE; y++)
    {
        for (int x = 0; x < SIZE; x++)
        {
            // Outer boundary is always wall.
            if (x == 0 || x == SIZE - 1 || y == 0 || y == SIZE - 1)
            {
                known[y][x] = 1;
            }
            else
            {
                known[y][x] = 0;
            }

            dist[y][x] = INF;
            visited[y][x] = false;
            prevX[y][x] = -1;
            prevY[y][x] = -1;
        }
    }

    // Start and target are known walkable cells.
    known[startY][startX] = 2;
    known[targetY][targetX] = 2;
    // Defines node structure.
    struct HeapNode
    {
        int x;
        int y;
        int distance;
    };
    // Creates a min heap to process the lowest distance node next.
    HeapNode heap[SIZE * SIZE * 4];
    int heapSize = 0;
    // Inserts a node into the above heap.
    auto heapPush = [&](int x, int y, int distance)
        {
            int index = heapSize;
            heap[index].x = x;
            heap[index].y = y;
            heap[index].distance = distance;
            heapSize++;

            while (index > 0)
            {
                int parent = (index - 1) / 2;

                if (heap[parent].distance <= heap[index].distance)
                {
                    break;
                }

                HeapNode temp = heap[parent];
                heap[parent] = heap[index];
                heap[index] = temp;

                index = parent;
            }
        };
	// Removes the root of the heap (the node with the smallest distance) and restores the heap property.
    auto heapPop = [&]() -> HeapNode
        {
            HeapNode result = heap[0];
            heapSize--;
            heap[0] = heap[heapSize];

            int index = 0;

            while (true)
            {
                int left = index * 2 + 1;
                int right = index * 2 + 2;
                int smallest = index;

                if (left < heapSize && heap[left].distance < heap[smallest].distance)
                {
                    smallest = left;
                }

                if (right < heapSize && heap[right].distance < heap[smallest].distance)
                {
                    smallest = right;
                }

                if (smallest == index)
                {
                    break;
                }

                HeapNode temp = heap[index];
                heap[index] = heap[smallest];
                heap[smallest] = temp;

                index = smallest;
            }

            return result;
        };
    // The probed part of the Dijkstra's algorithm. Once a location is read, it is marked as known.
    auto ensureKnown = [&](int x, int y)
        {
            if (known[y][x] != 0)
            {
                return;
            }

            griditem square = grid->GetGridSquare(x, y);

            if (square == griditem::wall)
            {
                known[y][x] = 1;
            }
            else
            {
                known[y][x] = 2;
            }
        };
    // Initialises by setting start node distance to 0. Inserts into priority queue.
    dist[startY][startX] = 0;
    heapPush(startX, startY, 0);
	// Cardinal movements.
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
	// Main Dijkstra's loop. Processes nodes from the priority queue. Algorithm begins expanding from the player's starting position.
    // Removes the smallest distance from the heap (again and again), skips if visited, finalises it otherwise. 
    // Explores the closest locations.
    // Each location is probed if needed. Not if wall.
	// If a shorter path is found, it is updated and added to the heap.
    while (heapSize > 0)
    {
        HeapNode current = heapPop();
        int x = current.x;
        int y = current.y;

        if (visited[y][x])
        {
            continue;
        }

        visited[y][x] = true;

        if (x == targetX && y == targetY)
        {
            break;
        }

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= SIZE || ny < 0 || ny >= SIZE)
            {
                continue;
            }

            ensureKnown(nx, ny);

            if (known[ny][nx] == 1)
            {
                continue;
            }

            int newDistance = dist[y][x] + 1;

            if (newDistance < dist[ny][nx])
            {
                dist[ny][nx] = newDistance;
                prevX[ny][nx] = x;
                prevY[ny][nx] = y;
                heapPush(nx, ny, newDistance);
            }
        }
    }
    // No valid path found if target is still INF.
    if (dist[targetY][targetX] == INF)
    {
        return;
    }
	// Prepares to reconstruct the shortest path.
    movedirection path[SIZE * SIZE];
    int pathLength = 0;

    int currentX = targetX;
    int currentY = targetY;
	// Reconstructs the path from the target back to the start using arrays.
    while (!(currentX == startX && currentY == startY))
    {
        int parentX = prevX[currentY][currentX];
        int parentY = prevY[currentY][currentX];

        if (parentX == -1 || parentY == -1)
        {
            return;
        }

        if (currentX == parentX && currentY == parentY - 1)
        {
            path[pathLength] = movedirection::up;
        }
        else if (currentX == parentX && currentY == parentY + 1)
        {
            path[pathLength] = movedirection::down;
        }
        else if (currentX == parentX - 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::left;
        }
        else if (currentX == parentX + 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::right;
        }

        pathLength++;
        currentX = parentX;
        currentY = parentY;
    }
	// Executes the moves in reverse order to navigate from the start to the target.
    for (int i = pathLength - 1; i >= 0; i--)
    {
        moveresults mr = grid->MovePlayer(path[i]);

        if (mr == moveresults::complete)
        {
            break;
        }
    }
}
// Basic Dijkstra 
void GridNavigatorAutomatic::Navigate()
{
	const int SIZE = 20; //Fixed size of the grid as per the provided grid code.
	const int INF = 1000000; // A large number representing infinity.

    // Read the whole grid once.
    griditem** maze = grid->GetGrid();

	int startX = -1, startY = -1; // Player's starting position
	int targetX = -1, targetY = -1; // Target's position

    // Find player and target.
	for (int y = 0; y < SIZE; y++)  // iterate through the rows
    {
		for (int x = 0; x < SIZE; x++) // iterate through the columns
        {
			if (maze[y][x] == griditem::player) // if the current cell is the player
            {
				startX = x; // store the player's x coordinate
				startY = y; // store the player's y coordinate
            }
			else if (maze[y][x] == griditem::target) // if the current cell is the target
            {
				targetX = x; // store the target's x coordinate
				targetY = y; // store the target's y coordinate
            }
        }
    }
	// If either the player or target is not found, exit the function. Basically, if the starting or target positions are invalid, we cannot proceed with navigation.
    if (startX == -1 || startY == -1 || targetX == -1 || targetY == -1)
    {
        return;
    }

	int dist[SIZE][SIZE]; //Stores shortest known distance from the start to each cell in the grid.
	bool visited[SIZE][SIZE]; //Tracks if a cell has been processed in Dijkstra's algorithm.
    int prevX[SIZE][SIZE]; //Previous node tracking
	int prevY[SIZE][SIZE]; //Previous node tracking

    for (int y = 0; y < SIZE; y++)
    {
        for (int x = 0; x < SIZE; x++)
        {
			dist[y][x] = INF; // Initialise all distances to infinity.
			visited[y][x] = false; //No nodes have been visited yet.
			prevX[y][x] = -1; //marks previous coordinates unknown.
            prevY[y][x] = -1; //marks previous coordinates unknown.
        }
    }

	struct HeapNode //Declares a structure to represent a node in the priority queue (min-heap) used in Dijkstra's algorithm. Each node contains the x and y coordinates of a cell in the grid and the distance from the start cell to that cell.
    {   // Variable declarations
        int x; 
        int y;
        int distance;
    };

	HeapNode heap[SIZE * SIZE * 4]; // Creates an array to represent the min-heap to pick the next closest location
	int heapSize = 0; // Tracks valid entries in the heap.
    
    auto heapPush = [&](int x, int y, int distance) //Defines a lambda that inserts a new sqaure into the head with its current distance from the start
        {
            int index = heapSize; // Chooses the next free position at the end of the heap
			heap[index].x = x; // Assigns the x coordinate of the new node.
			heap[index].y = y; // Assigns the y coordinate of the new node.
            heap[index].distance = distance; // Assigns the distance
            heapSize++;

            while (index > 0)
            {
                int parent = (index - 1) / 2; // Determines the index of parent node.

				if (heap[parent].distance <= heap[index].distance) // Condition: is the parent node's distance less than or equal to the current node's distance? If yes, the heap property is satisfied, and we can break out of the loop.
                {
                    break;
                }

				HeapNode temp = heap[parent]; // Temporarily store the parent node.
				heap[parent] = heap[index]; // Moves the current node up to the parent's position.
				heap[index] = temp; // Moves the parent node down to the current (child) node's position.

                index = parent;
            }
        };

    auto heapPop = [&]() -> HeapNode // Defines another lambda.
        {
            HeapNode result = heap[0]; // Copies the root node which is the current minimum distance
			heapSize--; // Decreases the size of the heap.
			heap[0] = heap[heapSize]; //Moves the last node in the heap to the root position to fill gap left by removal

            int index = 0;
            // After removing the root of the heap, this loop restores the min-heap property 
            // By repeatedly comparing the current node with its children and swapping it with the smallest child 
            // until it is in the correct position (i.e. smaller than both children).
            while (true)
            {
                int left = index * 2 + 1;
                int right = index * 2 + 2;
                int smallest = index;

                if (left < heapSize && heap[left].distance < heap[smallest].distance)
                {
                    smallest = left;
                }

                if (right < heapSize && heap[right].distance < heap[smallest].distance)
                {
                    smallest = right;
                }

                if (smallest == index)
                {
                    break;
                }

                HeapNode temp = heap[index];
                heap[index] = heap[smallest];
                heap[smallest] = temp;

                index = smallest;
            }
			// Returns the node with the smallest distance (the root of the heap).
            return result;
        };
	// Setting the start node distance to 0 and pushing it onto the heap to begin the algorithm.
	// Essentially, this is the starting point of Dijkstra's algorithm and the player.
    dist[startY][startX] = 0;
    heapPush(startX, startY, 0);
    // Defines movement directions
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
	// Main Dijkstra loop. Processes nodes from the priority queue. Algorithm begins expanding from the player's starting position.
    while (heapSize > 0)
    {
        HeapNode current = heapPop();
        int x = current.x;
        int y = current.y;
        // Skip visited nodes.
        if (visited[y][x])
        {
            continue;
        }
        // Marks current node visited.
        visited[y][x] = true;
        // Stops algorithm early once the target has been reached as shortest path has been found.
        if (x == targetX && y == targetY)
        {
            break;
        }
        // Explores nodes to attempt to find a shorter path.
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
			// Skip out of bounds nodes.
            if (nx < 0 || nx >= SIZE || ny < 0 || ny >= SIZE)
            {
                continue;
            }
            // Skips walls
            if (maze[ny][nx] == griditem::wall)
            {
                continue;
            }

            int newDistance = dist[y][x] + 1;
            // If shorter path to the node has been found, add to the heap.
            if (newDistance < dist[ny][nx])
            {
                dist[ny][nx] = newDistance;
                prevX[ny][nx] = x;
                prevY[ny][nx] = y;
                heapPush(nx, ny, newDistance);
            }
        }
    }
	// Target is unreachable, distance is still infinity. No valid path exists, so exit the function.
    if (dist[targetY][targetX] == INF)
    {
        return;
    }
    //Prepares to reconstruct the shortest path.
    movedirection path[SIZE * SIZE];
    int pathLength = 0;

    int currentX = targetX;
    int currentY = targetY;
	// Reconstructs the path from the target back to the start using arrays.
    while (!(currentX == startX && currentY == startY))
    {
        int parentX = prevX[currentY][currentX];
        int parentY = prevY[currentY][currentX];

        if (parentX == -1 || parentY == -1)
        {
            return;
        }

        if (currentX == parentX && currentY == parentY - 1)
        {
            path[pathLength] = movedirection::up;
        }
        else if (currentX == parentX && currentY == parentY + 1)
        {
            path[pathLength] = movedirection::down;
        }
        else if (currentX == parentX - 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::left;
        }
        else if (currentX == parentX + 1 && currentY == parentY)
        {
            path[pathLength] = movedirection::right;
        }

        pathLength++;
        currentX = parentX;
        currentY = parentY;
    }
	// Executes the moves in reverse order to navigate from the start to the target.
    for (int i = pathLength - 1; i >= 0; i--)
    {
        moveresults mr = grid->MovePlayer(path[i]);
		// If the target is reached, exit the loop.
        if (mr == moveresults::complete)
        {
            break;
        }
    }
}