Game Programming - CSCI 3213

Spring 2026 - Lecture 12

Oklahoma City University

• Understand spatial partitioning optimization techniques
• Learn when to use spatial partition vs traditional patterns
• Implement a level editor using Stack data structure
• Create dynamic track segment loading/unloading system
• Build ScriptableObject-based level configuration
• Optimize memory usage for infinite racing tracks

Definition

Spatial partitioning is an optimization technique that divides game space into manageable regions to improve performance.

Key Benefits:

• Reduced Calculations: Only process visible/nearby objects
• Memory Efficiency: Load/unload regions dynamically
• Faster Queries: Quickly find objects in specific areas
• Scalability: Handle massive worlds efficiently

1. Grid Partitioning (Uniform Grid)

• Divide space into equal-sized cells
• Simple to implement, fast lookups
• Best for evenly distributed objects

2. Binary Space Partitioning (BSP)

• Recursively divide space with planes
• Used in 3D rendering (Doom, Quake)
• Excellent for static geometry

3. Quadtree (2D) / Octree (3D)

• Hierarchical tree structure
• Adapts to object density
• Good for dynamic worlds

4. Segment-Based (Our Approach)

• Load/unload linear segments
• Perfect for racing games
• Uses Stack data structure

Challenge: Building Infinite Tracks

Racing games need long, varied tracks without consuming massive memory.

Our Solution:

• Segment-Based Track: Divide track into reusable pieces
• Dynamic Loading: Load segments ahead of player
• Automatic Cleanup: Destroy segments behind player
• Designer-Friendly: Configure tracks via ScriptableObjects
• Memory Efficient: Only 3-5 segments in memory at once

Last In, First Out (LIFO)

A stack is a collection where the last item added is the first one removed.

Core Operations:

• Push(item) - Add item to top of stack
• Pop() - Remove and return top item
• Peek() - View top item without removing
• Count - Number of items in stack

C# Example:

Stack<GameObject> segments = new Stack<GameObject>();

segments.Push(segment1);  // Add to stack
segments.Push(segment2);  // Add another

GameObject top = segments.Pop();  // Returns segment2
// segment1 is still in stack

Three Core Components:

1. Track ScriptableObject
   • Stores segment prefabs
   • Defines segment length
   • Designer-friendly configuration
2. TrackController
   • Manages segment loading/positioning
   • Uses Stack to store segment queue
   • Responds to player progress
3. SegmentMarker
   • Triggers when player passes segment
   • Signals cleanup to destroy old segments
   • Requests new segment loading

Designer-Friendly Level Configuration

using UnityEngine;
using System.Collections.Generic;

[CreateAssetMenu(fileName = "New Track", menuName = "Track")]
public class Track : ScriptableObject
{
    public string trackName;
    public float segmentLength = 40f;
    public List<GameObject> segments;
}

How It Works:

• trackName - Identifies the track (e.g., "Desert Circuit")
• segmentLength - Distance between segments (40 units)
• segments - List of prefabs to randomly select from

Steps to Create a Track:

1. Right-click in Project: Create → Track
2. Name the asset: "DesertTrack", "CityTrack", etc.
3. Set segment length: Usually 40-60 units
4. Add segment prefabs: Drag prefabs into list
   • Straight segments
   • Curved segments
   • Obstacles
   • Special features
5. Assign to TrackController: Drag Track asset to controller

using UnityEngine;
using System.Collections.Generic;

public class TrackController : MonoBehaviour
{
    public Track track;
    public BikeController bikeController;

    private Stack<GameObject> _segStack;
    private Transform _segParent;
    private float _zPos;
    private int _segCount;

    void Start()
    {
        _segParent = GameObject.Find("Track").transform;
        _segStack = new Stack<GameObject>();

        // Initialize stack with segments in REVERSE order
        for (int i = track.segments.Count - 1; i >= 0; i--)
        {
            _segStack.Push(track.segments[i]);
        }

        LoadSegment(3);  // Load first 3 segments
    }
}

The Reverse Order Problem

