Overview

Assignment 2A of COS30019 Introduction to AI, done in a team of four. The task is route finding on coordinate-based graphs: the program reads a map, searches from the start node to one of the goal nodes with the chosen algorithm, and prints the path, its cost and how many nodes were created. We built a command-line tool, a test suite, and a Pygame visualizer that shows how each algorithm explores a map.

At a glance

Course

COS30019 Introduction to AI

Language

Python

Algorithms

BFS, DFS, GBFS, A*, Dijkstra (CUS1), IDA* (CUS2)

Heuristic

Straight-line (Euclidean) distance

Maps

10 maps, plus one extra test map

Tests

pytest, 125 cases

Command-line path

1. Map file
2. Parser
3. Algorithm from the registry
4. SearchResult
5. Printed path and cost

What it shows

• One interface for every algorithm. Each algorithm is a subclass of an abstract GraphSearch with a single search() method that returns a SearchResult. The command line looks the class up by name in a registry.
• Separated responsibilities. Reading the map file and printing the result are standalone services, so the algorithms contain no input or output code.
• Frontier choices. BFS uses a queue and DFS a stack. GBFS and A* use a priority queue, and A* breaks ties by insertion order and then by the smaller node ID, as the brief requires.
• Two custom algorithms. Dijkstra finds the cheapest path using cost alone. IDA* repeats depth-limited searches with a growing f-cost limit, so it keeps A* quality with little memory.
• Tested on ten maps. Every algorithm is checked on each map for the expected path, cost and node count, which kept the six implementations consistent.
• Built to teach. Running algorithms side by side on the same map makes it easy to see why they expand nodes in different orders.

What I built

• The project skeleton: the folder structure, the abstract search class and the class diagram, so everyone could write their algorithm against the same interface.
• The SearchResult return type that every algorithm uses.
• The Pygame visualizer, on my own: choose a map, pick one or more algorithms and run them side by side with play, pause, step forward and back, and a speed slider.
• In the visualizer, the cost g(n), the heuristic h(n) and their sum f(n) can be shown on each node. Nodes are colour-coded as start, goal, frontier, visited and current.
• A resizable window that starts in fullscreen, a map picker, and the metrics panel.
• Tests for BFS and DFS on the first maps, and tests for the map parser.
• The README and the final PDF.

How it works

1. The map file lists the start node, the goal node or nodes, each node with its x and y position, and the directed edges with their costs.
2. The parser builds a graph, and the registry returns the algorithm class for a key such as BFS, DFS, GBFS, AS, CUS1 or CUS2.
3. The algorithm searches and returns a SearchResult with the path, the path cost and the number of nodes created.
4. The visualizer reuses the same maps. It runs each chosen algorithm one expansion at a time, so you can step through, go back, and compare them.

Run it

python search.py maps/Map1.txt AS

> Starting Node: 1
> Destination Node: [8]
> Number of nodes created: 10
> Path: 1 -> 4 -> 2 -> 5 -> 7 -> 8
> Path Cost: 30

python visualize.py
pytest