How an NPC Sees, Chooses, and Remembers
Work through the arithmetic inside Lesson 4.12's toy guard: the distance and dot product behind its view cone, stepped line-of-sight checks, utility scores and their switch points, and behavior trees.
Cheatsheet for Lesson 11.1
A one-page summary of “How an NPC Sees, Chooses, and Remembers” you can keep beside your notes. Plain Markdown.
Lesson 11.1 — How an NPC Sees, Chooses, and Remembers: cheatsheet
- Remember: The guard checks its view cone by comparing a dot product with a number worked out once. It never computes an angle.
- Also useful: Think of a talent show: every option gets a score for the current situation and the judge picks the highest. Change a score weight or formula and the winner changes.
Key terms
facing: The lab'sVec2type stores such a two-number vector, and the guard'sfacingis one too.- unit vector: A unit vector is a vector of length 1, the result of normalizing.
last_known: Its sensing code tells us which facts it can observe, a state trace tells us which choice it made on each tick, andseen_forandlast_knownhold what it carried from one tick into the next.
Formulas and patterns
a · b = a.x × b.x + a.y × b.y
Review
- Q: A fighter sees an enemy, has no cover, and has no potions left. It scores Attack as 0.4 + 0.6 × h and Take cover as 0.9 − 0.6 × h, where h is its health as a fraction of full health. Below what health does it stop attacking and take cover, and why? A: About 0.42, where 0.4 + 0.6h = 0.9 − 0.6h gives 1.2h = 0.5
- Q: A guard faces (1, 0). The unit direction to the player is (0.6, 0.8). With VIEW_CONE_COS = 0.5, can the guard see the player, ignoring walls and distance? A: Yes: 0.6 × 1 + 0.8 × 0 = 0.6, which is at least 0.5
Lesson 4.10 followed a toy guard through sixteen ticks of sensing, deciding, and acting. This lesson opens up what it described in words: the arithmetic behind the guard’s view cone and line of sight, and two other ways games choose what an NPC does. The earlier lesson is the first-pass behavior model; this is the worked explanation you can return to when a real guard’s choices need closer inspection. The geometry is the two-dimensional case of the vectors in Lesson 4.4.
The three checks in code
Section titled “The three checks in code”One method runs
the guard’s three checks
in their cheapest-first order. The first two use Vec2, the lab’s pair of x
and y coordinates; the last uses the wall list:
fn can_see(&self, target: Vec2, walls: &[Wall]) -> bool { let offset = target - self.position; if offset.length() > VIEW_DISTANCE { return false; } let Some(direction) = offset.normalized() else { return true; }; if direction.dot(self.facing) < VIEW_CONE_COS { return false; } line_of_sight(self.position, target, walls)}The return false lines reject a target as soon as a check fails.
normalized() returns an optional direction because a zero-length
arrow has no direction; the let Some(direction) ... else branch
handles that case. The following sections work through each calculation
with positions you can draw on a grid.
Checks in order, then the answer
Three checks, cheapest first
5 ≤ 10 and 0.8 ≥ 0.5 (about 36.9° from the facing), and nothing blocks the line: the guard sees the target.
The first two checks read offset, the arrow from the guard to the target: the
target’s position minus the guard’s, the same subtraction as in
Lesson 4.4. For a guard at (0, 0) and
a player at (4, 3), the offset is (4 − 0, 3 − 0) = (4, 3): 4 units along x and
3 along y. The lab’s Vec2 type stores such a two-number vector, and the
guard’s facing is one too.
Distance
Section titled “Distance”The arrow’s length is the distance from
Lesson 4.4 with two
coordinates, √(x² + y²). For (4, 3), that is √(4² + 3²) = √(16 + 9) = √25 = 5, within
VIEW_DISTANCE = 10, so the first check passes. A player at (15, 0) is
√(15² + 0²) = 15 away and fails it.
The view cone and the dot product
Section titled “The view cone and the dot product”A unit vector is a vector of length 1, the result of normalizing. It stores
a direction and nothing else. The guard keeps facing as a unit vector: (1, 0)
means it faces east, along the x axis. The offset (4, 3) has length 5, so its
direction is
(4 ÷ 5, 3 ÷ 5) = (0.8, 0.6), whose length is √(0.64 + 0.36) = √1 = 1. A target
standing exactly on the guard has an offset of length 0 and no direction; the
let Some(direction) ... else line counts it as seen.
In two dimensions, the dot product from Lesson 4.4 has two terms:
a · b = a.x × b.x + a.y × b.yFor two unit vectors, the dot product equals the cosine of the angle between them. Picture a circle of radius 1 around the guard. A unit direction at some angle from east ends on that circle, and the cosine of that angle is, by definition, the x-coordinate of that end point. As the angle grows from 0° to 180°, the end point slides around the circle from right to left, so its x falls steadily: 1 at 0°, 0 at 90°, and −1 at 180°. For a guard facing east, the dot product of (1, 0) with a unit direction (x, y) is x × 1 + y × 0 = x, exactly that cosine.
For any other facing, take the two unit vectors a and b and look at the arrow
from b’s tip to a’s tip, found the same way as offset: (a.x − b.x, a.y − b.y).
Call its length the tip gap. Pythagoras gives the tip gap squared, and
multiplying out the brackets regroups the terms:
(a.x − b.x)² + (a.y − b.y)² = a.x² − 2 × a.x × b.x + b.x² + a.y² − 2 × a.y × b.y + b.y² = (a.x² + a.y²) + (b.x² + b.y²) − 2 × (a.x × b.x + a.y × b.y)The first two groups are the vectors’ lengths squared, 1 each, and the last bracket is the dot product, so (tip gap)² = 1 + 1 − 2 × (a · b), which rearranges to a · b = 1 − (tip gap)² ÷ 2. Turning the guard swings both arrows together like one rigid shape, which leaves the gap between their tips unchanged, so the dot product cannot change either: what holds facing east holds for every facing. As a check, the arrow between the tips of (1, 0) and (0.8, 0.6) is (1 − 0.8, 0 − 0.6) = (0.2, −0.6), so the tip gap squared is 0.04 + 0.36 = 0.4, and 1 − 0.4 ÷ 2 = 0.8, the same as 1 × 0.8 + 0 × 0.6.
Why does 0.5 mean 60°? A triangle whose three sides are all 1 long has three equal angles, and a triangle’s angles add up to 180°, so each is 180 ÷ 3 = 60°. Two of its sides, starting from the same corner, are unit vectors 60° apart whose tips are 1 apart, so their dot product, the cosine of 60°, is 1 − 1² ÷ 2 = 0.5.
The test direction.dot(self.facing) < VIEW_CONE_COS therefore rejects every
direction whose cosine is below 0.5. The cosine falls steadily as the angle
grows, so that is every direction more than 60° from the facing, on either side.
For the player at (4, 3), the dot product of (0.8, 0.6) with the facing (1, 0) is 0.8 × 1 + 0.6 × 0 = 0.8, at least 0.5, so the player is inside the cone. (An inverse cosine, the calculator function that turns a cosine back into an angle, puts them about 37° from the facing.) A player at (0, 5) has direction (0 ÷ 5, 5 ÷ 5) = (0, 1) and a dot product of 0 × 1 + 1 × 0 = 0, a full 90° to the side, so the guard does not see them.
Comparing with a cosine worked out once, when the constant was written, costs two multiplications and one addition and never needs the slower inverse cosine, the same saving as the three-dimensional view test in Lesson 4.4.
Line of sight
Section titled “Line of sight”The last check, line_of_sight, walks from the guard toward the target in
steps of SIGHT_STEP = 0.1 and tests each sample point against the walls. Each
wall is an axis-aligned box, meaning its sides run along the x and y axes,
stored as two corners, min and max. A point is inside when both of its
coordinates lie between the corners.
On tick 8 of Lesson 4.10’s run, the guard
stands at (4, 0), the player at (8, 0), and a wall fills the box from (5.5, −1)
to (6.5, 1) between them. The samples are (4.0, 0), (4.1, 0), (4.2, 0), and so
on. The 16th, (5.5, 0), is the first inside the wall, because 5.5 ≤ 5.5 ≤ 6.5
and −1 ≤ 0 ≤ 1 (a point on the edge counts as inside), so the function returns
false long before it reaches the player.
Predict first
Same guard at (4, 0) and player at (8, 0), samples every 0.1: x = 4.0, 4.1, 4.2 and so on. This time a thin wall covers only x from 5.62 to 5.68 (y from −1 to 1).
Does line_of_sight find the thin wall?
Answer: No: every sample misses it, so the guard sees the player. The wall is 5.68 − 5.62 = 0.06 wide, thinner than the 0.1 step. Samples 5.6 and 5.7 land on either side, all 40 samples test clear, and the function returns true. Try the thin-wall example below.
The walk stops at the first sample inside
Samples on y = 0, guard at x 4, player at x 8
Samples land every 0.1 from x 4.0. The first one inside the wall is x 5.5, so the walk stops after 16 of 40 samples.
Optional reference: the lab's second line-of-sight test
A line can also slip past a wall. From (0, 0) to (4, 3), the line rises 3 for every 4 across, so every point on it has y = 3 ÷ 4 × x = 0.75 × x. A wall from (2, −1) to (3, 1) covers x from 2 to 3, where the line’s y runs from 0.75 × 2 = 1.5 to 0.75 × 3 = 2.25, higher than the wall’s top edge at y = 1. No sample lands inside, and the guard sees the player. The lab’s tests check both cases.
Besides that blind spot for walls thinner than the step, stepping costs more with distance. A check across the full view distance takes 10 ÷ 0.1 = 100 samples, each tested against every wall. Engines instead compute exactly where a ray crosses each collision shape, a ray cast, but the question they answer is the same one.
Choose among actions: utility scoring
Section titled “Choose among actions: utility scoring”A state machine answers “which mode am I in?” Some decisions are better framed as “which of these options is best right now?” Utility AI gives every option a score computed from the situation and runs the highest one. The second demo in the lab from Lesson 4.10 scores three options for a fighter:
fn score(choice: Choice, situation: Situation) -> f32 { match choice { Choice::Attack if situation.enemy_visible => 0.4 + 0.6 * situation.health, Choice::TakeCover if situation.enemy_visible && !situation.in_cover => { 0.9 - 0.6 * situation.health } Choice::Heal if situation.potions > 0 => 1.0 - situation.health, _ => 0.0, }}health here is a fraction: 30 health out of 100 is 30 ÷ 100 = 0.3. Each score
is a straight line in health, chosen so its meaning is readable. Attack scores
1.0 at full health and falls to 0.4 as health runs out. Taking cover scores 0.3
at full health and rises to 0.9. Healing scores nothing at full health and 1.0
at zero. An option that makes no sense right now, such as healing with no
potions, scores 0.
With an enemy in view, no cover, and one potion, the scores at several health levels are:
| Health | Attack: 0.4 + 0.6 × h | Take cover: 0.9 − 0.6 × h | Heal: 1.0 − h | Chosen |
|---|---|---|---|---|
| 1.0 | 0.4 + 0.6 = 1.00 | 0.9 − 0.6 = 0.30 | 0.00 | Attack |
| 0.75 | 0.4 + 0.45 = 0.85 | 0.9 − 0.45 = 0.45 | 0.25 | Attack |
| 0.5 | 0.4 + 0.3 = 0.70 | 0.9 − 0.3 = 0.60 | 0.50 | Attack |
| 0.3 | 0.4 + 0.18 = 0.58 | 0.9 − 0.18 = 0.72 | 0.70 | Take cover |
| 0.2 | 0.4 + 0.12 = 0.52 | 0.9 − 0.12 = 0.78 | 0.80 | Heal |
| 0.1 | 0.4 + 0.06 = 0.46 | 0.9 − 0.06 = 0.84 | 0.90 | Heal |
The switch points come straight from the formulas. Attack and cover score the same when 0.4 + 0.6h = 0.9 − 0.6h. Adding 0.6h to both sides and taking 0.4 from both gives 1.2h = 0.5, so h = 0.5 ÷ 1.2 ≈ 0.42. Cover and healing tie when 0.9 − 0.6h = 1.0 − h, which rearranges to 0.4h = 0.1, so h = 0.25. Above about 42% health this fighter attacks, between 25% and 42% it takes cover, and below 25% it drinks a potion. Changing one number in a formula moves one of those switch points, and that is how designers tune utility AI.
The lab’s choose function keeps only scores above 0 before it picks the
highest. With nobody in view, every option scores 0, so it returns None:
nothing on this list is worth doing, and another system, such as the patrol,
keeps control.
Optional reference: the demo's five situations
The demo also varies the situation, all at a health of 0.3 except where it says healthy:
| Situation | Attack | Take cover | Heal | Chosen |
|---|---|---|---|---|
| healthy, enemy in view | 1.00 | 0.30 | 0.00 | Attack |
| hurt, enemy in view, exposed | 0.58 | 0.72 | 0.70 | Take cover |
| hurt, enemy in view, in cover | 0.58 | 0.00 | 0.70 | Heal |
| hurt, in cover, no potions left | 0.58 | 0.00 | 0.00 | Attack |
| healthy, nobody in view | 0.00 | 0.00 | 0.00 | nothing |
Once in cover, taking cover scores 0, so the next best option wins. With no potions, healing scores 0 too, and attacking is all that is left.
Utility scoring has its own weak spot. Near a switch point, a tiny change in health can flip the choice back and forth every tick. Games damp this by adding a small bonus to whatever the NPC is already doing, so a rival option has to beat it clearly before the NPC switches. The trade against a state machine is that a state machine lists every transition by hand, so each new state needs arrows to and from the old ones, while utility scoring adds one scoring function per option but hides its behavior in numbers that need tables like the one above to tune.
Behavior trees, briefly
Section titled “Behavior trees, briefly”Larger games often organize NPC logic as a behavior tree instead. The lab does not build one, but the idea is a priority checklist whose entries can contain smaller checklists. The leaves are conditions (“is health 25 or less?”) and actions (“flee”). A selector tries its children from left to right and stops at the first one that succeeds. A sequence runs its children in order and stops at the first one that fails. This simplified tree starts at the root each tick.
The guard’s priorities fit in one selector:
Walk through one tick. At 30 health, the first sequence fails its health check, so the selector tries the next one. If the player remains visible for three ticks and is within attack range, that sequence chooses attack; if they are farther away, it chooses chase. At 20 health, the first sequence reaches flee and the selector does not inspect the attack or patrol branches. The diagram shows priority, not the pathfinding or animation code inside an action. In a production tree, a long-running action can also return running so the engine knows it has not succeeded or failed yet; such a tree must define how that state is resumed or checked on the next tick.
Compare it with the guard’s
state diagram. The four arrows
into Flee, one from each other state, became one child, placed first, because a
behavior tree re-checks its priorities from the top every tick. The tree keeps
no memory between ticks by itself, though. Values such as seen_for and
last_known live beside it, in a shared store that engines call a
blackboard. Real games mix all three techniques: a behavior tree for
priorities, small state machines inside some of its nodes, and utility scores
to choose between similar actions.
This simulation needs JavaScript. The lesson text around it works through the same numbers.
Stored as a C++ structure, the guard’s fields add up to 33 bytes: four 4-byte
floats, a 4-byte health, the 1-byte state at offset 0x14, and three more 4-byte
values. Each 4-byte field must start at a multiple of 4, so three padding bytes
follow the state and the structure takes 36 bytes. A state byte outside 0 to 4,
such as 9, can make a compiled switch that indexes its jump table without a
range check jump to an unrelated address and crash. These fields, offsets, and
padding are worked through in
Lesson 14.1, where recovering
object layouts is the subject.
The guard can now be read in three ways. Its sensing code tells us which facts
it can observe, a state trace tells us which choice it made on each tick, and
seen_for and last_known hold what it carried from one tick into the next.
None of those alone proves
why a particular guard moved. Together they let us check a claim such as “the
wall broke line of sight, so Chase became Search” against both behavior and
state. The rest of this chapter moves decisions like these into Lua scripts
that a game loads and limits.
Where the choice flips
A fighter sees an enemy, has no cover, and has no potions left. It scores Attack as 0.4 + 0.6 × h and Take cover as 0.9 − 0.6 × h, where h is its health as a fraction of full health. Below what health does it stop attacking and take cover, and why?
Utility scoring runs whichever option scores highest, so the choice flips where the two lines cross. Adding 0.6h to both sides of 0.4 + 0.6h = 0.9 − 0.6h and taking 0.4 from both gives 1.2h = 0.5, so h = 0.5 ÷ 1.2 ≈ 0.42. Above that health Attack scores more; below it Take cover does. With no potions, Heal scores 0, so the 0.25 switch point never comes into play. Changing one number in either formula moves the crossing, which is how designers tune utility AI.
Finished Lesson 11.1?
Mark it done and the lesson list shows a beside it. A chapter whose lessons are all done is marked done too. Progress is saved in this browser only.
Plain Markdown, saved in this browser.
This book grew out of the original Game Hacking Academy by attilathedud and has been rewritten as a beginner-first course. Like the original repository, its source is published under the Apache License 2.0.