21. Waypoints

Every bustling town square, every patrolling guard, every merchant making their daily rounds - all of these bring life to game worlds through simple movement patterns. Today we're implementing waypoint-based movement that will let our entities follow predetermined paths through the world.

The Fractal Code Cycle Applied to Waypoint Movement

Recall our fundamental pattern:

Input → Processing → Output

For waypoint movement:

• Input: Entity position, waypoint positions, movement speed, delta time
• Processing: Calculate direction to next waypoint, check arrival conditions, cycle to next waypoint
• Output: Updated entity velocity and waypoint index

What Are Waypoints Good For?

• Town guards patrolling their beats
• Villagers going about daily routines
• AI that follows predictable but dynamic patterns

Entity Flags: A Modular Approach

We've introduced a flag system for entities. Each entity will behave and present differently based on whether these flags are on or off:

Entity_Flags :: bit_set[Entity_Flag]
Entity_Flag :: enum {
    Sprite,
    Waypoints,
}

This allows entities to opt into specific behaviours. An entity with .Waypoints in its flags will process waypoint movement, whilst others won't waste processing time on unused systems.

Waypoint Data in Entities

We've extended our Entity struct to include waypoint information:

Entity :: struct {
    // ... existing fields ...
    // deleted: movement_normal - a vestige from a different entity movement style
    
    flags: Entity_Flags,
    
    waypoints: [8]Vec3,
    waypoint_count: int,
    waypoint_index: int,
}

The fixed-size array approach keeps memory layout simple whilst supporting up to 8 waypoints per entity - more than enough for most movement patterns.

The Waypoint Algorithm

The movement algorithm is simple:

1. Check Arrival Condition

// If the entity is close to the waypoint (which is on the
// ground), we assume it has arrived.
// It's arrived if it's close enough to get there this frame
// based on the movement_speed.
dist_check := entity.movement_speed * gs.time.delta

This prevents entities from "overshooting" waypoints by checking if they can reach the destination within the current frame.

2. Calculate Ground-Based Direction

// Direction to waypoint
// Though waypoints exist in 3D space, we are going to move
// between them in 2D (XZ) space and let the ground sampling
// handle elevation.
dest := entity.waypoints[entity.waypoint_index]
entity_ground_pos := entity.position
entity_ground_pos.y -= entity.collider_radius

dir := rl.Vector3Normalize(dest - entity_ground_pos)
dir.y = 0

We deliberately ignore the Y-axis for movement calculation, allowing future ground-following systems to handle elevation changes naturally.

3. Apply Movement and Check Arrival

entity.velocity = dir * entity.movement_speed * gs.time.delta

if rl.Vector3Length(dest - entity_ground_pos) < dist_check {
    entity.waypoint_index = (entity.waypoint_index + 1) % entity.waypoint_count
}

The modulo operation creates a cycling behaviour - when the entity reaches the last waypoint, it automatically returns to the first.

Integrating with Existing Systems

Flag-Based Processing

The sprite animation system has also been updated to use the flag system:

if len(sprite_animation.definition.frames) > 0 // Old way

// Update Entity sprite animations
if .Sprite in entity.flags {
    sprite_animation := &entity.sprite_animation
    // ... animation code ...
}

if .Waypoints in entity.flags {
    // Insert the waypoint related update code here!
}

This makes the entity system more modular and performant - entities only process the systems they actually use.

Collision Integration

The waypoint movement sets the entity's velocity, which our existing physics system then processes:

1. Waypoint system calculates desired movement
2. Physics system applies collision detection and response
3. Entity ends up at valid position, potentially adjusted for collisions

This separation means waypoint entities naturally avoid walking through walls.

Creating a Test Entity

We've added a test entity to demonstrate the waypoint system:

// Test Entity
h := entity_create()
e := entity_get(h)

e.waypoints[0] = Vec3{-2, 0, 8}
e.waypoints[1] = Vec3{0, 0, 12}
e.waypoints[2] = Vec3{3, 0, 11}
e.waypoints[3] = Vec3{3, 0.5, 8}
e.waypoints[4] = Vec3{4, 0, 11}
e.waypoint_count = 5
e.position = e.waypoints[2]
e.collider_radius = 0.25
e.flags += {.Waypoints}
e.movement_speed = 6

This creates an entity that follows a 5-point path through the world, starting at waypoint 2 and cycling continuously.

Visual Debugging

The rendering system now shows all entities and their waypoints:

for e in gs.entity.entities[1:] {
    rl.DrawSphereWires(e.position, e.collider_radius, 8, 8, {0, 255, 0, 80})

    for i in 0..<e.waypoint_count {
        rl.DrawSphereWires(e.waypoints[i], 0.05, 8, 8, {255, 255, 0, 80})
    }
}

Green wireframes show entity positions whilst yellow spheres mark waypoint locations, making it easy to visualise and debug movement patterns.

Design Considerations

Ground-Based Movement

By ignoring Y-axis movement and focusing on horizontal displacement, we've made the system compatible with the terrain-following functionality. Entities can have waypoints at different elevations whilst following ground contours naturally.

Future Improvements

Storing 8 waypoint Vec3s directly on Entity is a pragmatic choice, and will be revisited when we need more complex functionality.

We may want to do any number of the following:

• Make waypoints emit events
• Generate waypoints on the fly based on world conditions
• Turn waypoints on or off depending on time of day
• Assign multiple entities to the same set of waypoints

However, we don't know which of these we require as of yet, so rather than implement an over-engineered solution and going down a rabbit hole, we start with the simplest implementation we can and add to it as needed.

Once patterns emerge, we can then compress the system back down to it's minimum viable size.