Laboratoire Officiel - Actuellement: Génération de Terrain

Bienvenue dans ce que je nommerai le labo...
Ce topic se réserve ainsi à tout les systèmes informatiques réalisés en programmation. Peu fonctionnels ou utiles, peu importe...

Nous ne ferons ici que des expériences ne servant à rien, par exemple: Contrôle d'un disque dur à partir d'un microprocesseur, Faire Cuire un oeuf avec GameMaker (Création d'une plaque de cuisson fonctionnant sur USB), créer son propre lecteur mp3, ou bien des systèmes de base tel que des effets graphiques, des moteurs physiques, système de gestion des images png et toutes les idées farfelues qu'un programmeur peut avoir.

L'idée est d'en discuter afin de découvrir la meilleure voie pour les réaliser, de tâtonner, d'essayer, que chacun y mette un peu du sien etc. En discuter est nécessaire, car ce n'est qu'en confrontant nos suppositions, hypothèses, idées, façons de programmer & de penser que nous parviendrons à faire naître de nouvelles connaissances.

Je sais cela, car lorsque je discute avec des amis de programmation les idées et les solutions viennent plus vite, et sont beaucoup plus innovantes, alors que tout seul c'est dur de trouver parfois.

Pour l'heure le sujet est: Création d'un générateur de Terrain en 3d pour GameMaker

Nous étudierons comment réaliser la représentation graphique du terrain sous GameMaker, avec les fonctions 3d d'usage pour le moment, si elles ne s'avèrent pas assez puissantes, il sera nécessaire de passer sur une dll telle GM Irlicht, ou bien OpenGL, mais nous pourrons également développer notre propre système à partir de kjAPI.

Observations:

A regarder la forme d'un ocean, d'un lac ou encore d'une flaque d'eau, il est aisé de trouver des similitudes. Dans les trois cas on verra une côté, des îles, des baies, criques etc. Aussi si l'on regarde une bonne baguette de pain de tout près, on verra des vallées et des collines sur sa surface, comme sur la carte d'un monde à explorer.
On nomme cela une auto-similitude, des éléments de terrain de taille différente se ressemblent. On pourrait utiliser ce principe pour la création de l'algorithme, primordialement on créera les choses de grandes tailles, de façons à aller au plus petit, c'est l'inverse de ce qui se passe dans la réalité, mais un programmeur est avant tout un tricheur!

Méthode de Subdivision:

Cette méthode s'appelle méthode de subdivision. L'algorithme dit de subdivision fonctionne comme sur le schema:

Où chaque carré représente une étape et où les points bleus indiquent les points dont les valeurs sont déjà connues, et qui sont utilisés pour l'étape actuelle. Les points rouges indiquent cependant les points dont la hauteur est calculée durant l'étape.

Erosion:

Un facteur important et permettant de rendre le terrain plus naturel est l'érosion. Avec le temps roches et montagnes sont soumises aux vents et à l'eau, en conséquence il s'usent, s'arrondissent, s'affessent...
Créer un processus d'érosion est en soi assez simple, il suffit pour un point de faire la moyenne des points avoisinants et d'en user pour valeur pour ce point. Il faut donc connaître le rayon de voisinage et le nombre d'étapes, et la force de l'érosion résultera de la longueur du rayon de voisinage et du nombre d'étapes. Il est cependant compliqué de dire lequel influencera le plus le terrain, mais par expérience je pense qu'il faudrait utiliser une petite longueur pour le rayon et un nombre d'étape élevé, je songe que ça devrait donner des résultats corrects, au pire nous pourrions toujours revenir dessus plus tard.

Les Plateaux, ouch que c'est important! Voili Voilou:

Les Plateaux! L'idée est de niveler certaines zones du terrains pour qu'elles puissent accueillir des objets de gameplay dans un jeu, tels qu'un bâtiment, un groupement de véhicules, une zone d'atterissage ou que sais-je encore...
Pour ce faire l'usager sélectionnera un point sur la carte et un algorithme créera un plateau. Cet algorithme se constituera en ceci: Il augmente ou réduit la hauteur du terrain qui entoure le point choisi pour que le terrain alentour devienne plus "plat". Plus on est éloigné du point, plus la force de nivellation sera petite, donc le plateau changera de manière fluide en collines et vallées.
Pour que la méthode fonctionne il est nécessaire de préciser les coordonnées du centre du plateau ainsi que son rayon. Si le terrain obtenu ne s'avère pas être assez plat il va de soit qu'il suffit de répeter l'opération.

¤ Autres pistes à explorer pour la création d'un terrain:

- Préconçu: A l'aide d'un Bitmap Noir et Blanc (Et qui peut constituer des données de départ pour nos algorithmes présentés ci-dessus) dans lequel chaque nuance de gris représenterait une valeur de hauteur pour le terrain, d'ailleurs on pourrait utiliser des logiciels de génération de terrain tels que: http://www.world-machine.com/ qui permettent de générer des images bitmap des terrains, et les utiliser comme mentionné ci-dessus.

Continuons
Cela n'est que théories, idées et imaginations, et je donne ici une base afin que nous continuions, et que nous discutions à propos de la génération de terrain, de manière même toute autre, peu importe, du moment qu'au bout de nos péregrination nous parvenons à faire un gm6 fonctionnel qui permettra de générer des terrains. Je pense que vous autres avez également des idées pour générer un terrain, faîtes moi en part.

alors là !

je campe ici !!!

c'est ma nouvelle maison désormais !!!

je dois laisser le PC deux minutes, et je pose mes idées !!!!

1) la méthode de subdivision

