aalgorithm.c File Reference

Implementation of the A* algorithm. More...

#include "aalgorithm.h"
#include "pathqueue.h"
#include "map.h"
#include <math.h>
#include <stdlib.h>

Include dependency graph for aalgorithm.c:

Defines
#define	_ISOC99_SOURCE
#define	_XOPEN_SOURCE
A* Constants
#define	SQRT2   M_SQRT2
	Root square of two.
#define	WALL_COST   1000
	Cost of jumping a wall.
Functions
int	getPathLength (int xstart, int ystart, int xgoal, int ygoal)
void	GraphCell2XY (GraphMapCell *c, int *x, int *y)
	Returns X and Y index of a graph cell identified by a pointer.
A* Implementation Functions
This functions have not a meaning in A* algorithm, but are needed for implementation.
void	initGraphStructure (void)
	Init Graph structure with default values.
A* related functions
This functions have a meaning in theorical A*.
float	cFunction (int x1, int y1, int x2, int y2)
	Calculates the lenght of edge connecting two points.
void	calculateMapHeuristic (int xgoal, int ygoal)
	Calculates Map Heuristic values.
float	calculateCost (int x1, int y1, int x2, int y2)
	Calculates the cost of moving from the first cell to the second cell.
A* Main function
int	aAlgorithm (double xstart_real, double ystart_real, double xgoal_real, double ygoal_real, GraphMapCell **original_path)
	Search the shortest path between two points.

---

Detailed Description

Implementation of the A* algorithm.

Main functions.

Author:

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

Note:

The author asumes that the reader knows how A* algorithm works. In this documentation only the implementation is explained. More information "Principles of Robot Motion" by H. Choset&others (Algorithm 24, p531)