Skip to content

# 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.

## 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

• `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.
• Drag and drop the Status Text from the Canvas and associate it with the `Status Text` field of the PuzzleBoard script.
• Drag and drop the NumMoves Text from the Canvas and associate it with the `Number of Moves Text` field of the PuzzleBoard script.
• 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.

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

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.

Pages: 1 2 3 4 5

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

1. There is missing code contructor, mEdges and GetNeighbors in PuzzleMap sir

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; }