Skip to content

Ohohcakester/Any-Angle-Pathfinding

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

497 Commits

predefinedgrids

predefinedgrids

 
 

pyscripts

pyscripts

 
 

src

src

 
 

.classpath

.classpath

 
 

.gitignore

.gitignore

 
 

.project

.project

 
 

LICENSE

LICENSE

 
 

README.md

README.md

 
 

build.xml

build.xml

 
 

Repository files navigation

Any-Angle Pathfinding

A collection of algorithms used for Any-Angle Pathfinding with visualisations.

Some useful papers that include comparisons of Any-Angle Pathfinding algorithms:

  1. https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11295
  2. https://aaai.org/ocs/index.php/SOCS/SOCS17/paper/view/15790

Licensing of Source Code

The implementation of Anya 2016, from here, and JGraphT, from here, are licensed under their respective licenses.

Everything else is unlicensed.

Features

  1. Visualisations of the implemented algorithms:

  2. Testing functions that test computed path lengths and running times.

  3. Map Generators to generate grid maps:

    • DefaultGenerator
      • Generates random grid maps. A random seed can be set for determinstic map generation.
    • AutomataGenerator
    • MazeMapGenerator
      • Generates random maze-maps using a modification of Kruskal's algorithm.
    • TiledMapGenerator
      • Generates maps from tiling a set of existing maps
    • UpscaledMapGenerator
      • Generates maps from upscaling an existing map
      • Post-processing (smoothing) is done after upscaling with cellular automata iterations
    • AffineMapTransformation
      • Applies affine transformations (scaling/rotation/shear) to an existing map to generate new maps.

  4. Maps can also be imported from files. Refer to the uiandio/GraphImporter.java comments for details on how to create a grid file.

Information

Language: Java 8 Required

Visualisation: Java Swing

Dependencies: JUnit (not required if using ant build script)

Pre-Generated Maps

If you want to load existing pre-generated maps, the maps can be downloaded here:

To use them, unzip them and place the mazedata/ and originalbenchmarks/ directories in the root of the repository.

Larger Maps

The larger maps used for the comparison in these slides and this paper are stored only as code in StoredTestMazes (they are loaded by running the respective generation code). The exact maps used for the tests are found in AlgoTest. The large maps come from these four test sets: "scaledmazes", "tiledmazes", "automatadcmazes", "mazemaps".

I have also pre-generated the above maps for convenience. They are available here:

Build using Apache Ant

To build and run the code, run the following from the base directory (where build.xml is).

ant
java -jar dist/AAP.jar -Xmx4096m

To clean up generated files from the build script,

ant clean

How to use

The main class is in AnyAnglePathfinding.java.

Setting the choice variable in main() chooses which component of the program is to be run. More details of each component are given in the Components section.

  • [0] Visualisation: Generates an interactive visualisation of the algorithm.
  • [1] AlgoTest: Conducts running-time and path-length tests on the algorithms.
  • [2] Experiment: For other tests for the algorithms. (e.g. checking optimality of an algorithm)
  • [3] TestDataGenerator: Generate test data for the /mazedata directory.
  • [4] GridGraphVisualiser: Generates a visualisation of the graph. A handy tool for choosing start and end point coordinates.
  • [5] TextOutputVisualiser: Generates an interactive visualisation of the algorithm from a string.
  • [6] AlgoTest.runWithArgs: Run tests using command line arguments

In general, the maze to be used is configured in loadMaze(), and the algorithm to be run is configured in setDefaultAlgoFunction(), by setting the choice variable.

  • Some important Mazes in loadMaze(): (you can change the parameters in the corresponding case definition)
    • choice 0: Random mazes
    • choice 1: Random mazes with specified seeds
    • choice 58: Upscaled maps
    • choice 59: Tiled maps
    • choice 60: Automata Maps (Dynamic Cutoff)
    • choice 63: Affine transformation of existing maps
    • choice 66: Maze maps

Components

Components I use most often:

  • [0] Visualisation
  • [4] GridGraphVisualiser
  • [6] AlgoTest.runWithArgs

[0] Visualisation

Use this to generate a trace of the algorithm's search tree.

The initial view will be the completed path in blue. Step through the frames to view the algorithm's trace. Generally, blue circles are explored nodes, red lines are parent pointers. The start point and goal points are marked with circles.

Left/Right: Move backward/forward one step at a time.

PgUp/PgDown: Move backward/forward multiple steps at a time.

Up/Down: Move backward/forward one step at a time, will not loop around to the first frame from the last frame.

A/D and S/W: Move backward/forward multiple steps at a time, will not loop around to the first frame from the last frame.

O: Moves a step forward and takes a screenshot at the same time.

P: Same as O, but does not loop around to the first frame from the last frame.

L: Same as P, but jumps multiple steps at a time.

