Créer un jeu vidéo comme Minecraft

Dredri48

Grade : Membre accepté
Inscrit le: 10 Mai 2011, 13:13

Ecrit le: 10 Mai 2011, 23:27 Message non corrigé

Bonsoir, J'ai l'intention de créer un jeu vidéo dans le même style que Minecraft en C++ avec OpenGL. Pour que la taille de la map soit infinie, il faut que le terrain soit généré au fur et à mesure que le joueur avance avec des bloques différents mais de façon prédéterminée. J'aimerais avoir une idée sur la façon de créer un tel algorithme. Merci d'avance.

Grandbrinus

Grade : Apprenti
Inscrit le: 07 Mai 2011, 22:25

Ecrit le: 02 Juin 2011, 18:04 Message non corrigé

Déjà, je te conseille de lire le début du tutoriel concernant la construction d'un jeu vidéo :
http://www.jeux-libres.com/tutoriaux/tuto.php?id=437

Ensuite, rien n'est vraiment infini. Car pour cela, il faudrait un générateur de blocs aléatoires. Or, si tu veux que le joueur s'y retrouve un minimum dans la map, le mieux serai d'avoir une conservation des éléments.

Sinon a froid, j'aurai cet algorithme en tête, mais qui est un peu brutal ^^

Ouverture d'un fichier en persistant
Création d'un tableau 3D contenant les éléments visibles au départ
Ecriture de la map dans le fichier
Placement du joueur au centre de la carte

Boucle
Détection de l'appui d'une touche
Si le joueur avance et voit au delà de la carte
    Création aléatoire d'une ligne de blocs
    Entrée de la ligne dans le tableau 3D
    Supression de la ligne arrière du tableau 3D
    Sauvegarde de la ligne dans le fichier
Si le joueur avance mais ne voit pas au delà de la carte
    Récupération de la ligne arrière dans le fichier
    Suppression de la ligne la plus éloignée dans le tableau 3D
    Entrée de la ligne arrière dans le fichier
Fin de boucle

Un exemple va permettre de comprendre :
On a une carte de 5x5 (en 2D pour faire simple) dans un tableau, qui contient des éléments A, B, C, D et E

[A][A][A][A][A]
[B][B][B][B][B]
[C][C][C][C][C]
[D][D][D][D][D]
[E][E][E][E][E]

On inscrit cette carte dans un fichier F :

Fichier F:
AAAAA
BBBBB
CCCCC
DDDDD
EEEEE

On place le joueur sur la carte :
[A][A][A][A][A]
[B][B][B][B][B]
[C][C](J)[C][C]
[D][D][D][D][D]
[E][E][E][E][E]

Si le joueur avance vers la droite, on supprime la ligne qui se trouve derriere lui et on en rajoute une devant lui avec des éléments aléatoires (en gros on déplace tous les éléments du tableau vers la gauche) :

Entre lignes droites, les éléments non visible, retirés du tableau.
Entre crochets, éléments visibles inscrits dans le tableau.

|A|[A][A][A][A][N]
|B|[B][B][B][B][N]
|C|[C][C](J)[C][N]
|D|[D][D][D][D][N]
|E|[E][E][E][E][N]

En on insère cette nouvelle ligne dans le fichier F:

Fichier F:
AAAAAN
BBBBBN
CCCCCN
DDDDDN
EEEEEN

Si le joueur avance dans une direction dont la création à déjà été effectuée, on ne fait que lire dans le fichier puis créer la sur le plateau (ici, si le joueur va vers la gauche, on enleve la ligne des N dans le tableau et on remet la ligne normale)

[A][A][A][A][A]|N|
[B][B][B][B][B]|N|
[C][C](J)[C][C]|N|
[D][D][D][D][D]|N|
[E][E][E][E][E]|N|

J'espère que c'était clair ^^"

________
Tartalateam : Equipe indépendante du jeu vidéo - création de sites web / logiciels / animations flash

David

Grade : Expert
Inscrit le: 11 Mai 2005, 20:30

Ecrit le: 06 Juin 2011, 00:30 Message non corrigé

