engine.scope(({ start, cls, mget, map, spr, click, mouse, rect, rectfill, circfill, cursor, caption, btnp, base }) => { const { Sprites, Sounds, GridMud, Dirs4, Dirs8, Cost, Constants, key, initGrid } = base(); const sprites = { floor: Sprites.Floor, wall: Sprites.Wall, mud: Sprites.Mud, player: Sprites.Player }; const algorithms = ['BFS 4-dir', 'BFS 8-dir', 'Dijkstra', 'A*']; let playerPx = 12, playerPy = 12; let targetX = -1, targetY = -1; let path = []; let active = 0; let results = []; function findPathBfs4(sx, sy, gx, gy) { if (mget(gx, gy, 0) === 'wall') return null; const queue = [{ x: sx, y: sy }]; const visited = new Set([key(sx, sy)]); const parent = {}; while (queue.length > 0) { const { x, y } = queue.shift(); if (x === gx && y === gy) { const result = []; let cx = gx, cy = gy; while (cx !== sx || cy !== sy) { result.push({ x: cx, y: cy }); const p = parent[key(cx, cy)]; cx = p.x; cy = p.y; } return { path: result.reverse(), explored: visited }; } for (const [dx, dy] of Dirs4) { const nx = x + dx, ny = y + dy; if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue; if (visited.has(key(nx, ny))) continue; if (mget(nx, ny, 0) === 'wall') continue; visited.add(key(nx, ny)); parent[key(nx, ny)] = { x, y }; queue.push({ x: nx, y: ny }); } } return null; } function findPathBfs8(sx, sy, gx, gy) { if (mget(gx, gy, 0) === 'wall') return null; const queue = [{ x: sx, y: sy }]; const visited = new Set([key(sx, sy)]); const parent = {}; while (queue.length > 0) { const { x, y } = queue.shift(); if (x === gx && y === gy) { const result = []; let cx = gx, cy = gy; while (cx !== sx || cy !== sy) { result.push({ x: cx, y: cy }); const p = parent[key(cx, cy)]; cx = p.x; cy = p.y; } return { path: result.reverse(), explored: visited }; } for (const [dx, dy] of Dirs8) { const nx = x + dx, ny = y + dy; if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue; if (visited.has(key(nx, ny))) continue; if (mget(nx, ny, 0) === 'wall') continue; if (dx !== 0 && dy !== 0) { if (mget(x + dx, y, 0) === 'wall') continue; if (mget(x, y + dy, 0) === 'wall') continue; } visited.add(key(nx, ny)); parent[key(nx, ny)] = { x, y }; queue.push({ x: nx, y: ny }); } } return null; } function findPathDijkstra(sx, sy, gx, gy) { if (mget(gx, gy, 0) === 'wall') return null; const dist = {}; dist[key(sx, sy)] = 0; const parent = {}; const explored = new Set(); const queue = [{ x: sx, y: sy, d: 0 }]; while (queue.length > 0) { const { x, y, d } = queue.shift(); const k = key(x, y); if (explored.has(k)) continue; explored.add(k); if (x === gx && y === gy) { const result = []; let cx = gx, cy = gy; while (cx !== sx || cy !== sy) { result.push({ x: cx, y: cy }); const p = parent[key(cx, cy)]; cx = p.x; cy = p.y; } return { path: result.reverse(), explored }; } for (const [dx, dy] of Dirs8) { const nx = x + dx, ny = y + dy; if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue; const nt = mget(nx, ny, 0); if (nt === 'wall') continue; if (dx !== 0 && dy !== 0) { if (mget(x + dx, y, 0) === 'wall') continue; if (mget(x, y + dy, 0) === 'wall') continue; } const moveCost = (dx !== 0 && dy !== 0) ? Cost[nt] * 1.41 : Cost[nt]; const nd = d + moveCost; const nk = key(nx, ny); if (nd < (dist[nk] ?? Infinity)) { dist[nk] = nd; parent[nk] = { x, y }; let i = 0; while (i < queue.length && queue[i].d <= nd) i++; queue.splice(i, 0, { x: nx, y: ny, d: nd }); } } } return null; } function findPathAStar(sx, sy, gx, gy) { if (mget(gx, gy, 0) === 'wall') return null; function heuristic(x, y) { const dx = Math.abs(x - gx), dy = Math.abs(y - gy); return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy); } const g = {}; g[key(sx, sy)] = 0; const parent = {}; const explored = new Set(); const queue = [{ x: sx, y: sy, f: heuristic(sx, sy) }]; while (queue.length > 0) { const { x, y } = queue.shift(); const k = key(x, y); if (explored.has(k)) continue; explored.add(k); if (x === gx && y === gy) { const result = []; let cx = gx, cy = gy; while (cx !== sx || cy !== sy) { result.push({ x: cx, y: cy }); const p = parent[key(cx, cy)]; cx = p.x; cy = p.y; } return { path: result.reverse(), explored }; } for (const [dx, dy] of Dirs8) { const nx = x + dx, ny = y + dy; if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue; const nt = mget(nx, ny, 0); if (nt === 'wall') continue; if (dx !== 0 && dy !== 0) { if (mget(x + dx, y, 0) === 'wall') continue; if (mget(x, y + dy, 0) === 'wall') continue; } const moveCost = (dx !== 0 && dy !== 0) ? Cost[nt] * 1.41 : Cost[nt]; const ng = (g[k] ?? Infinity) + moveCost; const nk = key(nx, ny); if (ng < (g[nk] ?? Infinity)) { g[nk] = ng; parent[nk] = { x, y }; const f = ng + heuristic(nx, ny); let i = 0; while (i < queue.length && queue[i].f <= f) i++; queue.splice(i, 0, { x: nx, y: ny, f }); } } } return null; } function init() { cursor('crosshair'); initGrid(GridMud); } function update() { for (let i = 0; i < 4; i++) { if (btnp(String(i + 1)) && active !== i) { active = i; path = results[active]?.path ?? []; } } if (click()) { const pos = mouse(); const gx = Math.max(0, Math.min(15, Math.floor(pos.x / 8))); const gy = Math.max(0, Math.min(15, Math.floor(pos.y / 8))); const sx = Math.floor(playerPx / 8); const sy = Math.floor(playerPy / 8); results = [ findPathBfs4(sx, sy, gx, gy), findPathBfs8(sx, sy, gx, gy), findPathDijkstra(sx, sy, gx, gy), findPathAStar(sx, sy, gx, gy), ]; if (results[active]) { path = results[active].path; targetX = gx; targetY = gy; } } if (path.length > 0) { const tx = path[0].x * 8 + 4; const ty = path[0].y * 8 + 4; const dx = tx - playerPx; const dy = ty - playerPy; const dist = Math.sqrt(dx * dx + dy * dy); if (dist < 1) { playerPx = tx; playerPy = ty; path.shift(); } else { playerPx += (dx / dist) * Constants.Speed; playerPy += (dy / dist) * Constants.Speed; } } } function draw(time, frame) { cls(0); map(0); const r = results[active]; if (r) { for (const k of r.explored) { const [ex, ey] = k.split(',').map(Number); rectfill(ex * 8 + 2, ey * 8 + 2, ex * 8 + 5, ey * 8 + 5, 8); } } for (const step of path) circfill(step.x * 8 + 4, step.y * 8 + 4, 1, 9); if (targetX >= 0) { if (frame % 30 < 15) rectfill(targetX * 8 + 2, targetY * 8 + 2, targetX * 8 + 5, targetY * 8 + 5, 10); else rect(targetX * 8, targetY * 8, targetX * 8 + 8, targetY * 8 + 8, 10); } spr('player', Math.floor(playerPx) - 4, Math.floor(playerPy) - 4); caption(algorithms[active] + ' [' + (active + 1) + ']', 1, 1, 7); if (r) caption('path:' + r.path.length + ' explored:' + r.explored.size, 1, 8, 7); } start({ sprites, sounds: Sounds, init, update, draw, target }); });

Editando: Pathfinding: Complete Example

Ediciones recientes

Plugins