Pathfinding sans cases a*( comparaison de temps )

Soyez le premier à donner votre avis sur cette source.

Vue 6 367 fois - Téléchargée 371 fois

Description

/// 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 / Exemple :


////////////////////////////////////////////////
// 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 ^^ )

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
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 :)
cs_AlexMAN
Messages postés
1536
Date d'inscription
samedi 21 décembre 2002
Statut
Membre
Dernière intervention
24 mai 2009
1
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* ?
MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
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 !
cs_AlexMAN
Messages postés
1536
Date d'inscription
samedi 21 décembre 2002
Statut
Membre
Dernière intervention
24 mai 2009
1
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 :)
MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
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 !

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.