Concernant la création incrémentale de l'espace
Étant donné que l'espace est découpé en cases et que seules les cases adjacentes interagissent entre elles, une modification locale du graphe n'agit que sur une portion minime du graphe, c'est à dire des cases adjacentes à la case modifiée. Donc, pas besoin de tout recalculer à chaque fois.
La structure supportant ce changement atomique pourrait s'appuyer sur un dictionnaire de plante simulant un espace à deux dimensions ({(int, int):plante}), et sur un second dictionnaire donnant les couleurs associées ({(int, int):couleur}).
NEUTRE = 0
AMIE = 1
ENNEMIE = 2
COULEUR_NEUTRE = 'black'
COULEUR_AMIE = 'green'
COULEUR_ENNEMIE = 'red'
def liaison(p1, p2):
"""Retourne NEUTRE, AMIE ou ENNEMIE selon si la plante1 est neutre, amie ou ennemie avec la plante2"""
pass # TODO: appel aux dico AMIE et ENNEMIE
def voisines(x, y, espace):
"""Retourne un générateur de plante, représentant les voisins de (x;y) dans un ordre quelconque"""
return (espace[x+i, y+j]
for i, j in itertools.product(range(-1, 2), 2)
if j != 0 and i != 0 # on ne considère pas la case de la plante elle-même (elle n'est pas sa propre voisine)
)
def maj_couleur_carre(x, y, espace, couleurs):
"""Modifie la couleur du carré (x;y) selon ses liaisons avec ses voisins"""
plante = espace[x, y]
couleurs[x, y] = max(liaison(plante, voisine) for voisine in voisines(x, y, espace)))
def change_plante(x, y, espace, couleur, plante):
"""Modifie l'espace au coordonnées (x;y) pour que la plante donnée y soit placée
Si la plante est None, aucune plante ne sera placée et toute plante préexistante sera supprimée"""
espace[x, y] = plante
[maj_couleur_carre(i, j, espace, couleur) for i, j in voisines(x, y, espace)]
Concernant une recherche des meilleures solutions
Il existe des moyens, via des algorithmes indépendants du langage, pour résoudre ce problème combinatoire.
Pourtant, je ne ferais pas appel à une telle technique si le temps n'est pas une composante essentielle du programme. (si tout doit être calculé sur un microcontrôleur, avec des terrains et contraintes gigantesques)
Pour ce genre de problème, une méthode beaucoup plus simple est de plus en plus abordée : les langages logiques reposant sur la contrainte et la recherche de modèles stables.
La raison est la suivante : le problème est trop complexe pour avoir une solution optimale rapidement (combinatoire), et quand bien même un algorithme résoudrai le problème, sa complexité est telle que la maintenance n'est pas triviale. Autant sacrifier un peu de temps (et encore) pour travailler avec un outils plus adapté à la recherche de solution, suivant des heuristiques déjà prêtes, optimisées et optimisables.
Prolog, un langage français (cocorico), en est un bon exemple, très utilisé dans le domaine de la représentation de données, la query evaluation. (Watson d'IBM et le robonaute de la NASA utilisent Prolog comme base de donnée)
Answer Set Programming, un autre langage logique particulièrement optimisé pour les problèmes combinatoires, ne fonctionne pas comme Prolog, mais serais peut-être plus adapté dans ce cas. L'implémentation de Potassco, notamment Clingo dans ton cas (à essayer sur le web), permet d'interfacer l'outil avec python assez facilement, à l'aide du packaging pip.
Personnellement, j'utilise Answer Set Programming pour la manipulation et le traitement de concepts formels, et entre autre la recherche de cliques et de bicliques au sein d'un graphe. C'est impressionnant de simplicité et d'efficacité.
