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). 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.
This video shows how I solve the game manually (I am not quite good at it):
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.
The code has been pushed to this repo.
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.
Assumptions
We assure that the assumptions are satisfied in this example:
- there are limited number of states;
- 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.
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.
