1 Début de programmation dans le projet

Tout d’abord pour commencer, la première chose à faire fut le déplacement simple des unités selon 16 directions. Pour ce faire, il faut faire une recherche de la direction dans laquelle l’unité va se déplacer afin de sélectionner la portion d’image dans le fichier image de l’unité en déplacement qui sera à afficher à l’écran.
Par la suite, il faut changer les coordonnées des unités en fonction de leurs directions.
Une fois cette partie implémentée, une chose flagrante à l’œil survint : on ne voit pas le changement de directions des unités. Il a fallut décomposer l’algorithme de rotation des unités en 2 cas distincts à cause de la direction 0 qui faisait faire une rotation toujours dans le même sens.
 
 

2 Algorithme de cheminement

Comme les cartes sont divisées en tiles de 32 pixels, la recherche s’effectue au niveau des tiles. L’état des tiles est ‘walkable’ lorsque celui ci ne contient pas d’arbre ou de bâtiment sur sa surface. A partir du point de départ, on crée un arbre de recherche, cet arbre comporte 8 fils et garde le père du nœud pointé. Après beaucoup d’erreurs de pointeurs, et après m’être familiariser avec leur comportement la base fonctionnait plus ou moins correctement, avec quelques erreurs. Ma première idée fut le développement de A*, mais au lieu de faire une approximation au but je fais un calcul direct de la distance entre l’arrivée et le point actuellement en développement. L’algorithme développé se nomme ‘Best First’

ptrees = ^trees;
trees = record
  f0,f1,f2,f3,f4,f5,f6,f7 : ptrees;
  pere : ptrees;
  x,y : byte;
end;

ptree est l’arbre de recherche que l’on va développer, il contient donc 8 fils correspondants au tiles autour de celui que l’on développe, il garde le père du nœud pour faciliter le parcours de l’arbre pour le vider et comprend aussi les coordonnées du tile développé x et y.

pcoords = ^coords;
coords = record
  x,y : byte;
  suivant : pcoords;
  dist : longint;
  ptree : ptrees;
end;

pcoord est la liste des tiles ouverts, il contient les coordonnées, la distance jusqu’à l’arrivée afin de trier la liste chaînée de tiles. Le pcoord pointe sur l’arbre de recherche pour donner à la procédure Astar directement le nœud à développer.

maps = record
  walkable ,
  ecrit ,
  closed : Boolean;
  ptree : ptrees;
end;
support_maps = array [0..NTilesX-1,0..NTilesY-1] of maps;

searchmap prend des paramètres directement de BackTileMap(cf. I.7. L’Engin : The Next Generation) : walkable et plus tard closed de la carte sauvée par l’éditeur. Elle pointe aussi vers l’arbre, ceci sert lorsque l’on ne trouve pas de chemin, le booléen ecrit servira dans l’algorithme pour éviter de développer un tile de la carte déjà exploré.
 
 

Principe de la recherche :

On crée une liste de tiles ouverts (tiles explorés mais non développés).
On les trie par ordre croissant par rapport à la distance entre le nœud développé et l’arrivée.
Pour tous les tiles voisins du nœud développer,
                        S’il est ‘walkable’ et si ce tile n’a pas déjà été développé alors on crée un fils et on le met dans la liste des tiles ouverts.
On supprime le nœud qui vient d’être développé de la liste des tiles ouverts.

On réitère ces opérations jusqu’à ce que l’on trouve l’arrivée.
On renvoie à l’unité une liste chaînée de tiles qu’elle va franchir.
 
 

Une fois la base de l’algorithme implémentée, il restait des problèmes, 3 majeurs :
    -l’optimisation
    -pas de gestion de surfaces fermées
    -Impossible de cliquer sur un tile non ’walkable’
 
 

3 Optimisation

Au lieu de renvoyer une liste de tous les tiles à franchir, mieux vaut renvoyer une liste de points, où l’unité va changer de direction. Pour ce faire, j’ai effectué lors de la remontée de l’arbre de l’arrivée au point de départ de la recherche. Et seulement ensuite je vérifie dans cette liste les différences d’abscisses et d’ordonnées entre le tile précédent et le tile actuel avec le tile actuel avec le tile suivant. Les abscisses et les ordonnées sont converties en coordonnées en multipliant les tiles par leurs dimensions. Ceci permet aux unités de n’avoir que quelques points où elles doivent changer de directions. On renvoie une liste appelée pcoordonnée qui est attribuée à chaque unité.
 
 

4 Gestion des surfaces fermées

Définition de la surface fermée :
C’est une surface qui n’est pas accessible de l’extérieur
Ex : une île ou une colline

Les premières fois, il y avait des plantages lorsque l’on cliquait d’une surface ouverte vers une surface fermée car l’arbre se développait jusqu’à ce qu’elle soit bloquée et il ne trouvait jamais l’arrivée alors j’ai pensé qu’il fallait garder un pointeur sur l’élément le plus proche de l’arrivée dans l’arbre mais dans ce cas, toute la carte était développée cela rendait le jeu impossible car toute la carte était développée et il fallait pour cela attendre au moins 5 secondes.
Alors j’ai fait une recherche à partir de l’arrivée sachant qu’elle était sur une surface fermée, cette recherche s’effectuait en cercle concentrique autour de l’arrivée jusqu’à ce qu’il y ait un tile ‘walkable’, donc on changeait, l’arrivée.
Dans l’autre sens, si l’on essaie de déplacer une unité de la surface fermée vers la surface ouverte alors, on quitte lorsque l’unité ne puisse plus développer l’arbre et on garde le minimum.
Lorsque aucun changement de l’arrivée n’avait été fait, on obtenait :
 
 

Comme vous pouvez le voir, aucun chemin n’est trouvé.
L’algorithme recherche le premier tile ‘walkable’ autour de l’arrivée lorsque celui ci est une surface fermée .

Ex :

5 Pour cliquer sur un tile non ‘walkable’

On considère que tous les tiles non ‘walkable’ sont des surfaces fermées et ensuite on applique les algorithmes pour les surfaces fermées. Si l’on a une forêt dense où les unités ne peuvent pas entrer et que par malchance il y ait un tile ‘walkable’ alors on se retrouve dans une mauvaise position : toute la carte est développée.
 
 

6 Unités plus grandes qu’un soldat

Les soldats peuvent être comparés au niveau de leur taille a un tile tandis que les chars en représentent quatre. Lorsque l’on déplaçait un char, graphiquement il coupait les arbres. Il a donc fallut faire le même algorithme que le précédent avec quatre fois plus de vérifications. Donc il  ne faut même plus penser développer toute la carte car voir un moteur 2D rapide et ralentir le projet pour les déplacements n’est pas une chose envisageable. Les chars m’ont donc fait penser, par leurs agissements, à changer toute la technique de déplacement d’une surface ouvert vers une surface fermée.

7 Version finale

Au lieu de faire une recherche déjà longue en opérations pour trouver le point d’arrivée sur une surface fermée, l’algorithme garde le tile le plus proche de l’arrivée et lorsque l’on développe un tile qui s’éloigne par rapport au minimum on arrête la recherche.
Avant d’arriver à cette version beaucoup de problèmes sont survenus comme :
    -lorsque l’unité a fini de marcher, elle part tête baissée vers le point d’arrivée en traversant les surfaces fermées, les forêts, les rochers, et les bâtiments.
    -dans certaines directions le char commençait à aller sur les bases puis arriver à la quitter toujours dans la même direction, de même ils arrivaient à uitter                les surfaces fermées.