pour cette méthode, plusieurs choses sont à prendre en compte, et notement l'ordre d'affichage des polygonnes. en effet, si un poligone 'bas' est affiché après un polygone 'haut' , en plus d'un défaut du moteur d'ombres, cela conduirait inévitablement à une superposition des plus désagréables.

Il faut également trouver un format de stoquage des données... les classe t on par ordre 'croissant' , du haut à gauche en bas à droite ? ou stoque t on d'abbord les grand quadrillage, puis les moyen , et enfin les petits ...

Enfin, la texture : est - elle unique , et appliquée sur tout le model (je part du principe que c'est un model, puisque sinon, la vitesse d'affichage sera horrible ...) ou est elle constituée de 'tiles' provenant d'une même texture ?

2) préconcu par bitmap
probablement le plus simple .. mais aussi plus limité ...
taille fixe, compression non fesable (enfin, je voi pas comment ...)
on pourait utiliser le 'hight map' pour l'altitude, puis recharger la texture pour gagner de la place en RAM, mais bon ...

très sympa comme truc, il y a un tas de chose à penser

Sinon pour ma part, j'ai fait aujourd'hui, une fonction qui permet de charger une map, avec un fichier texte externe, avec ce type de présentation

Code:

 [6,6]{0,0,0,0,0,0}{0,1.0,1.2,1.2,1.0,0}{0,1.0,1.2,1.2,1.0,0} . . .

entre crochet, le nombre de ligne et de colonne, puis une matrice rangé ligne par ligne.
cette matrice, représentation l'altitude de chaque d'un carré découpé donc la en 5x5,

Puis j'ai aussi fait une fonction d'affiche qui permet seulement de dessiner la map en scallant dans les trois dimensions, et le truc en plus que je veux mettre c'est un matrice de texture, avec une seule image, et en fonction de chiffre de la matrice on se déplace sur l'image.

le but ultime de mon truc est de pouvoir, créer une map simplement avec un logiciel externe, et de l'importer simplement dans GM.

Je sais pas si mon message fait avancer le schmilblick , mais j'avais envie de le posté car j'y ai passé 2 heures et mon truc marche pas mal ^^

edit : et un petit lien pour que vous voyez
test_map_fichier_ext.zip - 0.05MB

en fait, faudrait que j eposte les sources de ma lib sur les matrices ... si je la retrouve :lng:

[TheDarkTiger] a écrit:

1) la méthode de subdivision

pour cette méthode, plusieurs choses sont à prendre en compte, et notement l'ordre d'affichage des polygonnes. en effet, si un poligone 'bas' est affiché après un polygone 'haut' , en plus d'un défaut du moteur d'ombres, cela conduirait inévitablement à une superposition des plus désagréables.

Effectivement... Il faudrait donc récuperer dans le fichier de valeur de la map récuperer les valeurs Z de chaque point et les classer par ordre croissant. Puis de les afficher dans cet ordre à partir d'une boucle for ou repeat.

Citation :

Il faut également trouver un format de stoquage des données... les classe t on par ordre 'croissant' , du haut à gauche en bas à droite ? ou stoque t on d'abbord les grand quadrillage, puis les moyen , et enfin les petits ...

