Welcome to our Unity game development tutorial series. In this tutorial, we will build the 8-Puzzle game and integrate A* (A-star) pathfinding to solve it. This tutorial is divided into three sections. First, we will focus on implementing the 8 puzzle game functionality, emphasising the programming aspects over design elements. Next, we will delve into implementing our pathfinding algorithms, including A*, Dijkstra’s, and Greedy Best-First Search. Finally, we will apply these pathfinding algorithms to solve various configurations of the 8-Puzzle.

# Page 1 – Introduction to 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.

**Read also 2D Grid-Based Pathfinding Using C# and Unity****Read also Graph-Based Pathfinding Using C# in Unity****Read also Solving 8 puzzle problem using A* star search in C++**

Our last tutorial, **Implement a Generic Pathfinder in Unity using C#**, implemented a generic pathfinder in Unity using C#. This tutorial will use that generic pathfinder and apply it to an 8-puzzle game. We will demonstrate how our generic pathfinder not only works on a 2d grid-based system but also solves an 8-puzzle problem.

## The 8-Puzzle Problem

The 8-Puzzle problem was invented and popularised by Noyes Palmer Chapman in the 1870s. It’s a smaller version of the more well-known 15-puzzle, consisting of a 3-by-3 grid with eight numbered square blocks and one blank square.

The objective of the puzzle is to rearrange the blocks into a specific order, typically shown with the blank square either at the beginning or end of the sequence. Blocks can be moved horizontally or vertically into the blank square to achieve the goal state.

The A* path-finding algorithm is commonly applied to grid-based pathfinding scenarios. However, in general, any pathfinding algorithm, including A*, can be utilised to solve graph-based problems. In this tutorial, we will use A* pathfinding to solve the 8-Puzzle problem.

## The 8-Puzzle Solution Search Space

The 8-Puzzle represents the largest possible N-puzzle that can be completely solved. While it is straightforward, it presents a substantial problem space. Larger variants like the 15-puzzle exist but cannot be entirely solved. This complexity classifies the N by N extension of the 8-Puzzle as an N-P hard problem.

The 8-Puzzle encompasses 9 factorial possible tile permutation states. Among these states, every second permutation is solvable. Therefore, there are a total of 9 factorial divided by 2 (9!/2), which is 181,440 solvable problem states.

Alexander Reinefeld from the Paderborn Center for Parallel Computing, Germany, demonstrated that the average length of all optimal solution paths is approximately 22 moves for any random configuration. Across the 181,440 solvable configurations, there are a total of 500,880 optimal solutions, providing an average solution density of 2.76 solutions per problem, with the range of solutions varying from 1 to 64.

The difficulty in solving the puzzle involves building the potential search tree and determining the most efficient path from the initial state to the goal state. To identify the optimal path, we employ Heuristic Search.

## Heuristic Search

Heuristic search is a method used to solve search problems more quickly than traditional methods. It often provides an approximate solution when conventional methods cannot, offering a generalised and approximate approach to problem-solving.

In simple terms, heuristic search can be likened to a rule of thumb or common-sense knowledge. While the answer isn’t guaranteed to be accurate, it aids in reaching a decision swiftly, sacrificing optimality, completeness, accuracy, or precision for speed.

Heuristic searches commonly involve heuristic values.

A heuristic value assigned to a node within the construction graph aims to capture the significance of that node’s value, such as cost or gain. Heuristic search, a form of informed search, utilises this heuristic value to optimise the search.

During each branching step, the search evaluates the heuristic value and selects which branch to pursue by ranking alternatives.

There are various types of heuristic search algorithms, with one notable example being the A* search algorithm.

### The A* Search

A* search is a computer search algorithm widely used for pathfinding and graph traversal. In our case of the 8-puzzle problem, we will use it for optimal graph traversal.

### The Cost Function of an 8-Puzzle State

The cost value of an 8-puzzle state is a combination of two values. It is often called the cost function **f**.

where **h** the heuristic cost gives how far the goal node is, and **g** is the number of nodes traversed from the start node to the current node. For **h,** we will use the Manhattan distance, and for g, we will use the depth of the current node.

