Modélisation de pieces de jeu

Version imprimable

26/05/2007, 10h58
Davidbrcz

1 pièce(s) jointe(s)

Modélisation de pieces de jeu

Bonjour a tous.
Je souhaité crée une version informatique du jeu Blokus.

J'ai déja quasiment toutes la conception du logiciel sur papier.

Par contre , je bloque sur un point.
La répresentation des pieces.

En effet les pieces sont toutes différentes et cela ne ma facilite pas la tache.
Je pense donc pour modeliser les pieces a une classe Piece qui contiendrai en autre un tableau représentant la position des carrés de la piece par rapport a un carrée de référence.

Exemple :
La piece est la suivante : http://www.developpez.net/forums/att...1&d=1180169997

Le carré de réference est celui en haut de la colone(avec le point rouge).
La tableau de la piece serait:
{(0;0),(0;-1),(0;-2),(1;-2),(2;-2)}

Est ce une bonne idée ?

Merci.
26/05/2007, 12h32
pseudemys

Bonjour,

je ne connais pas le jeu Blokus, donc je risque de répondre un peu à côté; je m'en excuse d'avance...

Bref, j'ai eu l'occasion de coder un truc similaire qui se rapproche du katamino. En gros tu as des pieces 2D que tu veux poser dans un support qui en contient déja.
La question est: comment représenter les pièces 2D pour vérifier de manière efficace quelles s'emboitent ou se superposent ?
Mon expérience à montré qu'une simple matrice de bit (donc tableaud'entiers) était la solution la plus efficace. Du coup quelques "et" sont suffisants pour vérifier si tu peux ou pas emboiter ta pièce.
L'autre avantage est que les symétries et rotations sont très faciles à calculer.

Ton exemple donne: { 4, 4, 7 }

NB: si tu as des pièces grosses tu peux utiliser gmp.
++
26/05/2007, 12h45
Davidbrcz

Tout d'abort ,merci de ton aide.
Ensuite pour connaitre blokus : Wikipedia

Pour l'histoire de la matrice , tu me conforte dans mon idée de départ mais ne vois pas ce que réprésente le tableau {4 4 7}.

Enfin pour les transformation matriciel ,quelqu'un pourrait me donner son cours de maths :D ? Merci.
26/05/2007, 14h33
pseudemys

4 en binaire donne 100
donc ça fait une matrice:
100
100
111

l'avantage est qu'avec des décallages et des "et" binaires tu peux vérifier si tu peux ajouter une pièce ou pas. Du point de vue du temps de calcul c'est vraiment très intéressant.
26/05/2007, 14h41
Davidbrcz

Je ne savais pas que 4 en binaire équivalait a 100.
Ah bas oui ca prend tout son sens.

Il ne me reste plus qua trouve un moyen de manipuler des tableaux de bit en C++.
Sinon je suis bon pour les tableau d'int.
26/05/2007, 16h24
pseudemys

tu risques d'avoir besoin de grand entier. La librairie gmp (http://gmplib.org/) est faite pour ça.

pour les opération sur les bits c'est là: http://gmplib.org/manual/Integer-Log...-Fiddling.html
http://gmplib.org/manual/Low_002dlevel-Functions.html
26/05/2007, 16h48
Davidbrcz

Euh , non ; je ne pense pas.
Pourquoi aurais-je besoin de grand entiers ?
Les pieces les plus grande sont les Pentamino

Je ne pense donc pas avoir besoin de grand entiers.

Edit : je bloque sur un autre point est la rotation des pieces.
Comme les piece vont etre représenté par une matrice cela a revient a faire de la rotation matricielle.
Je n'ai quasiment aucune connaisance dans ce domaine mais d'apres mes recherches , une matrice de rotation dans le plan d'angle X est :
x'= [ cos X -sin X ]*x
y'= [ sin X cos X ]*y

Il faut donc que je multiplie chaque chaque point par cette matrice , n'est ce pas ?

PS: pour les lien sur gmp , l'anglais et moi ca fait 1.5.
27/05/2007, 09h20
PRomu@ld

Citation:

