ALGO DE PATHFINDING AVEC PETIT JEU

Fichier a intégrer dans votre projet pour utiliser la dll.


/*--------------------------------------------------------------
V 1.0 (30/12/08)
	- Premiere version en vc6 (implementation algo glouton, dijkstra et A*)
	- Creation des classes CGraph, CLink, CResolver et 
	  ses heritage (DijsktraResolver...) et la classe CValue
	- Gestion des heuristiques pour glouton et a*

V 1.1 (08/01/09)
	- Maintenant on peut créé des graphes orienté ou non
	  (voir CGraph et CLink pour l'utilisation)
	- Correction d'un bug pour l'algo glouton sur le calcul
	  du cout d'un chemin 
	- On peut choisir de sauvgarder (ou pas) toutes les dests
	  quand on execute l'algo dijkstra (voir CDijkstraResolver)
	- Ajout de la classe CFileGraph pour pouvoir créé le graphe
	  a partir de deux fichiers texte

v 1.2 (14/02/09)
	- Passage en vc 2005
	- Ajout d'un nom pour les resolvers
	- Ajout de test pour blinder les methode resolves
	- Separation dans des fichiers differents des differentes
	  classe Graph, Heurist et resolver
	- Ajout d'une methode GetClone aux classes Value, Link, Graph 
	  et Resolver (retourne des copie independante au niveau memoire)
    - La valeur de l'heurist et maintenant un double (int avant)
	- Ajout de la classe CResultResolver (plus objet que de faire
	  un GetResult a chaque resultat)
    - Ajout de la methode GetTypeString dans Resolver
	- Correction d'une memory leak sur la destruction des graphs cloner
	- Ajout de la classe MultiResolver qui permet de resoudre les Resolver
	  de maniere parallèle (syncro ou pas)
    - Ajout d'une fct dans multires pour respecter l'ordre d'appel
	  des resultats (les resolver sont traités un apres l'autre)
    - Blindage des methode AddValue et AddLink dans CGraph
	  pour eviter les doublons

v 1.3 (15/06/09)
	- Passage en vc 2008
	- Ajout de 2 nouveaux ResultResolver
	- Ajout d'un ptr user aux result resolver
	- Création d'un projet DLL (AlgoDll)
	- Création des interfaces IResolver, IGraph, IValue ... pour l'export dll
	- Création de la classe CManager pour l'export dll

v 1.4 (04/06/09)
	- Ajout de la classe CGraphValidator qui permet de verifier que le graphe
	  est correct (correspondance entre les liens et les valeurs)
    - Ajout d'un getlasterror dans la classe graphe

v 1.5 (05/06/09)
	- Réécriture de la classe CMultiResolver
	- Ajout des classe CResolverThread et CResultThread
	  (maintenant le resolver delège le DoResult a un thread)

v 1.5.1 (11/07/09)
	- Amelioration de la structure de ResolverThread (Interface IRunnable)
	- Correction d'un bug dans le Resolver thread
	

Bug connuts :
	- aucun

a faire :
	- Finir l'algo fordBellman
	- Créé une classe CXmlGraph pour pouvoir lire un graph depuis une fiche xml
	- rajouter des algo pour faire autre chose ? (minimax, alpha-beta, forward checking ?????)

---------------------------------------------------------------*/


/*---------------------------------------------------------------
	Remarque :

	CResolver : Contient l'intelligence (les algos), resout les graphes
	CResultResolver : Appelé par le resolver lorsqu'il a trouvé le chemin
	CMultiResolver : Permet de resoudre les resolver de manière parallèle
	CValue : represente un sommet 
	CLinks : represente un arc (contient le cout de l'arc)
	CHeurist : Calcule l'heuristique (glouton et AStart)
	CGraph : Represente un graphe avec des sommets : IValue et
			 des arcs : CLink

	Schema :

	CMultiResolver
		  |
		  |------CResolver------------------------------------CGraph-----------CValue
					^						|				   ^			|
					|						|				   |			|
		   ------------------------		CResultResolver		   |			|
		   |		  |			  |							CFileGraph		--CLink
   CDijkstraResolver  |			  |
					  |			  |
			     CGoulonResolver  |
					|			  |
					|---CAStartResolver
					|
				CHeurist

---------------------------------------------------------------*/


/**************************************************************
Fichier commun qui permet pour l'utilisateur de la dll: 
	d'instancier la dll (fonction Lib de IManager)
	declare les interfaces

Pour la dll
	Declare les interfaces

ATTENTION : pour liberer la mémoire ne PAS faire de dellete 
			directement sur les interfaces, utiliser les
			methodes Free du manager

---------------------------------------------------------------*/

/**************************************************************/
//Declaration des types
//Type de graph
#define TYPE_GRAPH 0
#define TYPE_FILE_GRAPH 1

//Type de ResultResolver
#define TYPE_METRO_RESOLVER 0
#define TYPE_STD_RESOLVER 1

