Solving puzzle: The-Labylinth

There are 2 objectives in this puzzle:

• Find the control room (C)

• Back to starting point (T) after control room found.

Objective 1: Find the control room (C)

The map provided are not good for computer process, therefore I need to convert the ASCII map into score map, which

• Wall = MAX

• T : 0

• C: 0

• ? = MAX

The score map records the player exploration history, such that the play will not explore the same road again. In short,

1. When the player stepped on point (x, y), the score map (x,y) will be added by 1

2. The player choose the lowest cost when selecting direction

3. Repeat above until C was found

Objective 2: Back to starting position (T)

Once the player found the control room, he need to back to starting position (T). Unlike objective 1, the number of steps is limited, such that we need to found the optimal path to position T.

Given the current score MAP, we need to reset the explored path to very large number(e.g. 1000000), and then we calculate the optimal path by apply T with cost 1 to the following function:

Given a recursive function f(x) as:

1. Given a position x, get the cost of this position in score Map

2. Exploring all possible path (u, d, l, f) that x can go, then check whether the cost of these possible path > cost of x +1, we explore these path on if the current path is minimum

3. Repeat until C found

Then the 'optimal path' was found. Then final step is:

1. Starting from position C, go to the direction with minimum cost in the score map

2. Repeat until T is reach

Take away:

1. I found this game is great on merge both path finding and optimal path search into the same game, such that I spend many times to united the score map to use in both situation.

2. My solution in objective 2 is not optimal solution. It is because find the optimal path based on exploration history, which may not the best route until all unknow path discovered

#pathfinding #BFS