[1] AlgoTest

Use this to test algorithm runtimes/pathlength using the test suite defined in the code

The test to be run is specified in the function AlgoTest.run() in main/Algotest.java. The test parameters can be edited there.

String[] algoNames = new String[]{
    // Define algorithms to test here
    "Anya16",
    "BasicThetaStar",
};

String[] mapSetNames = new String[]{
    // Define the map sets to test on here
    "benchmarks",
    "automatadcmazes",
};

The list of algorithm names can be found in AlgoTest.getAlgo() and the list of map sets can be found in AlgoTest.testSequence.

The following map sets are used for the tests in these slides:

  • benchmarks
  • benchmarksrandom
  • scaledmazes
  • tiledmazes
  • automatadcmazes
  • mazemaps

[2] Experiment

Used to run various experiments on the algorithm. Check Experiment.run() for details

The Experiment.run() function has a bunch of commented-out experiments. I usually just define these on the fly as I need to test certain properties of certain algorithms.

Examples of some more notable experiments:

  • testAlgorithmOptimality(): Compares an algorithm's computed path length against a known optimal algorithm over an infinite sequence of randomly generated test cases. Very useful for quickly finding example test cases where an algorithm is suboptimal.

[3] TestDataGenerator

Used to generate/export grid maps to external files

I don't use this very frequently. (after all, I only need to generate test data once)

[4] GridGraphVisualiser

Used to preview a map

A very useful tool. It generates a visualisation of the currently-selected grid map. Press any unused key to print the list of hotkeys to the console. (e.g. arrow keys)

Use the left/right mouse buttons to place the start/goal points (respectively).

(Current) list of hotkeys:

ESC: Close the window.
9: Generates the path file from the currently selected points.
0: Generates the maze analysis for the maze.
A: Prints the maze analysis for the maze.
P: Prints the path analysis for the current selected path.
S: Generates a .map and a .scen file from the maze.
Z: Switch mode: Automatically display path between points.
X: Switch mode: Automatically display search tree between points.
C: Switch mode: Disable path computation.
V: Hold down for real-time pathfinding to mouse location

A common use of this tool is to find a good pair of start/goal points to use in [0] Visualisation. My usual workflow:

  1. Select a map in AnyAnglePathfinding.loadMaze() by setting the choice variable
  2. Run GridGraphVisualiser to generate a preview of the map
  3. Press Z to automatically display the shortest path between the start/goal points (powered by ENLSVGs)
  4. Use left/right mouse buttons to select a good pair of start/goal points.
  5. Press P to print the path analysis + coordinates of the two points.
  6. Copy down these coordinates and use them for [0] Visualisation.

[5] TextOutputVisualisation

Used to generate an algorithm trace from a string

I use this to view algorithm traces of algorithms not implemented in this framework. (e.g. implemented in C++). To do so, I run the algorithm on a certain map, and insert print statements to print out the algorithm trace.

(e.g., when it explores (5,8) with parent (2,4), I print out "2 4 5 8"). One item is printed per line.

The trace is terminated with a # character.

The trace should be printed in chronological order for the visualisation to make sense.

Each line of the trace is sequence of integers, seperated by spaces.

The following formats can be used in the trace:

  • <x1> <y1> <x2> <y2>: Draws a line from (x1,y1) to (x2,y2)
  • <x> <y>: Draws a point at (x,y)
  • <y> <xLn> <xLd> <xRn> <xRd> <px> <py>: Generates a fractional horizontal interval on row y, from xLn/xLd (left) to xRn/xRd (right). Also draws lines ot the base point (px, py). Used to trace Anya.
  • <y> <xLn> <xLd> <xRn> <xRd>: Same as above, but without the base point.

(Note: These are defined in the function GridObjects.create())

[6] AlgoTest.runWithArgs

Similar to AlgoTest, but we run with test parameters from the command line instead.

The arguments are as follows:

  • java -jar dist/AAP.jar <algorithmName> <mapSetName> <testType> <outputDirectory>

Example bash script used for running tests:

runtest() {
java -jar dist/AAP.jar -Xmx4096m  "$@"
}

runtest Anya16 benchmarks default output_benchmarks
runtest BasicThetaStar benchmarks default output_benchmarks

runtest Anya16 benchmarksrandom default output_benchmarksrandom
runtest BasicThetaStar benchmarksrandom default output_benchmarksrandom

The list of algorithm names can be found in AlgoTest.getAlgo() and the list of map sets and test types can be found in AlgoTest.testSequence.

About

A collection of algorithms used for any-angle pathfinding with visualisations.

Topics

algorithm visualisation pathfinding pathfinding-algorithm grid-map

Resources

Readme

License

Unlicense license
Activity

Stars

147 stars

Watchers

7 watching

Forks

24 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages