Skip to content

8-Puzzle Problem Using A* in C# and Unity

8-Puzzle Problem Using A* in C# and Unity

Page 5 – Integrating the Path Finder to Solve 8-Puzzle

This tutorial is divided into 5 pages.

  • Page 1: The first page of the tutorial introduces the 8-Puzzle game and its integration with A* pathfinding in Unity. It covers the problem’s history, its complexity, and heuristic search methods like A*. It also explains the puzzle’s state representation and neighbor construction for pathfinding, providing foundational knowledge for implementing and solving the 8-Puzzle.
  • Page 2: The second of the tutorial guides you through creating a new Unity 3D project named “8-Puzzle”. It details setting up the main camera, importing assets, and configuring a tile prefab. You create a puzzle board frame using cubes with wood textures and set up a basic UI with four buttons and two text fields for randomization, image cycling, resetting, and solving the puzzle using A*.
  • Page 3: The third covers the implementation of the PuzzleState class for the 8-puzzle game in C#. This class represents a unique puzzle state with an array of tile indices and includes constructors, equality checks, a hash code generator, and methods for finding the empty tile, swapping tiles, and calculating Manhattan cost. Additionally, it details creating neighbor indices for grid cells and generating neighboring puzzle states by moving the empty tile.
  • Page 4: In the fourth page, we implement the Path Finder using the three commonly used path finding algorithms, viz., the Dijkstra, the A* and the Gree-best-first search algorithms.
  • Page 5: In the fifth page, we apply the A* Path Finder to solve our 8-Puzzle game. We also create the necessary functionality to interactively play the game using the basic UI created in Page 2.

Contact me


Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/gamdev-unity/tree/8-puzzle.


View the tutorial on YouTube.


Apply A* to Solve 8-Puzzle

In the previous section of this tutorial, we learned about pathfinding and the algorithms used to solve pathfinding problems. We then implemented a generic pathfinder using C# by applying the three most commonly known and popular pathfinding algorithms: the A*, the Dijkstra, and the greedy best-first algorithms.

In this final section, we will apply the A* pathfinder to solve the 8-Puzzle. 

Puzzle Node

The state tree is the actual tree that comprises all the valid transitions from one state to another state, ultimately reaching the final goal (if the solution exists).

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes – source Wikipedia.

We have already implemented our Node in the previous section. Remember that the Node that we implemented previously is abstract. For our 8-puzzle, we will implement the concrete class named PuzzleNode that will derive from Node<PuzzleState>.

Why?

Because, in this problem, we are creating a tree of the PuzzleState. So each node in this tree must comprise the value PuzzleState.

  1. From the scripts folder, right-click and create a new C# script file and name it PuzzleNode.
  2. Double-click and open in Visual Studio.
  3. Remove MonoBehaviour and the Start and Update methods.
public class PuzzleNode : Node<PuzzleState>
Code language: C# (cs)
  • The PuzzleNode class inherits from a generic Node class, where the type parameter is PuzzleState. This suggests that Node is a base class designed to work with state-based objects, and PuzzleNode specializes it for PuzzleState.

The Constructor

public PuzzleNode(PuzzleState state): base(state)
{

}
Code language: C# (cs)
  • This constructor initializes a new instance of PuzzleNode with a given PuzzleState object (state).
  • It calls the base class constructor (base(state)) to initialize the inherited Node<PuzzleState> with the provided state.

Get Neighbour Method

public override List<Node<PuzzleState>> GetNeighbours()
{
    List<Node<PuzzleState>> neighbours = new List<Node<PuzzleState>>();
    List<PuzzleState> neighbour_states = PuzzleState.GetNeighbourOfEmpty(Value);

    for (int i = 0; i < neighbour_states.Count; i++)
    {
        neighbours.Add(new PuzzleNode(neighbour_states[i]));
    }
    return neighbours;
}
Code language: C# (cs)
  • This method overrides the GetNeighbours method from the Node base class.
  • It generates a list of neighboring nodes (neighbours) for the current PuzzleNode.
  • neighbours is initialized as an empty list of Node<PuzzleState>.
  • It calls PuzzleState.GetNeighbourOfEmpty(Value), which generates a list of PuzzleState objects representing the neighboring states of the current puzzle state (Value is the property from the base class Node that holds the state).
  • The method then iterates over each PuzzleState in the neighbour_states list.
    • For each neighboring state, it creates a new PuzzleNode using the PuzzleState and adds it to the neighbours list.
  • Finally, it returns the list neighbours, which contains PuzzleNode objects representing all valid neighboring states of the current puzzle state.

