Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 54 lines (34 sloc) 1.969 kb
ce6b89e @adamd Added travis build status to readme
authored
1 [![Build Status](https://secure.travis-ci.org/adamd/pathfinder.png?branch=master)](http://travis-ci.org/adamd/pathfinder)
bb9b2ec @adamd first commit
authored
2 PathFinder for Java
3 ===================
4
5 PathFinder is a project for finding paths in a 2-dimensional array from one point to another,
6 for example, finding a path for a character in a 2D game.
7 It uses interfaces to make it reusable in many different contexts.
8
9 The 2D-grid can be of any size.
10 In this grid only four directions of movement are possible: up, down, left, right.
11
12 There are several interfaces and three implementations of path-finders (AntPathFinder is recommended).
13
14 Running the Example
15 -------------------
16
17 If you just want to see it in action, type the following:
18
19 java com.adamldavis.pathfinder.PathPanel
20
21 Resize the window. Left click to create obstacles. Then right click and drag to find a path.
22
23 Usage
24 -----
25
26 First you need to implement the PathGrid interface or use SimplePathGrid which has a 2D array of booleans.
27
28 PathGrid grid = new SimplePathGrid(width, height);
29
30 Then you need to create a pathFinder and use it.
31
32 PathFinder finder = new AntPathFinder(200);
33 int[] path = finder.findPath(grid, x1, y1, x2, y2);
34
35 The path array is a series of numbers representing directions (0 = up, 1 = right, 2 = down, 3 = left).
36 The AntPathFinder will very quickly determine a path to the target using an optimized depth-first search.
37 It does not necessarily find the shortest path, but in most cases it does.
38
39
40 Known Issues
41 -------------
42 CrudePathFinder attempts to do an exhaustive search to find the shortest path but is limited to a certain number of iterations.
43 So it might take a long time to complete.
44
45 The other path finder, RandomPathFinder, breaks a path in half randomly, then delegates to CrudePathFinder.
46
47 I wrote the bulk of this code a long time ago, so please don't judge me by it.
48
49 License
50 -------
51
52 Copyright 2012, Adam L. Davis. All rights reserved.
53 Made Available for use under a BSD-style license. See LICENSE
Something went wrong with that request. Please try again.