tu risques d'avoir besoin de grand entier. La librairie gmp (http://gmplib.org/) est faite pour ça.

pour les opération sur les bits c'est là: http://gmplib.org/manual/Integer-Log...-Fiddling.html
http://gmplib.org/manual/Low_002dlevel-Functions.html

D'après ce que j'ai pu lire, la grille de jeu fait 400 cases, au pire, 400 int, c'est réelement négligeable.

Citation:

Il faut donc que je multiplie chaque chaque point par cette matrice , n'est ce pas ?

En fait, ce que tu donnes, c'est une rotation par rapport à l'origine du repère our lorsque tu vas faire une rotation d'une pièce, la rotation devrait se faire par rapport au centre de la pièce. Un changement de repère pourra t'aider.

En théorie, c'est parfait, mais dans la pratique, ça n'est peut-être pas utile d'une part avec l'utilisation des cosinus et des sinus va t'entrainer des arrondis qui on ne sait jamais vont t'entrainer des problèmes.

Le mieux est de faire une fonction qui à partir d'une pièce dans n'importe quelle position effectue la rotation de 90° et à partir de celle ci, tu peux faire les autres rotations.
27/05/2007, 10h15
pseudemys

Si le plateau fait 20x20 = 400 cases, il faut 20 entier de 20 bits de long...Donc c'est bon ça passe.

Il est clair qu'il ne faut pas utiliser les cosinus et sinus pour faire des rotations à 90 !
Exemple: rotation à 90 sur la droite les bits(i,j) dans un carré NxN deviennent bits(j, N-i).

Sinon, j'ai pas retrouvé mon code...mais si j'ai le temps ce soir je te ferais les rotations et les symétries (tu le veux en quoi le code C, C++, Java, Scala, ...?). Je me souviens aussi que je sauvegardait pour chaque pièce toutes ces symétires et rotations pour ne pas les recalculer.

++
27/05/2007, 10h32
PRomu@ld

Citation:

Si le plateau fait 20x20 = 400 cases, il faut 20 entier de 20 bits de long...Donc c'est bon ça passe.

Non, je parlais d'utiliser directement un int dans la matrice 20x20. ça nous fais 1600 octets, c'est rien en mémoire. Tu peux faire mieux en prenant des char dans ce cas, ça fait 400 octets, mais je ne vois pas l'intérêt de passer avec des manipulations de bits. A moins que le système soit très limité en mémoire.
27/05/2007, 10h50
Davidbrcz

Nan , le systeme c'est un PC normal.
Mais il ne faut pas oublier qu'en plus du plateau de 400 int , il faut aussi mettre en memoire les 21 pieces de chaque joueur(et il peut en avoir jusqu'a 4).
27/05/2007, 10h50
pseudemys

