- Pathfinding
- Finding a route between two points through a space with obstacles, costs, or rules.
- Graph
- A set of nodes (places) joined by edges (connections). Every map a search uses is a graph.
- Node
- One location in a graph, like a single grid cell, a city, or a maze junction.
- Edge
- A connection between two nodes. It can be one-way (directed) or two-way (undirected).
- Weight / cost
- How expensive it is to cross an edge or enter a tile. In the rover lab, open ground costs 1 and sand costs 3.
- Neighbor
- A node you can reach in one move. On the rover grid, that means up, down, left, or right.
- Heuristic
- A quick, educated guess. In A*, it estimates the cost left to reach the goal.
- g(n)
- The real cost paid so far to get from the start to node n.
- h(n)
- The heuristic estimate of the cost from node n to the goal.
- f(n)
- g(n) + h(n): the total estimated cost of a route through node n. A* expands the lowest f first.
- Admissible
- A heuristic that never overestimates the true remaining cost. It lets A* guarantee the cheapest path.
- Manhattan distance
- Horizontal steps plus vertical steps, like walking city blocks. Fits grids with no diagonal moves.
- Euclidean distance
- Straight-line (“as the crow flies”) distance between two points.
- Open set (frontier)
- Cells found but not checked yet. The waiting cells in the lab.
- Closed set
- Cells already checked. The search won't expand them again.
- Priority queue
- A to-do list that always gives back the lowest-scored item first. Dijkstra and A* both use one.
- Optimal path
- The cheapest possible route. BFS finds the fewest steps. Dijkstra and A* find the lowest total cost.
- Floodfill
- Filling every cell connected to a starting cell, like a paint-bucket tool.
- Backtracking
- Going back to the last choice point after hitting a dead end, then trying another way. DFS works this way.
- Navigation mesh (navmesh)
- Connected walkable polygons laid over a 3D game level. Characters search it in place of a fine grid.
- Replanning
- Running the search again when the map changes, like a map app rerouting around traffic.