The Puzzle Board

Finally, we will implement the PuzzleBoard script class where we will do all the necessary bindings. Go to the Project window in Unity Editor. Select the scripts folder, right-click and add a new script called PuzzleBoard. Attach this script to our PuzzleBoard game object in the hierarchy.

Double-click and open the script in Visual Studio.

public class PuzzleBoard : MonoBehaviour
{
Code language: C# (cs)

The PuzzleBoard class, which inherits from MonoBehaviour, is a Unity script for managing and interacting with a sliding puzzle game. It handles the initialization, rendering, user input, and solving of the puzzle.

The Variables

This section defines the class’s variables, both public and private, which are essential for the game’s functionality.

Public Variables

    public GameObject tilePrefab;
    public List<Texture> puzzleImages = new List<Texture>();

    public Text statusText;
    public Text numberOfMovesText;
Code language: C# (cs)
  • GameObject tilePrefab: The prefab for the puzzle tiles. This is used to instantiate the individual tiles on the board.
  • List<Texture> puzzleImages: A list of textures used for the puzzle images. Players can switch between these images.
  • Text statusText: A UI text element that displays the puzzle’s status (e.g., whether it is solved or in progress).
  • Text numberOfMovesText: A UI text element that shows the number of moves made by the player.

Private Variables

  • bool solved: A flag indicating whether the puzzle is currently solved.
  • PuzzleState goalState: Represents the goal state of the puzzle, typically where all tiles are in the correct order.
  • PuzzleState randomizedState: Stores the state of the puzzle after it has been randomized, used to reset the puzzle to this state.
  • int numberOfMoves: Tracks the number of moves the player has made.
  • int currentTextureIndex: Keeps track of the current texture being used for the puzzle. Allows switching between different puzzle images.
  • List<GameObject> tiles: A list of tile GameObjects that make up the puzzle.
  • List<Vector3> tilesLocation: A list of preset positions for the tiles in a 3×3 grid. Each Vector3 represents a position in the game world.

Positions in the Grid

The nine tile locations (positions) of the 8-Puzzle.
  • new Vector3(-1.0f, 1.0f, 0.0f): Top-left
  • new Vector3(0.0f, 1.0f, 0.0f): Top-center
  • new Vector3(1.0f, 1.0f, 0.0f): Top-right
  • new Vector3(-1.0f, 0.0f, 0.0f): Middle-left
  • new Vector3(0.0f, 0.0f, 0.0f): Center
  • new Vector3(1.0f, 0.0f, 0.0f): Middle-right
  • new Vector3(-1.0f, -1.0f, 0.0f): Bottom-left
  • new Vector3(0.0f, -1.0f, 0.0f): Bottom-center
  • new Vector3(1.0f, -1.0f, 0.0f): Bottom-right

More Private Variables

  • PuzzleState currentState: Represents the current state of the puzzle during gameplay.
  • bool randomizing: A flag indicating whether the puzzle is currently being randomized.
  • AStarPathFinder<PuzzleState> pathFinder: An instance of the A* pathfinding algorithm, specialized for PuzzleState objects. Used to solve the puzzle.
  • bool solvingUsingAStarInProgress: A flag indicating whether the A* algorithm is currently solving the puzzle.
  • int numberOfMovesAStar: Tracks the number of moves made by the A* algorithm during the solving process.

Create Tiles Function