Minecraft faut beaucoup parler de lui en ce moment. Pour ce qui est de la génération de la carte, renseigne-toi du côté des Générateur pseudo aléatoire. Il est possible de générer une suite de nombre "aléatoirement réparti" dont chacun des nombres suivants est "prédéterminé". Pour ce qui est de l'affichage, en effet, Grandbrinus a bien expliqué le principe permettant de n'afficher que ce dont il est nécessaire. La difficulté se situe au niveau de la structure des données. Il s'agit grossièrement du même problème que celui des système de navigation par GPS. Seule la partie intéressante doit être affiché. Et pour que le système puisse rester léger (peu gourmand en mémoire et temps de calcule) tu devras organiser des données de telle sorte qu'elle soit accessible rapidement et simplement. Tu trouveras peut-être cet algorithme (en JavaScript par contre) dans l'API Google Maps. Seul les images à afficher ne sont transmise au visiteur. Il serait impossible d'envoyer une image précise de la carte du monde aussi rapidement. En résumé, malgré les apparences, Minecraft, les systèmes de navigation GPS ainsi que Google Map ont probablement un algorithme commun. Il s'agit d'un sujet intéressant. ________ Apprenez à créer votre propre FPS en C++ avec OpenGL. C'est pas dur ! :-)

Grade : Expert
Inscrit le: 26 Dec 2007, 17:33

Ecrit le: 06 Juin 2011, 17:49 Message non corrigé

Oui ça doit être ça, génération d'une grille de manière aléatoire...et en fonction de la direction prise par le personnage, modifie les cases dans la grille de manière à ce que le personnage soit toujours au centre de la grille. Finalement c'est comme si tu te déplaçais avec une grille autour de toi, avec toi au centre et les autres cases sont des images générées aléatoirement... Si j'ai bien compris le système... ________ Parce qu'on ne peut s'exprimer que par nos créations. ^^

David

Grade : Expert
Inscrit le: 11 Mai 2005, 20:30

Ecrit le: 06 Juin 2011, 21:29 Message non corrigé

Je pense qu'on est tous d'accord sur ce point. Mais la difficulté n'est pas là. La difficulté réside dans la structure des données.

Méthode faussement intuitive

Sur Minecraft, la hauteur de la carte est d'environ 130 blocs. J’imagine qu'un bloque est définit par un octet (il peut donc y avoir 256 blocs différents). La façon simple d'afficher une carte est de charger, depuis un fichier, la totalité des blocs, puis d'afficher tout ceux dont la distance est inférieur à un certain seuil.

Réfléchissons maintenant à la structure des données qui compose le fichier comportant la carte.

On peut imaginer un fichier composé d'une multitude de blocs de 130 octets qui définissent la composition de chaque "colonne" de la carte. A priori, c'est la solution la plus intuitive.

Réfléchissons maintenant à l'organisation de ces "colonnes" dans le fichier. Ces colonnes sont définies suivant 2 axes : X et Y. Et c'est là que survient la réelle difficulté. En effet, dans un fichier, les données ne peuvent être enregistrées que de façon linéaire. Pour enregistrer une aligné de colonne, il n'y a pas de problème, on les met à la suite. Par contre, où enregistrer les données qui composent chaque alignés de colonne ? Intuitivement, on aurait envie de faire un grand tableau de beaucoup de lignes composées chacune de beaucoup de colonnes.

J’imagine que la cartes boucle sur elle même après 4294967296 blocs pour des raisons informatiques :

#include <stdio.h>
 
int main()
{
    unsigned long positionX = 4294967295;
    positionX++; // La retenue se fait sur le "33ème" bit
    printf("%lu\n", positionX);
    return 0;
}

Si nous voulons enregistrer une carte dévoilé sur sur 100 lignes, nous seront alors obligé de générer et mémoriser 100 x 4294967296 x 130 octets. Ce qui fait 52 000 Go. Il est claire que ce n'est pas envisageable ! Il ne faut donc pas mémoriser ça dans un tableau comme tel.

Possibilité

On s'est clairement rendu compte qu'il n'était pas possible de tout mémoriser. Il va falloir mettre au point un format qui permet de ne mémoriser que ce qui est dévoilée.

