[TUTO] - La technique mailbox

[hackotedelaplaque]

La technique "Mail Box"
Inventée par Bob Hyatt, hommage à lui


Application :

Jeux de stratégie sur plateaux, maps.


Principes Généraux :


Elle permet de stocker dans un tableau unidimensionnel (pour faire snob) une matrice habituellement à deux entrées.
Un jeu de plateau ou une map sont généralement constitués de "cases". Les cases de l'echiquier ou l'emplacement des tiles.
L'écran ou le plateau de jeu est composé par la succession de ces cases/tiles.

Origine
----------------------------------------------------->x
| case 1 | case 2 | case 3 | case 4 | case 5|
| (0,0) | (1,0) | (2,0) | (3,0) | (4,0) |
|------------------------------------------------------
| case 6 | case 7 | case 8 | case 9 | case10|
| (0,1) | (1,1) | (2,1) | (3,1) | (4,1) |
|------------------------------------------------------
| case11 | case 12 | case 13| case14 | case 15|
| (0,2) | (1,2) | (2,2) | (3,2) | (4,2) |
|------------------------------------------------------
| case 16 | case 17 | case 18| case 19|case 20|
| (0,3) | (1,3) | (2,3) | (3,3) | (4,3) |
|------------------------------------------------------
| case 21 | case 22 | case 23 |case 24 |case 25|
| (0,4) | (1,4) | (2,4) | (3,4) | (4,4) |
|------------------------------------------------------
V
Y

Pour représenter l'échiquier, on peut travailler sur les coordonnées pures x et y.

Mais on imaginera volontiers l'utilisation d'un tableau à 2 dimensions, la 1ère correspondant à la position sur la ligne, la seconde à la position sur la colonne.

Ainsi pour reprendre l'exemple si dessus.

Soit un tableau Mon_echiquier(ligne,colonne).
La case 1 correspond à Mon_echiquier(0,0).
La case 2 à Mon_echiquier(1,0).
La case 7 à Mon_echiquier(1,1).

La Section Data ressemblerait à ça :

Code : Tout sélectionner

Data.b 0,0 1,0 2,0 3,0 4,0
Data.b 0,1 1,1 2,1 3,1 4,1
Data.b 0,2 1,2 2,2 3,2 4,2
Data.b 0,3 1,3 2,3 3,3 4,3
Data.b 0,4 1,4 2,4 3,4 4,4

Pour gérer les déplacements, on travaille sur les deux vecteurs "ligne" et colonne".
Ainsi un déplacement d'une case à droite équivaut à [+1,+0].
Un déplacement de deux cases vers le haut équivaut [+0,-2].
Une diagonale d'une case, vers le haut et la gauche à [-1,-1].

Très logique en fin de compte……mais très vite complexe à manipuler à l'usage et source d'erreurs. Sans compter qu'un tableau à 2 dimensions consomme plus de ressources qu'un tableau à entrée unique (même si cet argument prévaut moins à l'heure de nos PC flambants- sauf le mien…-).


L'alternative : un tableau unidimensionnel.

Avec cette astuce, le même echiquier (ou map) peut être stocké dans un tableau à entrée unique.
On n' appréhende plus la case de cette façon :
Mon_echiquier(position_sur_la_ligne,position_sur_la_colonne)

Mais :

Mon_echiquier(index de la case).

Origine
-----------------------------------------------------x
| case 1 | case 2 | case 3 | case 4 | case 5|
| (0) | (1) | (2) | (3) | (4) |
|------------------------------------------------------
| case 6 | case 7 | case 8 | case 9 | case10|
| (5) | (6) | (7) | (8) | (9) |
|------------------------------------------------------
| case11 | case 12 | case 13| case14 | case 15|
| (10) | (11) | (12) | (13) | (14) |
|------------------------------------------------------
| case 16 | case 17 | case 18| case 19|case 20|
| (15) | (16) | (17) | (18) | (19) |
|------------------------------------------------------
| case 21 | case 22 | case 23 |case 24 |case 25|
| (20) | (21) | (22) | (23) | (24) |
|------------------------------------------------------
V
Y


L'accès aux cases est d'autant plus facile puisqu'il suffit de connaître un index et non plus deux vecteurs.

La DataSection serait alors simplement :

Code : Tout sélectionner

Data.b  0 , 1 , 2 , 3, 4
Data.b  5 , 6 , 7 , 8, 9
Data.b 10,11,12,13,14
Data.b 15,16,17,18,19
Data.b 20,21,22,23,24

La gestion des déplacements :

On retrouve les mêmes règles logiques, en plus simple :

Pour aller sur la case de droite ? Index+1
La case de gauche ? Index –1
En haut ? Dans le cas ci-dessus index –5
En diagonale Bas gauche ? Index +4.

Oui mais………

Il existe des déplacements aberrants :
Si je suis sur la case 5 et que je me déplace d'une case à droite selon la méthode décrite plus haut, je sors du plateau de jeu (cf schema plus haut). Pourtant le programme lui me renverrait que ma pièce ou mon sprite atterrit …sur la case 6 ??!! Aberrant !!!

Il nous faut donc prendre en charge ces exceptions.
Et rassurez vous c'est tout bête grâce à la technique mail box !

Vous avez du courrier :

La solution consiste à utiliser un tableau que j'appellerai "tableau de transposition" (ne décrochez pas, ce n'est pas si complexe).

