begin process at 2010 02 10 12:00:54
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > PATHFINDING SANS CASES A*( COMPARAISON DE TEMPS )

PATHFINDING SANS CASES A*( COMPARAISON DE TEMPS )


 Information sur la source

Note :
10 / 10 - par 1 personne
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Niveau :Débutant Date de création :14/06/2005 Vu / téléchargé :4 545 / 267
Auteur : MoDDiB

Ecrire un message privé
Commentaire sur cette source (12)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
/// Historique ///
Dans un jeu le pathfinding ne peut être gérer avec des cases trop grandes :
en effet pour un déplacement de type cavalier au échecs cela donne lieu à quelques
petits écart et non à une ligne droit comme on le désirerait !
C'est pourquoi j'ai mis au point ce pathfinding qui fonctionne
selon les principe du A* mais où le graphe est basé sur les points composants les polygones
infranchissables.
J'ai donc inclus les 2 pathfindings ( CNormalAstar pour le "normal" avec les cases )
et mis une comparaison du temps de calcul .

/// Fonctionnement ///
avec le bouton gauche de la souris faites des polygones quelconques
( de + de 30 pixels d'écart entre les points vous verrez pourquoi dans le code :))
puis avec le bouton droit lancez le pathfinding !
( vous pouvez remodifiez puis relancer etc..)
Le départ est en haut a gauche et l'arrivée en bas à droite
( ou inversement :))

/// Code ///
Le A* normal n'est pas lancé par défaut il faut décommenter
la ligne 284 de main.cpp ( car il est trop lent ).
Le code est TRES ( TROP ? ) commenté et propre il est accessible à tous
même si je n'explique pas clairement le principe du A*
La partie graphique est faite en win32 et cela afin d'être accessible
au plus de monde possible ( j'aurais tant voulu le faire avec wxwidgets sniff )
pour les linuxiens il n'y a pas grand choses à changer .
Si vous n'avez pas visual studio : n'oubliez pas d'inclure Winmm.lib au projet ( timGetTime() )
Commentaires en anglais mais bon c'est vachement francéiser comme anglais
donc tout le monde devrait comprendre ( si vous voyez de grosses fautes d'anglais
indiquez les moi ^^)





Source

  • ////////////////////////////////////////////////
  • // Astar
  • //
  • // Search the quickest way between 2 points
  • //
  • // [return] : The Node which countains the way
  • // in its parent
  • ////////////////////////////////////////////////
  • CNode *CNormalAstar::Astar(POINT dep , POINT arr )
  • {
  • // Clear the 2 lists of Nodes
  • opennode.clear() ;
  • closenode.clear() ;
  • // Make the first Node
  • // according to the departure point
  • CNode *n = new CNode ;
  • n->p = dep ;
  • n->CostFromStart = 0 ;
  • n->CostToEnd = CUtils::dist( n->p , arr );
  • n->TotalCost = n->CostToEnd ;
  • n->parent = NULL ;
  • // Add the first node in the open list
  • opennode.push_front(*n);
  • while ( opennode.empty() == false )
  • {
  • // Get the better Point
  • CNode *actual = new CNode ;
  • *actual = GetBetterNode() ;
  • // If this point is the arrival
  • if ( CUtils::dist(actual->p , arr ) == 0 )
  • {
  • return actual ;
  • }else
  • {
  • // list of accessibles points from the actual
  • int direction[4][2] = {RIGHT,LEFT,DOWN,UP};
  • // add the neighbour in the open list
  • for ( int d = 0 ; d < 4 ; d++ )
  • {
  • int x = actual->p.x + direction[d][0] ;
  • int y = actual->p.y + direction[d][1] ;
  • // if this case is reachable
  • if ( x >= 0 && x < WINDOW_WIDTH && y >= 0 && y < WINDOW_HEIGHT && terrain[x][y] != 2 )
  • {
  • CNode *neighbour = new CNode ;
  • neighbour->p.x = x ;
  • neighbour->p.y = y ;
  • if ( IsInClose( neighbour->p ) == false )
  • {
  • neighbour->CostFromStart = actual->CostFromStart ;
  • neighbour->CostToEnd = CUtils::dist ( neighbour->p , arr ) ;
  • neighbour->TotalCost = neighbour->CostFromStart + neighbour->CostToEnd ;
  • neighbour->parent = actual ;
  • // add the case in the open list
  • opennode.push_front(*neighbour);
  • }
  • delete neighbour ;
  • }
  • }
  • }
  • // Add the node in the closed list
  • closenode.push_front(*actual);
  • // Si qq'un me trouve pourquoi ce delete fait planter...
  • // delete actual ;
  • }
  • return n ;
  • }
////////////////////////////////////////////////
// Astar
//
// Search the quickest way between 2 points
//
// [return] : The Node which countains the way
//            in its parent
////////////////////////////////////////////////
CNode *CNormalAstar::Astar(POINT dep , POINT arr )
{

	// Clear the 2 lists of Nodes
      opennode.clear() ;
	 closenode.clear() ;

	// Make the first Node
	// according to the departure point
	CNode *n = new CNode ;
	n->p = dep ;
	n->CostFromStart = 0 ;
	n->CostToEnd = CUtils::dist( n->p , arr );
	n->TotalCost = n->CostToEnd ;
	n->parent = NULL ;
	
	// Add the first node in the open list
	opennode.push_front(*n);

	while ( opennode.empty() == false )
	{
		// Get the better Point
		CNode *actual = new CNode ;
		*actual = GetBetterNode() ;

		// If this point is the arrival
		if ( CUtils::dist(actual->p , arr ) == 0 )
		{
			return actual ;
		}else
		{

			// list of accessibles points from the actual
			int direction[4][2] = {RIGHT,LEFT,DOWN,UP};

			// add the neighbour in the open list
			for ( int d = 0 ; d < 4 ; d++ )
			{
				int x = actual->p.x + direction[d][0] ;
				int y = actual->p.y + direction[d][1] ;

				// if this case is reachable
				if ( x >= 0 && x < WINDOW_WIDTH && y >= 0 && y < WINDOW_HEIGHT && terrain[x][y] != 2 )
				{
					CNode *neighbour = new CNode ;
					neighbour->p.x = x ;
					neighbour->p.y = y ;

					if ( IsInClose( neighbour->p ) == false  ) 
					{
						neighbour->CostFromStart = actual->CostFromStart  ;
						neighbour->CostToEnd = CUtils::dist ( neighbour->p , arr ) ;
						neighbour->TotalCost = neighbour->CostFromStart  + neighbour->CostToEnd ;
						
						neighbour->parent = actual ;
						// add the case in the open list
						opennode.push_front(*neighbour);
					}

					delete neighbour ;
				}

			}

		}
		// Add the node in the closed list
		closenode.push_front(*actual);

	 // Si qq'un me trouve pourquoi ce delete fait planter...
	 //	delete  actual ;
	}



return n ;
}

 Conclusion

/// Remerciements
Merci à  ngryman pour sa classe Timer
Dédicace à Kirua : un petit A* lui fera plaisir :)

