yop,
J'ai une petite question d'algo pour laquelle les seules solutions que j'ai testées jusqu'à maintenant sont affreusement lentes. Je ne vois pas de méthode efficace et je ne sais pas s'il en existe, mais peut-être que ça parlera à certains d'entre vous.
Imaginons que je veuille générer une map de tiles. Je veux que le placement de ces tiles soit cohérent, par exemple si l'un d'eux représente une route verticale, le bord inférieur de celui qui sera placé juste au-dessus doit "continuer" cette route (il peut donc s'agir du même tile de route verticale, ou bien une route qui part du bas et tourne à gauche ou à droite, par exemple). On peut donc imaginer une liste de règles : à chaque tile est associée la liste de ceux qui peuvent se trouver à proximité (ceux pouvant être à gauche, ceux pouvant être à droite, etc).
Techniquement rien de bien compliqué pour l'instant, mais le problème arrive ici : comment générer aléatoirement une map de tiles qui respecte toutes ces contraintes ? Si on place un peu n'importe quoi de façon aléatoire, et même si on prend la peine de noter à chaque nouveau tile ceux qui du coup deviennent invalides sur les cases adjacentes, on a de grandes chances de se retrouver tôt ou tard bloqué (parceque deux tiles éloignés auront des contraintes incompatibles, et que la case en conflit ne pourra donc rien accepter qui satisfasse à la fois les deux règles concernées). C'est difficilement imaginable aussi de construire un algo récursif qui, en cas de blocage, annule son dernier coup et retente ailleurs : pour peu que le tile qui pose problème soit l'un des premiers placés, on peut attendre longtemps que ça finisse.
Auriez-vous des idées ?
[edit] Voyez le post ./9 pour un schéma explicatif