# Search Algorithms

A collection of search algorithms from Russel & Norvig's Artificial Intelligence: A Modern Approach, implemented early 2020 by Jayden Milne (@jaydenmilne)

## Instructions

1. Left click, or tap quickly, on a non-wall cell to place a tile.

Left clicking and dragging on a wall cell will remove walls.

2. Right click once to place the start node, right click again to place the goal node, or long tap.
3. Select a search strategy and heuristic
4. Adjust the search speed as desired
5. Press the "Run" button

While the search is running, press the play/pause button () to pause the search, and then use the step button () to advance the search one state at a time.

## Colors

• Start Node
• Goal Node
• Wall Node
• Node on Solution Path
• Node on Frontier
• Explored Node

## FAQ

### Why?

I started working on this for fun, but then realized it could count as a class project, so I put some extra effort.

I hadn't had much experience with some new Javascript features (canvas, async/await, classes), and this seemed like a good chance to learn.

### What are "intermediate states"?

A rough estimate of how many steps were required to find the solution. For example, for depth-first searches, it is the number of recursive calls. For breadth-first searches, it is the number of iterations of the main loop.

### It's broken on {mobile browser}.

The most I did was implement touch events, you should feel lucky you even got that much.

## Child States

By default algorithms will only consider 4-connected neighbors (up, down, left, right).

If selected, the "8-connected checkbox" will consider diagonal moves as well.

### 4-connected Search Order:

 4 3 2 1

### 8-connected Search Order:

 1 4 6 2 7 3 5 8