/// BUGS ///
- Je n'arrive pas a delete actual comme indiqué dans la preview
- Bugs avec les droites d'équations x = K ; j'avais pas envie de me prendre la tête avec ça
- Bugs avec le A* normal en effet la gestion des collisions se fais par rapport aux
équations de la droite ce qui causes bien des problemes ( normalement ça se fait par détection du point
dans les triangles des polygones mais bon .. flemme ^^ )

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Sources du même auteur

Source avec Zip EXERCICES DE VERBES IRRÉGULIERS (WIN32)
Source avec Zip TUTORIAL/DEBUT JEU POUR FAIRE UN SHOOT DIRECTX7 , BON MOTEU...
Toutes les sources de MoDDiB

 Sources de la même categorie

Source avec Zip OPERATION SUR LES MATRICES CARREES AVEC CLASSE GENERIQUE par chouhad
Source avec une capture OPÉRATIONS SUR MATRICES C++ par Minilogus
[DEV-C++] CALCUL DE LA RACINE CARRÉE D'UN RÉEL par Jhep
PROGRAMME QUI CALCUL LE PPCM ET LE PGCD par AnoSantino
EVALUER UNE EXPRESSION MATHÉMATIQUE par begueradj
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de MoDDiB le 14/06/2005 15:22:36

J'ai juste oublié de dire que si le polygone est concave ca ne fonctionnera pas très bien ( voire pas du tout :p )
Mais bon tout polygone concave peut se décomposer en polygones non concaves :)

Commentaire de vecchio56 le 14/06/2005 16:07:11 administrateur CS

