🗺️ Spatial Partition

Implementing a Level Editor

Game Programming - CSCI 3213

Spring 2026 - Lecture 12

Oklahoma City University

📚 Learning Objectives

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

🧩 Spatial Partitioning Overview

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

Note: This is an optimization technique, not a Gang of Four design pattern!

🔍 Partitioning Techniques

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

🏁 Level Editor Design Goals

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

Key Insight: Player bike stays stationary; track moves toward player!

📚 Stack Fundamentals (LIFO)

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

Why Stack? Segments loaded in reverse order = natural LIFO behavior

🏗️ System Architecture

Three Core Components:

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

📦 Track ScriptableObject

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

Workflow: Designers create Track assets, add prefabs, no code needed!

🎨 Designer Workflow

Steps to Create a Track:

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

Variety: More prefabs = more track variation!

🎮 TrackController Class (Setup)

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
    }
}

🔄 Stack Loading Strategy

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! ✅

Key Insight: Reversing during initialization gives us correct order during gameplay

📥 LoadSegment Method

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++;
        }
    }
}

📍 Positioning Segments

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

Remember: Player doesn't move; track comes to player!

♻️ Refilling the Stack

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]);
    }
}

Result: Infinite track by cycling through segments!

🚴 Moving the Track

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)

Illusion: Player feels like they're racing forward!

🚩 SegmentMarker Class

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

🧱 Segment Prefab Anatomy

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

Important: Marker must be CHILD of segment so both destroy together

💾 Memory Efficiency

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! 🎉

Scalability: Can create "infinite" tracks with minimal memory

📋 Full TrackController Implementation

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
        );
    }

📋 TrackController Methods

    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]);
    }
}

⚙️ Unity Setup Steps

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

🧪 Testing Your Track

What to Verify:

Initial Load: 3 segments appear at start
Track Movement: Track moves backward smoothly
Segment Loading: New segment appears when passing marker
Cleanup: Old segment destroys after passing
Stack Refill: Segments cycle when stack empties
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...");

⚠️ Common Pitfalls

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

🎲 Adding Randomization

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]);
}

📈 Progressive Difficulty

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]);
}

♻️ Object Pool Integration

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);
    }
}

🎨 Procedural Track Generation

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;
}

Examples: No Man's Sky, Minecraft, Spelunky

🌍 Beyond Racing Tracks

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's Spatial Tools

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

Takeaway: Learn from Unity's optimizations!

📊 Performance Metrics

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

🚫 When to Skip Spatial Partitioning

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

Best Practice: Profile first, optimize only if needed

📈 Unity Profiler

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

🔍 Code Review Observations

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;

🚀 Advanced Features

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

🎮 Games Using Spatial Partitioning

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

📚 Stack vs Queue Comparison

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());

Either works! Stack chosen for learning LIFO concept

🐛 Debugging Your Track System

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));
}

✅ Best Practices

Design Guidelines:

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

Remember: Spatial partitioning is about performance, not patterns

💪 Practice Challenge

Build Your Own Level Editor

Requirements:

Create 3 different segment prefabs (straight, left curve, right curve)
Build a Track ScriptableObject with all 3 segments
Implement TrackController with Stack-based loading
Add SegmentMarker to each prefab for cleanup
Make track move at 20 units/second
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

🎓 Lecture Summary

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!