    void CreateTiles()
    {
        for (int i = 0; i < tilesLocation.Count; i++)
        {
            GameObject tile = Instantiate(tilePrefab);
            tile.name = i.ToString();
            tile.transform.parent = transform;
            tiles.Add(tile);
            tiles[i].transform.position = tilesLocation[i];
        }
    }
Code language: C# (cs)


The CreateTiles method is responsible for instantiating and positioning tiles based on predefined locations (tilesLocation). It iterates over the tilesLocation list, where each entry represents a position in 3D space for a tile. For each iteration, the method instantiates a new GameObject using Instantiate(tilePrefab), assigning it a name corresponding to its index (i.ToString()).

The instantiated tile is then made a child of the current object’s transform (tile.transform.parent = transform), allowing it to be visually organized under the parent object. The tile is added to a list (tiles) to keep track of all instantiated tiles.

Finally, the method sets the position of the tile by retrieving the corresponding position from tilesLocation using the current index (tilesLocation[i]). This process ensures that each tile is created and positioned according to the predefined locations, effectively initializing the puzzle layout.

Set Texture Function

The SetTexture method assigns a section of a larger texture to each tile in a sliding puzzle, making it appear as if the puzzle image is split across multiple tiles.

    void SetTexture()
    {
        Texture mainTexture = puzzleImages[currentTextureIndex];
        int numRows = 3;
        int tileSize = mainTexture.width / numRows;

        for (int i = 0; i < 8; i++)
        {
            GameObject tile = tiles[i];
            Renderer renderer = tile.GetComponent<Renderer>();
            Material material = renderer.material;

            // Calculate the texture coordinates.
            int row = i / numRows;
            int col = i % numRows;

            float xMin = col * 
                (float)tileSize / mainTexture.width;

            float yMin = 1.0f - (row + 1) * 
                (float)tileSize / mainTexture.height;

            material.mainTexture = mainTexture;
            material.mainTextureScale = new Vector2(
                (float)tileSize / mainTexture.width,
                (float)tileSize / mainTexture.height);

            material.mainTextureOffset = new Vector2(xMin, yMin);
        }

        // We want the last tile to be empty and hence
        // transparent in color.
        tiles[8].GetComponent<Renderer>().material.color = 
            new Color(0.0f, 0.0f, 0.0f, 0.0f);
    }
Code language: C# (cs)

The SetTexture method is responsible for configuring the appearance of tiles in a 3×3 puzzle game based on a selected texture. It first retrieves the mainTexture from a list of available puzzleImages based on the currentTextureIndex.

It then calculates the tileSize by dividing the width of mainTexture by numRows (which is set to 3), determining the size of each tile in the grid. Inside a loop that iterates over the first 8 tiles (index 0 to 7), the method accesses each tile’s Renderer component and assigns it a portion of the mainTexture based on its position within the 3×3 grid.

It calculates xMin and yMin values to specify the offset within the texture for the current tile. These values are used to set the mainTexture, mainTextureScale, and mainTextureOffset properties of the tile’s material, ensuring that each tile displays the correct section of the texture.

Finally, the method sets the color of the 9th tile (index 8) to fully transparent, effectively making it appear empty, which is essential for the puzzle mechanics. This method ensures that the puzzle tiles visually represent the selected texture with correct positioning and transparency.

Coroutine to Animate Tile Movement

The Coroutine_MoveOverSeconds method is a coroutine in Unity that smoothly moves a GameObject from its current position to a specified end position over a given duration.

    public IEnumerator Coroutine_MoveOverSeconds(
        GameObject objectToMove,
        Vector3 end,
        float seconds)
    {
        float elaspedTime = 0;
        Vector3 startingPos = objectToMove.transform.position;

        while (elaspedTime < seconds)
        {
            objectToMove.transform.position = 
                Vector3.Lerp(
                    startingPos, end,
                    elaspedTime / seconds);
            elaspedTime += Time.deltaTime;

            yield return new WaitForEndOfFrame();
        }
        objectToMove.transform.position = end;
    }
Code language: C# (cs)

The Coroutine_MoveOverSeconds method is a Unity coroutine that smoothly moves a GameObject from its current position to a specified end position over a given duration. It works by interpolating the object’s position between the start and end positions over the specified time, updating the position each frame.

The coroutine uses Vector3.Lerp for linear interpolation and yield return new WaitForEndOfFrame() to wait until the next frame, ensuring smooth movement. Once the duration is reached, it sets the object’s position to the exact end position to complete the movement accurately.

Set Puzzle State

