jpa.tools.swing

Class PathFinder

java.lang.Object

jpa.tools.swing.PathFinder

public class PathFinder
extends Object

A* Algorithm to find rectilinear path through a Maze.

Author:

Pinaki Poddar

Constructor Summary

Constructors

Constructor and Description
PathFinder(Maze maze)

Method Summary

Modifier and Type	Method and Description
List<Point>	findPath(int x1, int y1, int x2, int y2) A* algorithm to find a path through a maze.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PathFinder

public PathFinder(Maze maze)

Method Detail

findPath

public List<Point> findPath(int x1,
                            int y1,
                            int x2,
                            int y2)

A* algorithm to find a path through a maze. The algorithm follows these steps

Add the starting square (or node) to the open list. Repeat the following: Current node is the lowest cost square on the open list Move current node to the closed list. For each of adjacent neighbor n to this current square If n is not reachable or if n is on the closed list, ignore. Otherwise do the following. If n is not on the open list, add it to the open list. Make the current square the parent of n. Record the cost of n. If n is on the open list already, replace if this path to n is lower cost. until the target node is added to the closed list, or fail to find the target square i.e. the open list is empty.

Parameters:

x1 - the x-coordinate of the starting point

y1 - the y-coordinate of the starting point

x2 - the x-coordinate of the target point

y2 - the y-coordinate of the target point

Returns:

a array of points in the form of x1,y1, x2,y2, ....