Bonjour/soir...

Dans ma quete d´apprentissage visant à créer le jeu ultime, je me retrouve face à un petit problème de conception.

La situation :
Le premier milestone de mon projet est un sokoban... pas trop dur à réaliser apparemment, mais je souhaite tout de même créer les éléments de ce jeu de façon à pouvoir les réutiliser. Le principe d´un sokoban : pousser des caisses!
Le problème : Pousser des caisses ne semble pas trop compliqué au premier abord, il suffirait d´avoir un tableau de la taille de l´espace de jeu pour mémoriser la position des caisses, et de faire des opérations dessus en fonction de la position du joueur... no problem pour cette conception mais... irréutilisable!
Tout d´abord parce que le tableau de caisses est creux, occupant donc un espace mémoire sans l´utiliser réellement! Aucun intérêt...
Second essai : On ne souhaite garder que les caisses. Ok! on va faire une liste de structures "caisse" qui mémorisera pour chacun sa propre position! plutot sympa, pas de gaspillage mémoire et en plus pour bouger une caisse il suffit de modifier ses coordonnées! Le pied en fait!
Ou pas... Comment je fais pour savoir si je bouge une caisse? je dois me farcir la liste entière à chaque mouvement? mais ca va pas la tête? c´est pire qu´avant!!
Pareil, irréutilisable... pourtant, ma structure caisse me plait... Damn! je sais pas comment faire...

Voilà... je suis encore bien noob en structures de données donc j´ai beau chercher... la solution me fuit! Comment gerer des interactions en fonction des positions d´objets avec le moins de gaspillage possible?
Si vous avez des pistes... ou de bons articles dessus?
Ca semble toucher à la collision ce genre de truc, mais le domaine me parait encore un peu hardcore. Pourtant, la simple sélection d´un personnage/item à la souris est une action élémentaire dans beaucoup de jeux, et c´est bien ce type d´évenement...

Merci

la solution me semble parfaite pourtant
si ton sokoban est de taille 1000 sur 1000 (ce qui est vachement gros pour un sokoban) et que tu code chaque case sur 4 octets (ce qui est un vrai gaspillage de mémoire), ca ne fait jamais que 4Mo. donc peanuts.

Si jamais tu trouve ca trop cher, il y a des solutions intermédaire:
Par exemple, tu découpe ton sokoban en section de 10x10. et par section tu stockes les informations dans une liste chaine. Quand tu as besoin d´acceder aux données d´une section, tu reconstruit ton tableau (local) de 10x10. Notes que tu n´as en fait besoin que des informations de ta section ou d´une section voisine. donc, une mémoire de 30x30.
Tu peux aussi ne pas le reconstruire et regarder directement dans la section.
De la meme facon, tu peux faire des "regroupement" en ligne, en colonne. Ou par n´importe quel fonction de hashage.

godrik a tout a fait raison sur ces deux points.

Moi j´utilise toujours ces deux regles la : (qui s´applique parfaitement a ton probleme)

1/ Ne jamais faire d´optim au moment de la conception. Car au final 80% du code n´a pas besoin d´etre optimisé (car prends pas beaucoup de place ou pas beaucoup de temps de calcul). Vaut mieux se consacrer sur les 20% qui reste, quand le projet est terminé.

2/ "Toujours decouper un gros probleme en plusieurs problemes plus simples.". Ici, ta grosse liste de caisses peut etre gerée plus facilement avec un "macro tableau" pour le sugerre godrik. Mais la on rentre deja dans de l´optim, voir regle numero 1.

je vias réenfoncer le clou avec une expérience récente a moi.
J´ai eubeson de faire un moteur de thread pour exploité les machine multi core efficacement. On pensait que l´on perdrait plein de temps dans les mutex et co. Finalement,ce qu´il ya de plus long dans notre systeme est le temps que le noyau nous donne la main. C´est notre plus grande (en fait quasiemnet la seule) perte de performance que l´on constate, et on y peut pas grand chose.

Vouaip, en fait j´ai du m´enflammer sur l´espace mémoire... c´est vrai qu´il faut y aller fort en chocolat pour que ca devienne remarquable!

L´idée était d´avoir des structures indépendantes, vu que ma caisse de sokoban est la base d´un objet générique qui servira un peu à tout par la suite. Mais apres tout, si j´ai des coordonnées, ca veut dire que j´ai un référentiel, donc le couplage est implicite... alors autant le gerer simplement!

Merci à vous deux!

@Lapin > Ici, ce n´était pas vraiment question d´optimisation (ou juste un peu), il me fallait juste une structures de données qui me permettre d´aller plus loin qu´un sokoban, parce que 90% des actions du jeu prévu seront gérées comme des déplacements de caisse! Mais je retiens le conseil, il est vrai que j´ai tendance à m´emporter facilement dans de la pré-optimisation.

Tu peux tres bien avoir un simple tableau 2D contenant des objets generiques qui font ce que tu veux.