l'intérêt c'est pas le gain en mémoire mais la vitesse d'exécution. Avec des bits tu va pouvoir comparer une ligne complète en un seul cycle d'horloge et non en N (longeur d'une ligne) * (accés mémoire + comparaison).

Pour simplifier si tu as une matrice 20x20 et que tu cherches à placer une pièce 5x5 ça donne:
- avec des entier 20 * 20 * 5 * 5 = 10 000 opérations
- des bits: 20 * 20 * 5 = 2 000 opérations

De plus, les opérations de décallage et les "et"/"ou" logiques sont des opérations qui prennent moins de temps (en général) que des oprérations entières.
Et surtout, tu gagne beaucoup de temps car tu lis beaucoup moins en mémoire, ce qui prend beaucoup de temps.
27/05/2007, 10h56
Davidbrcz

Oui.
Mais la manipulation des bit n'est pas mon fort.
De plus les rotation de bit sont des chose comme :
0001110000 ==> 0011100000

Or les rotations que je doit effectue avec les pieces sont des rotations dans le plan comme :
1 0 0 |==> 1 1 1
1 0 0 |==> 1 0 0
1 1 1 |==> 1 0 0

Et ceci , les rotation bit a bit ne me le permete pas.

(Pour info , je vais coder le jeu en C++, donc des exemple de rotation avec des cous de maths serait les bienvenue)
27/05/2007, 15h19
PRomu@ld

Citation:

l'intérêt c'est pas le gain en mémoire mais la vitesse d'exécution. Avec des bits tu va pouvoir comparer une ligne complète en un seul cycle d'horloge et non en N (longeur d'une ligne) * (accés mémoire + comparaison).

Pour simplifier si tu as une matrice 20x20 et que tu cherches à placer une pièce 5x5 ça donne:
- avec des entier 20 * 20 * 5 * 5 = 10 000 opérations
- des bits: 20 * 20 * 5 = 2 000 opérations

De plus, les opérations de décallage et les "et"/"ou" logiques sont des opérations qui prennent moins de temps (en général) que des oprérations entières.
Et surtout, tu gagne beaucoup de temps car tu lis beaucoup moins en mémoire, ce qui prend beaucoup de temps.

Je ne suis pas convaincu, pour avoir eu l'occasion de tester la différence entre occupation mémoire et rapidité lors de calculs intensif, il est apparu qu'il etait plus rapide d'utiliser deux entiers au lieu d'un seul sur lequel on effectuait des opérations bits à bits car lorsque tu fais une opération bit à bit, le processeur charge en mémoire un mot entier et pas un seul bit. De plus, l'opération de masquage de bit pour ne récupérer la partie qui nous concernait, s'averait plus lente que l'accès à l'un des deux entiers. De plus l'utilisation d'entier permettait d'avoir un meilleur alignement mémoire vis à vis de la solution par bit.
Le seul avantage que nous avons trouvé à l'utilisation des opérations sur les bits était lors de calculs nécéssitant de grosses quantités de mémoire, avec les opérations bit à bit, l'économie mémoire permettait au système de ne pas "swapper", ce qui au final s'averait plus rapide.

Il s'agissait là d'une application avec un calcul très intensif, je ne vois pas l'intérêt ici à utiliser de telle opérations. Elle ne permettent pas de gagner en performance (ou si c'était le cas, le temps gagné reste négligeable) et même elle rend le code moins propre et plus long à développer et à maintenir.
27/05/2007, 16h24
pseudemys

@Romu: en fait j'avais testé quatre solutions pour un dérivé de katamino:
1/ utilisation de domaine polyèdriques (algèbre linéaire) avec la PPL
2/ une modélisation qui ressemble un peu à la première idéé de david
3/ matrices d'entier
4/ vecteurs de bits
Et en termes de performances il y avait pas photo !

@David: non toutes tes pièces ne tiennent pas dans un carré mais ça n'a pas d'importance ! qd tu fais une rotation de 90° le nombre de lignes et de colonnes s'inversent, c'est tout !
27/05/2007, 16h42
PRomu@ld

Citation:

Mais toutes les pieces ne seront pas codé sur une matrice carée.

Tu dois pouvoir te ramener à une matrice carrée en englobant ta pièce dans cette dernière.
27/05/2007, 16h44
Davidbrcz

Oui c'est possible, mais ca va manger en mémoire.
27/05/2007, 16h49
PRomu@ld

Je ne comprend pas pourquoi tout le monde veut optimiser en mémoire un programme qui n'en a absolument pas besoin.

D'un point de vue mémoire, la représentation de ta grille occupe moins de 2 Ko. Gagner quelques octets n'a franchement aucun intérêt. Quand bien même tu arriverais à 1 Mo de mémoire, c'est absolument négligeable (sauf cas bien particulier d'applicatif embarqué).

D'un point de vu performance, c'est un programme qui ne devrait consommer que très peu de processeur. Gagner un ou deux cycles pour une opération qui n'est pas fréquement utilisé n'a absolument aucun intérêt.

A mon avis, mieux vaut se concentrer sur le code, son organisation, la qualité de la documentation, ça sera certainement plus profitable.
27/05/2007, 16h55
Davidbrcz

Tu a raison.
On part donc pour les tableau d'int.

Par contre pour les rotations , je devrais me baser par rapport au centre du carré, ou puis-je me basé sur le coin en haut a gauche sans me tapé trop de chagement de repère ?
Enfin pour le placage des pieces sur le plateau devrais aussi me basé sur le centre de la matrice ?

MercI.