    public void SetPuzzleState(PuzzleState state, float duration)
    {
        currentState = state;
        for (int i = 0; i < state.Arr.Length; i++)
        {
            StartCoroutine(Coroutine_MoveOverSeconds(
                tiles[state.Arr[i]],
                tilesLocation[i],
                duration));
        }
    }
Code language: C# (cs)

The SetPuzzleState method updates the puzzle’s current state and smoothly moves the tiles to their new positions over a specified duration. It sets currentState to the new state, then starts a coroutine for each tile to transition it to its target position using the Coroutine_MoveOverSeconds method we implemented earlier.

This ensures a smooth animation for all tile movements, aligning the visual representation with the new puzzle state.

Coroutine to Randomise Tiles

This coroutine effectively simulates the process of shuffling the puzzle tiles randomly within a specified number of moves and durations.

    IEnumerator Coroutine_Randomize(int depth, 
        float durationPerMove)
    {
        randomizing = true;
        int i = 0;
        while (i < depth)
        {
            List<PuzzleState> neighbours = 
                PuzzleState.GetNeighbourOfEmpty(currentState);

            // get a random index.
            int rn = Random.Range(0, neighbours.Count);
            currentState.SwapWithEmpty(neighbours[rn].EmptyTileIndex);
            i++;
            SetPuzzleState(currentState, durationPerMove);
            yield return new WaitForSeconds(durationPerMove);
        }
        randomizing = false;
        solved = false;
        statusText.gameObject.SetActive(false);

        randomizedState = new PuzzleState(currentState);
    }
Code language: C# (cs)

The Coroutine_Randomize method is a coroutine used to randomize the puzzle state by making a series of random moves. It first sets a flag (randomizing) to true to indicate that randomization is in progress. It then iterates depth number of times, where each iteration represents a random move.

During each iteration, it obtains a list of neighboring states (neighbours) that can be reached by moving the empty tile (the tile that represents the empty space). It randomly selects one of these neighboring states, swaps it with the empty tile in the current state (currentState), and updates the puzzle’s visual representation using SetPuzzleState with a specified duration for each move.

The coroutine then waits for a brief duration (durationPerMove) using yield return new WaitForSeconds(durationPerMove) before proceeding to the next iteration.

Once all random moves are completed, it sets randomizing to false, resets the puzzle’s state as unsolved (solved = false), hides the status text indicating the puzzle is being solved, and assigns the current randomized state to randomizedState for future reference.

The Randomize Method

The Randomize method is responsible for randomizing the puzzle tiles if certain conditions are met.

    public void Randomize()
    {
        if (solvingUsingAStarInProgress) return;
        Debug.Log("Randomize.");
        if (randomizing) return;
        StartCoroutine(Coroutine_Randomize(100, 0.02f));
    }
Code language: C# (cs)

First, it checks whether a solving process using A* search is currently in progress (solvingUsingAStarInProgress), and if so, it immediately returns without performing any action. Next, it checks whether the puzzle is already in the process of being randomized (randomizing), and again, if true, it returns without starting a new randomization process.

If neither condition is met, it starts a coroutine (Coroutine_Randomize) with parameters 100 (depth of randomization) and 0.02f (duration per move). This coroutine simulates random tile movements to shuffle the puzzle, making sure not to interfere with ongoing solving processes or redundant randomization attempts.

The Reset Method

The Reset method is designed to reset the puzzle to its initial randomized state.

