diff options
Diffstat (limited to 'html/tower/js/path.js')
| -rw-r--r-- | html/tower/js/path.js | 83 |
1 files changed, 68 insertions, 15 deletions
diff --git a/html/tower/js/path.js b/html/tower/js/path.js index 46e4bfb..91193e2 100644 --- a/html/tower/js/path.js +++ b/html/tower/js/path.js @@ -1,18 +1,49 @@ -// Path generation using a modified depth-first search algorithm +/** + * Path Generation Module + * + * This module demonstrates several advanced game development concepts: + * 1. Procedural Content Generation (PCG) + * 2. Pathfinding algorithms + * 3. Constraint-based generation + */ + +/** + * Generates a valid path through the game grid using a modified depth-first search. + * This algorithm ensures: + * - Path always moves from left to right + * - No diagonal movements + * - No path segments touch each other (except at turns) + * - Path is always completable + * + * @param {Array<Array<string>>} grid - 2D array representing the game grid + * @returns {Promise<Array<{x: number, y: number}>>} Promise resolving to array of path coordinates + * + * Implementation uses: + * - Backtracking algorithm pattern + * - Constraint satisfaction + * - Random selection for variety + */ function generatePath(grid) { const width = grid[0].length; const height = grid.length; - // Pick random start point on left edge + // Initialize with random start point on left edge const startY = Math.floor(Math.random() * height); let currentPos = { x: 0, y: startY }; - // Initialize path with start position const path = [currentPos]; grid[startY][0] = 'path'; + /** + * Determines valid moves from current position based on game rules + * Uses constraint checking to ensure path validity + * + * @param {Object} pos - Current position {x, y} + * @returns {Array<{x: number, y: number}>} Array of valid next positions + */ function getValidMoves(pos) { const moves = []; + // Prioritize right movement for path progression const directions = [ { x: 1, y: 0 }, // right { x: 0, y: -1 }, // up @@ -23,12 +54,12 @@ function generatePath(grid) { const newX = pos.x + dir.x; const newY = pos.y + dir.y; - // Check bounds + // Enforce boundary constraints if (newX < 0 || newX >= width || newY < 0 || newY >= height) { continue; } - // Check if cell is empty and not adjacent to path (except previous cell) + // Check path isolation constraint if (grid[newY][newX] === 'empty' && !hasAdjacentPath(newX, newY, grid)) { moves.push({ x: newX, y: newY }); } @@ -37,6 +68,15 @@ function generatePath(grid) { return moves; } + /** + * Checks if a position has adjacent path tiles (excluding previous path tile) + * Implements path isolation constraint + * + * @param {number} x - X coordinate to check + * @param {number} y - Y coordinate to check + * @param {Array<Array<string>>} grid - Current grid state + * @returns {boolean} True if position has adjacent path tiles + */ function hasAdjacentPath(x, y, grid) { const adjacentCells = [ { x: x, y: y - 1 }, // up @@ -54,14 +94,14 @@ function generatePath(grid) { }); } - // Generate path until we reach the right edge + // Main path generation loop with backtracking while (currentPos.x < width - 1) { const moves = getValidMoves(currentPos); if (moves.length === 0) { - // If no valid moves, backtrack + // Backtrack when no valid moves exist if (path.length <= 1) { - // Start over if we can't backtrack + // Restart if backtracking fails return generatePath(grid); } @@ -72,7 +112,7 @@ function generatePath(grid) { continue; } - // Choose random valid move + // Random selection for path variety const nextMove = moves[Math.floor(Math.random() * moves.length)]; currentPos = nextMove; path.push(currentPos); @@ -82,11 +122,24 @@ function generatePath(grid) { return Promise.resolve(path); } +/** + * Calculates a position along the path based on a progress value + * Implements smooth entity movement along path segments + * + * @param {number} progress - Progress along path (0-1) + * @param {Array<{x: number, y: number}>} path - Array of path coordinates + * @returns {{x: number, y: number}} Interpolated position along path + * + * Uses: + * - Linear interpolation (lerp) + * - Path segment traversal + * - Normalized progress tracking + */ function getPathPosition(progress, path) { - // Ensure progress is between 0 and 1 + // Normalize progress to valid range progress = Math.max(0, Math.min(1, progress)); - // Get the total path length + // Calculate total path length for normalization let totalLength = 0; for (let i = 1; i < path.length; i++) { const dx = path[i].x - path[i-1].x; @@ -94,10 +147,10 @@ function getPathPosition(progress, path) { totalLength += Math.sqrt(dx * dx + dy * dy); } - // Find target distance along path + // Convert progress to distance along path const targetDistance = progress * totalLength; - // Find the segment where the target position lies + // Find appropriate path segment let currentDistance = 0; for (let i = 1; i < path.length; i++) { const dx = path[i].x - path[i-1].x; @@ -105,7 +158,7 @@ function getPathPosition(progress, path) { const segmentLength = Math.sqrt(dx * dx + dy * dy); if (currentDistance + segmentLength >= targetDistance) { - // Calculate position within this segment + // Linear interpolation within segment const segmentProgress = (targetDistance - currentDistance) / segmentLength; return { x: path[i-1].x + dx * segmentProgress, @@ -116,6 +169,6 @@ function getPathPosition(progress, path) { currentDistance += segmentLength; } - // If we somehow exceed the path length, return the last point + // Fallback to end of path return { ...path[path.length - 1] }; } \ No newline at end of file |