//Type de Resolver
#define TYPE_GLOUTON_RES  0
#define TYPE_DIJKSTRA_RES 1
#define TYPE_ASTAR_RES    2

//Type d'heuristique
#define TYPE_METRO_HEURIST 0

/**************************************************************/
//Message des ResultResolver :
#define MSG_METRO_NEW_RESULT WM_APP+001
#define MSG_GAME_NEW_RESULT WM_APP+002


/**************************************************************/

//-----------------------------------------------
class IGraph;
class IValue
{
public:
	//Ajoute un sommet lier (pour la construction du graphe)
	virtual bool AddNextVal(IValue * pVal) = 0;
	
	//Setteur
	virtual void SetBestCout(int iBest) = 0;
	virtual void SetBestPrec(IValue * pVal) = 0;
	virtual void SetHeuristique(double iHeurist)  = 0;
	virtual void SetValueName(std::string strValName) = 0;

	//Getteur
	virtual double GetHeuristique() = 0; 
	virtual int GetBestCout() = 0;
	virtual IValue * GetBestPrec() = 0;
	virtual std::vector<IValue*> GetNextValList() = 0;
	virtual std::string GetValueName() = 0;

	virtual IGraph * GetGraph() = 0;
	virtual IValue * GetClone(IGraph * pAssosGraph) = 0;

	virtual void * GetUserPtr() = 0;
	
	virtual int GetRepere() = 0;
	virtual int ClearList() = 0;
};

//------------------------------------------------------------------
class ILink
{
public:
	
	//Retourne un ptr vers la valeur
	virtual IValue * GetVal1()= 0;
	virtual IValue * GetVal2()= 0;

	//Retourne le cout du lien
	virtual int GetCout()= 0;

	//Retourne le type du lien (double ou simple)
	virtual bool IsDoubleLink() = 0;

	//Retourne un clone du lien
	virtual ILink * GetClone(IValue * pVal1,IValue * pVal2)= 0;
};


//---------------------------------------------------------------------
class IGraph
{
public :

	virtual bool Init() = 0;//Initialise (construit l'arbre)

	//Ajoute des sommet au graphe, retourne false si l'id (iValRep) existe déja
	virtual bool AddValue(int iValRep,std::string strValName = "", void * pUserPtr = NULL) = 0;

	//Ajoute des liens entre les sommet, retourne false
	//si un lien existant contient les 2 même sommet
	//bool AddLink(CValue * pVal1,CValue * pVal2, int iCout) = 0;
	virtual bool AddLink(int iRepVal1, int iRepVal2, int iCout) = 0;
	virtual bool AddLink(IValue * pVal1,IValue * pVal2, int iCout) = 0;

	//Retourne un graphe independant (au niveau memoire)
	//du graphe cloné (pour l'utilisation en thread)
	//en general on laisse la destruction des graphs
	//clonner au resolver qui le recupère
	virtual IGraph * GetClone(bool bNoDestructGraph = false) = 0;

	//Retourne vrai si le graph doit etre detruit par sont resolver
	virtual bool DoDestruct() const = 0;

	//Retourne vrai si l'init a été fait (l'arbre a été construit)
	virtual bool IsInitialised() const  = 0;
	virtual void SetInitialised(bool bInit) = 0;

	//Retourne un ptr sur la CValue assosier a l'id
	virtual IValue * GetValue(int iValRep) = 0;
	
	//Retourne un ptr sur la CValue assosier au nom en param
	//ATTENTION : ambiguiter si plusieurs valeur porte le même nom
	//c'est la premiere trouver qui est retourné
	virtual IValue * GetValue(std::string strValName) = 0;
	
	//Utiliser lors de la construct du graphe pour savoir si un
	//sommet a déja été utilisé ou pas
	virtual bool IsValInList(IValue * pVal, std::vector<IValue*> * pList) = 0;
	virtual bool IsLienInList(ILink * pLien, std::vector<ILink*> * pList) = 0;

	//Retourne la distance (cout) entre les 2 sommet du graphe
	virtual int GetCout(IValue * pA, IValue * pB) = 0;

	//Initialise les valeur (avant de commencer l'algo)
	virtual void InitValues(std::vector<IValue*> * pList) = 0;

	//retourne la liste des valeur du graphe
	virtual std::vector<IValue*> GetValList() const  = 0; 
	virtual std::vector<ILink*> GetLinkList() const = 0;

	virtual std::string GetLastError() const = 0;
};


//--------------------------------------------------------
class IGraphValidator
{
public:

	virtual bool VerifGraph(IGraph * pGraph) = 0;
	virtual std::vector<std::string> GetAllErrors() = 0;

	virtual void TryToRepair(IGraph * pGraph) = 0;
};


//--------------------------------------------------------
class IResolver;
class IResultResolver
{
public:

