Bonjour,
Mes camarades et moi travaillons sur les problèmes dits difficiles.
L'an dernier nous avions travaillé sur le problème du voyageur de commerce et nous avions implémenté un algorithme génétique afin d'effectuer une résolution approché du problème.
Cette année, après une nouvelle étude des différents types de problèmes et par conséquent de la classification de Chomsky, nous cherchons à réaliser un petit jeu bien connu : le Tower Defense.
Un de nos objectif est de trouver le positionnement optimal de tours de tel sorte que l'ennemi n'arrive pas à la cible, ou du moins qu'il soit au maximum blessé.
Le jeu se présente ainsi :
Uploaded with ImageShack.us
Uploaded with ImageShack.us
Nous avons donc un point d'arrivé. L'ennemi, en l’occurrence un poulet, à n points d'entrée (la partie inférieur du plateau).
Le plateau peut être constitué d'obstacle ( buissons, autre...)
Modélisation du jeu :
Notre plateau de jeu est modélisé par un graphe. En effet, chaque case (sauf les obstacles) sont représentés par un sommet. Chaque sommet est relié à tout ses voisins. Une tour a un champs de vision bien défini, dans un premier temps nous considérons que son champ de vision est défini par la norme infinie. De plus une tour est flottante, c'est à dire qu'elle n'est pas considérée comme étant un obstacle. Le poulet perd un point de vie par case "vue" par une tour.
Notre poulet ne se déplace pas bêtement. En effet, il va essayer d'atteindre sa cible par le chemin le plus court qui le blesse le moins.
Cas où le poulet a un point de vie :
Dans ce cas, nous avons pensé à appliquer un algorithme de coupe minimal (min-cut) afin de trouver la plus petite coupe qui divise notre terrain de jeu en deux. Le problème est le suivant : Comment recouvrir un certain nombre de nos sommets (celles qui permettent la coupe) du graphe.
Cas où le poulet a n points de vie :
Dans ce cas, le problème nous parait plus complexe. En effet, effectuer n coupe minimal et ensuite appliquer une résolution de recouvrement ne parait pas être la meilleure des solutions.
Nous nous demandons alors comment placer nos tourelles de tels sortes que leur placement soit optimal ET que la OU les coupes (en terme de profondeur) soit maximal (afin que le poulet soit, à terme, le plus blessé possible).
Nous venons sur ce forum, non pas pour avoir la solution, mais avoir des idées, des indices, etc...
Toutes réflexions/idées sont les bienvenues
Merci d'avance !
-----
