路径查找器之谜
You should find the shortest path among the blocks. The red ball is the start, the green ball means finish. The first is a player who finds the path, then the computer shows its path. If the number of steps is the same, the player wins. If the computer shows the fewest number of steps, it'll be a winner.
There are 2 modes:
- Simple mode
The game has no end. If you go out, the next game starts with the same moment.
- Survival mode
The game has a timer. The player has some time for finding the path. If he makes a mistake, the game ends.
The puzzle game for Android PathFinder is based on the classic shortest path problem. Your task is to find the shortest path between two points minimizing the number of steps while you pass through the blocks. Usually people use a special set of algorithms for solving the shortest path problem. There are a dozen of them. But the game for Android PathFinder is built on A*search algorithm. According to this algorithm the search of the path from the start to the destination point is based on the finding all possible paths and choosing the shortest path to the destination point for the one that incurs the fewest number of steps for the shortest time.
So, how does the puzzle game PathFinder use the A*search algorithm? It calculates all steps from the start (the red ball) to the finish (the green ball) until it finds the shortest way. The algorithm operates on multiple ways looking for the path from the start and not from the previous point. Thanks to this rule the A*search algorithm minimizes the number of steps passing through the blocks. Then it finds the way with the fewest number of steps from the wide range of solutions. That's why the A*search algorithm is widespread in computer games.