COMP 3200 - Intro to Artificial Intelligence - Assignment 1 Tutorial

Overview

Dave Churchill explains how to implement COMP 3200 Assignment 1’s grid-search code in JavaScript, covering map access, open and closed lists, BFS/DFS iteration, legal actions, and path reconstruction. He also demonstrates practical testing with browser console logs and Firefox’s debugger, emphasizing that a faulty closed-list membership check can make search effectively unusable.

Key takeaways

Map integers 0, 1, and 2 are only UI color indices; legal movement depends on whether adjacent cells have equal environment values, not on interpreting them as terrain types.
The GUI expects open and closed visualization data as arrays of [x, y] states, so Node-based open lists need a conversion step that extracts coordinates.
BFS and DFS can share one search algorithm: select the first open-list element for BFS or the last for DFS, rather than duplicating the full iteration logic.
Every search termination path must set this.in progress to false; otherwise, the GUI continues calling search iteration and can produce millions of repeated executions.
A grid-based boolean closed list supports constant-time membership checks, while a faulty contains implementation can cause exponential revisitation and make a finite search effectively unusable.
Browser debugger breakpoints, variable inspection, and step controls provide a direct way to verify state changes and trace loops beyond what console logging alone can show.

Chapters

0:00 Reading Grid Values and Color Indices in environment.js

Map data in environment.js is stored as a one-dimensional array of integers that the UI renders as a two-dimensional grid.
The UI maps index 0 to gray, 1 to green, and 2 to blue; these colors are visual labels, not terrain types.
Use the environment get function with x and y coordinates to read a cell; legal movement requires the destination value to match the current cell.

4:40 Representing the Open List with a JavaScript Array

A JavaScript array can implement either a queue or stack for the search open list.
Initialize an instance field such as this.open with an empty array and use push(node) to add nodes.
Use shift() for get first, pop() for get last, and the array length to determine whether the list is empty.

8:00 Returning Open and Closed States for the GUI

The GUI’s open-list display expects an array of [x, y] states, even when the search open list stores Node objects.
Implement get states by looping through open nodes and collecting each node’s x and y coordinates into a new array.
A closed list that directly stores [x, y] states can return its array as-is; other data structures must convert their contents to that format.

14:13 Creating the Root Node and Initializing Search

start search receives start and goal coordinates, resets search data, and creates a root Node at the start location.
The Node constructor takes x, y, action, and parent; use null for the root’s nonexistent action and parent.
Add the root node to the open list so the search begins from the selected start state.
A faster closed-list option is a width-by-height grid of booleans, giving constant-time state membership checks.

19:59 Checking Legal Actions with Grid Coordinates

is legal action takes the current x and y plus a two-element action array containing the x and y movement offsets.
Compute the candidate next state by adding the action offsets to the current coordinates, then reject out-of-bounds destinations.
A move is legal when the destination’s environment value matches the current cell’s value; the specific color index does not matter.

23:35 Handling Search Failure and One Iteration at a Time

search iteration implements one pass through the search pseudocode and must stop doing work after the search is complete.
If the open list is empty, set the path cost to -1, clear the path, set in progress to false, and return.
The GUI repeatedly calls search iteration while in progress is true, so every terminal outcome must clear that flag.

28:30 Selecting BFS or DFS Nodes and Visualizing the Current Path

BFS and DFS should share the same search-iteration code; only node removal differs: get first for BFS and get last for DFS.
Avoid duplicating the entire algorithm inside separate BFS and DFS branches; select the retrieval operation at the point where a node is taken from open.
Assign the selected node to this.node if you want the GUI to draw its parent-pointer path in gray for visualization and debugging.

32:31 Checking Goals, Closed States, and Child Generation

The pseudocode’s node.state is not a Node field in this assignment; compare node.x and node.y with the goal coordinates.
When a goal is found, set the path and path cost, mark the search complete, and return rather than returning a solution value to the GUI.
If a selected state is already closed, return from this iteration; the pseudocode’s continue assumes a loop structure that this function does not use.
Choose one child-generation pattern: return a successor array for the caller to add, or add each child directly to open, but never do both.

37:27 Using Configured Actions Instead of Hard-Coded Directions

Loop over this.config.actions rather than writing separate legality checks for left, right, up, and down.
Assignment 1 locks the GUI to object size 1 and four-direction movement; the disabled controls preview options used in Assignment 2.
An index-based loop can pair each action with this.config.action costs in later assignments, where actions may have different costs.
For Assignment 1, every action costs 100, so path cost can be computed as path length multiplied by 100.

43:35 Avoiding Duplicate Open-List Insertions and Ignoring IDFS

The lecture notes show alternate expansion patterns, so check whether expand returns children or inserts them directly before adding anything to open.
Adding children inside expand and then adding the returned list again creates incorrect or duplicated open-list entries.
Assignment 1 requires BFS and DFS; the IDFS-related function remains in the skeleton only so the UI does not crash.

46:21 Testing Open-List Operations Through the GUI and Console

Build and test components incrementally, using start search as a convenient entry point because map clicks trigger it.
Console logging the start and goal coordinates and the open-list object can reveal whether the UI is calling search with valid states.
The UI may initially call start search with (-1, -1) values, and one click can set both start and goal to the same cell before a second click selects the other.
Check that adding one root node produces an open list with one Node object, then verify get first removes it; remove temporary logs before submitting.

55:30 Using Firefox Debugger Breakpoints and Step Controls

Firefox’s built-in JavaScript debugger can pause on exceptions and inspect program state without relying only on console output.
Set a breakpoint on an executable line, trigger the search through the GUI, and inspect variables by hovering over them.
Step over executes the current line, step in enters a called function such as the open-list constructor, step out exits the current function, and resume continues to the next breakpoint.
Inspect the open list before and after an insertion to confirm that the expected Node object was added.

1:01:01 Tracing Repeated Calls and Diagnosing Infinite Loops

A breakpoint inside the open-list add function can show when repeated calls insert duplicate nodes.
The GUI repeatedly invokes search iteration while this.in progress remains true; a function that never clears the flag can run millions of times.
Set a breakpoint inside search iteration and resume through successive stops to confirm whether the UI is repeatedly calling the same unfinished iteration.
A runaway browser tab can be difficult to stop, so open a fresh tab or restart Firefox to recover before continuing to debug.

1:04:43 Verifying Closed-List Membership Before Running Search

A broken closed-list contains function may never recognize visited states, causing search to revisit states and grow exponentially.
Test closed-list insertion and membership early—before running a full search—using start search as a trigger point.
The resulting runtime can be so large that a finite search appears to be an infinite loop.

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.