hexmaps, obtenir coordonées cases voisines dans un rayon donné

Salut,

Connaitriez-vous un algorithme permettant de d'obtenir les coordonnées de toutes les cases comprise dans un rayon r autour d'une case précise dans une hexmap ?

Cause admettons la grille ci dessous, avec un algorithme pour une grille carrée (D4 je crois...?), l'on obtient les coordonnées des cases turquoises et bleues ciel... Or ces dernière sont de trop...

J'ai bien trouvé que le nombre de cases superflues = fibonacci(r)*2, néanmoins les débuts d'idées qui me viennent devraient donner des solutions plutôt alambiquées et tout sauf élégantes...
http://img402.imageshack.us/img402/3023/grillef.jpg
En fait, la solution la moins fantaisiste que j'ai eu consiste à utiliser l'agorithme D4(?) et verifier la distance de chaque case par rapport à la case au centre... mais cela me semble vachement lourd, et je suis sûr qu'il y a beaucoup plus simple, non ?

Bonjour,
D'abord juste une idée de flemmard. A tout hasard, je ne suis pas entré dans votre problématique réelle. En regardant graphiquement votre bouzin, j'intuite que si vous pouvez obtenir facilement le motif turqoise et bleu ciel, vous pouvez tout aussi facilement en obtenir deux autres par changement des axes. Vous disposez donc de trois ensembles. Deux suffisent, les cellules turquoises sont l'intersection des deux, ce que Python sait faire très facilement.

Autre approche: vous raisonnez sur des "couronnes" d'indice N, chacune correspondant exactement au rayon N. Vous aurez donc une liste de listes ou mieux une liste d'ensembles. Bien entendu, il est alors immédiat d'avoir des "disques", un disque de rayon N étant l'union des couronnes de 0 à N. Mais garder les couronnes permet peut-être plus de souplesse.
Vous pouvez fabriquer ces couronnes de proche en proche, la N + 1 à partir de la N. Il suffit de faire six fois la même chose, à savoir déduire N + 1 cases à partir de N cases. Les N cases sont un coté avec un seul des sommets.
Ça devient intéressant si vous pouvez borner le rayon. A ce moment-là, vous créer vos ensembles d'une façon ou d'une autre, soit à la conception en générant éventuellement du code avec un script auxiliaire, soit lors des inits de votre programme. Vous pouvez d'ailleurs choisir pour le rayon un maximum raisonnable, et conserver la possibilité de le dépasser au prix d'un ralentissement temporaire en cours d'exécution.
J'ai utilisé ce genre de truc pour générer des tables de lookup, le code généré n'étant pas nécessairement du Python, mais plutôt du C ou de l'assembleur.

Ah oui merci :D

En effet, le coup de l'intersection est plutôt séduisant, parce que niveau code source je le pressent court et clair.
Me reste plus qu'à trouver comment changer d'axes :mouarf:...

Et l'idée que vous suggérez par la suite a aussi l'air très bien, même si dans mon cas j'aurais plus souvent besoin de disques que de couronnes, il suffira alors pour obtenir une couronne de faire une différence

Dans tous les cas, merci encore :ccool: