je continue
Pour l'implémentation, je pense que le mieux est de faire une fonction récursive (si tu ne connais pas la récursivité, je te conseille de te référer aux urls du sujet épinglé de ce forum). En supposant que
alea() est une fonction renvoyant un nombre aléatoire entre 0 et 100, pour une carte en 30*30, ça donnerait quelque chose comme ça (C++) :
int map[30][30]={ false }; // La carte du terrain : si un élément vaut 0, c'est de l'herbe, sinon de la mer
bool is_generated_map[30][30]={ false }; // Ce tableau permet de savoir quelles cases ont déjà été générées, pour ne pas repasser dessus.
int alpha=90; // Alpha : 90% de chances de garder la même tuile.
int decalage[8][2]={ {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1} };
void generate_map(int y, int x, int tuile_precedente)
{
if((y>29) || (y<0) || (x>29) || (x<0))
return;
int tuile;
if(alea()<=alpha)
{
tuile=tuile_precedente;
map[y][x]=tuile_precedente;
}
else
{
if(tuile_precedente==0)
{
tuile=1;
map[y][x]=1;
}
else
{
tuile=0;
map[y][x]=0;
}
}
is_generated_map[y][x]=true;
for(int dec=0; dec<8; ++dec)
{
if(!is_generated_map[y+decalage[dec][0]][x+decalage[dec][1]])
generate_map(y+decalage[dec][0], x+decalage[dec][1], tuile);
}
}
Le tableau decalage sert a passer à toutes les cases autour de la case courante (en haut à gauche, en haut, en haut à droite, etc...).
On aurait aussi pu remplacer le bloc de if en haut par un tuile=!tuile_precedente dans le cas où on change de tuile, puisqu'on utilise les valeurs 0 et 1 pour les tuiles et que 0=!1 et vice-versa, mais j'ai préféré ne pas trop complexifier le code.
Pour lancer la génération, il suffit d'appeler generate_map avec y et x comme coordonnées de la case de départ et tuile_precedente la tuile de départ (celle dont je parlais dans l'étape 1).
J'ai testé en codant ça vite fait la génération de maps en 30*30, en commençant invariablement à la position (15;15), avec de l'herbe comme tuile de départ. Si tu veux le code source du programme, c'est là :
http://membres.lycos.fr/sekren/generate/generate.cpp
Exemples de cartes générées (~ = mer, O = herbe) :
http://membres.lycos.fr/sekren/generate/map_98.txt << alpha=98%
http://membres.lycos.fr/sekren/generate/map_90.txt << alpha=90%
http://membres.lycos.fr/sekren/generate/map_50.txt << alpha=50%, pourri sauf pour un marais, éventuellement
On remarque tout de suite qu'il y a un probleme : les cartes générées présentent des "bras" de terre ou de mer, de longues lignes en diagonale. La raison en est trés simple : l'algorithme utilisé est un DFS, Depth First Search, une recherche en profondeur. Cela signifie qu'il va "persister" dans une direction, puis dans une autre, etc... (pour faire simple), justement parce qu'il procède en
profondeur. C'est tout à fait problématique, ici, et j'aurai dû y penser en proposant l'algo au dessus. Mais la solution est simple : il suffit de remplacer le parcours en profondeur par un parcours en
largeur, qui lui va procéder dans toutes les direction à la fois, en même temps. Avec la même façon de procéder mais en utilisant un parcours en largeur, tu obtiendras des cartes vraiment bien pour un alpha tournant dans les 90 à 100%. Si tu as besoin d'informations pour le parcours en largeur, je te suggere de jeter un oeil aux tutos du sujet épinglé de ce forum et d'utiliser google
De toute façon, je pense que je vais essayer d'implémenter ça pour voir ce que ça donne, et donc je posterai une réponse avec le code correspondant ici.
"Soyez un homme, Maître Ridley. Nous allons en ce jour, par la grâce de Dieu, allumer en Angleterre une chandelle qui, je le tiens pour certain, ne s'éteindra jamais."
---
http://www.sekren.org 
