Path planer internal functions

#define	SQRT2   1.41421356
#define	WALL_COST   1000
	Cost fo jumping a wall.
GraphMapCell	graph [MAP_HEIGHT][MAP_WIDTH]
void	pushNodeInOrder (NodeQueue *q, int x, int y)
float	cFunction (int x1, int y1, int x2, int y2)
#define	DBG   printf
#define	ABS_VAL(x)   ((x > 0.0)?(x):(-x))
#define	POW(x)   (x*x)
#define	PATH_ERROR   0.09
PathPoint *	newPathPoint (PathPoint *last, float x, float y)
void	calc_line (float x1, float y1, float x2, float y2, Line *l)
float	calc_dist (Line *l, float x, float y)
int	path_simplifier (double *path, int nbpoints, PathPoint *first_point, double *angle)

---

Detailed Description

Path Planer Architecture

PathPlaner is composed of three sublibraries or modules:

• aalgorithm.c : is the implementation of A* Algorithm. More details in aalgorithm().
• path_simplifier.c : The result path of A* is a set of discrete cells (or pixels) that should be simplify. More details in path_simplifier().
• pathqueue.c : It is an implementation of a points queue used by the others modules.

---

Define Documentation

#define PATH_ERROR   0.09

Max error for the path simplifier

Definition at line 20 of file path_simplifier.c.

Referenced by path_simplifier().

#define SQRT2   1.41421356

Root square of two.

Definition at line 17 of file aalgorithm.c.

Referenced by calculateCost(), and cFunction().

#define WALL_COST   1000

Cost fo jumping a wall.

Definition at line 18 of file aalgorithm.c.

---

Function Documentation

float calc_dist	(	Line *	l,
		float	x,
		float	y
	)

Calc the distance between a line and a point

Parameters:

	l	A pointer to line parameters
	x	Coordonate X of the point
	y	Coordonate Y of the point

Returns:

Cross cost

If it is a hotizontal line, the distance is the difference between y coordonate and b parameter.

If it is a vertical line, the distance is the difference between x coordonate and b parameter.

If it is a oblicuous line, the distance is .

Definition at line 77 of file path_simplifier.c.

References _Line::a1, _Line::a2, _Line::b, and POW.

Referenced by path_simplifier().

Here is the caller graph for this function:

void calc_line	(	float	x1,
		float	y1,
		float	x2,
		float	y2,
		Line *	l
	)

Calc line parameters from two points

Parameters:

	x1	Coordonate X of the first point
	y1	Coordonate Y of the first point
	x2	Coordonate X of the second point
	y2	Coordonate Y of the second point
	l	A pointer to line parameters

Returns parameters of a line : a1 * x + a2 * y = b

Definition at line 48 of file path_simplifier.c.

References _Line::a1, _Line::a2, and _Line::b.

Referenced by path_simplifier().

Here is the caller graph for this function:

float cFunction	(	int	x1,
		int	y1,
		int	x2,
		int	y2
	)

Calculates the lenght of edge connecting two points

Parameters:

	x1	Coordonate X of the first cell
	y1	Coordonate Y of the first cell
	x2	Coordonate X of the second cell
	y2	Coordonate Y of the second cell

Returns:

Lenght of edge

Definition at line 182 of file aalgorithm.c.

References ShmapIsFreeCell(), SQRT2, and WALL_COST.

Referenced by aAlgorithm().

Here is the call graph for this function:

Here is the caller graph for this function:

PathPoint* newPathPoint	(	PathPoint *	last,
		float	x,
		float	y
	)

Put the REAL coordonates (X,Y) in a list of points

Parameters:

	last	Last point of the points list
	x	Coordonate X of the first cell
	y	Coordonate Y of the first cell

Returns:

A pointer to allocated memory

Definition at line 30 of file path_simplifier.c.

Referenced by path_simplifier().

Here is the caller graph for this function:

int path_simplifier	(	double *	path,
		int	nbpoints,
		PathPoint *	first_point,
		double *	angle
	)

Simplify a given path

Parameters:

	path	A pointer to a list of points of the original path
	nbpoints	Number of points of the original path
	first_point	[out] A pointer to the list of points of simplest path
	angle	[out] Angle of the last line

Returns:

Number of point of the simplest path

This is an algorithm who tries to simplify the path given by A* Algorithm (

See also:

aalgorithm()). Basically, the algorithm works that follows: # Takes two points of the original path. # Calculates the line between them. # Calculates the distance between this line and all the points of the original path. If this distance is acceptable (less than PATH_ERROR), the line is part of the simply path. If not, goes to 1 taking two closer points . # The process finish when the last point is the final point.

In pseudo-code:

 first_index = 0;
 last_index = nbpoints;
 step = (last_index - first_index)/2
 WHILE (the first index less than nbpoints )
        Calc the line
        FOR all the points between path[first_index] and path[last_index]
                calc the distance betwen the point and the line
                Take the max_error
        END FOR
        IF max_error less than ACCEPTABLE_ERROR THEN
                The line is part of the simple path.
                first_index = last_index
                last_index = last_index + step
        ELSE reduce last_index
                step = (last_index - first_index)/2
                last_index = last_index - step;
        END IF
 END WHILE

Definition at line 106 of file path_simplifier.c.

Referenced by path_planner().

Here is the caller graph for this function:

void pushNodeInOrder	(	NodeQueue *	q,
		int	x,
		int	y
	)

Push in the queue the cell (x,y) order by heuristic value of the cell

Parameters:

	q	Coordonate X of the first cell
	x	Coordonate X of a cell
	y	Coordonate Y of a cell

Definition at line 314 of file aalgorithm.c.

References _GraphMapCell::f, _NodeQueue::first, graph, _NodeQueue::last, _Node::next, queueIsEmpty(), _Node::x, and _Node::y.

Referenced by aAlgorithm().

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

GraphMapCell graph[MAP_HEIGHT][MAP_WIDTH]

Graph structure used in A*.

Definition at line 20 of file aalgorithm.c.

Referenced by aAlgorithm(), calculateMapHeuristic(), getPathLength(), initGraphStructure(), and pushNodeInOrder().

---