Implementation of Dijkstra's algorithm and A* algorithm on a grid ----------------------GETTING STARTED---------------------- 1. Toggle `1` for NORMAL tiles, `2` for BLOCKED tiles, `3` to change START position, `4` to change END position. Mouse click on the grid to place new tile. 2. Toggle `d` for DIJKSTRA algorithm, `a` for A* algorithm. `SPACE` to run pathfinding 3. Play around with different board settings ------------------------------------------------------------ ------------------------CONTROLS------------------------ - space: run pathfinding algorithm - mouse click: place tile - 1: Change place tile type to NORMAL - 2: Change place tile type to BLOCK - 3: Change place tile type to START - 4: Change place tile type to END - 5: Change place tile type to WATER (cost 10 tile) - d: Change pathfinding algorithm to DIJKSTRA - a: Change pathfinding algorithm to A* -c: Change number of rows and columns (NUM_ROWS*NUM_COLUMNS should be LESS THAN 300 since that is the maximum number of clones allowed in a Scratch program) ------------------------------------------------------------ ------------------------NOTES----------------------- - Each node has a travel cost of 1 unless stated otherwise in `CONTROLS` - Dijkstra's algorithm is essentially a special case of A* with heuristic distance set to 0 - A* heuristic distance used in this implementation is Manhattan distance from END node ------------------------------------------------------------
https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
