Game Development Programming for Games Flashcards

24 sample cards from the Programming for Games deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. In Godot, what are signals and how do they support decoupled communication?

   Signals are Godot's implementation of the observer pattern: a node emits a signal (e.g. `emit_signal("health_changed")`) when an event occurs, and other nodes connect callback functions to it. This lets objects communicate without holding direct references, reducing coupling.

2. What problem does a pathfinding algorithm solve, and what is a common graph representation of a game map?

   Pathfinding finds a route (ideally the shortest or lowest-cost) between a start and goal position while avoiding obstacles. Game maps are commonly represented as a graph of nodes (grid cells, waypoints, or navmesh polygons) connected by weighted edges.

3. How does Dijkstra's algorithm work, and what is its typical time complexity with a binary heap?

   Dijkstra's algorithm finds shortest paths from a source by repeatedly expanding the unvisited node with the smallest known distance and relaxing its neighbors' distances. With a binary-heap priority queue its complexity is $O((V + E)\log V)$, where $V$ is vertices and $E$ is edges.

4. What is the A* (A-star) pathfinding algorithm, and what is its evaluation function?

   A* is a best-first search that finds the lowest-cost path using the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the actual cost from the start to node $n$ and $h(n)$ is a heuristic estimate of the cost from $n$ to the goal. It expands the node with the lowest $f(n)$.

5. For A* to be guaranteed to find an optimal (shortest) path, what property must its heuristic satisfy?

   The heuristic must be admissible: it must never overestimate the true remaining cost to the goal, i.e. $h(n) \leq h^{*}(n)$ for all nodes. (Consistency/monotonicity is a stronger condition that also guarantees optimality without re-expansions.)

6. What is the difference between Breadth-First Search (BFS) and Depth-First Search (DFS) for traversing a graph?

   BFS explores all neighbors at the current depth before moving deeper, using a queue (FIFO); on unweighted graphs it finds the shortest path in edges. DFS explores as far as possible along each branch before backtracking, using a stack or recursion (LIFO).

7. On a uniform-cost (unweighted) grid, why does Breadth-First Search always find the shortest path but plain Dijkstra offers no advantage?

   BFS explores nodes in order of increasing edge distance, so the first time it reaches the goal it has used the fewest edges — the shortest path. On a uniform-cost grid every edge has equal weight, so Dijkstra's priority ordering reduces to BFS ordering, adding overhead without benefit.

8. Describe how the Bubble Sort algorithm works and state its worst-case time complexity.

   Bubble Sort repeatedly steps through the list, comparing adjacent elements and swapping them if they are out of order, so larger elements 'bubble' to the end each pass. It has worst-case and average time complexity $O(n^{2})$ and best-case $O(n)$ when already sorted (with an early-exit optimization).

9. How does Merge Sort work, and what are its time and space complexities?

   Merge Sort is a divide-and-conquer algorithm: it recursively splits the array into halves, sorts each half, then merges the sorted halves. Its time complexity is $O(n\log n)$ in all cases, and it requires $O(n)$ auxiliary space for merging.

10. What is the average and worst-case time complexity of Quick Sort, and what causes the worst case?

    Quick Sort has average time complexity $O(n\log n)$ and worst case $O(n^{2})$. The worst case occurs when pivot selection is consistently poor (e.g. always the smallest or largest element), producing maximally unbalanced partitions; good pivot strategies make it rare.

11. How does Binary Search work, what is its time complexity, and what precondition must the data satisfy?

    Binary Search repeatedly compares the target to the middle element of a sorted array, discarding the half that cannot contain the target. It runs in $O(\log n)$ time. Its precondition is that the array must already be sorted.

12. What does it mean for a sorting algorithm to be 'stable', and name one stable and one unstable sort.

    A stable sort preserves the relative order of elements that compare equal. Merge Sort and Insertion Sort are stable; Quick Sort and Heap Sort are generally unstable (equal keys may be reordered).

