Discussion :

[Mindiell]

Sujet : Tower Defense
Map :
_ map vide
_ zone entree - zone sortie
_ murs sur la map ( zones constructibles pour les tours)

Donc en fait, c'est pas vraiment un labyrinthe .. juste qu'il y a des murs où je n'est pas le droit de passer dessus pour trouver mon chemin ...

Bah moi je te dirais bien de partir directement vers la zone de sortie, et si tu rencontres un mur (une tour), tu le contournes, puis tu reprends ton chemin.

Ce qui m'étonne c'est que ta map ne correspond pas du tout à un tableau. Qu'as-tu déjà fait ?

[acx01b]

salut j'avais fait un dijkstra dans un tableau (en 4-connexité):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void calc_chemin (Int i1, Int j1, Int i2, Int j2, Int v) {
    // si on est en dehors du tableau
    if (i1 == 0 || (i1 == maxi-1) || j1 == 0 || j1 == maxj-1) return ;
    // on met en (i1,j1) le poids v
    _matrice[j1][i1] = v;    
    v++; // on incrémente directement le poids
    if (i1 == i2 && j1 == j2) return ; // on est arrivé ! départ = arrivée
    // si le poids déja dans la case d'à côté est plus grand que le poids avec lequel on va y arriver, alors on y va
    if (v < _matrice[j1+1][i1] || _matrice[j1+1][i1] == 0) 
        calc_chemin (i1, j1+1, i2, j2, v);
    if (v < _matrice[j1-1][i1] || _matrice[j1-1][i1] == 0)
        calc_chemin (i1, j1-1, i2, j2, v);
    if (v < _matrice[j1][i1+1] || _matrice[j1][i1+1] == 0)
        calc_chemin (i1+1, j1, i2, j2, v);
    if (v < _matrice[j1][i1-1] || _matrice[j1][i1-1] == 0)
        calc_chemin (i1-1, j1, i2, j2, v);
}
 
/* on initialise à +infini toutes les cases vides du labyrinthe
on met -1 pour les murs 
puis on appelle dijkstra
*/
calc_chemin (xdepart,ydepart,xarrivee,yarrivee, 1);

[nicodn02]

ba en fait .. pour le calcul du chemin:
je pars d'une des zones d'entrées .. et je trouve un chemin (le plus court si possible) jsuqu'à une des zones de sorties, en évitant les murs
Autrement dit, sur la map :
_lieux de départ
_murs
_lieux d'arrivée

[Aszarsha]

Une technique assez simple, qui a été de très nombreuses fois éprouvée, est celle des points de contrôle.

Si tu n'as accès à la carte qu'une fois le programme lancé, il te faudra le calculer de manière automatique... Il y a quelques algorithmes assez efficaces (spacial partioning est le terme anglais si tu compte chercher). Perso, te conseillerais simplement de quadrier la carte puis d'élaguer les surplus, à la manière "marching cube" en 3d, de sorte à en avoir très peu dans les grands espaces et un maximum dans les petits espaces.
Tu n'as qu'à ensuite calculer la distance entre chaque points.
Dans tous les cas, c'est bien évidement à faire offline, c'est à dire lors de la sauvegarde de la carte (si tu y as accès), soit lors du chargement.

Il ne te restera qu'à effectuer un A* avec une heuristique (distance direct du point de contrôle le plus proche à un autre) extrêmement proche de l'heuristique optimale, donc particulièrement efficace.

Pour prendre en compte les obstacles, si tes points de contrôle sont correctement placés, c'est à dire de manière à former des lignes directes (si tu veux t'amuser, tu peux les relier par des splines... ) l'occlusion sera très facile à déterminer à l'exécution. C'est en plus une méthode très efficace dans le cas d'ajouts d'obstacles permanents, puisqu'il suffit alors de supprimer l'arrête reliant deux nœuds. En cas d'ajouts de nouvelles surface sur lesquels se déplacer, il suffit de modifier localement le graphe ; ça se fait également très simplement.


De manière plus avancée, tu pourras de plus optimiser ça avec :
- un regroupement des unités proches d'un point de contrôle et le calcul du chemin le plus court pour le groupe entier (à utiliser sur les grande "avenues", et les graphes à faible connexité)
- un système de programmation linéaire de type flot à coût minimum, pour déplacer un flot équivalent au nombre d'unité du point de contrôle le plus proche vers le point cible (à utiliser dans les petites "rues" et les graphes à forte connexité)
- un système de LoD sur le graphe des points de contrôle et de manière plus poussé un système hiérarchique par zones

Si il faut considérer le fait qu'un simple agent est une occlusion pour un autre, je voterais soit pour leur regroupement, ou pour un système de flocking behavior.

[benDelphic]

j aimerai bien voir un exemple pour mieux raisonner
voici un labyrinthe ... comment va tu coder ta matrice ?

[nicodn02]

mon labyrinthe sera coder comme sa .. en représentation visuel , sur un tab [][]:

|E|E|-|-|-|-|-|-|-|-|
|E|E|-|-|-|-|-|-|-|-|
|-|-|-|-|-|-|-|-|-|-|
|-|-|X|X|-|-|-|-|-|-|
|-|-|X|-|-|-|-|-|-|-|
|-|-|X|-|-|-|-|-|-|-|
|-|-|X|-|-|X|X|-|-|-|
|-|-|-|-|-|-|-|-|-|S|
|-|-|-|-|-|-|-|-|-|S|
|-|-|-|-|-|-|X|X|X|-|
|-|-|-|-|-|-|-|-|-|-|

où E : zone d'entrée (les créatures apparaisseront surement directement en tab[1][1]
S : zone de sortie (dès qu'une créature est sur une zone de sortie elle disparait)
X : mur

Aszarsha:
je ne comprend pas vraiment ce que tu viens de me dire --"

[Aszarsha]

En gros, ce que je te conseil, c'est de quadriller intelligemment la carte en waypoints (puisque apparemment elle peut être potentiellement grande), puis de faire des A* dessus.
Pour la gestion des occlusions, il me semble que c'est clair.
Une fois que tu aura ce système de fonctionnel, tu devrais ensuite étiqueter chaque arrête avec sa capacité (comme une débit dans des tuyaux) de manière à simuler un flot (d'unités par exemple).

Pour des détails, voir le message précédent.