1. Decision-Making & Reactions
1.1. Problem: NPCs act predictably, making them feel robotic.
1.1.1. Solution 1: Finite State Machines (FSM)
1.1.1.1. FSM organizes NPC behavior into different "states" (Idle, Attack, Patrol, Flee, etc.).
1.1.1.2. NPCs transition between states based on conditions (e.g., an enemy sees a player and switches from "Patrol" to "Attack").
1.1.1.3. Example: Pac-Man Ghosts switch between "Chase" and "Scatter" modes.
1.1.2. Solution 2: Behavior Trees or Utility AI
1.1.2.1. Behavior Trees allow NPCs to make decisions in a structured way (e.g., attack if the player is nearby, flee if low on health).
1.1.2.2. Utility AI makes decisions based on priorities (e.g., in a survival game, an NPC might choose food over combat if hunger is too high).
1.1.2.3. Example: The Last of Us NPCs use behavior trees to hide, flank, or attack based on the situation.
2. Adaptive Learning & AI Evolution
2.1. Problem: NPCs don’t learn from player behavior, making them repetitive.
2.1.1. Solution 1: Machine Learning (Reinforcement Learning)
2.1.1.1. NPCs analyze player actions and adapt over time.
2.1.1.2. Example: In Alien: Isolation, the Xenomorph learns how the player hides and changes its behavior accordingly.
2.1.2. Solution 2: Player Modeling & Dynamic Difficulty Adjustment
2.1.2.1. The game tracks the player’s skill level and adjusts NPC behavior accordingly.
2.1.2.2. Example: Resident Evil 4's adaptive AI makes enemies stronger if the player is performing well.
3. Pathfinding & Navigation
3.1. Problem: NPCs take unnatural paths, get stuck in obstacles, or move inefficiently.
3.1.1. Solution 1: A (A-Star) and Dijkstra’s Algorithm*
3.1.1.1. A* is widely used for pathfinding in games because it finds the shortest path while avoiding obstacles.
3.1.1.2. Dijkstra’s algorithm is similar but explores all possible paths, making it better for complex navigation
3.1.1.3. Example: In RPGs like The Witcher 3, NPCs use A* for smooth movement in cities.
3.1.2. Solution 2: Navigation Mesh (NavMesh)
3.1.2.1. A NavMesh divides the game world into walkable and non-walkable areas.
3.1.2.2. NPCs move more naturally because the game pre-defines paths that avoid obstacles.
3.1.2.3. Example: Assassin’s Creed NPCs walk on streets, avoid walls, and navigate dynamically.