Discussion :

[Yoratheon]

Bonjour à tous,

Je travaille sur un projet de jeux sur une grille 2 d. Lors de l'initialisation de la partie, je dois placer des joueurs sur la grille de jeux. Je souhaiterais que chaque joueur se trouve à égale distance de sont voisins précédents et suivants. La grille est carrée de coté G. Il y a entre 2 et N joueurs.

Je bloque totalement sur l'algorithme permettant de calculer la distance à laisser entre chaque joueur.

Si quelqu'un à une solution ou des pistes, je suis preneur.


Cordialement,

Yortheon

[tbc92]

En général, dans les jeux sur grilles, on ne parle pas de la distance classique (appelée distance euclidienne par les matheux) mais d'une autre distance, obtenue avec une autre formule, et qu'on appelle en générale distance de Manhattan (J'aime beaucoup ce nom).
Recherche "distance de Manhattan" sur Google, tu devrais trouver ton bonheur.

[Yoratheon]

J'ai vite fait vue cette distance en cours de cluster, je vais me pencher dessus.

Merci.

PS : je posterais si je trouve la solution (ou non).

[Yoratheon]

J'ai finalement trouver une solution, en m'inspirant de la distance de Manhattan.

Notons g la taille de la grille et j le nombre de joueurs.

La bordure extérieur de la grille noté s est égale à :

Code :

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

4 * g - 4

La distance optimal est donc :

Code :

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

(s - j) / j

Attention tout de même car la valeur retourné n'est pas toujours entière.

L'idéal est donc d'obtenir l'arrondi à l'entier le plus proche.

Voici le calcul de la distance optimal en pseudo code (avec comme distance minimal 2) :

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
 
fonction obtenirDistanceOptimal(g:entier, j:entier): entier
    surface, max, distanceOptimale : entier
 
    surface = 4 * g -4
    max = surface-j
    distanceOptimale = arrondi( max / j )
 
    si ( distanceOptimale < 2 ) alors
        retourne 2
    fin si
 
    si ( (surface-max > distanceOptimale) ET (j*(distanceOptimale + 1) <= (max)) ) alors
        retourne distanceOptimale + 1;
    fin si
 
    retourne distanceOptimale
fin fonction

Et pour ceux que cela intéresse, voici l'algorithme permettant de placer ces joueurs sur la grille avec la distance optimal :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
distanceOptimale, max, x, y : entier
grille[][] : Joueur // Type à adapter suivant le besoin
 
distanceOptimale = obtenirDistanceOptimal(tailleDeLaGrille, nombreDeJoueur)
max = tailleDeLaGrille - 1
 
pour j allant de 1 à nombreDeJoueur, faire
    si ( x <  max ) alors
        si ( y < max ) alors
            si (y > 0) alors
                x -= distanceOptimale +1
 
                si ( x > max ) alors
                    y += x - max
                    x = max
                sinon si ( x < 0 ) alors
                    y += x
                    x = 0
                fin si
            sinon
                x += distanceOptimale + 1
 
                si ( x > max ) alors
                    y += x - max
                    x = max
                fin si
 
        sinon
            x -= distanceOptimale +1
 
            si ( x > max ) alors
                y += x - max
                x = max
            sinon si ( x < 0 ) alors
                y += x
                x = 0
            fin si
        fin si
    sinon si ( y < max ) alors
        y += distanceOptimale +1
 
        si ( y > max ) alors
            x -= y - max
            y = max
        fin si
    sinon
        x -= distanceOptimale+1
    fin si
 
    grille[x][y] = nouveau Joueur()
fin pour

Voilà, en espérant que ce soit utile à d'autre également