salut a tous,

Pour mon jeu de gestion j'utilise un système d'ia a la dwarf fortress ou prison architect mais j'ai un probleme lors de l'attribution des task, par exemple quand je demande a un ouvrier de construire quelque chose il prend la task dans une pile FIFO, vérifie si elle est accessible et si elle l'est l'effectue, tout cela fonctionne quand la task inaccessible se trouve entouré, sauf que quand elle est en plein milieu de la map et que c'est l'ia qui est entouré la recherche d'accessibilité fait perdre énormément de FPS

voici ma fonction de vérification : http://pastebin.com/Gxs4Xn5X

je sait d’où viens le problème, la map fait 100x100cases et donc elle doit parcourir toutes les cases du vector, j'aimerais donc savoir si vous ne savez pas comment régler ou optimiser ce calcul voir si vous ne connaissez pas une meilleurs manière de vérifier l'accessibilité d'une case ?

merci d'avance pour toutes aide ^^

Hello

Je pense que ton problème vient de la logique de ton algo et non de la façon dont tu l'a fait en C++ (enfin quoique, tu utilise des vecteurs, des lists, des erases, .... Ca fait beaucoup d'allocation dynamique de mémoire, c'est pas optimisé, mais bon peu important sur un PC puissant, c'est correct).
Tu dis devoir tester toutes les cases de ta "map". Mais peut être qu'il n'est pas nécessaire de tout vérifier, peut être faut il juste tester une zone.

j'utilise des vector pour pouvoir stocker une map qui n'a pas de taille pré-defini, mais si tu pense que je devrais utiliser des tableau rien ne m’empêche de changer, c'est l'affaire de 5minutes ^^

J'avais justement deja pensé a limiter le calcul uniquement dans une zone mais si la case de construction est comprise dans une grandes zone fermé ça provoquerais un freeze a force de forcer l'ia a chercher le chemin, j'ai aussi pensé a limiter la distance par rapport a l'ia avant de lancer le calcul mais si l'ia traverse toute la map pour au final avoir un bloque inaccessible ça me parais accès chiant

si quelqu'un sait comment fait l'ia de Dwarf fortress ou de prison architect pour la vérification de ses task ce serais sympa ^^

Salut,

Si j'ai bien compris tu veux tester si il est possible d'aller d'un point A à un point B sur une map rectangulaire où certaines cases sont interdites d'accès?

Le probème est ta variable alreadySee, tu pourrai la remplacer par une map parallèle où chaque case est un booleen qui permet de savoir si tu est déja passé, ton algo aurai alors une complexité O(n) au lieu de O(n²).

Ensuite si c'est toujours trop lent et que le fait qu'une case change d'accessibilité n'est pas trop fréquent tu peux cacher les résultats en associant à chaque case de la map un id partagées par toutes ses cases connexes, tu mets à jour ces ids lorsqu'un chemin se ferme sur la map. Il faut alors juste tester si map[position].id == map[startPosition].id.

Utiliser un seul vector(en l'encapsulant dans une classe Matrix par exemple) pourrait être légèrement plus efficace qu'un vector de vector.

Enfin tu pourrai éviter les tests du genre (position.y-1 > -1) en entourant la map d'un bordure de cases innacessibles.

"si quelqu'un sait comment fait l'ia de Dwarf fortress ou de prison architect pour la vérification de ses task ce serais sympa ^^"

==> Tu limite la question à ceux qui connaissent ces jeux. Pourquoi pas, mais ne t'attends pas à avoir beaucoup de réponses.

Tu as aussi notre forum voisin "programmation" ou tu auras surement plus d'aide.

Bon j'ai pas lu ton code et je n'ai jamais joue a dwarf fortress donc je suis peut-etre totalement a cote, mais si c'est lie au pathfinding, as tu regarde du cote des algorithmes existants comme le A* par exemple?
Voila le lien wikipdedia:
http://en.wikipedia.org/wiki/A*_search_algorithm

ben quand je dit dwarf fortress ou prison architect ce sont des exemple qui me semble le plus proche de ce que je désire, mais tout les STR doivent avoir un système de ce type pour vérifier que le bâtiment a construire n'est pas bloqué

Hyrul -> c'est ça, par contre le calcul n'est pas lent quand l'objet est bloqué c'est quand le contraire ce produit (l'ia qui est coincé) que le programme regarde toutes les cases de la map (100x100 donc un gros paquet) et c'est ça qui prend du temps (il faut plusieurs secondes avant qu'elle n'aboutisse a ce que la case soit inaccessible)

voila le résultat du calcul avec le temps effectué pour : http://img15.hostingpics..net/pics/646017Sanstitre1.png

pour le moment j'ai trouvé une solution temporaire, j’empêche le calcul d'aller a plus de x case + différence entre la position de départ et d'arrivé ce qui empêche le calcul d'aller chercher complétement a l'opposer de l'ia

"érifie si elle est accessible et si elle l'est l'effectue, tout cela fonctionne quand la task inaccessible se trouve entouré, sauf que quand elle est en plein milieu de la map et que c'est l'ia qui est entouré la recherche d'accessibilité fait perdre énormément de FPS "

En français ça donne quoi?

si tu prenais tout le paragraphe c'est compréhensible :

"il prend la task dans une pile FIFO, vérifie si elle est accessible et si elle l'est l'effectue"

donc l'ia prend une task dans une pile FIFO, vérifie si elle est accessible et effectue cette tâche si il peut l'atteindre, si la tâche est entourer l'algorithme fonctionne normalement et indique que la case est inaccessible mais quand c'est l'ia qui est entouré de casse interdit l'algorithme cherches toutes les cases et fait perdre énormément de fps.