13. Compare the average-case time complexities of Bubble Sort, Insertion Sort, Merge Sort, and Quick Sort.

    Bubble Sort and Insertion Sort are $O(n^{2})$ on average. Merge Sort is $O(n\log n)$ in all cases. Quick Sort is $O(n\log n)$ on average (but $O(n^{2})$ worst case). Merge and Quick Sort scale far better for large inputs.

14. What is an array, and what is the time complexity of accessing an element by index versus inserting at the front?

    An array is a contiguous block of memory storing elements of the same type. Accessing an element by index is $O(1)$ because the address is computed directly. Inserting at the front (or middle) is $O(n)$ because subsequent elements must be shifted.

15. What is the key structural difference between an array and a singly linked list?

    An array stores elements contiguously with $O(1)$ index access but $O(n)$ insertion/deletion in the middle. A linked list stores elements as nodes, each holding data and a pointer to the next node; it allows $O(1)$ insertion/deletion given a node reference but only $O(n)$ sequential access (no direct indexing).

16. What is a stack, what is its access discipline, and what are its two primary operations?

    A stack is a linear data structure with Last-In-First-Out (LIFO) discipline: the most recently added element is removed first. Its primary operations are `push` (add an element to the top) and `pop` (remove the top element), both $O(1)$.

17. What is a queue, and how does its access discipline differ from a stack's?

    A queue is a linear structure with First-In-First-Out (FIFO) discipline: elements are removed in the order they were added. Its operations are `enqueue` (add to the rear) and `dequeue` (remove from the front). This contrasts with a stack's LIFO order.

18. What is a binary tree, and what specifically defines a Binary Search Tree (BST)?

    A binary tree is a hierarchical structure where each node has at most two children (left and right). A Binary Search Tree adds an ordering invariant: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger, enabling efficient search.

19. What are the average and worst-case time complexities for search in a Binary Search Tree, and when does the worst case occur?

    Search in a BST is $O(\log n)$ on average when the tree is balanced. It degrades to $O(n)$ in the worst case when the tree becomes unbalanced (e.g. inserting sorted data turns it into a linked-list-like chain).

20. What are the three depth-first tree traversal orders, and what does an in-order traversal of a BST produce?

    The three depth-first orders are pre-order (node, left, right), in-order (left, node, right), and post-order (left, right, node). An in-order traversal of a Binary Search Tree visits the keys in sorted ascending order.

21. What is a graph, and what is the difference between a directed and an undirected graph?

    A graph is a set of vertices (nodes) connected by edges. In an undirected graph edges have no direction (the relationship is mutual). In a directed graph (digraph) each edge has a direction, pointing from one vertex to another, representing a one-way relationship.

22. Compare an adjacency matrix and an adjacency list for representing a graph in terms of space and edge-lookup.

    An adjacency matrix uses $O(V^{2})$ space and checks whether an edge exists in $O(1)$; it suits dense graphs. An adjacency list uses $O(V + E)$ space and checks a specific edge in $O(\text{degree})$ time; it is more efficient for sparse graphs, which most game maps are.

23. What is a hash table, how does it achieve fast lookups, and how are collisions typically handled?

    A hash table stores key-value pairs, using a hash function to map each key to an index in an underlying array, giving $O(1)$ average lookup, insertion, and deletion. Collisions (two keys mapping to the same index) are resolved by chaining (storing a linked list per bucket) or open addressing (probing for another slot).

24. What is Big-O notation, and why is it used to compare algorithms and data structures in game programming?

    Big-O notation describes the asymptotic upper bound on an algorithm's running time (or space) as a function of input size $n$, ignoring constants and lower-order terms. It lets programmers compare scalability, e.g. distinguishing an $O(n\log n)$ algorithm from an $O(n^{2})$ one, which matters for performance-critical game loops.

What this deck covers

Programming for Games flashcards FAQ