    public void Reset()
    {
        if (solvingUsingAStarInProgress) return;
        SetPuzzleState(new PuzzleState(randomizedState));
        numberOfMoves = 0;
        numberOfMovesText.gameObject.SetActive(false);
        statusText.gameObject.SetActive(false);
    }
Code language: C# (cs)

It ensures that we can’t reset the puzzle while a solution is being computed by the PathFinder (solvingUsingAStarInProgress flag is checked to prevent resetting during this process).

It accomplishes this by setting the puzzle state (currentState) to a new PuzzleState instance based on the randomizedState, which represents the puzzle in its randomized arrangement. Additionally, it resets the numberOfMoves counter to zero, hides the numberOfMovesText and statusText UI elements to reflect that the puzzle is in a reset state, ready to be played again or randomized anew.

The Init Method


The Init method initializes the puzzle game by setting up the initial state and visual appearance.

    private void Init()
    {
        SetTexture();
        SetPuzzleState(new PuzzleState());

        statusText.text = "Puzzle in solved state. Randomize to play!";
        numberOfMoves = 0;
        solved = true;

        numberOfMovesText.gameObject.SetActive(false);
    }
Code language: C# (cs)

First, it calls SetTexture() to configure the appearance of the puzzle tiles based on the current texture index. Next, it sets the puzzle state to a new instance of PuzzleState, representing the solved state (with tiles in their original order). The statusText is updated to display “Puzzle in solved state. Randomize to play!” to inform the player about the current state of the puzzle.

The numberOfMoves counter is reset to zero, indicating that no moves have been made yet. The solved flag is set to true, signifying that the puzzle is in its initial solved state. Finally, the numberOfMovesText object is deactivated (set to inactive), hiding it from view initially.

The Start Method

The Start() method initializes the puzzle board when the game or scene starts running. It ensures that the puzzle is set up correctly and ready for interaction when the game begins.

    void Start()
    {
        PuzzleState.CreateNeighbourIndices();
        CreateTiles();
        Init();
    }
Code language: C# (cs)

First, PuzzleState.CreateNeighbourIndices() is called to generate the neighboring indices for each tile in the puzzle, preparing the puzzle state for potential moves.

Next, CreateTiles() is invoked to instantiate and position the tiles on the puzzle board based on predefined locations.

Finally, Init() is called to set up the initial state of the puzzle, such as displaying the solved state message, initializing the number of moves to zero, and hiding the number of moves display.

Picking of Tile

The PickTile method is used to determine which tile in the puzzle the player has clicked on based on the mouse position.

    private GameObject PickTile()
    {
        Vector3 mousePosition = Input.mousePosition;
        Ray ray = Camera.main.ScreenPointToRay(mousePosition);

        RaycastHit hitInfo;

        if (Physics.Raycast(ray, out hitInfo))
        {
            GameObject hitObject = hitInfo.collider.gameObject;
            return hitObject;
        }
        return null;
    }
Code language: C# (cs)

It first retrieves the current mouse position (Input.mousePosition) in screen coordinates. Then, it casts a ray (Camera.main.ScreenPointToRay(mousePosition)) from the camera through the mouse position into the scene. The Physics.Raycast method checks if this ray intersects with any colliders in the scene.

If an intersection is found (if (Physics.Raycast(ray, out hitInfo))), it retrieves the GameObject associated with the collider that was hit (hitInfo.collider.gameObject). This GameObject represents the tile that was clicked on and is returned by the method.

If no intersection is detected, indicating that the mouse click did not hit any puzzle tile, the method returns null, indicating that no tile was picked.

The Cost Functions

We define two static methods used in the context of solving a puzzle with the A* search algorithm.

    static public float ManhattanCost(PuzzleState a, PuzzleState goal)
    {
        return (float)a.GetManhattanCost();
    }Code language: C# (cs)

The ManhattanCost method calculates the Manhattan distance heuristic between a given puzzle state a and the goal state. It invokes the GetManhattanCost method of the PuzzleState instance a to compute the Manhattan distance, which is a common heuristic for estimating the minimum number of moves required to reach the goal state from a.