Prenons l'exemple d'une carte un peu dévoilée. Les case '1' sont les colonnes dévoilées. Les cases '0' constituent le reste de la carte à explorer.

000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000001111000000000000000000011110000000000000000000
000000000000001111000000000000000011111110000000000000000000
000000000000000111111100000000011111111000000000000000000000
000000000000000011111111111111111111111000000000000000000000
000000000000000000011111111111100000000000000000000000000000
000000000000000000000000000111100000000000000000000000000000
000000000000000000000000000111100000000000000000000000000000
000000000000000000000000001111100000111110000000000000000000
000000000000000000000000000011111111111110000000000000000000
000000000000000000000000000011111111111110000000000000000000
000000000000000000000000000000000000000000000000000000000000

Pour éviter de devoir mémoriser les colonnes non-dévoilées, on pourrait mémoriser ceci :

0:14|1:4|0:19|1:4|0:20
0:14|1:4|0:16|1:7|0:19
0:15|1:7|0:9|1:8|0:21
0:16|1:23|0:21
0:19|1:12|0:29
0:27|1:4|0:29
0:27|1:4|0:29
0:26|1:5|0:5|1:5|0:19
0:28|1:13|0:19
0:28|1:13|19

A partir de ce fichier, on peut connaitre chaque plages de colonnes dévoilées. Il est ensuite envisageable de mémoriser chaque plages de '1' dans des fichiers séparés.

Ainsi, il est possible de charger uniquement les plages de colonnes dévoilées (ou modifiés).

Structure plus gudicieuse

Après réflexion, je pense qu'on peut faire encore mieux : plutôt que d'enregistrer des lignes de colonnes, il est possible de découper la carte en moins de blocs qui serait alors plus gros (par exemple un bloc de 64x64x130 bloc dans un fichier). Cela permettrait de soulager la mécanique du disque dur.

Ne mémoriser que les blocs modifiés

Il est également possible de ne mémoriser que les blocs modifiés. En effet, l'algorithme de génération de la carte étant déterministe, il est possible de retrouver les blocs manquant à tout moment, tant qu'il n'ont pas été modifié.

Je vais m'arrêter là pour le moment. Mais je pense qu'il est nécessaire de bien réfléchir à la structure des données car malgré les apparances, il s'agit d'une tâche très délicate dans le développement d'un minecraft-like.

Dans un premier temps, je pense qu'il est nécessaire de faire une fonction déterministe qui retourne un bloc unique à une position donnés pour une clé de carte donnée.

1	uint8 bloc(uint32 x, uint32 y, uint8 z, uint32 cleCarte);

Je mettrais ma main à couper qu'il n'existe que 2³² cartes différentes de minecraft. Ce qu'il faut bien saisire ici c'est que la clé de la carte est généré aléatoirement (autrement dit, la carte est généré aléatoirement). Mais la création de la carte sous tes yeux quand tu avances et quelquechose de déterministe. Autrement dit, depuis l'instant où tu cré une nouvelle partie, la totalité de ta carté est déjà déterminé, bien qu'elle ne soit pas généré. Ce ne parait pas évident au premier abord.

Vérification

Pour vérifier ce déterminisme, tu crées une carte. Ensuite, tu la dupliques sur un autre PC. Puis chacun de son côté (sur 2 PC différents), avancez toujours tout droit dans une même direction. A tout les coups, vous rencontrerez les mêmes objets défiler sous vos yeux. La carte se génère de façon identique. Ce qui prouve le déterminisme de la génération de la carte.

Attention : Je ne suis pas allé vérifié. Mais par intuition, j'en suis presque certain, sinon il y aurait des bugs évident lorsqu'on explore la carte en décrivant un grand cercle. Il y aurait également des problèmes évident de capacité de mémoire pour mémoriser la carte. Alors que là, on ne mémorise que les bloque modifiés.

________
Apprenez à créer votre propre FPS en C++ avec OpenGL. C'est pas dur ! :-)

Envie de créer un jeu vidéo ? Le site qui vous accompagne de A à Z.

Les Tutoriels Les Forums Créez votre propre FPS Livre d'or

Méthode faussement intuitive

Possibilité

Structure plus gudicieuse

Ne mémoriser que les blocs modifiés

Vérification