Game AI & Pathfinding — Complete Guide
Game AI and pathfinding give non-player characters the ability to move, make decisions, and react to the player — from enemy patrols to companion follow-behavior. This guide covers A* pathfinding, finite state machines, behavior trees, navmesh navigation, and practical implementations in Godot and Unity, with real code examples you can adapt into your own projects. The same pathfinding algorithms power Doda Browser's map visualization tools and Durga Antivirus Pro's threat graph traversal engine.
What You'll Learn
By the end of this guide, you'll understand the four pillars of game AI — pathfinding, decision-making, perception, and animation — and be able to implement a complete enemy AI system from scratch.
Why Game AI Matters
Game AI is what separates a memorable game from a forgettable one. A well-designed enemy that flanks and takes cover creates the illusion of intelligence. A badly designed one that walks into walls breaks immersion. Beyond games, AI pathfinding algorithms are used in robotics, logistics, and cybersecurity threat traversal.
Real-World Use
This same A* algorithm is used by Durga Antivirus Pro to graph file system traversal paths during malware analysis. The behavior tree pattern powers NPCs in everything from The Last of Us to robots in Doda Browser's interactive tutorials.
Game AI Learning Path
flowchart LR
A[Game Dev Overview] --> B[Game Physics]
A --> C[Game AI & Pathfinding]
C --> D[Multiplayer Networking]
C --> E[Game Optimization]
C --> F{You Are Here}
style F fill:#f90,color:#fff
The Four Pillars of Game AI
1. Pathfinding
Pathfinding answers: how does the NPC get from A to B avoiding obstacles? The most common algorithm is A* (A-star), which finds the shortest path on a grid or graph.
2. Decision-Making
Decision-making determines which action the NPC takes. Common architectures: finite state machines (FSM), behavior trees (BT), utility systems, and goal-oriented action planning (GOAP).
3. Perception
Perception is how the NPC senses the world: line-of-sight checks, hearing ranges, damage events, or data from other NPCs. Without it, the NPC can't react.
4. Animation
Once the NPC decides to move, animation blends movement, attacks, and idle states. Root motion and blend trees handle state transitions seamlessly.
A* Pathfinding Algorithm
A* is the gold standard for grid-based pathfinding. It combines Dijkstra's algorithm (guarantees shortest path) with a heuristic (guesses distance to goal) for efficiency.
import heapq
class Node:
def __init__(self, x, y, walkable=True):
self.x = x
self.y = y
self.walkable = walkable
self.g = float('inf')
self.h = 0
self.f = 0
self.parent = None
def __lt__(self, other):
return self.f < other.f
def heuristic(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def get_neighbors(node, grid, cols, rows):
neighbors = []
for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
nx, ny = node.x + dx, node.y + dy
if 0 <= nx < cols and 0 <= ny < rows:
neighbor = grid[ny][nx]
if neighbor.walkable:
neighbors.append(neighbor)
return neighbors
def a_star(start, goal, grid, cols, rows):
open_set = []
closed_set = set()
start.g = 0
start.h = heuristic(start, goal)
start.f = start.h
heapq.heappush(open_set, start)
while open_set:
current = heapq.heappop(open_set)
if current == goal:
path = []
while current:
path.append((current.x, current.y))
current = current.parent
return path[::-1]
closed_set.add((current.x, current.y))
for neighbor in get_neighbors(current, grid, cols, rows):
if (neighbor.x, neighbor.y) in closed_set:
continue
tentative_g = current.g + 1
if tentative_g < neighbor.g:
neighbor.parent = current
neighbor.g = tentative_g
neighbor.h = heuristic(neighbor, goal)
neighbor.f = neighbor.g + neighbor.h
heapq.heappush(open_set, neighbor)
return None
rows, cols = 5, 5
grid = [[Node(x, y) for x in range(cols)] for y in range(rows)]
grid[2][2].walkable = False
grid[2][3].walkable = False
start = grid[0][0]
goal = grid[4][4]
path = a_star(start, goal, grid, cols, rows)
print(f"Path: {path}")
Expected output:
Path: [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]
The algorithm routed around blocked cells at (2,2) and (2,3). This exact logic runs in thousands of games — tower defense mazes, stealth guard patrols, RTS unit navigation.
Finite State Machines
An FSM is the simplest decision-making architecture. The NPC exists in one state at a time and transitions on events like "player seen" or "health low."
from enum import Enum
class State(Enum):
IDLE = 1; PATROL = 2; CHASE = 3; ATTACK = 4; FLEE = 5
class Enemy:
def __init__(self):
self.state = State.PATROL
self.health = 100
self.player_visible = False
self.distance_to_player = 100
def update(self):
if self.state == State.IDLE:
print("Standing still...")
elif self.state == State.PATROL:
print("Walking patrol route...")
elif self.state == State.CHASE:
print("Moving toward player...")
elif self.state == State.ATTACK:
print("Attacking player!")
elif self.state == State.FLEE:
print("Running away!")
if self.health < 30 and self.player_visible:
self.state = State.FLEE
elif self.player_visible and self.distance_to_player < 10:
self.state = State.ATTACK
elif self.player_visible and self.distance_to_player < 30:
self.state = State.CHASE
elif self.state in (State.CHASE, State.ATTACK) and not self.player_visible:
self.state = State.PATROL
enemy = Enemy()
for frame in range(5):
print(f"\nFrame {frame + 1}:")
enemy.distance_to_player = max(5, 50 - frame * 10)
enemy.player_visible = frame > 0
enemy.update()
Expected output:
Frame 1: Walking patrol route...
Frame 2: Moving toward player...
Frame 3: Moving toward player...
Frame 4: Attacking player!
Frame 5: Attacking player!
FSMs work well for simple NPCs but become unwieldy beyond 10–15 states. That's where behavior trees shine.
Behavior Trees
Behavior trees compose nodes hierarchically: Selectors (OR) try children in order until one succeeds; Sequences (AND) run all children in order, failing on any failure.
class Node:
def tick(self, enemy): raise NotImplementedError
class Sequence(Node):
def __init__(self, children): self.children = children
def tick(self, enemy):
for child in self.children:
if not child.tick(enemy): return False
return True
class Selector(Node):
def __init__(self, children): self.children = children
def tick(self, enemy):
for child in self.children:
if child.tick(enemy): return True
return False
class CheckHealth(Node):
def __init__(self, t): self.threshold = t
def tick(self, enemy): return enemy.health < self.threshold
class CheckPlayerVisible(Node):
def tick(self, enemy): return enemy.player_visible
class MoveToPlayer(Node):
def tick(self, enemy): print("Moving toward player..."); return True
class AttackPlayer(Node):
def tick(self, enemy): print("Attacking player!"); return True
class Flee(Node):
def tick(self, enemy): print("Fleeing from danger!"); return True
class Patrol(Node):
def tick(self, enemy): print("Patrolling..."); return True
bt_root = Selector([
Sequence([CheckHealth(30), Flee()]),
Sequence([CheckPlayerVisible(), MoveToPlayer(), AttackPlayer()]),
Patrol()
])
class EnemyBT:
def __init__(self):
self.health = 100
self.player_visible = False
def update(self): bt_root.tick(self)
enemy = EnemyBT()
for health, visible in [(100, False), (80, True), (20, True), (20, False)]:
enemy.health = health
enemy.player_visible = visible
print(f"\nHealth={health}, Visible={visible}:")
enemy.update()
Expected output:
Health=100, Visible=False: Patrolling...
Health=80, Visible=True: Moving toward player... Attacking player!
Health=20, Visible=True: Fleeing from danger!
Health=20, Visible=False: Patrolling...
Behavior trees are modular and reusable — which is why they dominate AAA game AI. Both Unity and Godot Engine support them via built-in tools or add-ons.
Navmesh Navigation
Grid-based A* works for 2D tile games, but 3D games use navmeshes — polygon meshes marking walkable areas. Engines bake navmeshes automatically. In Unity, set NavMeshAgent.destination. In Godot, use NavigationAgent3D.target_position. The engine handles path smoothing, obstacle avoidance, and slope limits.
Implementing Enemy AI in Godot
extends CharacterBody3D
@export var patrol_speed: float = 3.0
@export var chase_speed: float = 6.0
@export var detection_range: float = 15.0
enum State { PATROL, CHASE, ATTACK }
var current_state: State = State.PATROL
var navigation_agent: NavigationAgent3D
var target_player: Node3D = null
var patrol_points: Array[Vector3] = []
var current_patrol_index: int = 0
func _ready():
navigation_agent = $NavigationAgent3D
patrol_points = _get_patrol_points()
func _physics_process(delta):
match current_state:
State.PATROL: _patrol()
State.CHASE: _chase()
State.ATTACK: _attack()
_detect_player()
func _patrol():
if navigation_agent.is_navigation_finished():
current_patrol_index = (current_patrol_index + 1) % patrol_points.size()
navigation_agent.target_position = patrol_points[current_patrol_index]
velocity = global_position.direction_to(navigation_agent.get_next_path_position()) * patrol_speed
move_and_slide()
func _chase():
if target_player:
navigation_agent.target_position = target_player.global_position
velocity = global_position.direction_to(navigation_agent.get_next_path_position()) * chase_speed
move_and_slide()
func _attack():
pass
func _detect_player():
var players = get_tree().get_nodes_in_group("player")
if players.size() > 0:
target_player = players[0]
var dist = global_position.distance_to(target_player.global_position)
if dist < detection_range:
current_state = State.CHASE if dist > 3.0 else State.ATTACK
else:
current_state = State.PATROL
This patrols between waypoints, detects the player, chases using Godot's navmesh, and attacks on contact.
Common AI Mistakes
Forcing perfect pathfinding: Not every NPC needs A*. Steering behaviors (arrive, flee, wander) are cheaper and smoother for simple movement.
Tight coupling AI and animation: Keep them separate. The AI decides what to do; animation decides how it looks.
Ignoring perception: NPCs that see through walls break immersion. Use raycasts for line-of-sight before triggering chase.
Not capping pathfinding cost: Running A* every frame kills performance. Cache paths, recalculate every 0.5–1s, or use hierarchical pathfinding.
No fallback behavior: If A* finds no path, fall back to idle or search — not standing frozen.
Practice Questions
1. What's the difference between an FSM and a Behavior Tree?
An FSM has explicit states and transitions; a Behavior Tree composes nodes with Selectors (OR) and Sequences (AND). Behavior trees are more modular — nodes can be tested and recomposed independently.
2. Why use Manhattan distance as the A heuristic?*
Manhattan distance works for 4-directional grids where diagonal movement isn't allowed. For 8-directional or free movement, use Euclidean or Octile distance.
3. What is a navmesh and when should you use it?
A navmesh is a polygon mesh of walkable surfaces. Use it for 3D games with terrain, slopes, and complex geometry. Grids are sufficient for 2D tile-based games.
4. How do you optimize pathfinding for many NPCs?
Cache paths, recalculate at intervals, limit path length, and batch requests across frames.
5. Challenge: Modify the A example for diagonal movement (8-directional).*
Add diagonal offsets (1,1), (1,-1), (-1,1), (-1,-1) to get_neighbors() with cost 1.414, and switch the heuristic to Euclidean or Octile distance.
Mini Project: Patrol-and-Chase AI
Build a complete enemy AI that:
- Patrols between 3–5 waypoints using navmesh pathfinding
- Detects the player with raycast line-of-sight (not just distance)
- Chases when the player is detected within range
- Loses interest after 5 seconds out of sight
- Returns to the nearest patrol waypoint
Start with grid-based A* in Python or JavaScript before moving to a game engine. The core logic — detect → decide → move — is identical everywhere.
FAQ
Related Tutorials
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro