PathFinders

A basic implementation of common path finding (graph) algorithms.

This includes:

A-Star (A*) shortest path finding algorithm.
Bredth First Search algorithm (BFS)
Depth First Search algorithm (DFS)

You have actors (people) who are trying to get from point A-B. They need a path (a queue of points) to traverse. Have static methods: Model.getDeterminedPath() will give you a path to move to.

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)

------------- Algorithm basics

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

tmiles/PathFinders

PathFinders