Challenge: We want segments to appear in list order, but Stack is LIFO (Last In, First Out).

Solution: Load in Reverse!

// If list is: [Segment1, Segment2, Segment3]
// Push in reverse:
_segStack.Push(Segment3);  // Bottom of stack
_segStack.Push(Segment2);  // Middle
_segStack.Push(Segment1);  // Top

// Now Pop() returns Segment1 first! ✅

private void LoadSegment(int amount)
{
    for (int i = 0; i < amount; i++)
    {
        if (_segStack.Count > 0)
        {
            // Get next segment from stack
            GameObject segment = Instantiate(
                _segStack.Pop(),
                Vector3.zero,
                Quaternion.identity
            );

            // Set as child of Track parent
            segment.transform.SetParent(_segParent);

            // Position segment ahead of player
            segment.transform.localPosition =
                new Vector3(0, 0, _zPos);

            // Move position for next segment
            _zPos += track.segmentLength;
            _segCount++;
        }
    }
}

Track Layout Example

// Assume segmentLength = 40

LoadSegment(1):  Position at Z = 0
LoadSegment(1):  Position at Z = 40
LoadSegment(1):  Position at Z = 80

// _zPos increments by 40 each time
// Creates continuous track ahead of player

Visual Representation:

Player (stationary at Z=0)
    ↓
[Segment 0]─────[Segment 1]─────[Segment 2]
Z=0            Z=40           Z=80

Track moves BACKWARD toward player

Repopulate When Empty

private void LoadSegment(int amount)
{
    for (int i = 0; i < amount; i++)
    {
        // Check if stack is empty
        if (_segStack.Count == 0)
        {
            RepopulateStack();
        }

        // Rest of loading code...
    }
}

private void RepopulateStack()
{
    // Refill stack in reverse order again
    for (int i = track.segments.Count - 1; i >= 0; i--)
    {
        _segStack.Push(track.segments[i]);
    }
}

Track Moves Toward Player

void Update()
{
    // Move entire track backward at bike's current speed
    _segParent.Translate(
        Vector3.back *
        bikeController.CurrentSpeed *
        Time.deltaTime,
        Space.World
    );
}

How It Works:

• Vector3.back = negative Z direction (toward player)
• CurrentSpeed = player's velocity
• Time.deltaTime = frame-independent movement
• All segments move together (parented to Track object)

Automatic Segment Cleanup

using UnityEngine;

public class SegmentMarker : MonoBehaviour
{
    public TrackController trackController;

    private void OnTriggerExit(Collider other)
    {
        // Did the bike pass through this marker?
        if (other.GetComponent<BikeController>())
        {
            // Load 1 new segment ahead
            trackController.LoadSegment(1);

            // Destroy this entire segment
            Destroy(transform.parent.gameObject);
        }
    }
}

How to Set Up:

• Add Box Collider to marker GameObject
• Set as Trigger (check "Is Trigger")
• Place at END of each segment prefab
• Assign TrackController reference

Hierarchy:

SegmentPrefab (Parent)
├── Road Mesh
├── Obstacles (trees, barriers, etc.)
├── Decorations (lights, signs, etc.)
└── SegmentMarker (child)
    ├── Box Collider (Is Trigger = true)
    └── SegmentMarker.cs script

Marker Positioning:

• Place at Z = segment length (e.g., Z = 40)
• Collider should span full width of track
• Height tall enough to hit bike

How Many Segments in Memory?

Typical Setup:

• Load 3 segments at start
• Player passes segment → destroy 1, load 1
• Always maintain 3 active segments

Memory Comparison:

Without Spatial Partitioning:
- 100 segments × 10,000 polygons = 1,000,000 polys
- High memory usage, low FPS

With Spatial Partitioning:
- 3 segments × 10,000 polygons = 30,000 polys
- 97% memory reduction! 🎉

using UnityEngine;
using System.Collections.Generic;

public class TrackController : MonoBehaviour
{
    public Track track;
    public BikeController bikeController;

