COMP 3200 - Intro to Artificial Intelligence - Lecture 07 - Assignment 2

Overview

Dave Churchill introduces COMP 3200 Assignment 2, which replaces Assignment 1's simpler search algorithms with A* search over grid environments containing 1x1, 2x2, and 3x3 objects, four- or eight-directional actions, variable action costs, and selectable heuristics. The lecture explains collision-aware movement, connectivity precomputation with cardinal BFS, heuristic admissibility, A* data structures, tie-breaking, and a step-by-step JavaScript implementation and testing workflow, while explicitly excluding bidirectional search for COMP 3200.

Key takeaways

Assignment 2 requires A* search over 1x1, 2x2, and 3x3 grid objects, with cardinal actions costing 100 and diagonal actions costing 141.
Setting h to zero converts A* into uniform-cost search and provides the safest baseline for separating search-logic bugs from heuristic-implementation bugs.
A diagonal move is legal only when both corresponding cardinal moves are legal, which prevents corner-cutting and reduces diagonal legality to a few connectivity checks.
Precomputing connected sectors with cardinal BFS for every object size allows constant-time connectivity queries and avoids repeatedly checking all tiles occupied by an object.
Four-directional Manhattan distance is not admissible for eight-directional movement; diagonal Manhattan or Euclidean distance should be used when diagonal actions are enabled.
A binary-heap open list improves A* performance by making minimum-node access constant time and insertion O(log n), while h-based tie-breaking can substantially reduce unnecessary expansions.

Chapters

0:00 Assignment 2 Scope, Deadlines, and Course Roadmap

Assignment 1 is due at 11:59 p.m. on the lecture date, while Assignment 2 is released during the lecture.
Dave Churchill will separate rushed live coding from the main class and append a recorded programming tutorial to future assignment lectures.
The upcoming midterm covers all material completed by late October, and Assignment 3 will focus on game theory, minimax, and alpha-beta pruning.

2:00 Assignment 2 Interface and A* Search Demonstration

Assignment 2 retains Assignment 1's user interface but exposes only the student A* implementation and the reference solution.
A* selects the node with minimum f = g + h instead of using the first or last item in the open list.
The interface adds controls for object size, legal action sets, heuristic functions, and connected-state visualization.

6:00 Four- versus Eight-Directional Movement and Object Sizes

Four-directional movement uses the cardinal actions from Assignment 1, while eight-directional movement adds diagonal actions.
Changing object size from 1x1 to 2x2 or 3x3 can invalidate narrow corridors and force A* to choose longer routes.
The assignment tests object sizes 1, 2, and 3, so collision and boundary logic must work for all three dimensions.

9:00 Selectable Heuristics and Connected-State Visualization

The interface provides zero, four-directional Manhattan, eight-directional diagonal Manhattan, and Euclidean distance heuristics.
Holding the right mouse button highlights states reachable from the selected state for the current object size.
Bidirectional search appears in the interface for COMP 6980 but is excluded from COMP 3200, the assignment, and the exam.

12:00 Using Zero Heuristic to Debug A*

Setting h = 0 changes A* into uniform-cost search because f becomes g.
Dave Churchill recommends testing the search algorithm with the zero heuristic before implementing other heuristic functions.
If zero-heuristic tests fail, the defect is likely in A*, node generation, or action legality rather than in heuristic calculations.

14:00 A* Node Data and Variable Action Costs

Each node stores its x-y state, generating action, parent, g-cost, h-value, and derived f-value.
A child node's g-cost equals the parent's g-cost plus the selected action cost, allowing the goal node to report path cost directly.
Cardinal actions cost 100 and diagonal actions cost 141, so breadth-first search is no longer guaranteed to find minimum-cost paths.

19:00 Why Breadth-First Search Is Not Optimal with Diagonals

Breadth-first search minimizes the number of actions, which only guarantees optimal cost when every action has equal cost.
A two-step cardinal route can cost 200, while an alternative up-right then up-left route can cost 282 despite reaching the same location.
A* and uniform-cost search are required to account for the 100-versus-141 action-cost distinction.

22:00 Collision Rules for 1x1, 2x2, and 3x3 Objects

An object can occupy a state only when every underlying map tile has the same color and the entire object remains inside the map.
The state coordinate represents the object's top-left corner, including for 2x2 objects that have no unique center tile.
The canFit function can check every tile against the top-left tile; equality transitivity eliminates the need for pairwise comparisons.

26:00 Diagonal Movement Cannot Jump Over Obstacles