J'avais pensé stoquer par ordre décroissant, les plus grands d'abords et toujours plus petit (Comme sur le schema, en grand dans l'ordre de génération). Mais on pourrait peut-être faire autrement, au bout de l'algorithme on stoquerait les points selon leur valeur Z de façon croissante, comme je l'ai dit plus haut, ça éviterai d'augmenter le temps de chargement de la map.

Citation :

Enfin, la texture : est - elle unique , et appliquée sur tout le model (je part du principe que c'est un model, puisque sinon, la vitesse d'affichage sera horrible ...) ou est elle constituée de 'tiles' provenant d'une même texture ?

Je suppose que nous pourrions penser un système de heigthmap (comme tu le dis plus bas). Puis après dans le jeu selon le heigthmap user de textures différentes. Mais pour le moment on pourrait user d'une texture unique, prévue pour tout le modèle. (Quoique dans le cas de grosses maps ça va ramer...)

sagix a écrit:

très sympa comme truc, il y a un tas de chose à penser

Sinon pour ma part, j'ai fait aujourd'hui, une fonction qui permet de charger une map, avec un fichier texte externe, avec ce type de présentation

Code:

 [6,6]{0,0,0,0,0,0}{0,1.0,1.2,1.2,1.0,0}{0,1.0,1.2,1.2,1.0,0} . . .

entre crochet, le nombre de ligne et de colonne, puis une matrice rangé ligne par ligne.
cette matrice, représentation l'altitude de chaque d'un carré découpé donc la en 5x5,

Puis j'ai aussi fait une fonction d'affiche qui permet seulement de dessiner la map en scallant dans les trois dimensions, et le truc en plus que je veux mettre c'est un matrice de texture, avec une seule image, et en fonction de chiffre de la matrice on se déplace sur l'image.

le but ultime de mon truc est de pouvoir, créer une map simplement avec un logiciel externe, et de l'importer simplement dans GM.

Ben peut-être que l'on pourrait ajouter un système de génération de carte et ensuite elle serait éditable par ton logiciel, l'idée de pouvoir niveller vient de là.

Citation :

Je sais pas si mon message fait avancer le schmilblick , mais j'avais envie de le posté car j'y ai passé 2 heures et mon truc marche pas mal ^^

Je crois qu'au contraire tout peut aider. D'ailleurs c'est déjà du concret.


Sinon je suis content de voir que ça vous plaise, moi ça me plaît pas mal aussi.

bon bha ce week end , je travaille dessus

EDIT :

je vai sd'ailleurs essayer de faire un algorithme sur papier (pendant les cours ? non .... penssez vous ...)

je poste les trouvailles (si il y a) ici même demain

Ok.
Moi j'ai pas trop le temps, mais dès que je peux je m'y met aussi, parce que j'ai encore un truc de Levans à corriger en priorité.

j'ai trouvé sur papier un systemme ...

en fait, on met un nobre : c'est le nombre de division du carré de base(ex : 4 cad un carré divisé en 4 carré : deux en haut et deux en bas .)
puis, on lit les 4 prochaines lignes : si il y a un "|" devant, alors, c'est une altitude, sinon, c'est une sous division du carré en cours ...



bref, d'abbord le côté gauche, puis le droit( comme ca on vérifie si ya des autres sous-divisions) et cetera et cetera ...

Voila un premier test pour la subdivision, le principe est un quadrillage de 40x40, dont on connait les valeur de Z en chaque point et on n'affiche précisément seulement les carrées qui sont près du perso (la souris), puis des carrées de tailles de 2 fois plus grands, et 4 fois plus, ...

ce que je montre n'ai qu'un petit test, en 2D pour faire simple, une fonction récursive serait plus intelligente mais la c'est juste le principe ^^

test_subdivision2.gm6 - 0.00MB

[TheDarkTiger] a écrit:

j'ai trouvé sur papier un systemme ...

en fait, on met un nobre : c'est le nombre de division du carré de base(ex : 4 cad un carré divisé en 4 carré : deux en haut et deux en bas .)
puis, on lit les 4 prochaines lignes : si il y a un "|" devant, alors, c'est une altitude, sinon, c'est une sous division du carré en cours ...



bref, d'abbord le côté gauche, puis le droit( comme ca on vérifie si ya des autres sous-divisions) et cetera et cetera ...

Oui tout à fait d'accord, ça peut très bien fonctionner, faut pas l'oublier lorsqu'on voudra le mettre en application.

sagix a écrit:

Voila un premier test pour la subdivision, le principe est un quadrillage de 40x40, dont on connait les valeur de Z en chaque point et on n'affiche précisément seulement les carrées qui sont près du perso (la souris), puis des carrées de tailles de 2 fois plus grands, et 4 fois plus, ...

ce que je montre n'ai qu'un petit test, en 2D pour faire simple, une fonction récursive serait plus intelligente mais la c'est juste le principe ^^

test_subdivision2.gm6 - 0.00MB

De manière recursive? Je pense que c'est le plus intelligent en effet, parce que TDT avait soulevé le problème d'affichage des polygones, et par méthode récursive on pourrait tout calculer dans la foulée il me semble. Et ainsi plus de problèmes.

daminetreg a écrit:

De manière recursive? Je pense que c'est le plus intelligent en effet, parce que TDT avait soulevé le problème d'affichage des polygones, et par méthode récursive on pourrait tout calculer dans la foulée il me semble. Et ainsi plus de problèmes.

je vois pas pourquoi tu parles de calculs pour mon système, car moi je ne parle que de l'affiche, le système que j'ai montré ne marcherais seulement si les calculs faient avant.

Car dans ma tête, ca fonctionne comme ca :
avec un éditeur on crée par exemple une map 10x10, on applique une fonction de subdivision, ce qui fait que la map et désormais de 20x20,
puis on enregistre la map,
après quand on charge la map , on affiche le carré d'échelle 1:1 autour de la camera sur un rayon donné, puis après on affiche le reste mais avec une échelle de 2:1, comme ça c'est précis autour de la camera , et moi precis plus loin.

Ce systeme prend un peu plus de mémoire, et nécessite un temps de charge, mais contre partir, n'utilise pratiquement pas le processeur, pour faire des calculs.

sagix a écrit:

daminetreg a écrit:

De manière recursive? Je pense que c'est le plus intelligent en effet, parce que TDT avait soulevé le problème d'affichage des polygones, et par méthode récursive on pourrait tout calculer dans la foulée il me semble. Et ainsi plus de problèmes.

je vois pas pourquoi tu parles de calculs pour mon système, car moi je ne parle que de l'affiche, le système que j'ai montré ne marcherais seulement si les calculs faient avant.

Car dans ma tête, ca fonctionne comme ca :
avec un éditeur on crée par exemple une map 10x10, on applique une fonction de subdivision, ce qui fait que la map et désormais de 20x20,
puis on enregistre la map,
après quand on charge la map , on affiche le carré d'échelle 1:1 autour de la camera sur un rayon donné, puis après on affiche le reste mais avec une échelle de 2:1, comme ça c'est précis autour de la camera , et moi precis plus loin.

Ce systeme prend un peu plus de mémoire, et nécessite un temps de charge, mais contre partir, n'utilise pratiquement pas le processeur, pour faire des calculs.

Oui je suis d'accord avec ça, ce que j'entends par calcul, c'est l'affichage également. Pour moi lorsque je dis calculer, ça représente aussi bien faire les diverses opérations de subdivision qu'afficher, je sais c'est pas bien de ma part, je ferai un effort sur ce point là.

Vous vous demandez pourquoi je viens parler des courbes de Bézier, tout simplement parce que ça va nous être utile, pour calculer les nouveaux point de chaque subdivision d'un map,
car comme vous pouvez le voir sur l'image, j'utilise une courbe de Bézier de degré 3 ( défini par 4 points), 2 premier points pour le début et la fin de la courbe, et 2 autres qui forment des vecteurs avec les deux autres.

Et donc en fonction de ces 4 points on peut faire une jolie courbe bien arrondie, en calculant des point intermédiaire, avec cette équation

Code:

M(t)=(1-t)^3*A+3t(1-t)^2*B+3*t^2(1-t)*C+(t^3)*D

avec A,B,C,D 4 points et t appartenant [0,1].

Vous vous dites peut-être que c'est bien beau mais comment on fait si l'on connait juste les point et pas les vecteurs, il suffit assez simplement de les calculer à partir des points précédants, comme on sait que la courbe est tangeante au vecteur, si l'on prend un point An ,la direction de sont vecteur sera celle de (A[n-1],A[n+1]).

Une fois qu'on direction, le sens ce déduit simplement car les vecteurs iront entre les 2 points( ceux du début et de fin de la courbe).

Et enfin il faut trouver la norme du vecteur, sur ce point je ne sais pas trop encore car je n'ai pas fait de test pour voir ce que cela donnait mais je pense que la norme pourra être déduite en fonction de la différence entre l'altitude du point et le précédant à celui -ci.

Et enfin voila le .gm6, si vous voulez voir ce que ça donne ^^

courbe_bezier.gm6 - 0.01MB

J'ai essayer de faire un truc clair, j'espère que c'est le cas ^^

au fait, t'es en quelle classe ?

parce moi, en terminale, j'ai pas appris ca :snif2:

c'est en effet une exelente idée

je me souvien avoir vu à la cité des sciences un exposé , dansla partie maths, qui relatait exactement notre problèmme !
en fait, ils calculaient pas des carré, mais à partir des points qu'on eur donnait, ils cherchaient, les triangles les plus proches d'un triangles equilatéral ... et avec leur fonction, plus les points étaient loin de la camera, plus ils étaient ignorés ...

enfin, je me comprend, mais je vais essayer de vous faire un GM6 ou un dessin, pour que vous compreniez ...

bon, je vais en cours, à dans 4 heures !

Moi je suis en 1ere année de license d'info.

Mais je n'ai pas appris ça en cours,(la on a fini sur la matrice et application, pour faire des arbres....)
c'est juste que ça me trotait dans la tête depuis quelques jours, puis j'ai eu l'idée des vecteurs ^^ , après merci à google, en mettant courbe et vecteur il m'a trouvé ça

Sinon l'idée des triangles équilatérals est bien mais sur l'ordi travailler avec des carrées c'est ce qu'il y a de plus simple, de plus si la map n'a pas une texture complète , mais matricée, ça devient plus dur avec des triangles.
Mais fait un petit .gm6, ça peut toujours donner des idées.

En tous cas ton exemple est pas mal, ça pourrait également apprendre certaines choses à des débutants, pourrai je le mettre dans un prochain pack?

daminetreg a écrit:

En tous cas ton exemple est pas mal, ça pourrait également apprendre certaines choses à des débutants, pourrai je le mettre dans un prochain pack?

Oui pas de probleme

Un autre sujet pour le labo ne serait-il pas mieux? Parce que j'ai pas l'impression que ça nous motive de trop pour l'instant, on peut mettre celui-ci en stand-by et peut être faire autre chose qui touche à la 2d, par exemple faire un moteur de reflet pour de l'eau dans un jeu en 2d ou que sais-je encore, mais si vous trouvez le sujet actuel plus excitant moi je serai heureux de le garder.

Moi je n'ai pas compris à quoi sert les labos. Sinon j'aurai participé !

ca serait intéressant je vais me penché sur le sujet ce soir et si j'ai quelque chose de bien je le poste demain

bibi26 a écrit:

Moi je n'ai pas compris à quoi sert les labos. Sinon j'aurai participé !

Juste parler à propos d'un système, d'essayer de le faire de différentes façons etc.

Ah, je ne sais pas pour les autres, mais je n'ai jamais touché à la 3D, je participerai donc au prochain labo

daminetreg a écrit:

Un autre sujet pour le labo ne serait-il pas mieux? Parce que j'ai pas l'impression que ça nous motive de trop pour l'instant, on peut mettre celui-ci en stand-by et peut être faire autre chose qui touche à la 2d, par exemple faire un moteur de reflet pour de l'eau dans un jeu en 2d ou que sais-je encore, mais si vous trouvez le sujet actuel plus excitant moi je serai heureux de le garder.

bibi on a changé maintenant c'est un effet de reflet

Citation :

Un autre sujet pour le labo ne serait-il pas mieux? Parce que j'ai pas l'impression que ça nous motive de trop pour l'instant, on peut mettre celui-ci en stand-by et peut être faire autre chose qui touche à la 2d, par exemple faire un moteur de reflet pour de l'eau dans un jeu en 2d ou que sais-je encore, mais si vous trouvez le sujet actuel plus excitant moi je serai heureux de le garder.

Non

Hmm... Il serait effectivement judicieux de changer de sujet... Personnellement, je suis largué en 3D alors... :lng:

oui, changons de sujet, on reviendra là dessus plus tard ...

ou au pire, on peut parler d'un nouveau sujet ici, et faire un nouveau topic, ailleurs , ou ...

bon, changeons de sujet, c'est plus simple ...

Bah moi en attendant j'ai continué avec mes courbes de Béziers en les adaptant avec plusieurs points, mon système calcule juste la courbe qui pourrait passer par tous les points( je précise çà car j'ai vu que dans les autres systèmes , notament pour la subdivision on faisait un peu différemment )



bezier2.gm6 - 0.01MB

Ps: le calcul de la norme des vecteurs n'est pas encore au point

punaize, t'en à fait un boulot !

c'est exelent !

mais je ne sais pas si en 3D on pourat l'addapter ...

Adaptable mais un peu chaud. Moi ça me boterait de prendre le résultat, mais pas de bosser dessus

Sinon le projet de Bibi26 m'a l'air bien...
PS: j'avais vu 2 gm6 très interressant sur 64digits, mais j'arrive pas à downloader...