Visualizing Search Algorithms

This is an old project visualizing several search algorithms, such as: A-Star, Breadth-First-Search (BFS), Bellman-Ford, Depth-First-Search (DFS), Dijkstra, Greedy Best-First-Search

and also Kruskal and Prim for maze building with minimum spanning trees. You can draw obstacles, set start and end point and the program will visualize the search for you. Please read the section 'Usage' down below as the lock step is not that intuitive. This project was mainly done to learn a bit of C++. You could basically use this as a pixel art drawing tool. Draw some nice images and run the search algorithm through it.

Getting Started

Prerequisites

You need the SFML graphics library and cmake to build it.

On an arch based OS you can get the SFML library with:

sudo pacman -Sy sfml.

On ubuntu: libsfml-dev

sudo apt-get install libsfml-dev

Installing

1. clone or download the repo

git clone git@github.com:Laeri/search_alg.git

2. enter the folder and build it with cmake and make

cmake .

make

3. run the binary

bin/search_alg

Usage

1. Use left mouse to draw obstacles (blue)
2. Choose algorithm by pressing Left Arrow or Right Arrow on keyboard. You can cycle through several algorithms.
3. Hold ctrl, first and second click with left mouse sets the start and end point.
4. The search algorithm will immediately connect both points if possible.
5. If you want to show the steps manually, see down below (Lock Step Mode).
6. Reset everything with r, or reset and keep obstacles with t.
7. Press m or n to draw a maze (deletes obstacles).

Lock Step Mode

l - lock serach algorithm, you can set start and end point and it will not try to connect them immediately p - set to manual step, you can visualize every step of the algorithm u - unlock, manual step is set, it does just one step. Press repeatedly to show progress.

1. Choose Algorithm (by pressing Left, Right)
2. Draw obstacles
3. Lock by pressing l
4. Set manual stepping mode by pressing p
5. Step through the algorithm by repeatedly pressing u, each key press does one step.
6. Press p to get out of manual mode
7. Unlock with u

Keybindings

s - starts or stops the tree expansion

r - reset everything

t - reset only start and end point, keep obstacles

left mouse - click to create obstacles

ctrl + left mouse - create start and end point

Right Arrow or Left - cycle through search algorithms

Escape or q - quit

Mazes

m - create a maze (deletes other objects)

k - build a minimum spanning tree with Kruskal

License

This project is licensed under the MIT License - see the LICENSE.md file for details.