A diagonal move is illegal when the object would slide across or overlap a tile of another color during the movement.
For larger objects, a destination can appear to match the source color while still being illegal because part of the object crosses an obstacle.
A 2x2 object may need to travel around a passage that a 1x1 object can cross diagonally.

30:00 Deriving Diagonal Legality from Cardinal Actions

A diagonal action is legal only when both corresponding cardinal actions are legal, preventing corner-cutting and obstacle jumping.
For example, up-right requires both up-then-right and right-then-up movement to remain valid for the object size.
This rule converts a difficult geometric sliding test into a small set of Boolean checks.

33:00 A* Path Costs and Legal Route Geometry

A path cost is the sum of action costs, such as 100 for a cardinal move and 141 for a diagonal move.
The g-cost sequence in the example accumulates values such as 100, 741, 841, and 941 as the search progresses.
Apparently shortest diagonal routes can be illegal when they cut across obstacle corners; A* must use the legal-action rules rather than visual straight-line distance.

36:00 Implementing the Four Assignment Heuristics

Euclidean distance uses the Pythagorean formula based on the current x-y position and the goal x-y position.
Four-directional Manhattan distance is 100 times the sum of the absolute x and y differences.
Eight-directional diagonal Manhattan distance uses 141 times the smaller coordinate difference plus 100 times the remaining difference; zero returns 0.
Four-directional Manhattan is not admissible for eight-directional movement, although it is appropriate for four-directional movement.

40:00 Connectivity and Connected Sectors

Two states are connected for object size s when at least one legal path exists between them, regardless of path length.
Connectivity changes with object size because a 3x3 object may not fit through a passage that accommodates a 1x1 or 2x2 object.
Connectivity is transitive: if A connects to B and B connects to C, A is connected to C even without computing the shortest route.

44:00 Precomputing Connectivity with Cardinal BFS

The connected-sector algorithm scans the grid and starts a cardinal breadth-first search whenever it finds an unassigned state where the object fits.
Every reachable state receives the same sector number, allowing connectivity queries to compare two stored values in constant time.
A state that remains sector 0 represents a location where the selected object size cannot fit.

50:00 Multi-Size Sector Grids and Reusing Visited Data

Because computeSectors runs when the algorithm is initialized rather than whenever the UI size changes, it must compute sectors for sizes 1, 2, and 3 in advance.
The recommended representation is a three-dimensional array indexed by x, y, and object size, with an optional unused index 0.
The sector grid itself acts as a closed-list marker: zero means unvisited, while any nonzero sector number means the cell has already been classified.

58:00 Precomputed Sector and Legal-Action Optimizations

Once sectors are computed, a nonzero sector value proves that an object fits at a location, avoiding repeated checks of all underlying tiles.
Cardinal action legality can be tested by comparing the source and adjacent destination sector numbers.
For diagonal actions, three connectivity checks are sufficient because transitivity makes the fourth check redundant.

1:04:00 Closed Lists, Priority Queues, and A* Tie-Breaking

A Boolean 2D grid can replace an array-based closed list, providing constant-time membership checks.
A binary-heap priority queue removes the minimum-f node efficiently: insertion costs O(log n), while peeking at the minimum is O(1).
When many nodes share the same f-value, breaking ties toward lower h generally directs search toward the goal more efficiently than choosing randomly or favoring lower g.

1:10:00 Recommended JavaScript Implementation Order

Dave Churchill recommends implementing the open and closed lists first, then canFit, computeSectors, isConnected, and a separate manual legality function for sector construction.
Start search and search iteration largely reuse Assignment 1, with getMinF replacing getFirst or getLast.
The manual legality function is needed during sector BFS, while the optimized sector-based legality function is used during normal A* expansion.

1:18:00 Testing Heuristics, Action Arrays, and Object Size

Test A* with h = 0 first and verify that expansion spreads outward in a uniform-cost-search pattern.
Then test zero, eight-directional Manhattan, and Euclidean heuristics; four-directional Manhattan should not be expected to pass for eight-directional movement.
Expansion should iterate through config.actions by index so the corresponding config.actionCosts entry is available for every action.

1:25:00 Optional Binary Heap Integration and Final Assignment Checklist

The supplied BinaryHeap supports push, peek, and pop, and can be initialized with a scoring function such as node.f.
The Node class must calculate f from g and h, while the search object tracks the active size and a maximum object size of 3.
Bidirectional-search code can be ignored for COMP 3200; remaining issues should be reported to Dave Churchill through office hours, email, Discord, or D2L corrections.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.