Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Recherche un algorithme de déplacement pour un jeu de plateau


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Recherche un algorithme de déplacement pour un jeu de plateau
    Bonjour à toutes et à tous,
    Je me tourne vers vous suite à un problème que je n'arrive pas à résoudre depuis bientôt un mois malgré tout mes efforts.
    Effectivement je suis actuellement entrain de développer un jeu de plateau en JavaScript et je bloque sur l'algorithme à utiliser pour le déplacement.

    Pour mieux vous situer le contexte, le jeu est tour par tour, les joueurs (au nombre de 2) choisisses un vaisseau en début de partis qui à 2 caractéristiques à prendre pour mon algorithme :
    - le nombre de case de déplacement sont différent selon le vaisseau (et cette propriété peux changer aussi pendant la partie).
    - la taille du vaisseau peux varier de 1 à 3 cases de long (il à donc une orientation qui change selon ou il se déplace).
    La carte peux posséder divers obstacles :
    - les obstacles joueurs qui peuvent donc faire de 1 à 3 cases.
    - les obstacles de carte qui font tous une case.

    Ma problématique est donc quel serais le meilleur algorithme pour trouver ou peux se déplacer le joueur ou non. Jusqu'ici j'ai réussi à définir le périmètre maximum de déplacement, mais le problème est qu'il ne prend pas en charge les obstacles présent ni sa rotation si il se dirige vers tel ou tel endroit.

    Voici donc ou j'en suis dans ma recherche.
    Actuellement mon algorithme me donne ceci comme déplacement possible :
    Dans ce cas de figure le vaisseau fait 2 cases de taille (il avance par l'avant du vaisseau pour ce qui est de la rotation cependant son rayon de déplacement et calculer pour l'élément avant comme arrière) et son nombre de cases sur le quel il peux se déplacer est de 4.

    (carré vert = joueur / zone bleu = zone de déplacement / rond gris = obstacle)

    Hors ce que je cherche à obtenir est ceci :


    Si vous avez donc des idées, des débuts de piste ou même de la documentation que je n'aurais pas trouvé à ce sujet je suis preneur !! Merci d'avance pour votre temps et votre aide.

  2. #2
    Membre habitué
    Pourquoi veux-tu éliminer les cases bleues du haut, qui peuvent êtres atteintes si le vaisseau contourne les obstacles ?
    Il n'y a pas d'algorithme générique pour ce genre de problème, ça se gère en tableau et en termes de cases libres et de cases occupées.
    L'algo de base teste les cases.
    Savoir pour comprendre et vice versa.

  3. #3
    Nouveau Candidat au Club
    justement il ne peux pas contourner l'obstacle car il ne peux se déplacer que de 4 cases au maximum, hors sur le papier cela fait bien 4 cases sauf qu'il ne peux pas sauter par dessus.
    Je ne sais pas si je suis clair.

  4. #4
    Expert éminent sénior
    Bonjour

    Pourquoi ne fais-tu pas la liste de tous les cas possibles ?
    Il n'y a que 11 positions possibles pour passer au tour suivant.

    L'origine de la flèche symbolise l'arrière du vaisseau et la tête, l'avant.

    Chaque flèche provoque 11 flèches images. Si la flèche image a déjà été étudiée, avec autant ou moins de mouvements, on laisse tomber. Sinon, on la met dans la pile des flèches à étudier, avec le nombre de mouvements restants maximum.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  5. #5
    Nouveau Candidat au Club
    Effectivement c'est vrai que je n'avais pas du tout pensé à cette façon de faire.
    Pour ma part je ne peux pas avoir de déplacement latéral sans changement de direction cela limite donc les possibilités.
    Cependant je crois entrevoir un début de réponse à mon problème grâce à vous un grand merci !

  6. #6
    Expert éminent sénior
    Citation Envoyé par oodevilangeloo Voir le message
    Pour ma part je ne peux pas avoir de déplacement latéral sans changement de direction
    Alors le coloriage bleu est faux. Ou alors la rotation ne prend pas un tour. Mais dans ce cas là, on va à l'infini rien qu'en tournant.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.