Ca calcule quoi en fait? Le point tel que la moyenne des distances aux autres points est minimale, une sorte de barycentre? (j'y connais rien au pathfinding, je connaissais même pas le mot)

Commentaire de MoDDiB le 14/06/2005 16:39:44

Le calcul du centre ( barycentre ici ) ne permet que de déterminer les points de passages par les polygones a une distance x
En fait si tu connais bien : il s'agit de la recherche du plus court chemin :)
L'algo de recherche du plus court chemin est mis ici et le reste ce sont surtout des fonctions propres aux polygones qui représentent les obstacles !

Désolé je n'est pas été assez précis sur le fonctionnement propre du programme :
En gros :
- lors de la création du polygone ( obstable ) on dresse une liste des sommets
du polygone ( il s'agira des points de passages ) et des segments composant le sommet avec équation de droite
- Puis lors de la recherche du plus court chemin les points voisins sont ceux qui sont accessibles directement par ligne droite sans entrer en collisions avec une droite d'un polygone !

Cette méthode semble largement plus rapide que du case par case ( sans obstacle pour un terrain de 700*500 on a 0.01ms contre 45ms ) et surtout plus réaliste .
Je n'ai pas trouvé de tutoriaux concernant cette méthode ( enfin je n'ai pas énormément cherché ) mais j'avais vu un tutorial la dessus il y a 2-3ans il s'intulait : pathfinding pour jeux 3D

Dis moi encore si il y a des points d'ombres je me rends compte que j'ai bien expliqué chaque fonction mais pas la globalité :/

Commentaire de vecchio56 le 14/06/2005 17:28:33 administrateur CS

C'est bon j'ai compris, c'est parce que je ne faisais pas le clic droit à la fin :)

Commentaire de Kirua le 14/06/2005 20:27:45

Intéressant, j'ai causé de ce système pendant pas mal de cours de sciences avec Xurei (mon pote, si tu te souviens MoDDiB ;)).

Je me demande quand même si ça va pas poser de problème quand tu modifies le terrain... tu précalcules le graphe ou pas?

Commentaire de MoDDiB le 15/06/2005 00:29:11

Afin de gagner en efficacité : on peut tenir à jour une table contenant la liste des voisins pour chaque point (  cette liste serait classé suivant les abscisses pour un accès rapide par dichotomie ) et il suffirait ensuite de revérifier tous les points accessibles au point qui est modifié et si la modification date de plus de x milliseconde ( on peut refaire un calcul avec le tableau datant de 100 ms dans certains jeu sans probleme )
Donc ici non le graphe n'est pas précalculé le temps tient compte de ca :)

Commentaire de Kirua le 15/06/2005 09:17:05

Tiens, question: en pratique, si lors du parcours le mobile rencontre un obstacle dynamique (un PNJ, un OVNI ...), que fait-il? Il recalcule son chemin en tenant compte de lui? On en avait déjà causé "là bas" ^^ mais je pense que tu peux faire comme ça, et alors dans ton calcul de chemin tu ne considères comme obstacle que les objets dynamiques qui se trouvent à moins de x unités de toi. Ça te permet de ne pas faire de détour à cause d'une unité qui pourrait avoir bougé d'ici ton arrivée. En cas de collision avec cette unité, il suffit de recalculer le chemin: comme elle est tout près, elle sera prise en compte.

Commentaire de MoDDiB le 15/06/2005 11:00:37

Oui il s'agit d'une méthode de procéder qui a ses avantages et inconvénients ( si il s'agit d'une unités ennemi qui ne bougera pas il aurait mieux valu faire le tour .
Ces méthodes d'optimisation sont propres au jeu et peuvent être cumulé par dizaine .
D'ailleurs dans un jeu il y a au moins 2 pathfinding qui dépendent de l'échelle !

Commentaire de AlexMAN le 18/07/2005 19:35:53

Je pense savoir pourquoi lors du delete actual;, ton prog plante : j'ai recodé ton algo, et chez moi aussi ca plante. Lorsque tu delete actual, neighbour->parent = actual; pointe vers une zone 'vide', désallouée, donc pouf ca plante :(
Je ne suis pas sur que cela soit ca, mais chez moi aussi, en l'enlevant, tout baigne :)

Commentaire de MoDDiB le 18/07/2005 20:44:41

Merci mais en fait désolé, j'ai compris mon erreur depuis un moment  : il ne faut en aucun cas delete à ce moment là puisque sinon après lors de la reconstruction du chemin ça pointera vers rien :/

On doit donc stocker dans une liste en plus les adresses de tous les noeuds créer afin de ne pas oublier d'en supprimer !

Commentaire de AlexMAN le 18/07/2005 21:06:19

Par contre, une petite question : je trouve ton algo assez 'vide' en comparaison avec les tuts que j'ai pu lire sur le net. Est ce une version 'simple' ou au contraire 'optimisée' de A* ?

Commentaire de MoDDiB le 30/08/2005 13:46:15

Pardon de répondre aussi tardivement je travaillais loin de chez moi donc je n'ai pas vu le message :)
Il s'agit d'une version optimisé pour les jeux : elle donne un des chemins les plus court en un minimum de temps à savoir qu'avec toutes les version de A* sur le net il devient difficile de trouver le vrai A* le mieux est donc de l'adapter...
Pour résumé c'est donc une version simple , optimisé et perso :)

 Ajouter un commentaire

Nos sponsors


Sondage...

CalendriCode

Février 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,733 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)