[Pathfinding] Déplacement d'unités optimisé

Bonsoir,

J'essae de développer actuellement un RTS pour une console de jeux, la SONY PSP. Je programme entièrement en utilisant le language de script LUA et un style pseudo orienté objet en utilisant les métatables.

Pour le moment, je suis assez satisfait du résultat. J'ai un générateur de terrain et de ressources correct, scrolling de map, affichage et gestion d'une mini carte, déplacement d'unités avec l'algorithme de pathfinding A-star.

Seulement voilà..C'est là que je galère un peu.
Pour le moment, lorsqu'on déplace une unité, pas de souci.Quand il s'agit dun groupe d'unités, j'ai concu le code de sorte que dans ce cas, les unités soient listées dans une queue, etr le chemin de chaque unité est calculé l'un après l'autre, afin d'éviter les lags et freezes..car la PSP dispose de peu de ressources (333 Mhz maxi pour le CPU, 32 Mo de ram dispo quand on travaille avec le LuaPlayer).

Les unités évitent donc les obstacles (ressources, arbres, batiments)..mais elle ne s'évitent pas elles même..une unité peut donc traverser une autre qui est sur son chemin.

Je pense qu'il est possible d'améliorer cela, mais comment ? Je souhaiterais notamment pour le déplacement groupé, un seul chemin soit calculé, et que toutes les unités suivent ce chemin. Quel algorithme appliquer ? et comment faire en sorte qu'un unité soit un obstacle permanent pour une autre, sans générer pour autant trop de calculs...?

Merci par avance..S'il est nécessaire de détailler comment j'ai implémenter mon A-star, faites le moi savoir. :P

Hi, pour l’entre croisement des unités il suffit de les considérer comme étant des obstacles une méthode update qui considère l’état des lieux, je veux dire par là que le chemin pour chaque unité est défini, et à supposé que dans un état « i » l’unité « u1 » a un voisinage « V » pour toutes unité « u appartenant a V » qui s’entrecroiserait avec l’unité « u1 » à l’état « i+1 » tu appliques un petit algorithme de circonstance le choix ici est très grand.

Pour les chemins, quand tu sélectionne un ensemble d’unités il suffit de calculer le chemin juste pour l’une d’elles, ensuite tu déplace non pas unité par unité mais le bloc en entier, en gardant les distance (la symétrie).

Bonsoir et merci pour ce début de réponse...
hélas, je n'ai pas très bien compris la première partie de la réponse...
Ou alors ce que j'en ai compris ne me conviens pas trop, ça demande un peu trop de calculs...

J'ai une approche de solution, qu'en pensez vous ?
L'idée, c'est de considérer qu'une unité parfaitement immobile est un obstacle. Dès qu'elle se met en mouvement, elle n'est est plus un.
Ce qui est intéréssant, ç'est que cela permet en quelques itérations de mettre à jour la table de collisions suivant que l'on prend en considération QUE les unités immobiles...

Pour le déplacement groupé, ce que tu me proposes est assez général....En fait, il va y avoir un problème lors des traversés des zones étroites..Si la largeur du bataillon est supérieur au passage offert, alors ça risque de cailler...

De meilleures idées ? ou des liens ? merci!