    static public float TraversalCost(PuzzleState a, PuzzleState b)
    {
        return 1.0f;
    }
Code language: C# (cs)

The TraversalCost method returns a constant traversal cost of 1.0f, which is typically used in pathfinding algorithms like A* to represent uniform cost movement between states regardless of their specific details.

These methods contribute to the A* algorithm’s evaluation of potential paths by providing cost estimates based on heuristics and uniform traversal cost.

Coroutine To Find Path

The Coroutine_Solve method is a coroutine used to find a solution to a puzzle using the A* search algorithm.

    IEnumerator Coroutine_Solve()
    {
        statusText.gameObject.SetActive(true);
        statusText.text = "Finding solution using A* search.";
        pathFinder.Initialise(new PuzzleNode(new PuzzleState(randomizedState)),
            new PuzzleNode(new PuzzleState()));

        while (pathFinder.Status == PathFinderStatus.RUNNING)
        {
            pathFinder.Step();
            yield return null;
        }

        if (pathFinder.Status == PathFinderStatus.SUCCESS)
        {
            // We will show the solution.
            StartCoroutine(Coroutine_ShowSolution());
        }
        if (pathFinder.Status != PathFinderStatus.FAILURE)
        {
            Debug.Log("No solution found!");
        }
    }
Code language: C# (cs)

Initially, it sets the status text to indicate that the solution is being searched for by activating the game object associated with statusText and updating its text.

It then initializes the pathFinder with the start and goal states represented by PuzzleNode instances initialized with the current randomized state of the puzzle. The method then enters a loop where the A* algorithm continues to execute (pathFinder.Step()) until it either finds a solution (PathFinderStatus.SUCCESS) or determines that no solution exists (PathFinderStatus.FAILURE).

If a solution is found, it starts another coroutine (Coroutine_ShowSolution) to display the solution visually. If no solution is found, it logs a message to the console indicating that no solution was found.

The method yields execution each frame (yield return null) to allow other operations to continue while the A* search progresses.

Coroutine to Show Solution

The Coroutine_ShowSolution method is a coroutine responsible for displaying the solution of the puzzle after it has been found using the A* search algorithm.

    IEnumerator Coroutine_ShowSolution()
    {
        List<PuzzleState> reverseSolution = new List<PuzzleState>();
        PathFinder<PuzzleState>.PathFinderNode node = pathFinder.CurrentNode;
        while (node != null)
        {
            reverseSolution.Add(node.Location.Value);
            node = node.Parent;
        }
        statusText.text = "Solution found! The puzzle can be solved in " +
            (reverseSolution.Count - 1).ToString() + " moves.";
        if (reverseSolution.Count > 0)
        {
            SetPuzzleState(reverseSolution[reverseSolution.Count - 1]);
        }
        if (reverseSolution.Count > 2)
        {
            for (int i = reverseSolution.Count - 2; i >= 0; i -= 1)
            {
                numberOfMovesAStar++;
                numberOfMovesText.text = numberOfMovesAStar.ToString();
                numberOfMovesText.gameObject.SetActive(true);
                SetPuzzleState(reverseSolution[i], 0.5f);
                yield return new WaitForSeconds(1.0f);
            }
        }
        statusText.text = "Puzzle in solved state. Randomize to play!";
        solvingUsingAStarInProgress = false;
    }Code language: PHP (php)


Initially, it initializes an empty list reverseSolution to store the sequence of puzzle states leading to the solution. It then iterates through the path nodes starting from the current node (pathFinder.CurrentNode), adding each puzzle state to reverseSolution until it reaches the root node (where node becomes null).

After constructing the list, it updates the statusText to inform the player that a solution has been found and specifies the number of moves required to solve the puzzle (reverseSolution.Count - 1).

The method then sets the puzzle state to the final state of the solution, triggering the tiles to move into the solved configuration using SetPuzzleState.

If the solution involves more than two states (reverseSolution.Count > 2), it iterates backwards through reverseSolution, incrementing numberOfMovesAStar for each step and updating the numberOfMovesText to reflect this progress.

During this iteration, it smoothly transitions the puzzle state for each step with a delay (0.5f seconds between moves) to visually represent the solution process.

Finally, it updates the statusText to indicate that the puzzle is now in the solved state and ready to be randomized for a new playthrough, and it sets solvingUsingAStarInProgress to false to signify the completion of the A* search process.

The Solve Method

The Solve method in the PuzzleBoard class is responsible for initiating the solving process using an A* search algorithm to find the optimal solution for the sliding puzzle.