    private Stack<GameObject> _segStack;
    private Transform _segParent;
    private float _zPos;
    private int _segCount;

    void Start()
    {
        _segParent = GameObject.Find("Track").transform;
        _segStack = new Stack<GameObject>();

        for (int i = track.segments.Count - 1; i >= 0; i--)
            _segStack.Push(track.segments[i]);

        LoadSegment(3);
    }

    void Update()
    {
        _segParent.Translate(
            Vector3.back * bikeController.CurrentSpeed * Time.deltaTime,
            Space.World
        );
    }

    public void LoadSegment(int amount)
    {
        for (int i = 0; i < amount; i++)
        {
            if (_segStack.Count == 0)
                RepopulateStack();

            GameObject segment = Instantiate(
                _segStack.Pop(),
                Vector3.zero,
                Quaternion.identity
            );

            segment.transform.SetParent(_segParent);
            segment.transform.localPosition = new Vector3(0, 0, _zPos);
            _zPos += track.segmentLength;
            _segCount++;
        }
    }

    private void RepopulateStack()
    {
        for (int i = track.segments.Count - 1; i >= 0; i--)
            _segStack.Push(track.segments[i]);
    }
}

1. Create Track Parent

• Empty GameObject named "Track"
• Position at (0, 0, 0)
• All segments will be children

2. Create Track ScriptableObject

• Right-click → Create → Track
• Add segment prefabs to list
• Set segment length (e.g., 40)

3. Add TrackController Script

• Attach to Track GameObject
• Assign Track asset
• Assign BikeController reference

4. Configure Segment Prefabs

• Add SegmentMarker to each prefab
• Set Box Collider as trigger
• Assign TrackController reference

What to Verify:

1. Initial Load: 3 segments appear at start
2. Track Movement: Track moves backward smoothly
3. Segment Loading: New segment appears when passing marker
4. Cleanup: Old segment destroys after passing
5. Stack Refill: Segments cycle when stack empties
6. Performance: Consistent FPS with only 3 segments active

Debug Tips:

// In LoadSegment():
Debug.Log($"Loaded segment {_segCount}, Stack count: {_segStack.Count}");

// In SegmentMarker.OnTriggerExit():
Debug.Log("Segment destroyed, loading next...");

1. Forgetting Reverse Order

// ❌ Wrong - segments load backwards!
for (int i = 0; i < track.segments.Count; i++)
    _segStack.Push(track.segments[i]);

// ✅ Correct - reverse for LIFO behavior
for (int i = track.segments.Count - 1; i >= 0; i--)
    _segStack.Push(track.segments[i]);

2. Marker Not a Child

• If SegmentMarker is separate, only marker destroys
• Segment stays in scene → memory leak!
• Solution: Destroy transform.parent.gameObject

3. Trigger Not Set

• Forgetting "Is Trigger" checkbox
• Marker acts as solid wall, blocking player

Problem:

Segments always appear in same order = predictable tracks

Solution: Random Selection

private void RepopulateStack()
{
    // Create shuffled copy of segments
    List<GameObject> shuffled = new List<GameObject>(track.segments);

    // Shuffle using Fisher-Yates algorithm
    for (int i = shuffled.Count - 1; i > 0; i--)
    {
        int j = Random.Range(0, i + 1);
        GameObject temp = shuffled[i];
        shuffled[i] = shuffled[j];
        shuffled[j] = temp;
    }

    // Push shuffled segments
    for (int i = shuffled.Count - 1; i >= 0; i--)
        _segStack.Push(shuffled[i]);
}

Increase Challenge Over Time

public class Track : ScriptableObject
{
    public List<GameObject> easySegments;
    public List<GameObject> mediumSegments;
    public List<GameObject> hardSegments;
}

// In TrackController:
private void RepopulateStack()
{
    List<GameObject> segments;

    if (_segCount < 10)
        segments = track.easySegments;
    else if (_segCount < 30)
        segments = track.mediumSegments;
    else
        segments = track.hardSegments;

    // Push selected difficulty segments
    for (int i = segments.Count - 1; i >= 0; i--)
        _segStack.Push(segments[i]);
}