On utilise la valeur –1 pour marquer les exceptions.

Voici mon nouveau data section :


Data.b -1, -1, -1, -1, -1, -1, -1 ;
Data.b -1, -1, -1, -1, -1, -1, -1 ;
Data.b -1, 1, 2, 3, 4, 5, -1 ;
Data.b -1, 6, 7, 8, 9,10, -1 ;
Data.b -1,11, 12, 13,14,15, -1 ;
Data.b -1,16, 17, 18,19,20, -1 ;
Data.b -1,21, 22, 23,24,25, -1 ;
Data.b -1, -1, -1, -1, -1, -1, -1 ;
Data.b -1, -1, -1, -1, -1, -1, -1 ;

(Pour l'histoire, ceci ressemblerait à une boîte à lettres, d'où le nom de la technique).

Nous appellerons ce tableau MailBox() (mais vous pouvez choisir cde l'appeler LadyDi si vous préféreez)

Notez qu’au milieu de tous ces « -1 » on retouve la structure de notre echiquier avec nos cases de 1 à 25 (Attention à votre définition du point de départ, 0 ou 1. Une source d'erreur très fréquente).

Il nous reste à reprendre le tableau de 5x5 qui représente notre echiquier près transposition au moyen de la boite aux lettres.

Code : Tout sélectionner

  
  Data.b 15, 16, 17, 18, 19
  Data.b 22, 23, 24, 25, 26
  Data.b 29, 30, 31, 32, 33
  Data.b 36, 37, 38, 39, 40
  Data.b 43, 44, 45, 46, 47

D’où sortent ces chiffres ? C’est très visuel, comparez avec Mailbox() et vous allez comprendre.
Dans la boîte aux lettres, le 15ème élément à la valeur 1. La numérotation de nos cases commence donc à 15.
La case 23 correspond elle au 46ème élément de la boîte aux lettres.
Etc.… Vous avez pigé le truc.

Oui mais à quoi ça sert ?

Reprenons notre exemple de "déplacement impossible".

La pièce sur la case 5 ne peut pas se déplacer à droite car elle a atteint le bout de l'échiquier.

On va donc interroger Mailbox(mon_echiquier(19+1)). [Rappel la 5ème case vaut 19 comme on vient de le voir].Autrement dit, quelle valeur me renvoie l'élément du tableau Mailbox à la position ma_case+1
Que constate-t-on ? Que MailBox(20)= -1 !! Le déplacement est impossible !

Autre exemple :
On va considérer un coup qui lui est autorisé.
Aller de la case 12 à la case 7. Soit un déplacement de 1 case en haut.
Que renvoie mailbox(mon_echiquier(30-7)) ? 7 !
Le coup est bien légal car la valeur renvoyée est bien celle de la case d'arrivée !

Essayez d’autres cas de figures pour vous en convaincre.


Conclusion :
Vous voyez tout l'intérêt de cette méthode pour la manipulation de ce type de données.
Je vous assure qu’on gagne un temps monstrueux ! La seule difficulté consiste à établir la boîte mail et transposer les valeurs (là il ne faut pas se louper). Mais vous le faites une fois pour toutes et après la marge d’erreur est nulle !!

J'espère ne pas avoir été trop rébarbatif et que ce tuto vous aura accroché jusqu'au bout.
Désolé aussi pour les schémas et les datasections qui sont pas super bien alignés au final...

J'ai poussé les exemples dans le champs qui m'intéressait personnellement (les jeux de plateaux) mais les applications ne se limitent évidemment pas à ce genre.

N'hésitez pas à m'interroger sur le sujet, j'ai eu l'occasion de bien en faire le tour avec mon PureMarel.

[Crystal Noir]

Très intéressant va falloir que je fasse quelques essais sur un projet test

[Backup]

cette technique est aussi employé pour les jeux de plateau
on évite des calcul de collision, parce que chaque déplacement du personnage
correspond a un déplacement dans les data

et s'il rencontre "-1" (dans ton exemple) , il cogne contre un mur !!

le plus dur etant de faire correspondre les tile du décors du sprite avec les Datas !!

c'est une légère variante, mais le principe reste le même

Merci pour ce petit mémo !

[Anonyme]

juste une remarque sur les tableaux à une entrée , ( ce que j'écrit est valable aussi pour les zones mémoire obtenu avec allocatememory() )


Si je veut representé se genre de tableau :

Map.l(10,10)

en

Dim Map.l(10*10)

10*10 c'est pour l'exemple, mettez directement 100


il n'est pas facile de choisir une coordonée en X & Y pour se déplacé dedans
pourtant une méthode simple est éfficace fonctionne,

Admettons que nous voulons modifié la valeur de la ligne 5 et de la colonne 3
on ne peut pas faire Map(5,3) car c'est un tableau à une dimension

Premierement, on sait donc que

Code : Tout sélectionner

X=5
Y=3

alors pour connaitre l'index qu'il faut modifier on procède comme cela :

Code : Tout sélectionner

Index = (Y*10)+X

10 car notre plateau à une largeur de 10

Ensuite pour modifier notre tableau à une dimension on fait donc comme cela :

Code : Tout sélectionner

Dim Map(100)  ; Déclaration du tableau
*Ptr = @Map() ; Récupération de l'adresse du tableau
PokeL(*Ptr + (5*4) + 10 * (3*4),255) ; Ecriture de 255 en X=5 & Y=3

Voici le détail de la dernière ligne de code

- *Ptr , c'est l'adresse du tableau
- (5*4) , le 5 represente le X , le 4 la taille de la donné a modifier , ici un long
si c'etait un byte, cela aurait donné (5*1) , un quad : (5*8) , etc...
- le 10 reprensente la longueur d'une ligne
- (3*4) représente les y et 4 un long.

j'espère avoir été clair

Voici aussi un code pour un tableau & une structure :

Code : Tout sélectionner

Structure Map_Info
  *Sprite.l
  Position_X.f
  Position_Y.f
  Flag.b
EndStructure




Dim Map.Map_Info(100)
*Ptr = @Map()


X = 5
Y = 3


Sprite_Address         = (*Ptr + (X*SizeOf(Map_Info)) + 10 * (Y*SizeOf(Map_Info)))
Position_X_Address     = (*Ptr + (X*SizeOf(Map_Info)) + 10 * (Y*SizeOf(Map_Info))+4) ; on décalle en fonction du type de variable par rapport à la structure...
Position_Y_Address     = (*Ptr + (X*SizeOf(Map_Info)) + 10 * (Y*SizeOf(Map_Info))+8)
Flag_Address           = (*Ptr + (X*SizeOf(Map_Info)) + 10 * (Y*SizeOf(Map_Info))+12)


PokeL(Sprite_Address      ,1)
PokeF(Position_X_Address  ,150)
PokeF(Position_Y_Address  ,250)
PokeB(Flag_Address        ,1)


Index = (Y*10)+X

Debug Map(Index)\Sprite
Debug Map(Index)\Position_X
Debug Map(Index)\Position_Y
Debug Map(Index)\Flag

cela fonctionne très bien avec des zone mémoire aussi
en esperant avoir été compréhensible

[hackotedelaplaque]

Premierement, on sait donc que

X=5
Y=3

alors pour connaitre l'index qu'il faut modifier on procède comme cela :

Code : Tout sélectionner

Index = (Y*10)+X 

Empiriquement je ne trouve pas ça mais :

Code : Tout sélectionner

Index = (Y*10)+X-10

Où 10 est naturellement la largeur du tableau.

Très pratique pour trouver l'index en tout cas. Je l'ignorais.

Pour la 2ème partie avec tous ces affreux pointeurs et autres poke , j'ai besoin d'avoir PB sous les yeux pour bien assimiler, je verrais ce soir.

cette technique est aussi employé pour les jeux de plateau
on évite des calcul de collision, parce que chaque déplacement du personnage
correspond a un déplacement dans les data

Exact. J'envisage d'ailleurs un projet de Plate formes en utilisant ce principe.

[Anonyme]

Empiriquement je ne trouve pas ça mais :

Code:
Index = (Y*10)+X-10

Bah, admettons alors que tu veut modifier la case 1,1 de ton tableau

cela fait donc
(1 * 10) + 1 - 10 = 1

alors que c'est le 11° élément qui represente la case en 1,1
dans un tableau le zero compte aussi

Map(0,0) = 1° element
Map(1,1) = 11° element sur un tableau d'une taille de 10

[hackotedelaplaque]

(Attention à votre définition du point de départ, 0 ou 1. Une source d'erreur très fréquente).

Et c'est même moi qui l'avais dit !

Toutes mes excuses.

[kerkael]

Hello,

Pourquoi sur la première ligne de la mailbox on trouve une rangée de -1 supplémentaire, ainsi qu'à la fin ?
Est-ce que ça marche aussi bien sans ces 2 lignes ?