Bonsoir, je crée une intelligence artificielle qui joue toute seule au snake, et j'ai actuellement des soucis avec une optimisation que j'ai du mal à intégrer:
 
 
Pour que le snake survive le plus longtemps, il faudrait qu'il ne s'enferme pas dans sa propre queue, et pour cela calculer avant de jouer un coup si la situation est irréversible puis ensuite calculer si l'espace de la prison est suffisament grand pour s'en sortir en vie.
 
Des images parleront probablement beaucoup plus que des mots:
 
 
Ici, le serpent fonce sur le fruit .
 
 
 
 
Après avoir mangé le fruit, 2 possibilités s'offrent à lui:
 
-tourner à droite, il est en sécurité
 
-tourner à gauche, il va forcément mourir par la suite, il entre en prison pris au piège par sa propre queue
 
 
 
Actuellement, le snake se débrouille pour comprendre qu'il doit tourner à droite, mais plus la prison est grande en terme de carreaux, plus la puissance de calcul nécessaire est grande .
 
 
 
Si vous m'avez suivi, alors j'aurais besoin de votre aide pour réaliser une fonction qui analyserait la situation à chaque déplacement, et détecterait la présence de la tête du serpent à l'entrée d'une prison potentielle, et (le serpent étant de toute manière dans une prison) choisirait de faire bouger le snake vers la prison la plus grosse.
 
On dispose d'un tableau qui représente la matrice du terrain, 0=sol, 1=queue du snake , avez vous idée d'un algo qui puisse s'en sortir?
 
J'ai pas mal cherché et je bloque sévère
 
 
 
merci !  

Bonjour,
 
Peut être que ces quelques liens pourront vous être utile :
https://stackoverflow.com/questions [...] ing-itself
http://www.datagenetics.com/blog/april42013/
http://www.cs.unh.edu/~ruml/cs730/ [...] l-2011.pdf
http://www.gamedev.net/page/resour [...] nake-r1175
http://bramridder.com/ai-blog.php/ [...] snake-game

Salut
J'ai peut-être une idée
 
Si le snake tourne à gauche, alors sa tête est dans le même sens que ce qu'il était quand il était sur la ligne du dessus (là où il y a actuellement sa queue). Et si c'est le cas alors il meurt forcément puisqu'il est alors enfermé (spirale dans le même sens).
Te suffit de positionner sur chaque segment de queue un indicateur indiquant son sens de déplacement. Et en cas de contact avec ce segment alors la tête devra tourner dans le sens inverse. Cela ne dépend pas de l'espace libre restant donc temps de calcul minimum. Toutefois, quand un segment change de direction faut penser à mettre son indicateur à jour.
Ou alors, pas d'indicateur mais quand la tête atteint un segment, là tu calcules sa direction en live pour faire partir la tête dans l'autre sens...

Mon algo arive à se sortir de certaine de ces situations, c'est pas forcément un arrêt de mort de rentrer dans le même sens que la queue (il suffit de faire des zigzags ordonnés dans la cage jusqu'à ce qu'elle s'ouvre, parfois c'est possible)
Donc éliminer drastiquement tout ces cas sur ce critère n'est pas possible.
Et quid de la rencontre avec un mur?
Le mur n'a pas de vecteur direction (mon snake ne peut pas se cogner aux murs)
J'ai trouvé la solution sur un autre forum, il faut utiliser l'algorithme du pot de peinture, qui compte le nombre de cases dans la cage via une fonction recursive qui checke les cases à proximités de la case envoyée en paramètre.
Ca fait le taf
Merci en tout cas !
 
Honrisse, je regarde tes liens

Le site datagenetics n'apporte pas grand chose pour le snake, mais les articles du blog sont vraiment passionnants !
Le pdf  est très bien fichu, avec des stats et tout c'est intérressant mais ça manque d'un peu de technique
QUand aux autres sujets, ils sont sur les matchs entre plusieurs snake, ce qui n'à pas été prévu d'être implémenté dans mon code, donc la pluspart des algos utilisés ne me sont pas utiles
Merci beaucoup en tout cas!

 
Salut.
C'est possible d'avoir le lien   ?
J'ai trouvé ce lien qui est intéressant aussi : http://www-cs-students.stanford.ed [...] eprog.html

Je regarde ton lien

Pour ce qui est de l'algo du pot de peinture, bha le mec m'a donné son nom et j'ai chercher sur google ^^
Pour t'éviter de chercher, ce topic donne l'idée générale:
http://forum.macfr.com/index.php?showtopic=15827

Sauf qu'au lieu de checker des pixels on checke des cases, et au lieu d'en changer la couleur on stocke le nombre de case dans une variable qui circule recursivement + tableau à 2 entrées qui stocke les cases sur lesquelle le programme est déjà passé.

 
Le site datagenetics, je connaissais pas, mais c'est une vraie perle. Donc   pour le lien et drap pour plus tard