    public void Solve()
    {
        if (solvingUsingAStarInProgress) return;
        numberOfMovesAStar = 0;
        solvingUsingAStarInProgress = true;

        pathFinder.HeuristicCost = ManhattanCost;
        pathFinder.NodeTraversalCost = TraversalCost;

        StartCoroutine(Coroutine_Solve());
    }
Code language: C# (cs)

Before starting the solving process, the method checks if another solving process (solvingUsingAStarInProgress) is already in progress and returns early if so. It then resets the numberOfMovesAStar counter to zero and sets solvingUsingAStarInProgress to true to indicate that a solving process is underway.

Next, it configures the pathFinder object by setting its heuristic cost function (HeuristicCost) to ManhattanCost and its node traversal cost function (NodeTraversalCost) to TraversalCost, which are both static methods of the PuzzleBoard class.

Finally, the method starts the solving process by calling StartCoroutine(Coroutine_Solve()), which initiates a coroutine to execute the A* search algorithm asynchronously and find the optimal solution for the puzzle.

The Next Image

The NextImage method is responsible for transitioning the puzzle to the next image in a sequence of puzzle images.

    public void NextImage()
    {
        if (solvingUsingAStarInProgress) return;
        Debug.Log("NextImage.");
        currentTextureIndex++;
        if (currentTextureIndex == puzzleImages.Count)
        {
            currentTextureIndex = 0;
        }
        Init();
    }Code language: JavaScript (javascript)


It first checks if a solving process using A* search is in progress (solvingUsingAStarInProgress flag) and immediately returns if true, preventing the image change during the solving process.

It increments the currentTextureIndex to move to the next image in the puzzleImages list and resets it to 0 if it reaches the end of the list (circular behavior).

Finally, it calls the Init method to initialize the puzzle with the new image, resetting the puzzle state to its solved configuration and updating the displayed image accordingly. This method provides a way to cycle through a series of puzzle images and restart the puzzle with a new image when needed.

The Update Method

The Update method is called once per frame by Unity and handles user input and puzzle logic. It contains three main conditional blocks that respond to specific key presses or mouse clicks for testing without the UI.

        if (Input.GetMouseButtonDown(0))
        {
            GameObject obj = PickTile();
            if (obj != null && !solved)
            {
                int empty = currentState.EmptyTileIndex;
                List<int> neighbours = 
                    PuzzleState.GetNeighbourIndices(empty);

                for (int i = 0; i < neighbours.Count; i++)
                {
                    if (obj.name == 
                        currentState.Arr[neighbours[i]].ToString())
                    {
                        numberOfMoves++;
                        numberOfMovesText.gameObject.SetActive(true);
                        numberOfMovesText.text = numberOfMoves.ToString();
                        currentState.SwapWithEmpty(neighbours[i]);
                        SetPuzzleState(currentState, 0.2f);

                        solved = currentState.Equals(goalState);

                        if (solved)
                        {
                            statusText.gameObject.SetActive(true);
                            statusText.text = "Yay! " +
                                "You have solved the puzzle. " +
                                "Click Next to play a new puzzle";
                        }
                    }
                }
            }
        }

        if (Input.GetKeyDown(KeyCode.R))
        {
            StartCoroutine(Coroutine_Randomize(100, 0.02f));
        }
    }
Code language: C# (cs)

First, it checks if the ‘N’ key is pressed (Input.GetKeyDown(KeyCode.N)) and calls the NextImage method if true, which progresses to the next puzzle image.

Next, it checks if the left mouse button is clicked (Input.GetMouseButtonDown(0)) and retrieves the clicked tile (GameObject obj) using the PickTile method.

