vendredi 11 juin 2010 à 17:11:35 |
Problème pour calculer le H pour l'A star ( * )
jedinos
|
Bonjour à tous !
Dans ce tuto du pathfinding A star
, l'auteur ne nous donne pas de code source mais l'idée de l'algorithme.
Le problème, c'est que je n'arrive pas à calculer H.
Je vous donne mon code:
Code C/C++ : #include <stdlib.h>
#include <stdio.h>
#include <SDL.h>
#include "Prototypes.h"
int main(int argc, char *argv[])
{
int continuer = 1, i;
SDL_Event event;
SDL_Surface *ecran = NULL, *rectangle[5] = {NULL};
SDL_Rect position_Rectangle;
position_Rectangle.x = 0;
position_Rectangle.y = 0;
if (SDL_Init(SDL_INIT_VIDEO) == -1) // Démarrage de la SDL. Si erreur alors...
{
fprintf(stderr, "Erreur d'initialisation de la SDL : %s\n", SDL_GetError()); // Ecriture de l'erreur
exit(EXIT_FAILURE); // On quitte le programme
}
ecran = SDL_SetVideoMode( 640, 480, 32, SDL_HWSURFACE | SDL_DOUBLEBUF );
SDL_WM_SetCaption("A star (*) !", NULL);
SDL_FillRect(ecran, NULL, SDL_MapRGB(ecran->format, 255, 255, 255));
IA_Star();
print_Card( ecran );
SDL_Flip( ecran );
while( continuer )
{
SDL_WaitEvent(&event);
switch(event.type)
{
case SDL_QUIT:
continuer = 0;
break;
}
}
for( i = 0; i < 5; i++ )
SDL_FreeSurface(rectangle[i]);
SDL_Quit();
return 0;
}
void print_Card( SDL_Surface *ecran )
{
int i;
SDL_Surface *rectangle[5] = {NULL}, *ligne[2] = {NULL};
SDL_Rect position_Rectangle, position_Ligne;
position_Rectangle.x = 0;
position_Rectangle.y = 0;
position_Ligne.x = 0;
position_Ligne.y = 0;
for( i = 0; i < 5; i++ )
{
rectangle[i] = SDL_CreateRGBSurface(SDL_HWSURFACE, 20, 20, 32, 0, 0, 0, 0);
SDL_FillRect(rectangle[i], NULL, SDL_MapRGB(ecran->format, i * 63, i * 63, i * 63) );
if( i == 2 )
{
SDL_FillRect(rectangle[i], NULL, SDL_MapRGB(ecran->format, 0, 255, 0) );
}
}
ligne[0] = SDL_CreateRGBSurface(SDL_HWSURFACE, 640, 1, 32, 0, 0, 0, 0);
ligne[1] = SDL_CreateRGBSurface(SDL_HWSURFACE, 1, 640, 32, 0, 0, 0, 0);
SDL_FillRect(ligne[0], NULL, SDL_MapRGB( ecran->format, 225, 225, 225 ) );
SDL_FillRect(ligne[1], NULL, SDL_MapRGB( ecran->format, 225, 225, 225 ) );
for( i = 0; i < 768; i++ )
{
if( i > 0 )
position_Rectangle.x += 20;
if( i % 32 == 0 && i > 0 )
{
position_Rectangle.y += 20;
position_Rectangle.x = 0;
}
if( carte_2[i] == 0 )
{
SDL_BlitSurface(rectangle[0], NULL, ecran, &position_Rectangle);
}
else if( carte_2[i] == 1 )
{
SDL_BlitSurface(rectangle[1], NULL, ecran, &position_Rectangle);
}
else if( carte_2[i] == 2 )
{
SDL_BlitSurface(rectangle[2], NULL, ecran, &position_Rectangle);
}
else if( carte_2[i] == 3 )
{
SDL_BlitSurface(rectangle[3], NULL, ecran, &position_Rectangle);
}
else
{
SDL_BlitSurface(rectangle[4], NULL, ecran, &position_Rectangle);
}
}
for( i = 0; i < 24; i++ )
{
position_Ligne.y = i * 20;
SDL_BlitSurface(ligne[0], NULL, ecran, &position_Ligne);
}
position_Ligne.y = 0;
for( i = 0; i < 32; i++ )
{
position_Ligne.x = i * 20;
SDL_BlitSurface(ligne[1], NULL, ecran, &position_Ligne);
}
}
/*-------Sert a determiner le chemin le plus court-------*/
void IA_Star( void )
{
/* F est / sera la somme de G et de H. */
int F = 0, G = 10, H = 0;
/* Ces " listes " vont me servir à savoir quelle sont les cases du graphe à " explorer ". */
char liste_Ouverte[768] = {0};
char liste_Ferme[768] = {0};
/*
Pour calculer le H.
J'envoie l'adresse de H ( pointeur ).
*/
calcule_H( &H );
/* J'ecris dans stdout la vaeur de H pour savoir si elle est bonne. */
fprintf( stdout, "H = %d\n", H );
}
/*-------Calcule H pour l'A star ( * )-------*/
void calcule_H( int *H )
{
/* Initialisation de variables; " un " et " trois " vont me servir a calculer ce fameux H. */
int un = 0, trois = 0;
int i, a = 0, b = 0;
/* Explore le graphe. */
for( i = 0; i < 768; i++ )
{
if( b == 0 )
{
/* Incremente " trois " de dix jusqu'a que : */
trois += 10;
/* Si carte_2[i] == 3, faire ces calculs ( fais au hasard ). */
if( carte_2[i] == 3 )
{
trois /= 32 * 10;
trois -= ( ( i % 32 ) + ( i % 32 / 32 ) );
/* b sert à ne plus modifier la valeur de 3. */
b = 1;
}
}
if( a == 0 )
{
/* Incremente " un " de dix jusqu'a que : */
un += 10;
/* Si carte_2[i] == 1, faire ces calculs ( fais au hasard ). */
if( carte_2[i] == 1 )
{
un /= 32 * 10;
un -= ( ( i % 32 ) + ( i % 32 / 32 ) );
/* a sert à ne plus modifier la valeur de 1. */
a = 1;
}
}
}
/* Calcule finale de H. */
*H = un - trois;
if( *H < 0 )
{
*H = trois - un;
}
/* pas de valeur a renvoyer car j'utilise un pointeur. */
}et Prototype.h:
Code C/C++ : int carte_2[768] =
{
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
};
void print_Card( SDL_Surface *ecran );
void IA_Star( void );
void calcule_H( int *H );
void calcule_G( int *G );
void calcule_F( int *F, int *H, int *G );
Pouvez vous m'aidé là dessu ?
Merci d'avance !
-------------------------------------------------
Yes, weekend! |
|