---
key: lesson/npc-pathfinding
type: lesson
id: npc-pathfinding
lang: en
title: Pathfinding and following a route
summary: >-
  Choose a space representation and traversal costs while separating a computed
  path from actual NPC movement.
updatedAt: '2026-10-20'
status: active
url: 'https://gamemechanics.pro/en/lessons/npc-pathfinding/'
jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/en/lesson/npc-pathfinding.json'
markdownUrl: 'https://gamemechanics.pro/content/knowledge/en/lesson/npc-pathfinding.md'
aliases:
  - навигация
  - navigation
  - Дейкстра
  - Dijkstra
  - BFS
  - A*
tags:
  - npc-ai
  - pathfinding
  - algorithms
sourceIds:
  - source-f4e30147f2944e5d
sources:
  - id: source-f4e30147f2944e5d
    title: 'Amit Patel, Red Blob Games: Introduction to the A* Algorithm'
    url: 'https://www.redblobgames.com/pathfinding/a-star/introduction.html'
    verifiedAt: null
relations:
  - type: requires
    direction: outgoing
    label: Before you start
    key: lesson/collision-basics
    title: Collision fundamentals
    url: 'https://gamemechanics.pro/en/lessons/collision-basics/'
    jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/en/lesson/collision-basics.json'
    markdownUrl: 'https://gamemechanics.pro/content/knowledge/en/lesson/collision-basics.md'
  - type: explains
    direction: outgoing
    label: Apply the principle
    key: mechanic/point-and-click--family-24
    title: 'Maps, routes and mazes'
    url: >-
      https://gamemechanics.pro/en/knowledge/mechanic/point-and-click--family-24/
    jsonUrl: >-
      https://gamemechanics.pro/api/v1/knowledge/en/mechanic/point-and-click--family-24.json
    markdownUrl: >-
      https://gamemechanics.pro/content/knowledge/en/mechanic/point-and-click--family-24.md
  - type: practices
    direction: outgoing
    label: Put it into practice
    key: practice/maintenance-patrol
    title: Maintenance patrol
    url: 'https://gamemechanics.pro/en/knowledge/practice/maintenance-patrol/'
    jsonUrl: >-
      https://gamemechanics.pro/api/v1/knowledge/en/practice/maintenance-patrol.json
    markdownUrl: >-
      https://gamemechanics.pro/content/knowledge/en/practice/maintenance-patrol.md
  - type: reviews
    direction: outgoing
    label: Review through a lens
    key: lens/schell-026
    title: Functional Space
    url: 'https://gamemechanics.pro/en/knowledge/lens/schell-026/'
    jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/en/lens/schell-026.json'
    markdownUrl: 'https://gamemechanics.pro/content/knowledge/en/lens/schell-026.md'
  - type: contains
    direction: incoming
    label: Learning paths
    key: path/npc-behavior
    title: NPC behavior
    url: 'https://gamemechanics.pro/en/learn/npc-behavior/'
    jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/en/path/npc-behavior.json'
    markdownUrl: 'https://gamemechanics.pro/content/knowledge/en/path/npc-behavior.md'
placements: []
supersededBy: []
attributes:
  category: engineering
  level: intermediate
  minutes: 6
endsAt: null
provenance: >-
  Original gamemechanics.pro material. Check illustrative examples in your own
  project.
license: CC-BY-4.0
codeLicense: MIT
attribution: gamemechanics.pro contributors
---
# Pathfinding and following a route

id: npc-pathfinding
type: lesson
key: lesson/npc-pathfinding
lang: en
status: active
url: https://gamemechanics.pro/en/lessons/npc-pathfinding/

Choose a space representation and traversal costs while separating a computed path from actual NPC movement.

## Prerequisites

Finding a sequence of cells and moving a character through it without getting stuck are separate tasks. Start with a space model, then check both parts.

## The principle

Search operates on a graph: nodes and allowed transitions between them. [Red Blob Games](https://www.redblobgames.com/pathfinding/a-star/introduction.html) applies the same idea to different spatial representations. A tile grid is convenient but optional.

With equal edge costs, breadth-first search (BFS) finds a path with the fewest transitions. With differing nonnegative costs, Dijkstra accounts for their sum. A* adds an estimate of the remaining cost. On a four-connected grid without diagonals, Manhattan distance multiplied by the minimum step cost is a suitable lower bound; unusual transitions such as teleporters can invalidate it.

<span id="example-maintenance-corridors"></span>

## Practical example

### Maintenance corridors

This illustrative graph has two routes from A to G. Only the listed edges exist, and each is bidirectional:

| Edge | Cost |
| ---- | ---: |
| A–B  |    1 |
| B–G  |    4 |
| A–C  |    2 |
| C–D  |    1 |
| D–G  |    1 |

A–B–G has two transitions and costs 5. A–C–D–G has three and costs 4. BFS solves the transition-count problem, not minimum cost. Dijkstra should select the second route. A* with a zero heuristic reduces to Dijkstra and provides a useful baseline check.

Now place the corridors in a game. Include robot width when computing traversability. A closing door can invalidate an old path. A navigation-change signal or detected blockage should trigger recomputation or an understandable failure, according to the project's rules.

## Common mistakes

- Assuming straight-line distance remains a guaranteed lower bound with cheap teleporters.
- Treating an empty path as success when the goal is unreachable. Start equal to goal is a separate case.
- Recomputing every frame without need or cost measurement.
- Forgetting that a smoothed segment can cut an impassable corner.

## Verify it

1. Calculate both path costs manually and compare the algorithm's result.
2. Remove D–G: route A–B–G must remain, with cost 5. Then remove B–G and check an explicit “no path” result.
3. Check start equal to goal and a door closing during travel.
4. Follow the computed route with the real collider, including narrow turns.

## Prompt for an AI agent

> Separate route search from robot movement. Return the route, total cost and status. Compare BFS and Dijkstra on the supplied graph, then handle blockages. Do not declare navigation complete based on one drawn line.

Review the model through the [Functional Space lens](/en/lenses/#schell-026).

## Connected materials

- Before you start: [Collision fundamentals](https://gamemechanics.pro/en/lessons/collision-basics/) (key: lesson/collision-basics)
- Apply the principle: [Maps, routes and mazes](https://gamemechanics.pro/en/knowledge/mechanic/point-and-click--family-24/) (key: mechanic/point-and-click--family-24)
- Put it into practice: [Maintenance patrol](https://gamemechanics.pro/en/knowledge/practice/maintenance-patrol/) (key: practice/maintenance-patrol)
- Review through a lens: [Functional Space](https://gamemechanics.pro/en/knowledge/lens/schell-026/) (key: lens/schell-026)
- Learning paths: [NPC behavior](https://gamemechanics.pro/en/learn/npc-behavior/) (key: path/npc-behavior)

## Sources and provenance

Original gamemechanics.pro material. Check illustrative examples in your own project.

- [Amit Patel, Red Blob Games: Introduction to the A* Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html) (id: source-f4e30147f2944e5d)

CC-BY-4.0 · gamemechanics.pro contributors