Il y a quelques temps de ça j'avais créé un path finding basé sur A* pour des programmes C.
Je viens de le recoder sous forme d'une classe C++.
// --------------------------------------------------------------------------------------- //
// A* Path Finding C++ class //
// Copyright (c) 2005 Spomky.Dev //
// <http://www.spomky.com/> //
// ---------------------------------------------------------------------------------------- //
// This program is free software; you can redistribute it and/or modify //
// it under the terms of the GNU General Public License as published by //
// the Free Software Foundation; either version 2 of the License, or //
// (at your option) any later version. //
// //
// You may not change or alter any portion of this comment or credits //
// of supporting developers from this source code or any supporting //
// source code which is considered copyrighted (c) material of the //
// original comment or credit authors. //
// //
// This program is distributed in the hope that it will be useful, //
// but WITHOUT ANY WARRANTY; without even the implied warranty of //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
// GNU General Public License for more details. //
// //
// You should have received a copy of the GNU General Public License //
// along with this program; if not, write to the Free Software //
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA //
// ---------------------------------------------------------------------------------------- //
// Author: Florent MORSELLI (webmaster@spomky.com) //
// URL: http://www.spomky.com //
// Project: The API project for C and C++ programming (A.I.) //
// ---------------------------------------------------------------------------------------- //
#ifndef PATH_H
#define PATH_H
#include <stdlib.h>
#include <string.h>
/*MACRO*/
/*ENUMERATIONS*/
enum PATH_MODE {PATH_short = 0, PATH_best};
enum PATH_BOOL {PATH_error = -1, PATH_false, PATH_true};
/*STRUCTURES*/
typedef struct
{
unsigned long x;
unsigned long y;
unsigned long z;
}PATH_POINT;
typedef struct
{
unsigned int *data;
unsigned long width;
unsigned long height;
unsigned long deep;
}PATH_MAP;
typedef struct
{
void* parent;
void* son;
unsigned long F;
unsigned long G;
unsigned long H;
PATH_POINT point;
bool isClosed;
}PATH_NODE;
class CPath
{
public:
/*PROTOTYPES 2D*/
CPath ( unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned int* , PATH_MODE = PATH_best , bool = false );
/*PROTOTYPES 3D*/
CPath ( unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned long , unsigned int* , PATH_MODE = PATH_best , bool = false );
/*COMMUN*/
CPath( );
~CPath( );
//Retourne true si l'objet est initialisé
bool isInitialized( void );
//Informations au sujet de la classe
char* getName ( void ){ return "A* Path Finding C++";};
char* getVersion ( void ){ return "2.0.1.0";};
char* getCopyright ( void ){ return "Copyright (c) 2005 Spomky.Dev (http://www.spomky.com/)";};
//Lance la recherche
PATH_BOOL search( void );
//Retourne true si la recherche a été fructueuse
PATH_BOOL isSuccess ( void );
//Efface la recherche
void freePath ( void );
//Change le point de départ
PATH_BOOL setStartPoint( PATH_POINT* );
//Change le point d'arrivé
PATH_BOOL setEndPoint( PATH_POINT* );
//Change la carte et ses dimensions
PATH_BOOL setNewMap( unsigned long , unsigned long , unsigned int* );
PATH_BOOL setNewMap( unsigned long , unsigned long , unsigned long , unsigned int* );
//Change le mode de recherche
PATH_BOOL setSearchMode( PATH_MODE );
//Change la limite H&V
PATH_BOOL setHVMode( bool );
//Change le type de points
PATH_BOOL set3DMode( bool );
//Retourne le point de départ
PATH_BOOL getStartPoint( PATH_POINT* );
//Retourne le point d'arrivé
PATH_BOOL getEndPoint( PATH_POINT* );
//Retourne les dimensions de la carte
PATH_BOOL getMapSize( unsigned long* , unsigned long* );
PATH_BOOL getMapSize( unsigned long* , unsigned long* , unsigned long* );
//Retourne le mode de recherche
PATH_BOOL getSearchMode( PATH_MODE* );
//Retourne la limite H&V
PATH_BOOL getHVMode( void );
//Change le type de points
PATH_BOOL get3DMode( void );
//Fonctions permettant de récupérer les points du chemin trouvé
PATH_BOOL getFirstPoint( PATH_POINT* );
PATH_BOOL getLastPoint( PATH_POINT* );
PATH_BOOL getCurrentPoint( PATH_POINT* );
PATH_BOOL gotoFirstPoint( void );
PATH_BOOL gotoLastPoint( void );
PATH_BOOL gotoNextPoint( void );
PATH_BOOL gotoPreviousPoint( void );
//Fonctions permettant de naviguer parmi les erreurs
const char* getError( unsigned long );
unsigned long getErrorNumber( void );
void clearAllErrors( void );
private:
/*PROTOTYPES 2D*/
bool isGoodWay(unsigned long, unsigned long);
PATH_NODE* add_node(unsigned long, unsigned long, PATH_NODE*);
PATH_NODE* isNodeInList(unsigned long, unsigned long);
bool isNewFGHBetterThanOld(unsigned long, unsigned long, PATH_NODE*, PATH_NODE*);
/*PROTOTYPES 3D*/
bool isGoodWay(unsigned long, unsigned long, unsigned long);
PATH_NODE* add_node(unsigned long, unsigned long, unsigned long, PATH_NODE*);
PATH_NODE* isNodeInList(unsigned long, unsigned long, unsigned long);
bool isNewFGHBetterThanOld(unsigned long, unsigned long, unsigned long, PATH_NODE*, PATH_NODE*);
/*COMMUN*/
/*Pour le calcul*/
PATH_NODE* getBestNode( void );
void setFGH( PATH_NODE* );
void buildFullPath( void );
PATH_MAP map;
PATH_MODE search_mode;
PATH_POINT start_point;
PATH_POINT end_point;
bool use_hv_move_only;
/*Pour la recherche*/
PATH_NODE** node_list;
PATH_NODE* node_end;
PATH_NODE* node_current;
unsigned long node_number;
/*Pour les vérifications*/
bool is_Searched;
bool is_Success;
bool is_3D;
bool is_MapInitialized;
bool is_StartPointInitialized;
bool is_EndPointInitialized;
/*Pour les erreurs*/
bool addNewError( const char* );
char **error_list;
unsigned long error_number;
/*Autres*/
void clearAllNodes( void );
};
#endif
// --------------------------------------------------------------------------------------- //
// A* Path Finding C++ Class //
// Copyright (c) 2005 Spomky.Dev //
// <http://www.spomky.com/> //
// ---------------------------------------------------------------------------------------- //
// This program is free software; you can redistribute it and/or modify //
// it under the terms of the GNU General Public License as published by //
// the Free Software Foundation; either version 2 of the License, or //
// (at your option) any later version. //
// //
// You may not change or alter any portion of this comment or credits //
// of supporting developers from this source code or any supporting //
// source code which is considered copyrighted (c) material of the //
// original comment or credit authors. //
// //
// This program is distributed in the hope that it will be useful, //
// but WITHOUT ANY WARRANTY; without even the implied warranty of //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
// GNU General Public License for more details. //
// //
// You should have received a copy of the GNU General Public License //
// along with this program; if not, write to the Free Software //
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA //
// ---------------------------------------------------------------------------------------- //
// Author: Florent MORSELLI (webmaster@spomky.com) //
// URL: http://www.spomky.com //
// Project: The API project for C and C++ programming (A.I.) //
// ---------------------------------------------------------------------------------------- //
#include "path.h"
CPath::CPath ( )
{
this->node_list = NULL;
this->node_end = NULL;
this->node_number = 0;
this->error_number = 0;
this->error_list = NULL;
this->start_point.x = 0;
this->start_point.y = 0;
this->start_point.z = 0;
this->end_point.x = 0;
this->end_point.y = 0;
this->end_point.z = 0;
this->map.width = 0;
this->map.height = 0;
this->map.data = NULL;
this->search_mode = PATH_best;
this->is_MapInitialized = false;
this->is_StartPointInitialized = false;
this->is_EndPointInitialized = false;
this->is_3D = false;
this->is_Searched = false;
return;
}
CPath::CPath ( unsigned long Xs, unsigned long Ys, unsigned long Xe, unsigned long Ye, unsigned long width, unsigned long height, unsigned int *map, PATH_MODE mode, bool hv_move )
{
if ( map == NULL || width == 0 || height == 0 )
return;
this->node_list = NULL;
this->node_end = NULL;
this->node_number = 0;
this->map.data = map;
this->map.width = width;
this->map.height = height;
this->start_point.x = Xs;
this->start_point.y = Ys;
this->end_point.x = Xe;
this->end_point.y = Ye;
this->use_hv_move_only = hv_move;
this->search_mode = mode;
this->error_number = 0;
this->error_list = NULL;
this->is_Searched = false;
if( this->add_node(this->start_point.x, this->start_point.y, NULL) )
{
this->is_MapInitialized = true;
this->is_StartPointInitialized = true;
this->is_EndPointInitialized = true;
this->is_3D = false;
this->node_current = this->node_list[0];
return;
}
return;
}
CPath::CPath ( unsigned long Xs, unsigned long Ys, unsigned long Zs, unsigned long Xe, unsigned long Ye, unsigned long Ze, unsigned long width, unsigned long height, unsigned long deep, unsigned int *map, PATH_MODE mode, bool hv_move )
{
if ( map == NULL || width == 0 || height == 0 || deep == 0 )
return;
this->node_list = NULL;
this->node_end = NULL;
this->node_number = 0;
this->map.data = map;
this->map.width = width;
this->map.height = height;
this->map.deep = deep;
this->start_point.x = Xs;
this->start_point.y = Ys;
this->start_point.z = Zs;
this->end_point.x = Xe;
this->end_point.y = Ye;
this->end_point.z = Ze;
this->use_hv_move_only = hv_move;
this->search_mode = mode;
this->is_Searched = false;
if ( this->add_node(this->start_point.x, this->start_point.y, this->start_point.z, NULL) )
{
this->is_MapInitialized = true;
this->is_StartPointInitialized = true;
this->is_EndPointInitialized = true;
this->is_3D = true;
this->node_current = this->node_list[0];
return;
}
return;
}
CPath::~CPath ( )
{
this->freePath();
}
PATH_NODE* CPath::add_node(unsigned long x, unsigned long y, PATH_NODE* parent)
{
bool isgoodpath;
if (this->use_hv_move_only)
{
if (parent != NULL && abs(x-parent->point.x)+abs(y-parent->point.y) != 1)
return NULL;
}
if ((isgoodpath = !this->isGoodWay(x,y)))
return NULL;
if (!(this->node_list = (PATH_NODE**)realloc(this->node_list,(this->node_number+1)*sizeof(PATH_NODE*))))
return NULL;
if (!(this->node_list[this->node_number] = (PATH_NODE*)malloc(sizeof(PATH_NODE))))
{
this->node_list = (PATH_NODE**)realloc(this->node_list,this->node_number*sizeof(PATH_NODE*));
return NULL;
}
this->node_list[this->node_number]->parent = parent;
this->node_list[this->node_number]->point.x = x;
this->node_list[this->node_number]->point.y = y;
this->node_list[this->node_number]->isClosed = isgoodpath;
if (x ==this->end_point.x && y == this->end_point.y)
this->node_end = this->node_list[this->node_number];
this->setFGH(this->node_list[this->node_number]);
++(this->node_number);
return this->node_list[this->node_number-1];
}
PATH_NODE* CPath::add_node(unsigned long x, unsigned long y, unsigned long z, PATH_NODE* parent)
{
bool isgoodpath;
if (this->use_hv_move_only)
{
if (parent != NULL && abs(x-parent->point.x)+abs(y-parent->point.y)+abs(z-parent->point.z) != 1)
return NULL;
}
if ((isgoodpath = !this->isGoodWay(x,y,z)))
return NULL;
if (!(this->node_list = (PATH_NODE**)realloc(this->node_list,(this->node_number+1)*sizeof(PATH_NODE*))))
return NULL;
if (!(this->node_list[this->node_number] = (PATH_NODE*)malloc(sizeof(PATH_NODE))))
{
this->node_list = (PATH_NODE**)realloc(this->node_list,this->node_number*sizeof(PATH_NODE*));
return NULL;
}
this->node_list[this->node_number]->parent = parent;
this->node_list[this->node_number]->point.x = x;
this->node_list[this->node_number]->point.y = y;
this->node_list[this->node_number]->point.z = z;
this->node_list[this->node_number]->isClosed = isgoodpath;
if (x == this->end_point.x && y == this->end_point.y && z == this->end_point.z )
this->node_end = this->node_list[this->node_number];
this->setFGH(this->node_list[this->node_number]);
++(this->node_number);
return this->node_list[this->node_number-1];
}
PATH_NODE* CPath::getBestNode( void )
{
if (this->node_number == 0)
return NULL;
PATH_NODE* found = NULL;
unsigned int cptr;
for (cptr = 0; cptr < this->node_number; ++cptr)
{
if ((found != NULL && this->node_list[cptr]->isClosed == false && found->F > this->node_list[cptr]->F) || (found == NULL && this->node_list[cptr]->isClosed == false))
found = this->node_list[cptr];
}
return found;
}
PATH_NODE* CPath::isNodeInList(unsigned long X, unsigned long Y)
{
unsigned long cptr;
for (cptr = 0; cptr < this->node_number; ++cptr)
{
if (this->node_list[cptr]->point.x == X && this->node_list[cptr]->point.y == Y)
return this->node_list[cptr];
}
return NULL;
}
PATH_NODE* CPath::isNodeInList(unsigned long X, unsigned long Y, unsigned long Z)
{
unsigned long cptr;
for (cptr = 0; cptr < this->node_number; ++cptr)
{
if (this->node_list[cptr]->point.x == X && this->node_list[cptr]->point.y == Y && this->node_list[cptr]->point.z == Z)
return this->node_list[cptr];
}
return NULL;
}
//Calcule F = G + H du noeud passé en argument
void CPath::setFGH(PATH_NODE* Son)
{
if (Son->parent == NULL)
{
Son->H = 0;
Son->G = 0;
Son->F = 0;
}
else
{
if (!this->is_3D)
{
Son->H = (abs(Son->point.x - this->end_point.x)+abs(Son->point.y - this->end_point.y)) * 10;
if (this->search_mode == PATH_short)
{
if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) == 2)
Son->G = 14 + ((PATH_NODE*)Son->parent)->G;
else if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) == 1)
Son->G = 10 + ((PATH_NODE*)Son->parent)->G;
}
else
{
if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) == 2)
Son->G = this->map.data[Son->point.y*this->map.width+Son->point.x]*14 + ((PATH_NODE*)Son->parent)->G;
else if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) == 1)
Son->G = this->map.data[Son->point.y*this->map.width+Son->point.x]*10 + ((PATH_NODE*)Son->parent)->G;
}
}
else
{
if (this->search_mode == PATH_short)
{
Son->H = (abs(Son->point.x - this->end_point.x)+abs(Son->point.y - this->end_point.y)+abs(Son->point.z - this->end_point.z)) * 10;
if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) + abs(Son->point.z - ((PATH_NODE*)Son->parent)->point.z) == 3)
Son->G = this->map.data[Son->point.y*this->map.width+Son->point.x*this->map.height+Son-> point.z]*17 + ((PATH_NODE*)Son->parent)->G;
else if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) + abs(Son->point.z - ((PATH_NODE*)Son->parent)->point.z) == 2)
Son->G = this->map.data[Son->point.y*this->map.width+Son->point.x*this->map.height+Son-> point.z]*14 + ((PATH_NODE*)Son->parent)->G;
else if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) + abs(Son->point.z - ((PATH_NODE*)Son->parent)->point.z) == 1)
Son->G = this->map.data[Son->point.y*this->map.width+Son->point.x*this->map.height+Son-> point.z]*10 + ((PATH_NODE*)Son->parent)->G;
}
else
{
Son->H = (abs(Son->point.x - this->end_point.x)+abs(Son->point.y - this->end_point.y)+abs(Son->point.z - this->end_point.z)) * 10;
if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) + abs(Son->point.z - ((PATH_NODE*)Son->parent)->point.z) == 3)
Son->G = 17 + ((PATH_NODE*)Son->parent)->G;
else if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) + abs(Son->point.z - ((PATH_NODE*)Son->parent)->point.z) == 2)
Son->G = 14 + ((PATH_NODE*)Son->parent)->G;
else if (abs(Son->point.x - ((PATH_NODE*)Son->parent)->point.x) + abs(Son->point.y - ((PATH_NODE*)Son->parent)->point.y) + abs(Son->point.z - ((PATH_NODE*)Son->parent)->point.z) == 1)
Son->G = 10 + ((PATH_NODE*)Son->parent)->G;
}
}
Son->F = Son->G + Son->H;
}
}
// Renvoi vrai si le nouveau parent du noeud est meilleur que l'ancien
bool CPath::isNewFGHBetterThanOld(unsigned long X, unsigned long Y, PATH_NODE* old, PATH_NODE* parent)
{
if (old->parent == parent)
return false;
unsigned long newG = 0;
if (this->search_mode == PATH_short)
{
if (parent->point.x == X && parent->point.y == Y)
return false;
if (abs(parent->point.x - X) + abs(parent->point.y - Y) == 2)
newG = this->map.data[Y*this->map.width+X]*14 + parent->G;
else if (abs(parent->point.x - X) + abs(parent->point.y - Y) == 1)
newG = this->map.data[Y*this->map.width+X]*10 + parent->G;
}
else
{
if (parent->point.x == X && parent->point.y == Y)
return false;
if (abs(parent->point.x - X) + abs(parent->point.y - Y) == 2)
newG = 14 + parent->G;
else if (abs(parent->point.x - X) + abs(parent->point.y - Y) == 1)
newG = 10 + parent->G;
}
if (newG < old->G)
return true;
return false;
}
bool CPath::isNewFGHBetterThanOld(unsigned long X, unsigned long Y, unsigned long Z, PATH_NODE* old, PATH_NODE* parent)
{
if (old->parent == parent)
return false;
unsigned long newG = 0;
if (this->search_mode == PATH_short)
{
if (parent->point.x == X && parent->point.y == Y && parent->point.z == Z)
return false;
if (abs(parent->point.x - X) + abs(parent->point.y - Y) + abs(parent->point.z - Z) == 3)
newG = 17 + parent->G;
else if (abs(parent->point.x - X) + abs(parent->point.y - Y) + abs(parent->point.z - Z) == 2)
newG = 14 + parent->G;
else if (abs(parent->point.x - X) + abs(parent->point.y - Y) + abs(parent->point.z - Z) == 1)
newG = 10 + parent->G;
}
else
{
if (parent->point.x == X && parent->point.y == Y && parent->point.z == Z)
return false;
if (abs(parent->point.x - X) + abs(parent->point.y - Y) + abs(parent->point.z - Z) == 3)
newG = this->map.data[Y*this->map.width+X*this->map.height+Z]*17 + parent->G;
else if (abs(parent->point.x - X) + abs(parent->point.y - Y) + abs(parent->point.z - Z) == 2)
newG = this->map.data[Y*this->map.width+X*this->map.height+Z]*14 + parent->G;
else if (abs(parent->point.x - X) + abs(parent->point.y - Y) + abs(parent->point.z - Z) == 1)
newG = this->map.data[Y*this->map.width+X*this->map.height+Z]*10 + parent->G;
}
if (newG < old->G)
return true;
return false;
}
PATH_BOOL CPath::search( void )
{
if ( !this->isInitialized() )
{
this->addNewError("The object is not initialized");
return PATH_error;
}
if ( this->is_Searched )
{
this->addNewError("The search have already been done");
return PATH_error;
}
if (!this->is_3D)
{
if (!this->isGoodWay(this->end_point.x, this->end_point.y))
return PATH_false;
}
else
{
if (!this->isGoodWay(this->end_point.x, this->end_point.y, this->end_point.z))
return PATH_false;
}
PATH_NODE* PATH_current_node,* temp;
int ligne, colonne, etage;
do
{
//Récuperer le meilleur noeud de la PATH_node_liste ouverte
if ((PATH_current_node = getBestNode()) != NULL)
{
// Le mettre dans la PATH_node_liste fermée
PATH_current_node->isClosed = true;
// Analyser ses 8 voisins
for(ligne = -1; ligne < 2; ++ligne)
{
for(colonne = -1; colonne < 2; ++colonne)
{
if (this->is_3D)
{
for(etage = -1; etage < 2; ++etage)
{
temp = this->isNodeInList(PATH_current_node->point.x+colonne, PATH_current_node->point.y+ligne, PATH_current_node->point.z+etage);
if (temp == NULL)
{
this->add_node(PATH_current_node->point.x+colonne, PATH_current_node->point.y+ligne, PATH_current_node->point.z+etage, PATH_current_node);
}
else
//Sinon
{
if (this->isNewFGHBetterThanOld(PATH_current_node->point.x+colonne, PATH_current_node->point.y+ligne, PATH_current_node->point.z+etage,temp,PATH_current_node))
{
temp->parent = PATH_current_node;
if (temp->isClosed == false)
this->setFGH(temp);
}
}
}
}
else
{
temp = isNodeInList(PATH_current_node->point.x+colonne, PATH_current_node->point.y+ligne);
if (temp == NULL)
{
this->add_node(PATH_current_node->point.x+colonne, PATH_current_node->point.y+ligne, PATH_current_node);
}
else
{
if (isNewFGHBetterThanOld(PATH_current_node->point.x+colonne, PATH_current_node->point.y+ligne,temp,PATH_current_node))
{
temp->parent = PATH_current_node;
if (temp->isClosed == false)
this->setFGH(temp);
}
}
}
}
}
}
}
while(this->node_end == NULL && (PATH_current_node = getBestNode()) != NULL);
is_Searched = true;
if (this->node_end == NULL)
return (PATH_BOOL)(this->is_Success = false);
buildFullPath();
return (PATH_BOOL)(this->is_Success = true);
}
void CPath::buildFullPath()
{
if (this->node_end == NULL)
return;
PATH_NODE* temp = this->node_end;
this->node_end->son = NULL;
do
{
((PATH_NODE*)temp->parent)->son = temp;
temp = (PATH_NODE*)temp->parent;
}
while (temp->parent != NULL);
}
bool CPath::isGoodWay(unsigned long X, unsigned long Y)
{
if (Y >= this->map.height || X >= this->map.width)
return false;
return this->map.data[Y*this->map.width+X];
}
bool CPath::isGoodWay(unsigned long X, unsigned long Y, unsigned long Z)
{
if (Y >= this->map.height || X >= this->map.width || Z >=
this->map.deep)
return false;
return this->map.data[Y*this->map.width+X*this->map.height+Z];
}
void CPath::freePath ( void )
{
if (this->isInitialized() == false)
return;
this->node_end = NULL;
this->node_current = NULL;
this->is_3D = false;
this->is_Searched = false;
this->map.data = NULL;
this->map.width = 0;
this->map.height = 0;
this->start_point.x = 0;
this->start_point.y = 0;
this->end_point.x = 0;
this->end_point.y = 0;
this->use_hv_move_only = false;
this->search_mode = PATH_short;
this->is_MapInitialized = false;
this->is_StartPointInitialized = false;
this->is_EndPointInitialized = false;
this->clearAllNodes();
this->clearAllErrors();
}
PATH_BOOL CPath::isSuccess ( void )
{
if ( !this->is_Searched )
{
this->addNewError("The search have not been done");
return PATH_error;
}
return (PATH_BOOL)this->is_Success;
}
PATH_BOOL CPath::getFirstPoint( PATH_POINT* value )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
value->x = this->node_list[0]->point.x;
value->y = this->node_list[0]->point.y;
value->z = this->node_list[0]->point.z;
return PATH_true;
}
PATH_BOOL CPath::getLastPoint( PATH_POINT* value )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
value->x = this->node_end->point.x;
value->y = this->node_end->point.y;
value->z = this->node_end->point.z;
return PATH_true;
}
PATH_BOOL CPath::getCurrentPoint( PATH_POINT* value )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
value->x = this->node_current->point.x;
value->y = this->node_current->point.y;
value->z = this->node_current->point.z;
return PATH_true;
}
PATH_BOOL CPath::gotoNextPoint( void )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
if (this->node_current->son == NULL)
return PATH_false;
this->node_current = (PATH_NODE*)this->node_current->son;
return PATH_true;
}
PATH_BOOL CPath::gotoPreviousPoint( void )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
if (this->node_current->parent == NULL)
return PATH_false;
this->node_current = (PATH_NODE*)this->node_current->parent;
return PATH_true;
}
PATH_BOOL CPath::gotoFirstPoint( void )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
this->node_current = this->node_list[0];
return PATH_true;
}
PATH_BOOL CPath::gotoLastPoint( void )
{
if (!this->is_Searched && !this->is_Success)
{
this->addNewError("The search have not been done or does not succed");
return PATH_error;
}
this->node_current = this->node_end;
return PATH_true;
}
PATH_BOOL CPath::setStartPoint( PATH_POINT* value )
{
if (this->is_Searched)
{
this->addNewError("You need to free the object before changing start point");
return PATH_error;
}
if ( value->x > this->map.width || value->y > this->map.height || value->z > this->map.deep )
{
this->addNewError("The new point is out of the map");
return PATH_error;
}
if (this->is_3D)
{
if ( !this->isGoodWay(value->x, value->y, value->z) )
{
this->addNewError("The new point is not a good point");
return PATH_error;
}
if ( value->x == this->end_point.x && value->y == this->end_point.y && value->z == this->end_point.z )
{
this->addNewError("The new start point is the same as the final one");
return PATH_error;
}
}
else
{
if ( !this->isGoodWay(value->x, value->y) )
{
this->addNewError("The new point is not a good point");
return PATH_error;
}
if ( value->x == this->end_point.x && value->y == this->end_point.y )
{
this->addNewError("The new start point is the same as the final one");
return PATH_error;
}
}
//this->clearAllNodes();
this->start_point.x = value->x;
this->start_point.y = value->y;
this->start_point.z = value->z;
this->node_list[0]->point.x = value->x;
this->node_list[0]->point.y = value->y;
this->node_list[0]->point.z = value->z;
if (this->node_number == 0 && this->is_3D);
this->add_node(this->start_point.x, this->start_point.y, NULL);
if (this->node_number == 0 && !this->is_3D);
this->add_node(this->start_point.x, this->start_point.y, this->start_point.z, NULL);
this->is_StartPointInitialized = true;
return PATH_true;
}
PATH_BOOL CPath::setEndPoint( PATH_POINT* value )
{
if (this->is_Searched)
{
this->addNewError("You need to free the object before changing final point");
return PATH_error;
}
if ( value->x > this->map.width || value->y > this->map.height || value->z > this->map.deep )
{
this->addNewError("The new point is out of the map");
return PATH_error;
}
if (this->is_3D)
{
if ( !this->isGoodWay(value->x, value->y, value->z) )
{
this->addNewError("The new point is not a good point");
return PATH_error;
}
if ( value->x == this->start_point.x && value->y == this->start_point.y && value->z == this->start_point.z )
{
this->addNewError("The new final point is the same as the start one");
return PATH_error;
}
}
else
{
if ( !this->isGoodWay(value->x, value->y) )
{
this->addNewError("The new point is not a good point");
return PATH_error;
}
if ( value->x == this->start_point.x && value->y == this->start_point.y )
{
this->addNewError("The new final point is the same as the start one");
return PATH_error;
}
}
this->end_point.x = value->x;
this->end_point.y = value->y;
this->end_point.z = value->z;
if (this->node_number == 0 && this->is_3D);
this->add_node(this->end_point.x, this->end_point.y, NULL);
if (this->node_number == 0 && !this->is_3D);
this->add_node(this->end_point.x, this->end_point.y, this->end_point.z, NULL);
this->is_EndPointInitialized = true;
return PATH_true;
}
PATH_BOOL CPath::setNewMap( unsigned long width , unsigned long height , unsigned int* map )
{
if (this->is_Searched)
{
this->addNewError("You need to free the object before changing the map");
return PATH_error;
}
if ( this->start_point.x > width || this->start_point.y > height )
{
this->addNewError("The start point is out of the new map");
return PATH_error;
}
if ( this->end_point.x > width || this->end_point.y > height )
{
this->addNewError("The final point is out of the new map");
return PATH_error;
}
if ( width == 0 || height == 0 || map == NULL)
{
this->addNewError("The size of the new map is not valid or data are void");
return PATH_error;
}
if ( this->is_3D )
{
this->addNewError("This is the 2D function but the object is set as 3D");
return PATH_error;
}
this->map.width = width;
this->map.height = height;
this->map.data = map;
this->is_MapInitialized = true;
return PATH_true;
}
PATH_BOOL CPath::setNewMap( unsigned long width , unsigned long height , unsigned long deep , unsigned int* map )
{
if (this->is_Searched)
{
this->addNewError("You need to free the object before changing the map");
return PATH_error;
}
if ( this->start_point.x > width || this->start_point.y > height || this->start_point.z > deep )
{
this->addNewError("The start point is out of the new map");
return PATH_error;
}
if ( this->end_point.x > width || this->end_point.y > height || this->end_point.z > deep )
{
this->addNewError("The final point is out of the new map");
return PATH_error;
}
if ( width == 0 || height == 0 || deep == 0 || map == NULL)
{
this->addNewError("The size of the new map is not valid or data are void");
return PATH_error;
}
if ( !this->is_3D )
{
this->addNewError("This is the 3D function but the object is set as 2D");
return PATH_error;
}
this->map.width = width;
this->map.height = height;
this->map.deep = deep;
this->map.data = map;
this->is_MapInitialized = true;
return PATH_true;
}
PATH_BOOL CPath::setSearchMode( PATH_MODE mode )
{
this->search_mode = mode;
return PATH_true;
}
PATH_BOOL CPath::setHVMode( bool mode )
{
this->use_hv_move_only = mode;
return PATH_true;
}
PATH_BOOL CPath::set3DMode( bool mode )
{
this->is_3D = mode;
return PATH_true;
}
PATH_BOOL CPath::getStartPoint( PATH_POINT* value )
{
if ( !this->is_StartPointInitialized )
{
this->addNewError("The start point is not initialized");
return PATH_error;
}
*value = this->start_point;
return PATH_true;
}
PATH_BOOL CPath::getEndPoint( PATH_POINT* value )
{
if ( !this->is_EndPointInitialized )
{
this->addNewError("The final point is not initialized");
return PATH_error;
}
*value = this->end_point;
return PATH_true;
}
PATH_BOOL CPath::getMapSize( unsigned long* width , unsigned long* height )
{
if ( !this->is_MapInitialized )
{
this->addNewError("The map is not initialized");
return PATH_error;
}
if ( this->is_3D )
{
this->addNewError("This is the 2D function but the object is set as 3D");
return PATH_error;
}
*width = this->map.width;
*height = this->map.height;
return PATH_true;
}
PATH_BOOL CPath::getMapSize( unsigned long* width , unsigned long* height , unsigned long* deep )
{
if ( !this->is_MapInitialized )
{
this->addNewError("The map is not initialized");
return PATH_error;
}
if ( !this->is_3D )
{
this->addNewError("This is the 3D function but the object is set as 2D");
return PATH_error;
}
*width = this->map.width;
*height = this->map.height;
*deep = this->map.deep;
return PATH_true;
}
PATH_BOOL CPath::getSearchMode( PATH_MODE* value )
{
return (PATH_BOOL)this->search_mode;
}
PATH_BOOL CPath::getHVMode( void )
{
return (PATH_BOOL)this->use_hv_move_only;
}
PATH_BOOL CPath::get3DMode( void )
{
return (PATH_BOOL)this->is_3D;
}
bool CPath::isInitialized ( void )
{
return ( this->is_MapInitialized && this->is_StartPointInitialized && this->is_EndPointInitialized );
}
const char* CPath::getError( unsigned long num )
{
if ( this->error_number == 0 )
return false;
if ( num > this->error_number )
return false;
return this->error_list[num];
}
unsigned long CPath::getErrorNumber( void )
{
return this->error_number;
}
bool CPath::addNewError( const char* msg )
{
if (!(this->error_list = (char**)realloc(this->error_list,(this->error_number+1)*sizeof(char*))))
return false;
if (!(this->error_list[this->error_number] = (char*)malloc(sizeof(char)*(strlen(msg)+1))))
{
this->error_list = (char**)realloc(this->error_list,this->error_number*sizeof(char*));
return false;
}
strcpy(error_list[this->error_number],msg);
++(this->error_number);
return true;
}
void CPath::clearAllErrors( void )
{
unsigned long cptr;
if ((this->error_number))
{
for (cptr = 0; cptr < this->error_number; ++cptr)
free(this->error_list[cptr]);
free(this->error_list);
}
this->error_number = 0;
}
void CPath::clearAllNodes( void )
{
unsigned int cptr;
if ((this->node_number))
{
for (cptr = 0; cptr < this->node_number; ++cptr)
free(this->node_list[cptr]);
free(this->node_list);
}
this->node_number = 0;
}
J'ai trouvé quelques bugs (dont certains qui font planter le programme) mais dans l'ensemble ça fonctionne bien.
Je mets des exemples d'utilisation bientôt.
Pour le moment je n'ai que celui-ci :
// --------------------------------------------------------------------------------------- //
// A* Path Finding Demo //
// Copyright (c) 2005 Spomky.Dev //
// <http://www.spomky.com/> //
// ---------------------------------------------------------------------------------------- //
// This program is free software; you can redistribute it and/or modify //
// it under the terms of the GNU General Public License as published by //
// the Free Software Foundation; either version 2 of the License, or //
// (at your option) any later version. //
// //
// You may not change or alter any portion of this comment or credits //
// of supporting developers from this source code or any supporting //
// source code which is considered copyrighted (c) material of the //
// original comment or credit authors. //
// //
// This program is distributed in the hope that it will be useful, //
// but WITHOUT ANY WARRANTY; without even the implied warranty of //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
// GNU General Public License for more details. //
// //
// You should have received a copy of the GNU General Public License //
// along with this program; if not, write to the Free Software //
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA //
// ---------------------------------------------------------------------------------------- //
// Author: Florent MORSELLI (webmaster@spomky.com) //
// URL: http://www.spomky.com //
// Project: //
// ---------------------------------------------------------------------------------------- //
//Inclusion des librairies de base
#include <stdlib.h>
#include <stdio.h>
//Inclusion de la classe
#include "../path.h"
int main(int argc, char *argv[]);
//La carte utilisée
//Elle fait 10 de large pour 10 de haut
unsigned int map[] = {
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,0,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,};
int main(int argc, char *argv[])
{
//On a besoin des coordonnées de départ et d'arrivée (4 arg) + méthode de recherche (rapide ou meilleur) + utilisation ou non des seuls mouvements verticaux
if (argc != 7)
{
printf("Usage : demo Xstart Ystart Xend Yend search_mode hv_only\n\n \
search_mode : 0 or 1\n \
hv_only : 0 or 1\n\n");
exit(EXIT_FAILURE);
}
//On créé l'objet
CPath chemin(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]), atoi(argv[4]), 10, 10, (unsigned int*)&map, (PATH_MODE)atoi(argv[5]), atoi(argv[6]));
//On affiche un texte simple en utilisant les fonctions de la classe
printf("%s version %s\n%s\n\n",chemin.getName(),chemin.getVersion(),chemin.getCopyright());
if (chemin.isInitialized())
{
//On lance la recherche
if (chemin.search() == PATH_true)
{
//Et si ça marche on affiche les points du chemin
printf("I found a way!\n");
PATH_POINT result;
chemin.getFirstPoint(&result);
printf("{%i,%i}\n",result.x,result.y);
while ( chemin.gotoNextPoint() )
{
chemin.getCurrentPoint(&result);
printf("{%i,%i}\n",result.x,result.y);
}
}
else
{
printf("I did not found any way!\n");
}
}
printf("Nombre d'erreur(s) : %i\n",chemin.getErrorNumber());
unsigned long compteur;
for (compteur=0;compteur<chemin.getErrorNumber();compteur++)
{
printf("\tErreur n°%i : %s\n",compteur+1,chemin.getError(compteur));
}
exit(1);
}
)
