Greedy Best-First
Ready to supercharge your AI? While breadth-first search guarantees the shortest path, it can be painfully slow on large maps - exploring EVERYWHERE before finding the target. What if your AI could be smarter and guess which direction to search first?
Enter Best-First Search - the algorithm that adds intuition to pathfinding! Instead of blindly searching in all directions, your AI will make educated guesses about where the target might be, dramatically speeding up path discovery.
What You’ll Master:
- Heuristic-guided pathfinding (AI with intuition!)
- Trading perfect paths for blazing speed
- Manhattan distance calculations
- Priority queue magic for smarter searching
- Performance optimization for real-time games
Prerequisites:
- Completed the breadth-first pathfinding tutorial
- Ready to see your AI get seriously smart!
Time to give your pathfinding algorithm a brain upgrade that’ll make it 5-10x faster!
The Speed Revolution: Why Best-First Wins
Did You See That?! 🤯 Best-First Search just demolished Breadth-First in that race! While Breadth-First methodically searched EVERYWHERE like a thorough but slow detective, Best-First made smart guesses and bee-lined toward the target like a heat-seeking missile.
The Secret Sauce: Heuristics
Best-First doesn’t search blindly - it uses a heuristic function (fancy term for “educated guess”) to estimate how far each tile is from the target:
// Manhattan Distance: "Taxi cab" distance
function manhattanDistance(x1, y1, x2, y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
// This tells us: "tile (5,3) is probably 7 steps from target (10,8)"
const estimate = manhattanDistance(5, 3, 10, 8); // = 5 + 5 = 10
Why “Manhattan”? 🏙️ Imagine you’re driving in Manhattan - you can’t drive diagonally through buildings! You have to go block by block, just like our tile-based movement.
The Trade-off:
- ✅ Best-First: 5-10x faster, finds “good enough” paths
- ✅ Breadth-First: Always finds the shortest possible path, but slower
For real-time games, speed usually wins! Players won’t notice if the AI takes 10 steps instead of 9, but they WILL notice if the game freezes for half a second.
Implementing Smart Pathfinding
Let’s upgrade our pathfinding system with intelligence! The key changes from breadth-first are:
- Add heuristic calculation to each node
- Sort the search queue by estimated distance to target
- Always explore the most promising tiles first
class SmartPathNode {
constructor(x, y, parent = null, actualCost = 0, targetX = 0, targetY = 0) {
this.x = x;
this.y = y;
this.parent = parent;
this.actualCost = actualCost; // Steps taken to reach this tile
this.heuristic = this.calculateHeuristic(targetX, targetY);
this.estimatedTotal = actualCost + this.heuristic; // Best guess of total path cost
}
calculateHeuristic(targetX, targetY) {
// Manhattan distance - our "smart guess"
return Math.abs(this.x - targetX) + Math.abs(this.y - targetY);
}
getKey() {
return `${this.x},${this.y}`;
}
}
// The magic: Best-First Search with heuristic guidance
function findPathBestFirst(startX, startY, targetX, targetY, map) {
const startNode = new SmartPathNode(startX, startY, null, 0, targetX, targetY);
const openList = [startNode]; // Tiles to explore (priority queue)
const closedSet = new Set(); // Tiles already fully explored
while (openList.length > 0) {
// 🔥 THE MAGIC: Sort by heuristic (best guess first!)
openList.sort((a, b) => a.heuristic - b.heuristic);
const current = openList.shift();
// Found the target!
if (current.x === targetX && current.y === targetY) {
return buildPathArray(current);
}
// Mark as fully explored
closedSet.add(current.getKey());
// Explore neighbors
const neighbors = getValidNeighbors(current, targetX, targetY, map);
for (const neighbor of neighbors) {
const key = neighbor.getKey();
// Skip if already fully explored
if (closedSet.has(key)) continue;
// Add to exploration queue
const existingIndex = openList.findIndex(node => node.getKey() === key);
if (existingIndex === -1) {
openList.push(neighbor);
} else if (neighbor.actualCost < openList[existingIndex].actualCost) {
// Found a better path to this tile!
openList[existingIndex] = neighbor;
}
}
}
return null; // No path found
}
function getValidNeighbors(node, targetX, targetY, map) {
const directions = [
{ x: 0, y: -1 }, // Up
{ x: 1, y: 0 }, // Right
{ x: 0, y: 1 }, // Down
{ x: -1, y: 0 } // Left
];
return directions
.map(dir => {
const newX = node.x + dir.x;
const newY = node.y + dir.y;
return new SmartPathNode(newX, newY, node, node.actualCost + 1, targetX, targetY);
})
.filter(neighbor => isValidTile(neighbor.x, neighbor.y, map));
}
💡 The Breakthrough: By sorting the queue with openList.sort((a, b) => a.heuristic - b.heuristic), we always explore the most promising tiles first. It’s like having a GPS that says “this route LOOKS shorter” instead of trying every possible street!
Game Integration: Click-to-Move 2.0
Now let’s integrate our speed-demon pathfinding into a real game system:
const gameWorld = {
player: {
x: 5,
y: 5,
isMoving: false,
pathQueue: [],
moveSpeed: 3
},
// Enhanced click handling with fast pathfinding
handleClick(mouseX, mouseY) {
const tileX = Math.floor(mouseX / TILE_SIZE);
const tileY = Math.floor(mouseY / TILE_SIZE);
if (!this.isValidTile(tileX, tileY)) return;
// Use our smart pathfinding!
const path = findPathBestFirst(
this.player.x,
this.player.y,
tileX,
tileY,
gameMap
);
if (path) {
this.player.pathQueue = path;
this.player.isMoving = true;
// Visual feedback
this.showPathPreview(path);
console.log(`🎯 Smart path found: ${path.length} steps!`);
} else {
console.log('❌ No path to target!');
this.showErrorFeedback(tileX, tileY);
}
},
// Smooth movement along the calculated path
update() {
if (!this.player.isMoving || this.player.pathQueue.length === 0) {
return;
}
const nextWaypoint = this.player.pathQueue[0];
const targetPixelX = nextWaypoint.x * TILE_SIZE + TILE_SIZE / 2;
const targetPixelY = nextWaypoint.y * TILE_SIZE + TILE_SIZE / 2;
// Move toward waypoint
const dx = targetPixelX - this.player.sprite.x;
const dy = targetPixelY - this.player.sprite.y;
const distance = Math.sqrt(dx * dx + dy * dy);
if (distance < this.player.moveSpeed) {
// Reached waypoint - move to next!
this.player.x = nextWaypoint.x;
this.player.y = nextWaypoint.y;
this.player.sprite.x = targetPixelX;
this.player.sprite.y = targetPixelY;
this.player.pathQueue.shift();
if (this.player.pathQueue.length === 0) {
this.player.isMoving = false;
console.log('🏁 Destination reached!');
}
} else {
// Smooth movement
this.player.sprite.x += (dx / distance) * this.player.moveSpeed;
this.player.sprite.y += (dy / distance) * this.player.moveSpeed;
}
}
};
Performance Boost: Best-first search typically runs 5-10x faster than breadth-first, making real-time pathfinding viable for:
- RTS games with dozens of units
- RPG companions following the player
- Tower defense enemies navigating mazes
- Puzzle games with dynamic obstacles
Advanced Optimizations: Enterprise-Level Performance
Pro-Level Techniques for handling massive game worlds:
1. Hierarchical Pathfinding
For huge maps, don’t search tile-by-tile - use waypoints!
class HierarchicalPathfinder {
constructor(map) {
this.map = map;
this.waypoints = this.generateWaypoints(); // Key navigation points
this.waypointPaths = this.precalculatePaths(); // Pre-computed routes
}
findLongDistancePath(startX, startY, targetX, targetY) {
// Step 1: Find nearest waypoints
const startWaypoint = this.findNearestWaypoint(startX, startY);
const targetWaypoint = this.findNearestWaypoint(targetX, targetY);
// Step 2: Use pre-calculated waypoint-to-waypoint path
const waypointPath = this.waypointPaths[startWaypoint][targetWaypoint];
// Step 3: Add local paths (start → first waypoint, last waypoint → target)
const fullPath = [
...findPathBestFirst(startX, startY, waypointPath[0].x, waypointPath[0].y, this.map),
...waypointPath,
...findPathBestFirst(waypointPath[waypointPath.length-1].x, waypointPath[waypointPath.length-1].y, targetX, targetY, this.map)
];
return fullPath;
}
}
2. Asynchronous Pathfinding
Prevent game freezes on complex searches:
async function findPathAsync(startX, startY, targetX, targetY, map, maxStepsPerFrame = 50) {
return new Promise((resolve) => {
const startNode = new SmartPathNode(startX, startY, null, 0, targetX, targetY);
const openList = [startNode];
const closedSet = new Set();
let stepCount = 0;
function processChunk() {
for (let i = 0; i < maxStepsPerFrame && openList.length > 0; i++) {
openList.sort((a, b) => a.heuristic - b.heuristic);
const current = openList.shift();
stepCount++;
if (current.x === targetX && current.y === targetY) {
resolve(buildPathArray(current));
return;
}
closedSet.add(current.getKey());
// Add neighbors...
const neighbors = getValidNeighbors(current, targetX, targetY, map);
// ... processing logic
}
if (openList.length > 0) {
requestAnimationFrame(processChunk); // Continue next frame
} else {
resolve(null); // No path found
}
}
processChunk();
});
}
// Usage: Non-blocking pathfinding
findPathAsync(startX, startY, targetX, targetY, gameMap).then(path => {
if (path) {
player.followPath(path);
}
});
3. Smart Caching
class PathfindingCache {
constructor(maxSize = 1000) {
this.cache = new Map();
this.maxSize = maxSize;
}
getPath(startX, startY, targetX, targetY) {
const key = `${startX},${startY}->${targetX},${targetY}`;
return this.cache.get(key);
}
storePath(startX, startY, targetX, targetY, path) {
if (this.cache.size >= this.maxSize) {
// Remove oldest entry
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
const key = `${startX},${startY}->${targetX},${targetY}`;
this.cache.set(key, path);
}
}
Incredible Achievement! You’ve mastered intelligent pathfinding that’s ready for professional game development! Your AI can now:
- Find paths 5-10x faster than basic breadth-first
- Make smart decisions using heuristics
- 🏗️ Scale to massive worlds with hierarchical techniques
- ⏱️ Never freeze the game with async processing
- Handle real-time scenarios like RTS games
Next Level: Ready to learn A* pathfinding? It combines the best of both worlds - the optimality of breadth-first with the speed of best-first. Your journey into advanced game AI is just beginning!