A* algorithm for solving Sliding Tiles Game
Tags: astar, csharp, planning
Published: 2020-12-14 11:24:51

This weekend I found in my old hard disk a tiny game I wrote years ago. I was learning motion planning algorithms in that period, thus this game was one exercise of mine for testing the **A* search algorithm** (see [introduction](https://en.wikipedia.org/wiki/A*_search_algorithm)). This algorithm is a very traditional one thus I will not present it in my post. One who is interested can read [this book] (http://lavalle.pl/planning/) By Steven M. LaValle for details. 

## Number tiles Game in Visual Studio

I developed the sliding number tiles game (shown below) as a small desktop software using Visual Studio.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/l9iasejgl73xuj6bxkt7.PNG)

This video shows how I solve the game manually (I am not quite good at it):
{% youtube kU1aec4fqfc %}

## Solving it using A*

Now I touch "S"-key of my keyboard, and the A* algorithm starts to solve the puzzle (search a path). And I push "S"-key again, it starts to show the solution.
{% youtube tsv5wD8s2Ks %}

The code has been pushed to [this repo](https://github.com/jemaloQ/astar_search_game.git). 

Below are simple explanations of the algorithm in this example.

## Algorithm explanation

### Node and graph
Each configuration of this game corresponds to a node in its state graph as shown below. So in order to solve this game, we need to find a path that links node start to node target via a sequence of intermediate nodes.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/z65q1qk594ahgpippp6a.PNG)

### Assumptions

We assure that the **assumptions** are satisfied in this example: 
  1. there are limited number of states; 
  2. there is a valid heuristic function for assessing the distance between nodes: sum of distance (in number of moves) for each tile from its current position to its target position

### Some conceptions:
**Closed set**: a set of nodes that has been assessed 
**Frontier set**: a set of nodes that are about to be explored

### StateNode class
Each state node object in the code has value members:
**parent**: a node from which current node comes with one move
**g**: path cost from **start** node to current node
**h**: distance cost from current node to **target** node
**isExpanded**: a flag noting if all neighbors of this node are in **Closed set**

### Algorithm pseudo-code details:

**Init**: put start node into closed set and frontier set

**Explore_node** for a given node:

I have developed the core function of this algorithm *explore_Tree*(**n_i**) and it do the following works in a recursive way: 
    (1) for each neighbor nodes **n_k** of node **n_i**, check firstly if **n_k** is already included in closed set. 
    (2) If we get YES for step 1, and if current cost of **n_k** (namely: **g+h**) is lower than its cost in the **closed set**, update its cost and update its parent as **n_i**;  
    (3) If we get NO for step 1: put current node **n_k** into **frontier** and **closed set**, calculate its cost, define **n_k**'s parent as **n_i**
    (4) delete **n_i** from **frontier set**
    (5) check if any node in **frontier** has reached target node
    (6) if target reached, return True
    (7) if target not yet reached, select **node of the lowest cost from frontier set**, and call function *explore_Tree()* for it.

If **Explore_node** finally returns True, it means that the optimal path is found. We can then retrieve the path by tracking recursively the parent, starting from the target node.

### Illustration

The following image shows the first step of this algorithm: exploring neighbors of the start node and assessing the cost of each node. 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/mo16qo6j52ir6n6d0gpn.PNG)

Following the step shown above, the image below shows the how A* explores recursively the "optimal" move. In this step, it locates the lowest-cost node in frontier then explores its neighbors and assesses their cost. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/2fj62u79o04fh8g64pxh.PNG)