121 lines
3.5 KiB
TypeScript
121 lines
3.5 KiB
TypeScript
import { GridCell, CellType, Position } from '../types';
|
|
|
|
export const GRID_SIZE = 40;
|
|
|
|
// Helper to check if a valid path exists from (0,0) to (end, end)
|
|
const checkSolvability = (grid: GridCell[][]): boolean => {
|
|
const q: Position[] = [{ x: 0, y: 0 }];
|
|
const visited = new Set<string>();
|
|
visited.add("0,0");
|
|
|
|
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
|
|
const targetX = GRID_SIZE - 1;
|
|
const targetY = GRID_SIZE - 1;
|
|
|
|
while (q.length > 0) {
|
|
const { x, y } = q.shift()!;
|
|
|
|
if (x === targetX && y === targetY) return true;
|
|
|
|
for (const [dx, dy] of dirs) {
|
|
const nx = x + dx;
|
|
const ny = y + dy;
|
|
|
|
if (nx >= 0 && nx < GRID_SIZE && ny >= 0 && ny < GRID_SIZE) {
|
|
const key = `${nx},${ny}`;
|
|
if (!visited.has(key)) {
|
|
const cell = grid[ny][nx];
|
|
// Traps and Walls are considered obstacles for a "safe path"
|
|
if (cell.type !== 'wall' && cell.type !== 'trap') {
|
|
visited.add(key);
|
|
q.push({ x: nx, y: ny });
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return false;
|
|
};
|
|
|
|
// Helper to force a path if one doesn't exist
|
|
// Uses a simple random walk biased towards the end to carve a path
|
|
const carvePath = (grid: GridCell[][]) => {
|
|
let currX = 0;
|
|
let currY = 0;
|
|
const targetX = GRID_SIZE - 1;
|
|
const targetY = GRID_SIZE - 1;
|
|
|
|
// Safety limit to prevent infinite loops (though unlikely)
|
|
let steps = 0;
|
|
const maxSteps = GRID_SIZE * GRID_SIZE;
|
|
|
|
while ((currX !== targetX || currY !== targetY) && steps < maxSteps) {
|
|
// Force current cell to be safe (unless it's start)
|
|
if (grid[currY][currX].type !== 'start') {
|
|
grid[currY][currX].type = 'safe';
|
|
}
|
|
|
|
// Determine next step
|
|
const validMoves = [];
|
|
// Bias: Try to move towards the goal
|
|
if (currX < targetX) validMoves.push({ x: currX + 1, y: currY }); // Right
|
|
if (currY < targetY) validMoves.push({ x: currX, y: currY + 1 }); // Down
|
|
|
|
// Small chance to move backwards/up to make the path less straight
|
|
if (Math.random() < 0.1 && currX > 0) validMoves.push({ x: currX - 1, y: currY });
|
|
if (Math.random() < 0.1 && currY > 0) validMoves.push({ x: currX, y: currY - 1 });
|
|
|
|
// Fallback if stuck (shouldn't happen with Right/Down logic but good for safety)
|
|
if (validMoves.length === 0) {
|
|
break;
|
|
}
|
|
|
|
const next = validMoves[Math.floor(Math.random() * validMoves.length)];
|
|
currX = next.x;
|
|
currY = next.y;
|
|
steps++;
|
|
}
|
|
|
|
// Ensure end is set correctly
|
|
grid[targetY][targetX].type = 'end';
|
|
};
|
|
|
|
export const generateGrid = (): GridCell[][] => {
|
|
const grid: GridCell[][] = [];
|
|
|
|
// 1. Generate Random Grid
|
|
for (let y = 0; y < GRID_SIZE; y++) {
|
|
const row: GridCell[] = [];
|
|
for (let x = 0; x < GRID_SIZE; x++) {
|
|
let type: CellType = 'safe';
|
|
|
|
const rand = Math.random();
|
|
if (rand < 0.25) { // Increased density slightly to make carving more meaningful
|
|
type = 'wall';
|
|
} else if (rand < 0.35) {
|
|
type = 'trap';
|
|
}
|
|
|
|
if (x === 0 && y === 0) type = 'start';
|
|
if (x === GRID_SIZE - 1 && y === GRID_SIZE - 1) type = 'end';
|
|
|
|
row.push({
|
|
x,
|
|
y,
|
|
type,
|
|
revealed: (x === 0 && y === 0) || (x === GRID_SIZE - 1 && y === GRID_SIZE - 1),
|
|
steppedOn: x === 0 && y === 0,
|
|
});
|
|
}
|
|
grid.push(row);
|
|
}
|
|
|
|
// 2. Check and Fix Solvability
|
|
if (!checkSolvability(grid)) {
|
|
// console.log("Map unsolvable, carving path...");
|
|
carvePath(grid);
|
|
}
|
|
|
|
return grid;
|
|
}; |