Package jpa.tools.swing

Class PathFinder

java.lang.Object

jpa.tools.swing.PathFinder

public class PathFinder
extends java.lang.Object

A* Algorithm to find rectilinear path through a Maze.

Author:

Pinaki Poddar

Constructor Summary

Constructors

Constructor	Description
PathFinder(Maze maze)

Method Summary

Modifier and Type	Method	Description
java.util.List<java.awt.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 java.util.List<java.awt.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, ....