aalgorithm.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	_GraphMapCell
Typedefs
typedef struct _GraphMapCell	GraphMapCell
Functions
int	aAlgorithm (double xstart_real, double ystart_real, double xgoal_real, double ygoal_real, double **original_path)
void	calculateMapHeuristic (int xgoal, int ygoal)
float	calculateCost (int x1, int y1, int x2, int y2)
void	initGraphStructure (void)
int	getPathLength (int xstart, int ystart, int xgoal, int ygoal)
void	ShmapAllFreeSpace (void)

---

Detailed Description

Header file of aalgorithm.c

Author:

Jose Maria Martin Laguna <jmmartin@etud.insa-toulouse.fr>

Definition in file aalgorithm.h.

---

Typedef Documentation

typedef struct _GraphMapCell GraphMapCell

Information of a cell in A* Algorithm

Todo:

Maybe it is possible to simplify this structure.

---

Function Documentation

int aAlgorithm	(	double	xstart_real,
		double	ystart_real,
		double	xgoal_real,
		double	ygoal_real,
		double **	original_path
	)

Search the shortest path between two points

Parameters:

	xstart	Coordonate X of the start point
	ystart	Coordonate Y of the start point
	xgoal	Coordonate X of the goal point
	ygoal	Coordonate Y of the goal point
	original_path	[out] The original path. See details bellow.

See also:

graph

Returns:

-1 if the goal is not founded, the number of points to the goal is founded on success.

The original path will be return as a list of points as follows: {xstart,ystart, x[1], y[1], x[2], y[2], ..., x[nbpoints-2], y[nbpoints-2], xgoal, ygoal}

This is an implementation of A* Algorithm (Algorithm 24, p531) defined in the book "Principles of Robot Motion" by H. Choset&others

prioritySet : Set of nodes to process order by heuristic distance

nbest : Best node to reach the goal

1. Init graph structure with default values.

2. Calculate Heuristic distances.

3. Initial values : put start node in queue.

4. REPEAT until the queue is empty.
   1. Pick nbest from prioritySet and remove

   2. add to processed

   3. IF nbest == goal ; EXIT

   4. Expand nbest :for all x E Star(nbest) that are not in C

   5. IF is not in Priorityset add to prioritySet.

   6. ELSE update backpointer to point to nbest.

5. Deallocates memory of the queue

Definition at line 45 of file aalgorithm.c.

References _GraphMapCell::bx, _GraphMapCell::by, calculateMapHeuristic(), cFunction(), delQueue(), drainQueue(), _GraphMapCell::f, _GraphMapCell::g, getPathLength(), graph, _GraphMapCell::h, initGraphStructure(), isInQueue(), newQueue(), popNode(), _GraphMapCell::processed, pushNodeInOrder(), pushNodeLast(), queueIsEmpty(), ShmapCell2Point_X(), ShmapCell2Point_Y(), ShmapIsCellInMap(), ShmapIsFreeCell(), ShmapPoint2Cell_X(), ShmapPoint2Cell_Y(), _Node::x, and _Node::y.

Here is the call graph for this function:

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

Calculates the cost of moving from the first cell to the second cell.

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:

Cross cost

Warning:

Cells must be contiguous

Definition at line 272 of file aalgorithm.c.

References SQRT2.

void calculateMapHeuristic	(	int	xgoal,
		int	ygoal
	)

Calculates Map Heuristic values.

Parameters:

	xgoal	Coordonate X of the goal
	ygoal	Coordonate Y of the goal

This function calculates the map heuristic values (the distance to the goal that is supoused to be the shortest). The chosen method has been the euclidean distance. The distance between a point of the grid and the goal is .

Another method explained in the book is coded but not used.It is called Brushfire algorithm. (section 4.3.2 of the book)

Definition at line 201 of file aalgorithm.c.

References calculateCost(), graph, _GraphMapCell::h, isInQueue(), MAP_HEIGHT, MAP_WIDTH, newQueue(), popNode(), _GraphMapCell::processed, pushNode(), queueIsEmpty(), ShmapIsCellInMap(), _Node::x, and _Node::y.

Here is the call graph for this function:

int getPathLength	(	int	xstart,
		int	ystart,
		int	xgoal,
		int	ygoal
	)

Returns the number of points of original path

Parameters:

	xstart	Coordonate X of the first cell
	ystart	Coordonate Y of the first cell
	xgoal	Coordonate X of the second cell
	ygoal	Coordonate Y of the second cell

Returns:

number of points of original path This function set also the path cell MAP_PATH, MAP_GOAL, MAP_START attributes into the map.

Definition at line 370 of file aalgorithm.c.

References _GraphMapCell::bx, _GraphMapCell::by, graph, MAP_GOAL, MAP_PATH, MAP_START, and ShmapSetCellValue().

Here is the call graph for this function:

void initGraphStructure

(

void

)

Init Graph structure with default values

See also:

graph

Definition at line 291 of file aalgorithm.c.

References _GraphMapCell::bx, _GraphMapCell::by, _GraphMapCell::f, _GraphMapCell::g, graph, _GraphMapCell::h, MAP_HEIGHT, MAP_WIDTH, and _GraphMapCell::processed.

void ShmapAllFreeSpace

(

void

)

Initialize Map Memory with MAP_FREE value and MAP_FLAG_NO_FLAG flag.

See also:

map MAP_FREE

Definition at line 105 of file map.c.

Referenced by ShmapInit().

Here is the caller graph for this function:

---