JavaScript Coding Test Course, Game Development

Problem Description

This is an algorithm problem that tracks the movement path of game characters.

Problem: Given a game map, the character starts at (0, 0) and moves to position (n, m). The character can move one step at a time in the upward, downward, left, or right directions, and obstacles are set as impassable tiles. When a map including obstacles is given, find the number of all possible paths for the character to reach the target location.

Input:

• First line: integers n, m (1 ≤ n, m ≤ 10)
• Next n lines: m integers (0 is an empty space, 1 is an obstacle)

Output: The number of paths to the target location

Problem-Solving Approach

To solve the problem, we will use the Depth First Search (DFS) method. DFS is effective in exploring all possible paths and counting the number of valid paths. We will proceed with the following steps:

1. Initialize the map as a 2D array.
2. Implement a recursive function to explore the path from (0, 0) to (n, m).
3. Stop the exploration when encountering obstacles or boundaries, and count the paths.
4. After exploring all paths, return the number of paths.

Code Implementation

Now, based on the above approach, we will proceed with the code implementation using JavaScript.

function countPaths(map, x, y, n, m) {
    // If the goal position is reached
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // If encountering boundaries or obstacles
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // Mark the current position as visited
    const temp = map[x][y];
    map[x][y] = 1; // Mark as obstacle to indicate visit
    
    // Move up, down, left, and right
    const paths = countPaths(map, x + 1, y, n, m) +
                  countPaths(map, x - 1, y, n, m) +
                  countPaths(map, x, y + 1, n, m) +
                  countPaths(map, x, y - 1, n, m);
    
    // Restore the visited position
    map[x][y] = temp;
    
    return paths;
}

function findAllPaths(map) {
    const n = map.length;
    const m = map[0].length;
    return countPaths(map, 0, 0, n, m);
}

// Test case
const gameMap = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

console.log(findAllPaths(gameMap)); // Output the number of paths

The above code calculates the number of paths that can be traversed from (0, 0) to (n-1, m-1) on the game map. It demonstrates well how to handle obstacles and boundaries.

Optimization

The implementation above is simple and easy to understand. However, this method may be inefficient due to duplicate explorations. To solve this, we can use memoization techniques. By using memoization, we can save the number of paths that have already been calculated and reuse the stored results when calculating at the same position, improving performance.

const memo = {};

function countPathsOptimized(map, x, y, n, m) {
    const key = x + ',' + y;
    // Check memoization
    if (key in memo) {
        return memo[key];
    }
    
    // If the goal position is reached
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // If encountering boundaries or obstacles
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // Mark the current position as visited
    const temp = map[x][y];
    map[x][y] = 1;
    
    // Calculate paths
    const paths = countPathsOptimized(map, x + 1, y, n, m) +
                  countPathsOptimized(map, x - 1, y, n, m) +
                  countPathsOptimized(map, x, y + 1, n, m) +
                  countPathsOptimized(map, x, y - 1, n, m);
    
    // Restore the visited position
    map[x][y] = temp;
    
    // Store in memoization
    memo[key] = paths;
    
    return paths;
}

function findAllPathsOptimized(map) {
    memo = {};
    const n = map.length;
    const m = map[0].length;
    return countPathsOptimized(map, 0, 0, n, m);
}

The optimized code above is almost similar to the previous code, but this time it prevents redundant calculations through memoization. This greatly enhances performance.

Conclusion

Through this course, we learned how to solve problems related to game development using JavaScript. We learned the basic approach needed to solve problems using DFS and memoization techniques. Practice solving algorithm problems to encounter and tackle more challenges.

Game development requires creative and logical thinking. By solving various algorithm problems, enhance your coding abilities and apply them to real projects. We will prepare more lectures related to algorithms and game development in the future. Thank you!