NAME

path_finder - a terminal based A* path renderer

SYNOPSIS

$> path_finder                 # display default map
$> path_finder --map map_file  # use file as a map
$> path_finder 1.1  8.10       # find path

DESCRIPTION

path_finder is a simple terminal base program to display A* paths, it uses AI::Pathfinding::AStar. path_finder has a built-in map, but you can create your own, and options that let you control heuristics and display.

Apart from displaying the map and found paths (if any), it will also display the "path length/cost" for each leg, the number of visited cells as well as time spend computing the paths.

TARGET COORDINATES

You pass coordinates as x.y, you can pass a multiple route legs.

$> path_finder 1.1  8.10       # find path from [x=1, y=1] to [x=8, y=10]

$> path_finder 1.1  8.10 27.14 # as above plus leg [x=8, y=10] to [x=27, y=14]

COSTS

The A* path finding uses costs to determine which path is the best. The "opaque" cells have an infinite cost and are not even considered.

Orthogonal cost is 10 by default but can be changed

Diagonal costs is 140 but this version of b<path_finder> only does othogonal routing.

"Translucent" cost varies between 0 and 9, see option --translucent_cost.

"Extra_cost" can be assigned to cells aound 'opaque' cells, See options --keep_clear and --keep_clear_cost.

Default costs

orthogonal_cost = 40

diagonal_cost = 140

keep_clear_cost = 40

permeable_cost = 0-9 (if option --pcd is use otherwise OPAQUE)

Starting with costs

I recommend that you use these options to start with and look at the heatmap then play with the costs from there.

--orthogonal_cost 1 --keep_clear_cost 5

OPTIONS

--help # display this help

--map map_file # use user defined map file

The map_file contains ASCII character, space corresponds to a coordinate that can be used in the A* path, other characters represent "opaque" coordinates (but see option --permeable below)

                       .---.
          .---.        |   |
.---.     |   |        '---'
|   |     '---'  .---.
'---'            |   |
         .---.   '---'
         |   |
         '---'

--display_scanning # display the map scanning

Display the portion of the map scanned during the A* path finding

--scanning_sleep:i # pause during leg computation

To allow a better visualization effect, a short pause is used, the default is 1000, when multi legs paths are computed, smaller value gives shorter delay.

--pause # pause and wait for user input

Pause between each leg map scanning and each leg rendering, waits for "Enter" to be pressed.

--heatmap_all # show whole map heatmap

path_finder normally only displays the coordinates that have been searched by the A* algorithm, use this option to show a complete heatmap.

Note that a "pseudo" heatmap is displayed, a real heatmap would require multiple passes, the pseudo heatmap give a good enough visualisation. Time information is not relevant when this option is used as we spend more time looking at all the nodes then would be necessary to compute paths.

--no_map_display # do not display the map at all

Useful if you want to modify the code and output other type of data

--obstruct # multi leg path obstruct each other

When set this option makes the cells used in a path opaque rendering them unavailable for the next leg.

--orthogonal_cost :i # assign a cost to orthogonal moves

--diagonal_cost :i # assign a cost to diagonal moves

--keep_clear # assign a cost to cells close to opaque cells

This makes the path stay clear of opaque cells if possible. A* might still use cells that are close to opaque cells if there is no other path or the path cost including the extra cost to keep cleat is the cheapest.

--keep_clear_cost :i # cost assigned to cells close to opaque cells

--permeable_cost character=cost # class assigned to opaque cells

You can set a class on the command line, this lets you "go through walls".

A* will still try to find the most efficient path and so setting the class to a high value forces the algorithm to go through as few "walls" as possible.

As an example the default map has a vertical line consisting of 'I', you can assign a value to 'I' with --pc I=9.

Adding --pc 5=50 --pc 1=10 would also make those cells permeable, otherwise they will be opaque.

       1               .---.
       5  .---.        |   |
.---.  I  |   |        '---'
|   |  I  '---'  .-7-.
'---'  I         |   |
       I   .---. '-8-'
       5   |   |
       1   '---'

--permeable_cost_default

0-9 are normally OPAQUE, use this option to assign class 0 a zero cost, class 1 a cost of 1, ... unless the class is already assigned to with --permeable_cost option.

--obstruction:s

You can add obstructions on the map, they will be displayed in the heatmap, the format is:

x.y:value

The value is uses in the computation of the path cost and *may* change the path.

Use a positive value superior the orthogonal cost (10 by default) to see some effect.

A value of -1 makes the cell opaque.

A large negative value will act as a magnet and draw the path towards it.

All options:

help
map|m=s
heatmap_all|H
no_map_display
stats
json
pause|p
display_scanning|ds
obstruct
obstruction|o
keep_clear|kc
orthogonal_cost|oc:i
diagonal_cost|dc:i
keep_clear_cost|kcc:i
permeable_cost|pc:i
permeable_cost_default|pcd
XHK:f
YHK:f
HK:f

DEPENDENCIES

AI::Pathfinding::AStar is embedded in the program but you'll need to install Heap::Binomial.

MODULES/AUTHOR

https://metacpan.org/pod/AI::Pathfinding::AStar does the path finding.

path_finder is part of https://github.com/nkh/P5-App-Asciio where it is used to find the feasibility of automatic link routing.