sorte de pathfinding

[blendman]

salut

Pour un jeu, j'ai besoin d'un système de pathfinding très rapide et simple, car je compte l'utiliser pour le personnage principal, ainsi que pour ses compagnons (4) et les ennemis. Donc, je cherche une technique vraiment très optimisée et rapide.
Donc, j'évite les classiques A* qui sont beaucoup trop gourmands dès qu'on a 25 personnages qui cherchent le chemin en même temps ^^.

J'ai donc pensé à plusieurs techniques, dont un système de chemin qui longerait les blocks collisions.
Voici en gros ce à quoi je pensais :


Le personnage doit aller à l'endroit de la cible bleue.
1ère possibilité : trouver le chemin vert : longer les block collisions (ici les rectangles rouges).
2ème possibilité : trouver le chemin mauve (ça me semble plus complexe)

Qu'en pensez-vous ? Avez-vous de meilleures suggestions ou des techniques vraiment très rapides ?

Merci.

[comtois]

Solutions que je n'ai jamais mises en oeuvre mais qui semblent fort prometteuses :

pathfinding à l'aide QuadTree
WayPoints pathfinding

[comtois]

et j'avais fait un quadTree ici

[Fig]

J'ai déja fait un pathfinding HpA* (hierarchical pathfinding) et précédemment un pathfinding avec quadtree. (ça a été ma première tentative de réduction d'espace)
Dans tous les cas tu dois te servir de l'algo A* même si le graph de recherche est réduit par ces techniques.
Le pathfinding le plus rapide est par triangulation (TRA*) mais celui-ci je ne l'ai pas essayé. (je trouve la construction de l'abstraction trop compliqué pour moi qui travaille avec une grille et non en 3d)
Il y a aussi le POV* qui peut être intéressant dans ton cas. (on place des points qui peuvent être reliés en ligne droite: ils peuvent voir)

A* est bien assez rapide pour ton jeu s'il est codé correctement même sans utiliser ces techniques. (il faut se poser des questions: quel est la taille de la carte de mon jeu, quel longueur de pathfinding est exigé, est il besoin d'un pathfinding cooperatif ou est ce que le simple évitement des unités entre elles est suffisant etc...)

Mais tu ne trouveras pas un pathfinding "facile" qui sait éviter les obstacles à moins d'utiliser des chemins déjà pré calculés.

[blendman]

Mais tu ne trouveras pas un pathfinding "facile" qui sait éviter les obstacles à moins d'utiliser des chemins déjà pré calculés.

Je pensais aussi m'orienter vers cette solution :
1) prévoir plusieurs type de block collision :
- rouge : des blocks qui empêchent de passer et qu'on ne peut pas contourner (mais qu'on peut éventuellement longer), par exemple un mur, sauf pour le dernier élément qui serait lui un block bleu (élément de "sortie", comme une porte)
- bleu : ce sont soit des block seuls (qu'on peut contourner) soit un block terminant un mur (le dernier de la rangée, qu'on peut contourner par la droite, la gauche, le haut ou le bas (ou une diagonale))
2) prévoir une sorte de chemin pré-calculés que je pourrais poser par moi-même. Mais cela signifie que le chemin ne pourrait pas être modifié et tout le monde empruntera le même (ou quasiment le même), ce qui n'est pas gênant.

Là, j'essaie de trouver une solution simple pour que chaque personnage prenne le chemin ^^.