Problem: Instantiate/Destroy is Expensive

Creating and destroying segments every few seconds causes GC spikes.

Solution: Pool Segments

// Instead of Instantiate:
GameObject segment = _segmentPool.GetObject();
segment.transform.SetParent(_segParent);
segment.transform.localPosition = new Vector3(0, 0, _zPos);
segment.SetActive(true);

// Instead of Destroy in SegmentMarker:
private void OnTriggerExit(Collider other)
{
    if (other.GetComponent<BikeController>())
    {
        trackController.LoadSegment(1);

        // Return to pool instead of destroying
        _segmentPool.ReturnObject(transform.parent.gameObject);
    }
}

Beyond Prefabs: Generate Segments

Instead of pre-made segments, create them algorithmically.

Advantages:

• Infinite unique tracks
• Smaller game file size
• Adjustable difficulty parameters

Concept:

private GameObject GenerateSegment()
{
    GameObject segment = new GameObject("Generated Segment");

    // Add road mesh based on rules
    AddRoadMesh(segment, GetRandomCurve());

    // Procedurally place obstacles
    AddObstacles(segment, Random.Range(3, 8));

    // Add decorations
    AddScenery(segment);

    return segment;
}

Where Else to Use Spatial Partitioning?

1. Open World Games

• Load/unload city blocks as player moves
• Skyrim, GTA, Zelda: BotW

2. Multiplayer Games

• Only send updates for nearby players
• Interest management in MMOs

3. Physics Optimization

• Only check collisions within same grid cell
• Massive performance boost

4. AI Perception

• NPCs only "see" objects in their quadrant
• Reduced AI queries

5. Rendering Culling

• Don't render objects outside camera frustum
• Occlusion culling in Unity

Unity Already Uses Spatial Partitioning!

1. Occlusion Culling

• Don't render objects blocked by other objects
• Window → Rendering → Occlusion Culling

2. LOD (Level of Detail) Groups

• Switch to lower-poly meshes when far away
• Distance-based optimization

3. Lightmap UVs

• Pre-bake lighting into texture atlas
• Spatial UV layout optimization

4. Physics Layers

• Control which objects can collide
• Reduces collision checks

Before Spatial Partitioning:

Track Length: 5000 units
Segment Count: 125 segments (40 units each)
Active Objects: 125 segments always rendered
Memory: ~500 MB
FPS: 15-20 (unplayable)

After Spatial Partitioning:

Track Length: Infinite
Segment Count: 3 active at a time
Active Objects: 3 segments dynamically loaded
Memory: ~15 MB
FPS: 60+ (smooth gameplay)

Key Improvements:

• 97% memory reduction
• 300% FPS increase
• Unlimited track length

Not Always Necessary!

Skip if:

• Small Scenes: 10-20 objects total? Just render everything
• Static Cameras: Fixed camera angle shows same view always
• Mobile/Simple Games: Overhead might exceed benefits
• Already Fast: 60 FPS without optimization? Don't over-engineer

Premature Optimization Warning:

"Premature optimization is the root of all evil" - Donald Knuth

Measure Before Optimizing

Opening the Profiler:

• Window → Analysis → Profiler
• Press Play in Editor
• Watch CPU, Memory, Rendering graphs

What to Look For:

• CPU Spikes: Which scripts are slow?
• GC Allocations: Is garbage collection stalling frames?
• Draw Calls: Are you rendering too many objects?
• Batching: Can you combine meshes?

Profiler Deep Dive:

// Click on a frame spike to see:
- Hierarchy of function calls
- Time spent in each method
- Memory allocations per frame

This Was a Code Review Lecture!

Unlike previous lectures, this code is simplified and NOT production-ready.

Missing Elements:

• Error Handling: What if Track asset is null?
• Edge Cases: What if segments list is empty?
• Constants: Magic numbers (3 segments) should be variables
• Events: SegmentMarker could use UnityEvents

Production Improvements:

// Add validation:
if (track == null || track.segments.Count == 0)
{
    Debug.LogError("Track not configured!");
    enabled = false;
    return;
}

// Make configurable:
public int initialSegmentCount = 3;

Ideas to Expand the Level Editor:

1. Branching Paths

• Player chooses left or right route
• Each path has different segments

2. Vertical Segments

• Hills, valleys, jumps
• Y-position changes per segment

3. Special Events

• Boss fight segments
• Cutscene triggers
• Checkpoint markers

4. Weather/Time Transitions

• Day → night transition
• Weather changes (rain, fog)

5. Track Editor UI

• In-game track builder
• Share custom tracks online

1. Temple Run / Subway Surfers

• Endless runner with segment loading
• Exactly like our implementation!

2. Mario Kart Series

• Track divided into sections
• Load ahead, cull behind

3. Minecraft

• Chunk-based world (16×16 blocks)
• Load chunks around player

4. Grand Theft Auto V

• City divided into grid cells
• Stream in assets dynamically

5. Dark Souls

• BSP-based level streaming
• Seamless world without loading screens

Why Stack Instead of Queue?

Stack (LIFO):

• Last In, First Out
• Loaded in reverse → natural order
• Used in our TrackController

Queue (FIFO):

• First In, First Out
• No need to reverse list
• More intuitive for sequential loading

Queue Alternative:

private Queue<GameObject> _segQueue;

// Initialize (no reverse needed!)
for (int i = 0; i < track.segments.Count; i++)
    _segQueue.Enqueue(track.segments[i]);

// Load segment
GameObject segment = Instantiate(_segQueue.Dequeue());

Common Issues and Solutions:

1. Segments Not Loading

// Add debug logs:
Debug.Log($"Stack count: {_segStack.Count}");
Debug.Log($"Loading segment at Z: {_zPos}");

2. Track Not Moving

• Check BikeController reference is assigned
• Verify CurrentSpeed property is public
• Add Debug.Log(bikeController.CurrentSpeed)

3. Segments Not Destroying

• Ensure SegmentMarker collider is trigger
• Check bike has Collider component
• Verify marker is CHILD of segment

4. Visual Debugging

// In Scene view, enable Gizmos
private void OnDrawGizmos()
{
    Gizmos.color = Color.yellow;
    Gizmos.DrawWireCube(transform.position,
        new Vector3(10, 5, track.segmentLength));
}

Design Guidelines:

1. Profile First: Measure before optimizing
2. Consistent Segment Size: Makes calculations predictable
3. Tune Loading Distance: Load far enough ahead to avoid pop-in
4. Pool Objects: Combine with Object Pool pattern
5. Use ScriptableObjects: Designer-friendly configuration
6. Add Visual Feedback: Loading spinner during heavy operations
7. Test Edge Cases: Empty lists, null references
8. Document Decisions: Why Stack? Why 3 segments?

Build Your Own Level Editor

Requirements:

1. Create 3 different segment prefabs (straight, left curve, right curve)
2. Build a Track ScriptableObject with all 3 segments
3. Implement TrackController with Stack-based loading
4. Add SegmentMarker to each prefab for cleanup
5. Make track move at 20 units/second
6. Add randomization to RepopulateStack()

Bonus Challenges:

• Add difficulty progression (easy → hard segments)
• Integrate with Object Pool pattern
• Create in-game UI to switch between tracks
• Add collectibles that spawn on random segments

What We Learned:

• ✅ Spatial partitioning optimization techniques
• ✅ Stack (LIFO) data structure for segment management
• ✅ ScriptableObject-based track configuration
• ✅ Dynamic loading/unloading for memory efficiency
• ✅ Segment-based level editor implementation
• ✅ Performance profiling and optimization strategies

Key Takeaways:

• 🎯 Spatial partitioning = 97% memory reduction
• 🎯 Player stationary, track moves = clever illusion
• 🎯 Always profile before optimizing
• 🎯 Combine with Object Pool for best performance

Next Lecture:

Lecture 13: Additional Design Patterns - Command, Observer, State, and more!