PathFinders
A basic implementation of common path finding (graph) algorithms.
- A-Star (A*) shortest path finding algorithm.
- Bredth First Search algorithm (BFS)
- Depth First Search algorithm (DFS)
How to run
- 1. Launch model.java
- 2. Your only person (in red) is at grid coordinate (5,5)
- 3. Person can only move in cardinal direction (NESW)
- 4. Left click to set the destination
- 5. Right click to set a building (in blue) which appears as your obstacle
- 6. Upon reaching location, program will terminate (as of V1.0)
- 1. Check if at point
- 1.1 If so return the destination
- 2. If adjacent to block
- 2.1 Return a path with starting and ending point
- 3. If not adjacent or at desination
- 3.1 Set up openlist & closed list
- 3.1.1 Open list is the set of all outer adjacent blocks
- 3.1.2 Closed list if the set of all the blocks you have visited and set adjacent into the open list
- 3.2 Put initial location into closed list
- 3.3 While not at desination determine adjacent clear blocks (no buildings)
- 3.4 For all blocks, assigns g, h, f values for that block
- 3.4.1 G value is the distance from start to current block (1 more than the g value of parent)
- 3.4.2 H value is a heuristic value (guess at distance <= actual distance) - Used manhatten distance
- 3.4.3 F Value is the sum of the g & h values
- 3.5 Add any adjacent blocks that aren't in open list into it
- 3.5.1 Select the closest block (smallest f value) as the your current block
- 3.6 Continue steps 3.3 until case 2
- 3.6.1 At this point, you are adjacent, so add that adjacent point to path
- 3.6.2 Traverse from final point to no parent , adding to path at all points
Notable help: Pathfinding Tutorial