Chapter 6: Common data structures: List, Stack, and Queue
The introduction explains why arrays fit data-oriented design and why built-in collections, despite making dynamic changes easier, warrant scrutiny.
After this chapter you will be able to
- Array locality and pooling. Explain why the book has used arrays of primitive types to store game data.
- Dynamic data structure tradeoff. Describe the tension between fixed-size array data and the convenience of built-in collections when elements must be added or removed.
- List access and flexibility. Describe how a C# List supports indexed retrieval, insertion, removal, and dynamic growth, and why those features suit a changing set of enemies.
- List memory and performance costs. State the potential downside the section identifies for C# List despite its convenience.
- List and Linked List locality. Explain how a C# List of primitive values differs from a Linked List in storage, and why that difference matters when traversing the data.
- List convenience and hidden costs. Describe why List initially looks useful for data-oriented design, and state the performance caution the section gives about using it for GameData’s EnemyPosition data.
- List resizing costs. Trace what happens when a List runs out of space and explain why resizing affects performance and garbage collection.
- Preallocated List capacity. Explain how preallocating a List to its expected maximum size addresses resize-related costs, and state the limit of that solution.
- Element shifting in List. Explain why removing an element at an index or inserting one in the middle of a List can be costly.
- List versus array performance. Describe how the section compares a List with an array and what the results show. Explain that the section offers possible reasons for the difference but does not establish its cause.
- Limits of compiler optimization. Explain why the section says compiler optimizations cannot be relied on to make an inefficient choice perform like a simpler one.
- Cost of alive checks. Explain why checking an EnemyAlive boolean for every enemy is an unattractive way to move only living enemies.
- Separate alive and dead indices. Describe the proposed roles of the alive and dead enemy index arrays.
- Alive enemy index traversal. Explain how AliveEnemyIndices lets the game move only living enemies by looping over their stored indices rather than all enemies.
- Index array count and capacity. Distinguish fixed data arrays from the preallocated index array whose number of used entries changes. Explain why AliveEnemyIndices needs capacity for every enemy, while AliveEnemyCount determines how many entries to loop over.
- Array-backed enemy index append. Describe how spawnEnemy() replaces List.Add() by storing enemyIndex at the position indicated by AliveEnemyCount and then increasing that count.
- Postincrement indexing order. Explain why incrementing AliveEnemyCount after it is used as an array index places the new value correctly, while incrementing it first selects the wrong position.
- Fixed-bound array compaction. Trace how removal scans all entries within the original AliveEnemyCount while a separate count tracks where surviving values are written. Explain why the loop does not change AliveEnemyCount as it runs.
- Logical count after removal. Explain why removeEnemy() assigns the final count to gameData.AliveEnemyCount and why an old value left beyond that count does not matter.
- Visible data manipulation. Explain why the section prefers an explicit line of code over a generic helper when adding an alive enemy index.
- Problem-specific array behavior. Explain why the implementation is not treated as a reusable List data structure, even though adding and removing indices resembles List operations.
- Array.Copy removal shift. Trace how removeEnemy() finds an enemyIndex and uses Array.Copy() to shift the later entries of gameData.AliveEnemyIndices left over it.
- Copy versus loop choice. Explain why Array.Copy() can suit removal of one unique index from a sufficiently large array, while a loop can be better for small arrays or removing multiple matches.
- Alive enemy movement loop. Trace how moveEnemies() changes from looping over balance.NumEnemies to looping over gameData.AliveEnemyCount and retrieving each enemyIndex from gameData.AliveEnemyIndices.
- Dead index stack choice. Justify treating DeadEnemyIndices as a stack rather than a queue: spawning needs any index not used by a live enemy, not the oldest available index.
- Dead index push and pop. Trace how removing an enemy adds its index to DeadEnemyIndices and how spawning retrieves it, including why the count is decremented before indexing during a pop.
- Queue ordering and usefulness. Distinguish a queue’s FIFO order from a stack’s LIFO order, and explain why FIFO is useful for processing discovered positions but unnecessary when enemy spawning needs any unused index.
- Circular queue state. Describe what queueStart, queueEnd, and queueCount track, and how the indices wrap around a fixed-size array.
- Enqueue and dequeue behavior. Trace how an item is added at queueEnd and removed from queueStart without shifting or clearing the stored values.
- Alive and dead index tracking. Explain why GameData holds separate arrays of alive and dead enemy indices and an integer count for each array.
- Delta-time enemy spawn trigger. Describe how GameData.SpawnTime and Balance.SpawnTime determine when to spawn an enemy in Tick().
- Alive and dead array capacity. Explain why both enemy-index arrays are allocated with a length of Balance.NumEnemies.
- Initial enemy index state. Describe how StartGame() initializes the alive and dead enemy indices: the alive count is zero, while the dead array contains every possible index in reverse order and its count equals balance.NumEnemies. Explain why reverse order makes index 0 the first value popped from the end.
- Enemy spawn and removal. Describe how spawning restores enemy positioning and how an out-of-bounds enemy is removed from the alive indices and added to the dead indices.
- Two-pass enemy removal. Explain why out-of-bounds enemy indices are collected in a first loop and removed afterward.
- Current state versus changes. Explain why the current AliveEnemyIndices and DeadEnemyIndices arrays cannot by themselves tell the Board which enemy GameObjects to show or hide.
- Per-frame visual change output. Describe how Logic can pass added and removed enemy indices to the Board, and why updating only those GameObjects is preferable to checking every GameObject each frame.
- Temporary array lifetime. Justify keeping the Board's per-frame visual-change arrays temporary rather than in GameData or as heap arrays retained for the whole gameplay session, and describe the task-level lifetime proposed for them.
- Temporary enemy index arrays. Describe how Board.Tick() prepares separate temporary arrays for added and removed enemy indices, sizes them to handle all enemies, tracks how many indices are used, and passes them to Logic for population.
- Recording newly spawned enemy indices. Trace how Tick() passes the stack-allocated Span<int> array and a reference to the count to spawnEnemy(), where the new enemyIndex is stored in addedEnemyIndices before addedEnemyCount is incremented.
- Removed enemy index tracking. Trace how an enemy removal records its index and how the removal data reaches removeEnemy().
- Board visibility updates. Describe how Board.Tick() uses the added and removed enemy indices to show and hide GameObjects.
- Purpose Built Array Structures. Explain why the chapter favors arrays with small amounts of explicit state over built-in List, Stack, and Queue for the behaviors the game needs. Distinguish when a Stack-like array is preferable to a circular Queue.
- Logic To Board Change Arrays. Trace how temporary arrays communicate enemy additions and removals from Logic code to the Board without combining gameplay logic and visual code.
What it builds on
- Data locality and contiguous memory - arrays of structs vs arrays of classes (chapter 2) · Data locality and contiguous memory.
- Using object pools to avoid memory fragmentation and garbage collection (chapter 3) · Using pools to avoid fragmentation and garbage collection.
- Reducing code complexity by separating data and logic (chapter 1) · Reducing code complexity.
- Memory fragmentation (chapter 3) · Introduces memory fragmentation as a performance concern.
- The GameData (chapter 4) · The role of GameData as the game’s data container.
- Avoiding fragmented memory and garbage collection with object pools (chapter 3) · The earlier discussion of memory growth and object pools.
- AllocateGameData() - Allocating all the data for our game (chapter 4) · The earlier allocation of gameplay data for enemies.
- Functions called by Tick() (chapter 4) · The existing gameplay functions that move enemies.
Section by section
Introduction
The introduction explains why arrays fit data-oriented design and why built-in collections, despite making dynamic changes easier, warrant scrutiny.
- Array locality and pooling: Explain why the book has used arrays of primitive types to store game data.
Why it matters: These are the performance and memory-management reasons behind the chapter’s preference for arrays. - Dynamic data structure tradeoff: Describe the tension between fixed-size array data and the convenience of built-in collections when elements must be added or removed.
Why it matters: Convenient add-and-remove operations do not by themselves settle whether a collection suits performance-sensitive game data. - Black-box code and alternatives: Explain why the section favors understandable array-based implementations over treating built-in collections as black boxes.
Why it matters: The argument for array-based structures concerns code clarity as well as data locality and memory management.
Key terms: arrays of primitive types, data locality, L1 cache, object pools, arrays, List, Stack, Queue, data-oriented design, black-box code
6.1 C# List
Introduces what C# List provides for changing collections of enemies and flags potential memory and performance costs.
- List access and flexibility: Describe how a C# List supports indexed retrieval, insertion, removal, and dynamic growth, and why those features suit a changing set of enemies.
Why it matters: These conveniences explain why a List is appealing for enemy data before considering its costs. - List memory and performance costs: State the potential downside the section identifies for C# List despite its convenience.
Why it matters: List convenience is not the only consideration when choosing a structure for performance-sensitive game data.
Key terms: C# List, index, dynamically, List, memory fragmentation, performance slowdowns
6.1.1 C# List vs Linked List
This section compares the memory layout and traversal performance of C# List and Linked List, then cautions that List’s convenient interface can conceal performance costs.
- List and Linked List locality: Explain how a C# List of primitive values differs from a Linked List in storage, and why that difference matters when traversing the data.
Why it matters: Memory layout helps explain why two collections that hold the same values can perform differently in a game. - List convenience and hidden costs: Describe why List initially looks useful for data-oriented design, and state the performance caution the section gives about using it for GameData’s EnemyPosition data.
Why it matters: A convenient collection is not automatically the right performance choice for GameData.
Key terms: C# List, Linked List, data locality, contiguous memory, nodes, List, GameData, EnemyPosition array, dynamic resizing
6.1.2 List and dynamic resizing
This section explains the performance costs of a List growing dynamically and how preallocating capacity avoids resize-related costs.
- List resizing costs: Trace what happens when a List runs out of space and explain why resizing affects performance and garbage collection.
Why it matters: A List can incur copying and garbage-collection costs when it grows beyond its capacity. - Preallocated List capacity: Explain how preallocating a List to its expected maximum size addresses resize-related costs, and state the limit of that solution.
Why it matters: Preallocation addresses resizing costs, but it is not a blanket guarantee that every List operation is cheap.
Key terms: List, dynamic resizing, garbage collector, preallocate, RemoveAt()
6.1.3 List and built-in functions
This section explains the copying and allocation costs hidden behind C# List insertion and removal helpers.
- Element shifting in List: Explain why removing an element at an index or inserting one in the middle of a List can be costly.
Why it matters: Convenient List operations can do substantially more work than their names suggest. - Capacity growth during insertion: Describe the additional work required when an insertion takes a List beyond its capacity.
Why it matters: An insertion can trigger an allocation and a full copy in addition to making room for the new element.
Key terms: List, Insert(), RemoveAt(), capacity, array
6.1.4 List and performance
This section compares List and array access performance, uses the result to argue for measuring built-in structures, and explains why compiler optimizations cannot replace simple, performance-conscious code.
- List versus array performance: Describe how the section compares a List with an array and what the results show. Explain that the section offers possible reasons for the difference but does not establish its cause.
Why it matters: A familiar collection can be slower than its underlying storage in the kind of loop your game runs often. - Testing built-in data structures: Justify testing the performance of built-in data structures rather than assuming their implementations are efficient.
Why it matters: Measuring the collection you use can expose costs that its convenient interface does not reveal. - Limits of compiler optimization: Explain why the section says compiler optimizations cannot be relied on to make an inefficient choice perform like a simpler one.
Why it matters: Good data and code choices remain your responsibility even when a compiler can optimize them further.
Key terms: List, array, data-oriented design, built-in data structures, black-box code, garbage collector, compiler optimizations, SIMD instructions, arrays
6.1.5 Replacing List with an array
The section motivates replacing per-enemy alive checks with arrays of alive and dead enemy indices so enemies can be removed and respawned while retaining array-based data.
- Enemy data by index: Explain why enemy indices matter when enemies can die and respawn in an array-based design.
Why it matters: Indices let the game track enemies without changing how their array-stored data is referenced. - Cost of alive checks: Explain why checking an EnemyAlive boolean for every enemy is an unattractive way to move only living enemies.
Why it matters: It explains the performance reason for tracking active enemies separately instead of testing every enemy during movement. - Separate alive and dead indices: Describe the proposed roles of the alive and dead enemy index arrays.
Why it matters: The two collections provide a way to track active enemies and reuse dead enemies’ indices.
Key terms: data-oriented design, index, arrays, EnemyAlive, branch check, branch prediction, moveEnemies(), alive enemy array, dead enemy array, Stack
6.2 DOD List Implementation
This section introduces a preallocated array of alive enemy indices and a count that lets gameplay process only the indices currently in use.
- Alive enemy index traversal: Explain how AliveEnemyIndices lets the game move only living enemies by looping over their stored indices rather than all enemies.
Why it matters: The index array identifies which enemies need movement work. - Index array count and capacity: Distinguish fixed data arrays from the preallocated index array whose number of used entries changes. Explain why AliveEnemyIndices needs capacity for every enemy, while AliveEnemyCount determines how many entries to loop over.
Why it matters: The count separates the number of entries currently in use from the array's allocated capacity.
Key terms: AliveEnemyIndices, GameData, EnemyPosition, AliveEnemyCount, preallocated size, Logic.AllocateGameData()
6.2.1 DOD Implementation of List.Add()
This section shows how to append an enemy index to an array-backed list and why the count must be incremented after it is used as the array index.
- Array-backed enemy index append: Describe how spawnEnemy() replaces List.Add() by storing enemyIndex at the position indicated by AliveEnemyCount and then increasing that count.
Why it matters: The array and its count together provide the add operation that List.Add() would otherwise handle. - Postincrement indexing order: Explain why incrementing AliveEnemyCount after it is used as an array index places the new value correctly, while incrementing it first selects the wrong position.
Why it matters: Changing the increment order makes the append write to the wrong array position.
Key terms: List.Add(), AliveEnemyIndices, AliveEnemyCount, enemyIndex, spawnEnemy(), increment operator (++)
6.2.2 DOD implementation of List Remove()
This section explains how to remove enemy indices from a DOD array by compacting its values and updating its logical count.
- Fixed-bound array compaction: Trace how removal scans all entries within the original AliveEnemyCount while a separate count tracks where surviving values are written. Explain why the loop does not change AliveEnemyCount as it runs.
Why it matters: Keeping the scan bound fixed lets removal examine every original entry while packing the remaining entries together. - Logical count after removal: Explain why removeEnemy() assigns the final count to gameData.AliveEnemyCount and why an old value left beyond that count does not matter.
Why it matters: Updating the count prevents an unused trailing array entry from being treated as a live enemy index.
Key terms: gameData.AliveEnemyIndices, gameData.AliveEnemyCount, count, enemyIndex, removeEnemy()
6.2.3 DOD List helper functions, or lack of
Explains why the DOD implementation uses explicit, problem-specific array manipulation instead of generic List-like helper functions.
- Visible data manipulation: Explain why the section prefers an explicit line of code over a generic helper when adding an alive enemy index.
Why it matters: Keeping a simple data operation visible makes it easier to see what the code does. - Problem-specific array behavior: Explain why the implementation is not treated as a reusable List data structure, even though adding and removing indices resembles List operations.
Why it matters: A solution can change with the game’s needs without being constrained by a List-like label or API.
Key terms: DOD, helper functions, abstractions, List, alive enemy indices, data structures
6.2.4 Array.Copy()
This section shows how Array.Copy() can remove one alive-enemy index by shifting later entries left, and when a manual loop is preferable.
- Array.Copy removal shift: Trace how removeEnemy() finds an enemyIndex and uses Array.Copy() to shift the later entries of gameData.AliveEnemyIndices left over it.
Why it matters: The copy arguments show how an array can support removal without using List.Remove(). - Copy versus loop choice: Explain why Array.Copy() can suit removal of one unique index from a sufficiently large array, while a loop can be better for small arrays or removing multiple matches.
Why it matters: The best removal approach depends on both array size and whether one value or many matching values must be removed.
Key terms: Array.Copy(), removeEnemy(), gameData.AliveEnemyIndices, enemyIndex, gameData.AliveEnemyCount, List.Remove(), first occurrence, AliveEnemyIndices
6.2.5 Using the AliveEnemyIndices array
The section changes enemy movement to process only alive enemies and explains why an unsorted index array can still benefit from cache locality.
- Alive enemy movement loop: Trace how moveEnemies() changes from looping over balance.NumEnemies to looping over gameData.AliveEnemyCount and retrieving each enemyIndex from gameData.AliveEnemyIndices.
Why it matters: The loop no longer does movement work for enemies that are not alive. - Cache locality despite index gaps: Explain why unsorted or widely spaced alive-enemy indices do not eliminate the data-locality benefit described here.
Why it matters: It explains why indirect access to alive enemies can remain useful even without adjacent indices.
Key terms: moveEnemies(), balance.NumEnemies, gameData.AliveEnemyCount, gameData.AliveEnemyIndices, enemyIndex, data locality, cache line, L1 cache, main memory
6.3 DOD stack implementation
The section shows how to reuse dead enemy indices with a simple array-backed stack instead of a FIFO queue.
- Dead index stack choice: Justify treating DeadEnemyIndices as a stack rather than a queue: spawning needs any index not used by a live enemy, not the oldest available index.
Why it matters: Choosing the structure around the actual retrieval requirement avoids unnecessary bookkeeping. - Dead index push and pop: Trace how removing an enemy adds its index to DeadEnemyIndices and how spawning retrieves it, including why the count is decremented before indexing during a pop.
Why it matters: The count makes it possible to reuse an available index without searching the array.
Key terms: DeadEnemyIndices, Stack, Queue, first-in, first-out (FIFO), DeadEnemyCount, enemyIndex, push, pop, removeEnemy()
6.4 Queue
This section explains when FIFO order matters and how a fixed-size circular array can implement a queue without shifting stored values.
- Queue ordering and usefulness: Distinguish a queue’s FIFO order from a stack’s LIFO order, and explain why FIFO is useful for processing discovered positions but unnecessary when enemy spawning needs any unused index.
Why it matters: It helps you choose a queue only when the order of removal serves the game’s needs. - Circular queue state: Describe what queueStart, queueEnd, and queueCount track, and how the indices wrap around a fixed-size array.
Why it matters: Those three values identify the active queue without moving the array itself. - Enqueue and dequeue behavior: Trace how an item is added at queueEnd and removed from queueStart without shifting or clearing the stored values.
Why it matters: Advancing indices avoids copying every remaining value on each dequeue. - Use specific capacity guarantees: Justify why this use-specific queue implementation omits generic full and empty checks.
Why it matters: The optimization depends on guarantees supplied by the surrounding system, not on checks being universally unnecessary.
Key terms: Queue, Stack, FIFO, LIFO, circular array, queueStart, queueEnd, queueCount, enqueueing, dequeuing
6.5 Putting it all together
6.5.1 Adding the alive and dead indices arrays to GameData
This subsection adds enemy-status arrays and a spawn timer to GameData to support dynamic spawning and dying.
- Alive and dead index tracking: Explain why GameData holds separate arrays of alive and dead enemy indices and an integer count for each array.
Why it matters: These fields let the game track enemy status as enemies spawn and die. - Delta-time enemy spawn trigger: Describe how GameData.SpawnTime and Balance.SpawnTime determine when to spawn an enemy in Tick().
Why it matters: The comparison supplies a time-based trigger for enemy spawning.
Key terms: GameData, alive enemy indices, dead enemy indices, GameData.SpawnTime, Balance.SpawnTime, delta time, Tick()
6.5.2 Allocating the alive and dead indices arrays
This subsection explains how large to make the alive and dead enemy-index arrays and why both need the full capacity.
- Alive and dead array capacity: Explain why both enemy-index arrays are allocated with a length of Balance.NumEnemies.
Why it matters: Sizing both arrays for the worst case ensures either one can hold indices for every enemy.
Key terms: Balance.NumEnemies, alive and dead indices arrays
6.5.3 Initializing the alive and dead indices arrays
Explains how StartGame() initializes the alive and dead enemy index arrays and their counts before enemies spawn.
- Initial enemy index state: Describe how StartGame() initializes the alive and dead enemy indices: the alive count is zero, while the dead array contains every possible index in reverse order and its count equals balance.NumEnemies. Explain why reverse order makes index 0 the first value popped from the end.
Why it matters: These starting values let spawning take available enemy indices from the dead array and add them to the alive set.
Key terms: StartGame(), GameData.AliveEnemiesCount, GameData.DeadEnemyIndices, GameData.DeadEnemyCount, balance.NumEnemies, Stack
6.5.4 Spawning and positioning enemies
The section updates enemy spawning and out-of-bounds removal to use alive and dead index arrays, while avoiding skipped enemies and temporary heap allocations.
- Enemy spawn and removal: Describe how spawning restores enemy positioning and how an out-of-bounds enemy is removed from the alive indices and added to the dead indices.
Why it matters: It connects enemy spawning and removal to the game's new index arrays. - Two-pass enemy removal: Explain why out-of-bounds enemy indices are collected in a first loop and removed afterward.
Why it matters: It prevents out-of-bounds enemies from being missed when the alive list changes. - Temporary stack-allocated indices: Explain why the temporary indices array uses stackalloc and Span<int>.
Why it matters: The temporary storage supports safe removal without adding garbage-collector work. - Alive-index function updates: State which other game functions must be changed to use gameData.AliveEnemyIndices.
Why it matters: The alive-index change must be reflected in other functions that work with enemies.
Key terms: spawnEnemy(), removeEnemy(), alive enemy indices array, dead enemy indices array, AliveEnemyIndices, AliveEnemyCount, temporary array, Span<int>, stackalloc, stack
6.6 Visualizing enemy changes on the board
The section explains why the Board needs per-frame enemy changes, rather than current alive/dead lists alone, and why temporary change arrays suit that job.
- Current state versus changes: Explain why the current AliveEnemyIndices and DeadEnemyIndices arrays cannot by themselves tell the Board which enemy GameObjects to show or hide.
Why it matters: A current-state list does not give the Board enough information to update just the GameObjects that changed. - Per-frame visual change output: Describe how Logic can pass added and removed enemy indices to the Board, and why updating only those GameObjects is preferable to checking every GameObject each frame.
Why it matters: Passing only changes lets the Board avoid unnecessary per-frame GameObject work. - Temporary array lifetime: Justify keeping the Board's per-frame visual-change arrays temporary rather than in GameData or as heap arrays retained for the whole gameplay session, and describe the task-level lifetime proposed for them.
Why it matters: Limiting each temporary array to the task that uses it avoids both repeated heap cleanup and long-lived memory use.
Key terms: AliveEnemyIndices, DeadEnemyIndices, AliveEnemyCount, Board, Logic, addedEnemyIndices, removedEnemyIndices, GameObjects, GameData, Board.Tick()
6.6.1 Allocating temporary arrays in the Board
Board.Tick() prepares stack-allocated temporary arrays to track enemy indices added and removed during a frame.
- Temporary enemy index arrays: Describe how Board.Tick() prepares separate temporary arrays for added and removed enemy indices, sizes them to handle all enemies, tracks how many indices are used, and passes them to Logic for population.
Why it matters: The arrays let Board.Tick() track changes for the frame without allocating heap memory.
Key terms: Board.Tick(), Span<int>, stackalloc, enemy indices, Logic
6.6.2 Populating the addedEnemyIndices array
This section shows how spawning an enemy records its index in a temporary array for newly added enemies.
- Recording newly spawned enemy indices: Trace how Tick() passes the stack-allocated Span<int> array and a reference to the count to spawnEnemy(), where the new enemyIndex is stored in addedEnemyIndices before addedEnemyCount is incremented.
Why it matters: Recording the index during spawning keeps the array of newly added enemies up to date.
Key terms: spawnEnemy(), Tick(), Span<int>, addedEnemyIndices, enemyIndex, addedEnemyCount
6.6.3 Populating the removedEnemyIndices array
The section records removed enemy indices, passes them to the board, and uses added and removed indices to keep enemy GameObjects visually in sync with gameplay.
- Removed enemy index tracking: Trace how an enemy removal records its index and how the removal data reaches removeEnemy().
Why it matters: Recording removals gives the board the indices it needs to hide the right enemies. - Board visibility updates: Describe how Board.Tick() uses the added and removed enemy indices to show and hide GameObjects.
Why it matters: These updates make the visible enemies match the changes recorded by gameplay logic. - Initial enemy visibility: Explain why Board.Show() now starts with every enemy GameObject inactive.
Why it matters: Starting inactive prevents enemy GameObjects from appearing before their enemies spawn.
Key terms: removeEnemy(), removedEnemyIndices, removedEnemyCount, enemyIndex, Board.Tick(), addedEnemyIndices, addedEnemyCount, GameObject, Board.Show(), StartGame()
6.7 Conclusion
The section concludes that purpose-built arrays and index-based data can replace general-purpose collections while keeping gameplay logic separate from visual updates.
- Purpose Built Array Structures: Explain why the chapter favors arrays with small amounts of explicit state over built-in List, Stack, and Queue for the behaviors the game needs. Distinguish when a Stack-like array is preferable to a circular Queue.
Why it matters: Choosing only the behavior a game needs can avoid collection overhead and keep the implementation simpler. - Index Based Object References: Describe how indices let the game reference enemies and other objects through arrays in GameData.
Why it matters: Indices provide a compact way to track objects without duplicating their data. - Logic To Board Change Arrays: Trace how temporary arrays communicate enemy additions and removals from Logic code to the Board without combining gameplay logic and visual code.
Why it matters: The arrays pass just the changes the Board must display while keeping gameplay decisions in Logic.
Key terms: List, Stack, Queue, data locality, dynamic growth, circular Queue, index, GameData, arrays of indices, Logic
6.8 Summary
The summary draws together the chapter’s performance lessons about built-in collections, index-based arrays, and problem-specific array operations.
Where this is used later
- Dictionary performance (chapter 10) · Dynamic resizing of a List.
- Adding SIMD vectorization using the Burst compiler (chapter 12) · Provides the rationale for structuring data so SIMD vectorization is possible.
- Branch prediction (chapter 11) · Provides a gameplay example of unpredictable branch outcomes.
- Continuing gameplay (chapter 7) · the alive enemy indices array
- (chapter intro) (chapter 11) · The use of the AliveEnemyIndices array.
- Setting the pool size (chapter 10) · alive enemy indices stored separately from enemy data
- Showing newly added enemies (chapter 10) · Showing newly added enemies uses the record of which enemy indices were added.
- Hiding removed enemies (chapter 10) · Hiding removed enemies builds on identifying which enemy indices were removed.
Concepts explained in this chapter
- listA C# List is a dynamically sized sequence collection that stores elements in an internal array and provides indexed access and element operations.
- arrayAn indexed sequence of elements, typically stored in contiguous memory.
- queueA data structure that stores elements for first-in, first-out retrieval.
- stack memoryA region of runtime memory typically used for function call frames and short-lived local values.
- temporary dataRuntime data whose lifetime spans only a short operation or update rather than the entire gameplay session.
- data-oriented programmingAn approach to structuring software around the flow and transformation of data rather than relationships between objects.
- branch predictionBranch prediction is processor hardware behavior that predicts the outcome of a conditional branch before it is resolved.
- contiguous memory layoutA region of memory in which elements occupy adjacent addresses without gaps between them.
- data localityThe degree to which related data is stored or accessed close together in the memory hierarchy.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
