Algo de pathfinding avec petit jeu

Télécharger le projet
Commenter

Description

sa sert a résoudre les problème de type recherche du plus court chemin dans un graphe
(3 algo son implémente : glouton, dijkstra et A*)

Le zip se compose de 3 projets
Algo : contient le code et un exemple d'utilisation tres basique en ligne de commande
AlgoDll : con,tient un mise en dll de la serie de classe
TestAlgoDll : petite interface contenant 2 exemple d'utilisation de la dll

Fonctionnement :

- on crée un graph avec la classe CGraph qui permet d'ajouter des sommet (value) et des arc (Link) ou

- Ensuite (pour utiliser glouton ou A*) il faut définir une heuristique en écrivant un classe hériter de CHeurist qui redéfinit la fct ComputeHeuristValue

- Puis il faut créé un resultResolver (vous devez réécrire un classe qui hérite de CResultResolver et dont la fonction DoResult sera appeler a chaque fin de resolution)

- puis on créé un objet de type resolver (DijkstraResolver, GloutonResolver ou AStarResolver) selon l'algo a utiliser en lui passant le graph, le sommet initial et final, le ResultResolver et pour glouton et A* l'heuristique.

Créé un objet CMultiResolver (permet de résoudre les revolver dans un thread)
et ajouter le resolver grâce a AddNewResolver

Il y a une petite interface d'exemple (un truc pour calculer le plus court chemin entre 2 stations de metro) qui est basique

et un petit jeu un peu plus complexe

Il y a beaucoup de commentaire, mais poser des question si vous avez des problèmes j'y répondrai.

Source / Exemple : 


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;
};

Conclusion :


Version a peu prêt stable
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (kts_system)