I recently played through Untrusted, a JavaScript game that encourages you to add code to its levels, in order to progress. It has been quite fun, especially level 13, which required you to write AI for a bot in the game. Without spoiling the fun for you, this post explores some ways of tackling the problem.
But first, a demo!
The task
A classic AI scenario: you need to navigate through a grid maze.
R is the robot, k is the key, # is a wall.
The robot should get to the key, moving left/right/top/bottom, and cannot go through walls.
The task does not pit you against adversaries and there are no random events. This allows the AI to plan its actions once and then execute the plan. The interesting part is how to find the path, a task also known as pathfinding.
Describing the problem
Before using any path searching algorithms, it is useful to define the problem space -- where the robot is, where it can move from there, and whether a given location is the goal (the key). Only then can a search be performed on the problem. In a 2D map, it is suitable to encode each location by its (x,y) coordinates -- this can represent every position of the robot in the maze. Here is how this looks like in code:
class Problem {
// define where the robot is initially
startState() {
return { x: 1, y: 1 };
}
// define whether the state is a goal (the blue key)
isGoal({ x, y }) {
return map.getObjectTypeAt(x, y) == "blueKey";
}
// define where the robot can go next, from a given state
successors({ x, y }) {
const adjacentCells = map.getAdjacentEmptyCells(x, y);
// augment the adjacent cell data with a direction
// { state: { x: 0, y: 1 }, direction: "left" }
return adjacentCells.map(
([ [ nextX, nextY ], direction ]) =>
({ state: { x: nextX, y: nextY }, direction }));
}
}
The map.* methods are from the kindly-provided game API. The problem extracts information from the map and converts it to robot states.
Depth-first search (DFS)
A correct path for getting from one state to the goal is a sequence of moves beteween these states. If the robot is at state (0,0) and the key is at (1,0), one correct path is ["right"]. Another correct path is ["top","right","bottom"] - for some problems, you may be looking for an optimal path, for others -- just if there is one.
With the problem definition, we can devise a path to the blue key using graph search:
function id(state) {
// convert a state to a unique identifier
return state.x + 1000 * state.y;
}
function depthFirst (problem) {
// states that have been visited
const closed = new Set();
// the states that still need to be checked
const fringe = [
// at first, only the starting state
{ state: problem.startState(), path: [] }
];
while (fringe.length) {
var node = fringe.pop();
var state = node.state;
var path = node.path;
// if the state is a goal, we have completed the search
if (problem.isGoal(state)) {
return path;
}
// do not repeat the algorithm over visited nodes
if (closed.has(id(state))) {
continue;
}
// add all successor states to the list of unchecked states
problem.successors(state).forEach(
(successor) => fringe.push({
state: successor.state,
path: path.concat([ successor.direction ])
});
);
// mark the state as visited
closed.set(id(state), true);
}
// no path to a goal state was found :(
return null;
}
// get the path to the goal
var path = depthFirst(new Problem());
The above code is more or less everything that you need in order to complete the level. However, you may find that it doesn't find the shortest path to the key. Depth-first search moves through the first possible node, then through its first adjacent node, and so on -- until it finds a goal or runs out of nodes.
Breadth-first search (BFS)
Instead of going deeper in the maze, the robot can consider nearby spaces first. It will first check all locations that are successors of the starting field, and only then check all of their successors. This makes it naturally search for the shortest path, as longer paths are only considered after all neighboring cells are checked. Enter breadth-first search.
To achieve this, the above algorithm can be modified, so that it uses a queue of states, instead of a stack.
// pass the fringe as a parameter
function graphSearch (problem, fringe) {
const closed = new Set();
fringe.push({ state: problem.startState(), path: [], cost: 0 });
while (fringe.length) {
let node = fringe.pop();
let { state, path, cost } = node;
if (problem.isGoal(state)) {
return path;
}
if (!closed.has(key(state.x, state.y))) {
closed.add(key(state.x, state.y));
problem.successors(state).forEach(
(successor) => fringe.push({
state: successor.state,
path: path.concat([ successor ]),
cost: cost + 1
})
);
}
}
return [];
}
// breadth-first search
var queue = [];
queue.pop = queue.shift;
var path = graphSearch(new Problem(), queue);
// depth-first search
var stack = [];
var path = graphSearch(new Problem(), stack);
With just a change to the fringe data structure, the algorithm strategy switches. Notice that this search will surely lead to optimal solutions, but will exhaustively check all its options for shorter paths, even if they clearly move it away from the goal.
A* search
Breadth-first search yields great results, but at what cost? The robot always tries all short paths first, even if they get it farther from the goal. But what if the robot had a metal detector that can sense the key? It could determine if it is getting closer to the key, or moving in the other direction.
This is what A* (A-star) search does. It uses a heuristic function to determine whether a given search node is likely to be on the right path. One simple heuristic function in a grid maze is the manhattan distance - the absolute difference between the x and y of the robot and the key. Much like a metal detector, it will not tell which direction in the maze leads to the key, only if the key is near. With the heuristic in place, the robot can prioritize the search, so that nodes closer to the key are expanded
// calculate absolute distance to key, between states
const goal = map.getKeyLocation();
const abs = Math.abs;
const manhattanDistance = (a, b) => (abs(a.x - b.x) + abs(a.y - b.y));
// use distance to prioritize states
const fringe = new PriorityQueue(
(item) => (item.cost + manhattanDistance(item.state, goal))
);
// calculate path
let path = graphSearch(problem, fringe);
Again, changing the fringe changes the algorithm strategy. I like to think that A-star is more general than BFS and DFS, just like a priority queue is a more general data structure than a stack and a queue.
Now, go play Untrusted!