#ifndef __TOOLS_H__ #define __TOOLS_H__ #include #include #include #include #include #include #include #include #include #include #include // alt: -Wno-deprecated-declarations #define GL_SILENCE_DEPRECATION #ifdef __APPLE__ #include #else #include #endif #include #include // échange les variables x et y, via z #define SWAP(x, y, z) (z) = (x), (x) = (y), (y) = (z) // réel aléatoire dans [0,1] #define RAND01 ((double)random()/RAND_MAX) // taille maximum du nom d'un fichier #define MAX_FILE_NAME 256 //////////////////////// // // SPÉCIFIQUE POUR TSP // //////////////////////// // Un point (x,y). typedef struct { double x, y; } point; // Construit la prochaine permutation de P de taille n dans l'ordre // lexicographique. Le résultat est écrit dans P. La fonction renvoie // true sauf si à l'appel P était la dernière permutation. Dans ce cas // false est renvoyé et P n'est pas modifiée. Il n'est pas nécessaire // que les valeurs de P soit dans [0,n[. bool NextPermutation(int *P, int n); // Primitives de génération des points. point *generatePoints(int n); // n points au hasard dans [0,width] x [0,height] point *generateCircles(int n, int k); // n points au hasard sur k cercles concentriques point *generatePower(int n, double p); // points selon loi puissance sur un disque point *generateConvex(int n); // n points au hasard en position convexe point *generateGrid(int *n, int p, int q); // points sur une grille régulière pxq point *generateLoad(int *n, char *file); // points lus depuis un fichier // Format d'un fichier de points: si n<0, alors les points seront // recentrés dans la fenêtre. Les paramètres "factor" et "shift", qui // sont optionnels, permettent de transformer chaque point (x_i,y_i) // en (x_i*f + dx, y_i*f + dy). Les lignes vides ou commençant par // '##' sont ignorées. // // ## ceci est un commentaires // n // factor = f // shift = dx dy // // x_1 y_2 // ... ... // x_n y_n // Primitives de dessin. void drawTour(point *V, int n, int *P); // affichage de la tournée P void drawPath(point *V, int n, int *P, int k); // desine les k premiers points de P // Un graphe G (pour MST). typedef struct { int n; // n=nombre de sommets int *deg; // deg[u]=nombre de voisins du sommet u int **list; // list[u][i]=i-ème voisin de u, i=0..deg[u]-1 } graph; void drawGraph(point *V, int n, int *P, graph G); // affiche graphe, arbre et tournée //////////////////////// // // SPÉCIFIQUE POUR A* // //////////////////////// // Une position d'une case dans la grille. typedef struct { int x, y; } position; // Une grille. typedef struct { int X, Y; // dimensions: X et Y int **texture; // texture des cases: texture[x][y], 0<=x