	virtual void DoResult(std::vector<IValue*> vectResult, IResolver * pResolver) = 0;
	virtual bool DoDestruct() = 0;
	virtual bool Break() = 0;
};


//-------------------------------------------------------
class IResolver
{
public:
	//Resout le problème (applique l'algo choisit sur le graphe)
	virtual inline bool Resolve() = 0; 

	//Retourne le type du Resolver dans une chaine
	virtual std::string GetTypeString() = 0;

	//Retourne un resolver, clone de celui qui appele (au niveau graph value...)
	//mais ou le sommet de debut et de fin peuvent etre changés,
	//pour le resultResolver si il est a NULL on utilise celui du resolver a cloner
	virtual IResolver * GetClone(int iRepDebut, int iRepFin, IResultResolver * pRslResolver = NULL) = 0;
	virtual IResolver * GetClone(IValue * pDebut, IValue * pFin, IResultResolver * pRslResolver = NULL) = 0;

	//Retourne le nom du resolver
	virtual std::string GetName() = 0; 

	//Retourne un pointeur sur le graph associer a ce resolver
	virtual IGraph * GetGraph() = 0;

	virtual long GetExecTime() = 0;

	virtual void SetDebut(IValue * pVal) = 0;
	virtual void SetFin(IValue * pVal) = 0;

	virtual std::string GetLastError() = 0;
};

//-----------------------------------------------
class IHeurist  
{
public:
	virtual int ComputeHeuristValue(IValue * pVal, IValue * pValEnd) = 0;
};

//-------------------------------------------------
class IMultiResolver
{
public:
	virtual bool Start() = 0;
	virtual bool Stop() = 0;
	virtual bool AddNewResolver(IResolver * pResolver) = 0;
};

//------------------------------------------------
class IManager
{
public:

#ifdef USE_ALGO_DLL
	//------------------------------------------------------
	//Initialise la dll et retourne un ptr sur le CManger
	//Decharge la dll si bLoad = false
	//------------------------------------------------------
	static IManager * Lib(std::string csFileName, bool bLoad)
	{
		static HINSTANCE hIns = NULL;
		static IManager * pMan = NULL;
		void (*GetPulgin)(IManager ** pMan);
		GetPulgin = NULL;

		if (bLoad && !hIns)
		{
			//Transforme le std::string en wchar
			WCHAR buf[512];
			for(size_t i=0; i < (size_t)csFileName.length()+1;i++)
				buf[i] = csFileName[i];

			hIns = LoadLibrary(buf);
			
			if (hIns)
			{	
				GetPulgin = (void (*)(IManager ** pMan)) GetProcAddress(hIns,"_GetPulginManager");
			}

			if (GetPulgin)
				GetPulgin(&pMan);
		}
		else if (hIns && pMan && bLoad)
		{
			return pMan;
		}
		else if (!bLoad)
		{
			FreeLibrary(hIns);
			hIns = NULL;

			if (pMan) 
				delete pMan;

			pMan = NULL;
			return NULL;
		}

		return pMan;
	}

#endif

	//Methode permettant de créé les objets nessesaire
	virtual IValue * CreateNewValue(int iValRep,IGraph * pGraph, std::string strValName = "",void * pUserPtr = NULL) = 0;
	virtual ILink * CreateNewLink(IValue * pVal1,IValue * pVal2, int iCout, bool bDoubleLink = false) = 0;
	
	virtual IGraph * CreateNewGraph(bool bOriented = false, bool bNoDestructGraph = true) = 0;
	virtual IGraph * CreateNewFileGraph(std::string strValueFileName, std::string strLinkFileName, std::string strSeparateurA = ";", std::string strSeparateurB = ";") = 0;

	virtual IResultResolver * CreateNewResultResolver(int iType, bool bDestructWithResolver = false, void * pUserPtr = NULL,DWORD dwTimeBetweenResult = 0) = 0;
	
	virtual IGraphValidator * GetGraphValidator() = 0;

	//pHeurist peut etre NULL si le resolver n'en a pas besoin
	virtual IResolver * CreateNewResolver(int iType,IGraph * pGraph, IHeurist * pHeurist, int iRepDebut, int iRepFin, IResultResolver * pRslResolver = NULL, std::string strName = "") = 0;
	virtual IResolver * CreateNewResolver(int iType,IGraph * pGraph, IHeurist * pHeurist, IValue * pDebut, IValue * pFin, IResultResolver * pRslResolver = NULL, std::string strName = "") = 0;
	virtual IResolver * CreateNewResolver(int iType,IResolver * pOtherResolver) = 0;

	virtual IHeurist * CreateNewHeurist(int iType, std::string strCoordFileName) = 0;
	virtual IMultiResolver * GetMultiResolver() =0;

	virtual void FreeResolver(IResolver * pRes) = 0;
	virtual void FreeGraph(IGraph * pGraph) = 0;
	virtual void FreeResultResolver(IResultResolver * pResultRes) = 0;
};