summaryrefslogtreecommitdiff
path: root/digital/avr/modules/path/path.txt
blob: 3868ea775609dc58009b2e27801e21cd6c811e80 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
=====================
 Path finding module
=====================
:Author: Nicolas Schodet

Introduction
============

This module will find a path for a mobile point between obstacles on a
rectangular area.

Obstacles are represented as circles in which the mobile can not enter.  The
mobile point does not have a size, therefore, obstacles must be larger by the
real mobile radius, and the area on which the mobile evolves should be
shrunken by this same radius.

The module can also handle obstacles life time, to make them disappear after a
defined time.

Usage
=====

First initialise the module with the area border (shrunken by the mobile
radius) using ``path_init``.

You can place obstacles using the ``path_obstacle`` function.  Give it the
obstacle index, its position and radius, its factor and its life time.  Use a
life time of PATH_OBSTACLE_VALID_ALWAYS for infinite duration.  Call
``path_decay`` regularly to make obstacles disappear after the given delay.

If factor is not 0 (2 or more), the obstacle can be entered, but it will cost
more to do it.  This can be used to mark an area which should be avoided, but
might be entered if other paths are too long or inexistent.

You can also set the source and destination position using the
``path_endpoints`` function.

Once you want to compute a path, call ``path_update``.  It will use the
currently set positions and obstacles to compute the path.  Once the update is
done, you can call ``path_get_next`` to get the first point of the found path.
If no path was found, this function returns 0.

This interface only gives you the first point of the path because it is
assumed that the path will not be up to date any more once the mobile arrives
at the first point.  This will change in the future.

Sometime, the source position is located inside an obstacle, for example
because we were too pessimistic about its size.  In this case, the algorithm
will not find any path.  It can be directed to find a path anyway using the
``path_escape`` function.  The factor determines the will to escape quickly
from the obstacle.  If it is 1, the obstacle is completely ignored, bigger
factors will make the algorithm find shorter path inside the obstacle.

When the path is updated, a user callback can be called by the path module to
report the found path.  It receives the list of points of the path and the
list of obstacles.  The callback is defined in the ``avrconfig.h`` file.

The number of possible obstacles and the number of points per obstacle used in
the algorithm are defined at compile time.

Borders are used to eliminate path points outside the area.  They are ignored
for the source and destination points.  This is done on purpose, as it would
not be convenient to forbid any path computation as long as the mobile is too
close from the area borders.

How does it work?
=================

The base of the path finding algorithm is the Dijstra algorithm.  This
algorithm is able to find the shortest path between two nodes in a graph,
taking into account arc weight.

To be continued...

API
===

.. include:: path.exd