Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
514 connectés 

  FORUM HardWare.fr
  Programmation
  C

  Rendre la géométrie d'une matrice compréhensible à un programme

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Rendre la géométrie d'une matrice compréhensible à un programme

n°2217809
brikdelay
Posté le 27-01-2014 à 23:32:16  profilanswer
 

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:
 
 http://image.noelshack.com/fichiers/2014/05/1390861192-avant-fruit.png
Ici, le serpent fonce sur le fruit .
 
 
 http://image.noelshack.com/fichiers/2014/05/1390861194-fruit.png
 
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
 
 http://image.noelshack.com/fichiers/2014/05/1390861198-apres-fruit.png
 
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 :o
 
 
 
merci !  :jap:

mood
Publicité
Posté le 27-01-2014 à 23:32:16  profilanswer
 

n°2217815
honrisse
Posté le 28-01-2014 à 08:37:35  profilanswer
 
n°2217907
Sve@r
Posté le 28-01-2014 à 17:51:33  profilanswer
 

brikdelay a écrit :


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
 
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 :o


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...


Message édité par Sve@r le 28-01-2014 à 21:12:20

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
n°2217967
brikdelay
Posté le 28-01-2014 à 22:14:22  profilanswer
 

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) :p
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 ! :jap:
 
Honrisse, je regarde tes liens :jap:

n°2217978
brikdelay
Posté le 29-01-2014 à 08:30:08  profilanswer
 

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!

n°2217989
honrisse
Posté le 29-01-2014 à 10:03:12  profilanswer
 

brikdelay a écrit :


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 :)


 
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


Message édité par honrisse le 29-01-2014 à 10:06:32
n°2218049
brikdelay
Posté le 29-01-2014 à 18:39:40  profilanswer
 

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é.

 


Message édité par brikdelay le 29-01-2014 à 18:41:34
n°2218106
Yonel
Monde de merde !
Posté le 30-01-2014 à 10:38:24  profilanswer
 


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


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  Rendre la géométrie d'une matrice compréhensible à un programme

 

Sujets relatifs
[VBA] travailler sur un tableau pendant qu'un programme tourne[VBS]Programme decompression tar.gz, quel outil
[VB.NET] Programme d'envoi de paquetBug programme asm 8086
Matrice, extraire par indexaide pour un programme en python (réception de e mails)
Aide pour un petit programme en CProgramme répertoire téléphonique (BUG) HELP PLEASE !!!
programme non open source sous linuxBesoin d'aide pour creer un programme
Plus de sujets relatifs à : Rendre la géométrie d'une matrice compréhensible à un programme


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR