Maze games and BFS (Leetcode #490 #505)
Recently when I was reviewing Ludum Dare game jam competition and those artworks from the past years, some of the witty ideas really inspired me. In LD 37(2016, the theme: one room）, @managore(Daniel Linssen) created the coolest chatroom platform game Walkie Talkie with perfect implementation and top entries. Since he is always one of my favourite indie game designers so I'm looking forward to his game this year.
This 1-bit style game called adrena-line that made for Ludum Dare 46(Deeper and Deeper) is also published on his personal website. And this maze really reminds me of a classic BFS leetcode problem and its extension.
Breadth-First Search
In BFS, we first explores a graph starting at a node and visits all the node's neighbors, then visits all the neighbors's neighbors and continues in this fashion. In pseudocode, we could present a simple template for the similar problems.
1int BFS(Node Node start, Node target){
2 Queue<Node> q; // core datastructure
3 Set<Node> visited; // avoid visited nodes to be added
4
5 q.offer(start); // add start point to the queue
6 visited.add(start);
7 int step = 0; // record radius steps
8
9 while(q not empty){
10 int sz = q.size();
11 // add one step radius for all the nodes in queue
12 for(int i = 0; i < sz; i++){
13 Node cur = q.poll();
14 // judge: is it the desitination?
15 if(cur is target)
16 return step;
17 // add cur's neighbors to queue
18 for(Node x: cur.adj())
19 if(x not in visited){
20 q.offer(x);
21 visited.add(x);
22 }
23 }
24 // update steps
25 step++
26 }
27}Leetcode 490 Discription
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
This problem is a classic 2D matrix BFS traversing, we may choose to initialize a direction array first.
1int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};The critical part is the right time for conditional checking whether the current node is the destination. We could put this code right after polling elements from the queue.
1class Solution {
2 public boolean hasPath(int[][] maze, int[] start, int[] destination) {
3 int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
4 boolean[][] visited = new boolean[maze.length][maze[0].length];
5 Queue<int[]> q = new LinkedList<>();
6 q.add(start);
7 visited[start[0]][start[1]] = true;
8 while (!q.isEmpty()){
9 int[] cur = q.poll();
10 if (cur[0] == destination[0] && cur[1] == destination[1]){
11 return true;
12 }
13 for(int[] dir : dirs){
14 int x = cur[0], y = cur[1];
15 while(x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] != 1){
16 x += dir[0];
17 y += dir[1];
18 }
19 x -= dir[0];
20 y -= dir[1];
21 if(!visited[x][y]){
22 q.add(new int[] {x, y});
23 visited[x][y] = true;
24 }
25 }
26 }
27 return false;
28
29 }
30}Leetcode 505 Discription
Almost the same as #490 except for return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
1class Solution {
2 int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
3 public int shortestDistance(int[][] maze, int[] start, int[] destination) {
4 int[][] distance = new int[maze.length][maze[0].length];
5 for(int[] row:distance) Arrays.fill(row, Integer.MAX_VALUE);
6 distance[start[0]][start[1]] = 0;
7 dijkstra(maze, start, distance);
8 return distance[destination[0]][destination[1]] == Integer.MAX_VALUE? -1 : distance[destination[0]][destination[1]];
9 }
10
11 public void dijkstra(int[][] maze, int[] start, int[][] distance){
12 PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
13 q.offer(new int[]{start[0], start[1], 0});
14 while (!q.isEmpty()){
15 int[] cur = q.poll();
16 for(int[] dir : dirs){
17 int x = cur[0] + dir[0], y = cur[1] + dir[1], count = 0;
18 while(x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0){
19 x += dir[0];
20 y += dir[1];
21 count++;
22 }
23 x -= dir[0];
24 y -= dir[1];
25 if(distance[cur[0]][cur[1]] + count < distance[x][y]){
26 distance[x][y] = distance[cur[0]][cur[1]] + count;
27 q.add(new int[]{x, y, distance[x][y]});
28
29 }
30 }
31 }
32
33 }
34}