For our A* search, we will use the sum of the Manhattan distance and the current depth of the node as the total cost.

**Manhattan distance**

We use the Manhattan distance heuristic for its simplicity and ability to estimate the number of moves required to bring a given puzzle state to the solution state. We compute this distance by the sum of the lengths of each tile from where it should belong.

```
function manhattan_distance(node, goal) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return dx + dy
```

Code language: JavaScript (javascript)

For example, the Manhattan distance between “213540678” and “123456780” is **9** and between “647850321” and “123456780” is **21**.

The diagram below shows the Manhattan cost for a specific tiles configuration.

## The Puzzle State

To solve the 8-Puzzle problem, we need a data structure to represent the puzzle’s tiles, which we will refer to as the puzzle’s **state**. Each state represents a unique combination of tiles, and throughout our solving process, we will need to manage potentially hundreds or thousands of these states. Each distinct tile arrangement in the puzzle corresponds to a node within a tree data structure.

To represent these states, we will use an integer array whose indices correspond to specific tile positions. The values stored at these indices represent the tile numbers. In this one-dimensional array representation, each index is fixed and represents a predefined tile location. This precise representation is crucial for our problem-solving process.

For example, index 0 corresponds to the top-left tile, index 1 to the top-center tile, and so on up to index 8 for the bottom-right tile. The value stored at each index indicates the actual tile number present in that location.

For instance, in a given state, as seen here, index 0 holds the value 2, index 1 holds 3, and index 8 holds 7, indicating the tile numbers in those respective positions. Index 4 holds the empty tile.

By manipulating the values in this array representation, while adhering to the constraint of where the empty tile can move with each action, we can efficiently progress towards reaching the goal state of the puzzle. This approach allows us to efficiently track and navigate through the various configurations of the puzzle during the solving process, making our solution approach highly effective.

## The Neighbours

Our next objective is to construct the graph of neighbours for the 8-Puzzle problem. This involves determining the neighbouring indices, for each of the 9 indices.

Constructing the graph of neighbours involves determining the possible moves or adjacent positions (neighboring indices) that the empty space (representing the movable tile) can move to from each tile position (or index) within the puzzle grid. In the context of the 8-Puzzle:

- We have a 3×3 grid where each cell is represented by an index ranging from 0 to 8, as described in the PuzzleState.
- Now, the task is to identify, for each index (representing a tile position), which other indices (tile positions) are its neighboring positions, meaning where the empty space can move to from that particular position.

By constructing this graph of neighbours, we establish the valid moves or transitions between different states of the puzzle, enabling the A* search to efficiently navigate the puzzle space and find the optimal sequence of moves to reach the goal configuration from any given start configuration. This graph representation is fundamental for implementing search algorithms in solving the 8-Puzzle problem.

For example, starting with tile index 0, the neighbouring indices, where the empty tile can move, are indices 1 and 3. Similarly, for tile index 1, the neighbours are indices 0, 2, and 4, and so on.

We will summarise this relationship in a list of neighbour indices for each tile index.

- Index 0: {1, 3}
- Index 1: {0, 2, 4}
- Index 2: {1, 5}
- Index 3: {4, 0, 6}
- Index 4: {3, 5, 1, 7}
- Index 5: {4, 2, 8}
- Index 6: {7, 3}
- Index 7: {6, 8, 4}
- Index 8: {7, 5}

With this mapping in place, we can then easily determine the neighbours for any tile index. For instance, for tile index 6, the neighbours are tile indices 7 and 3. It’s important to note that these indices refer to positions within the array representation of the puzzle state, not the actual values stored in those array elements.Now, let’s proceed to implement this functionality. We will utilise static variables and methods for this purpose. We will also contain this code with a region called **Neighbours**.

In the next page we will create the Unity Project, then create the frame and the basic UI.

A committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. **The past is something that you cannot undo. The future is something that you can build**.

*I enjoy coding, developing games and writing tutorials. *Visit my GitHub to see the projects I am working on right now.

Educator | Developer | Mentor

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

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