If a valid tile is clicked and the puzzle is not solved, it identifies the empty tile’s index, retrieves the neighboring tile indices, and iterates through them to find a matching tile name with the clicked object. If a match is found, it increments the numberOfMoves, updates the UI to display the move count, swaps the clicked tile with the empty tile, updates the puzzle state visually with a smooth transition (SetPuzzleState), checks if the puzzle is solved by comparing the current state (currentState) with the goal state (goalState), and updates the game status and UI if the puzzle is solved.

Lastly, it checks if the ‘R’ key is pressed (Input.GetKeyDown(KeyCode.R)) and starts the coroutine Coroutine_Randomize to randomize the puzzle tiles over 100 iterations with a 0.02-second delay per move, if no other solving process is currently in progress. This method integrates user input with puzzle mechanics, enabling player interactions and puzzle-solving gameplay.

Similarly, you can add in another key press binding to trigger the Solve method. You can also refactor this subsection of code.

Game Object Bindings in Unity Editor

Go to the Unity Editor and then associate the following:

  • Select the PuzzleBoard game object from the hierarchy. Drag and drop the tile prefab from the Prefabs folder and associate it with the Tile Prefab field of the PuzzleBoard script.
This picture shows the association of the tile prefab.
  • Drag and drop the Status Text from the Canvas and associate it with the Status Text field of the PuzzleBoard script.
This picture shows the association of the Status text.
  • Drag and drop the NumMoves Text from the Canvas and associate it with the Number of Moves Text field of the PuzzleBoard script.
This picture shows the association of the Number of Moves text.
  • Go to the Images folder in the Project window. Then associate each of the downloaded images to the Puzzle Images field. You can also bring in your image sources (just ensure that they are of 1:1 resolution) and associate with the puzzle images.
This picture shows the association of the puzzle images.

Attach an On Click event functions for the four buttons in the UI Canvas as shown below.

This picture shows the association of the On Click event of the Randomize button with the Randomize method of PuzzleBoard script.
This picture shows the association of the On Click event of the Reset button with the Reset method of PuzzleBoard script.
This picture shows the association of the On Click event of the Next Image button with the NextImage method of PuzzleBoard script.
This picture shows the association of the On Click event of the Solve with A* button with the Solve method of PuzzleBoard script.

Click Play and run. Your game should be working now.

Once you Click on the Randomize button, your tiles will be randomised, as shown below.

You can play by clicking on the tiles interactively. You can also click the Solve Using A* button to let A* solve the puzzle for you.

This animated gif shows A* pathfinder solving the 8-Puzzle.

Read My Other Tutorials

  1. Implement a Generic Pathfinder in Unity using C#
  2. Create a Jigsaw Puzzle Game in Unity
  3. Generic Finite State Machine Using C#
  4. Implement Bezier Curve using C# in Unity
  5. Create a Jigsaw Tile from an Existing Image
  6. Create a Jigsaw Board from an Existing Image
  7. Solving 8 puzzle problem using A* star search
  8. A Configurable Third-Person Camera in Unity
  9. Player Controls With Finite State Machine Using C# in Unity
  10. Finite State Machine Using C# Delegates in Unity
  11. Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
  12. Augmented Reality – Fire Effect using Vuforia and Unity
  13. Implementing a Finite State Machine Using C# in Unity
  14. Solving 8 puzzle problem using A* star search in C++
  15. What Are C# Delegates And How To Use Them
  16. How to Generate Mazes Using Depth-First Algorithm
Pages: 1 2 3 4 5

2 thoughts on “8-Puzzle Problem Using A* in C# and Unity”

    1. Hi Bladin,

      The codes are all there. You should be able to see in the PuzzleMap section. Below extracted from the post.
      public List> GetNeighbours(PuzzleNode loc)
      {
      List> neighbours = new List>();
      int zero = loc.Value.GetEmptyTileIndex();
      List intArray = GetNeighbors(zero);
      for (int i = 0; i < intArray.Count; ++i) { PuzzleNode state = new PuzzleNode(this, new PuzzleState(loc.Value)); state.Value.SwapWithEmpty(intArray[i]); neighbours.Add(state); } return neighbours; }

Leave a Reply

Your email address will not be published. Required fields are marked *