1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    février 2009
    Messages
    1
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2009
    Messages : 1
    Points : 1
    Points
    1

    Par défaut Remplissage de zone à la sauce Paper.io

    Bonjour à toutes et à tous,

    Présentation du problème :
    Je souhaiterais trouver et reproduire l'algorithme qui régit la physique des jeux Paper.io ou Splix.io.
    Ci-dessous quelques explications :
    1/ Vous disposez d'une zone dite "conquise" :
    Nom : ZoneConquise.PNG
Affichages : 35
Taille : 410 octets
    2/ A l'aide d'un curseur pouvant se déplacer horizontalement ou verticalement, vous pouvez tracer les nouvelles frontière de votre zone conquise :
    Nom : Curseur.PNG
Affichages : 33
Taille : 2,3 Ko
    3/ Les nouvelles frontières de la zone conquise sont mises à jour dès que le curseur retourne en zone conquise. L'intégralité du chemin et de la zone intérieure est conquise :
    Nom : Conquete.PNG
Affichages : 33
Taille : 882 octets

    Un problème qui me semblait assez simple à première vue

    Ressources à disposition :
    - les coordonnées x et y de chaque point ;
    - le chemin emprunté par le curseur en temps réel ;
    - et donc les coordonnées et angles des sommets du chemin ;
    - les coordonnées de la zone de départ.

    Pistes explorées :
    1/ J'ai commencé par me dire : "Dès que tu es de retour sur une zone conquise cherche l'espace intérieur de ton tracé de chemin". Problèmes :
    - la zone du chemin n'est pas fermée, de la zone conquise ferme le reste du polygone :
    Nom : FermeturePolygone.PNG
Affichages : 33
Taille : 1,1 Ko
    - comment déterminer la zone intérieure de la zone extérieure :
    Nom : ExterieurInterieur.PNG
Affichages : 33
Taille : 1,1 Ko
    Si je dispose de tous les sommets du polygone (en ignorant donc le problème précédent), j'ai trouvé le très bon algorithme cité par royhowie ici.

    - quel point contrôler pour le test extérieur/intérieur :
    Nom : QuelControle.PNG
Affichages : 33
Taille : 1,8 Ko
    - il risque d'y avoir plusieurs zone intérieure :
    Nom : ZonesMultiples.PNG
Affichages : 34
Taille : 2,3 Ko
    2/ Sentant l'embourbement poindre je me suis dis : "Peut-être que je peux simplement convertir le chemin en zone conquise puis partir à la recherche des trous". Problèmes :
    - comment mettre à jour les angles du nouveau territoire. Les zones peuvent être tarabiscotées :
    Nom : QuelsAngles.PNG
Affichages : 33
Taille : 3,2 Ko
    - parcourir l'ensemble des points internes au polygone pour convertir en zone conquise doit être extrêmement gourmand en calcul.

    L'appel à l'aide :
    Comme je commence à caler, j'ai décidé de demander de l'aide à la communauté. C'est là que vous intervenez
    Avez-vous déjà eu l'occasion de travailler sur des sujets similaires ?
    Auriez-vous des idées, pistes ou conseils qui pourrait m'aider face à un tel problème ?

    Si vous ne comprenez pas quelque chose (j'ai essayé de faire simple mais j'ai tout à fait pu mal m'expliquer), ou avez besoin de plus d'informations, faites le moi savoir !
    Je vous remercie d'avance pour vos lumières.

    A+

    Quentin

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 992
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 992
    Points : 15 927
    Points
    15 927

    Par défaut

    Bonsoir,

    Je propose un truc tout simple:
    1. Tracer le contour de la forme totale (contour tracing algorithm)
    2. Faire un remplissage "scanline" du contour.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 250
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 250
    Points : 3 448
    Points
    3 448

    Par défaut

    Salut

    si je comprend bien tu veut remplir les éléments qui se trouve entouré par les zones conquise

    1°) le plus simple pour connaitre le sens du remplissage c'est de chercher le min et le max en x et en y de tes zones précédemment conquise
    2°) Vérifier que la zone est bien une zone fermé (le dernier élément de ton polygone est égale au premier P[0]=P[N])
    3°) si la case se trouve entre le min et le max en x et en y il y'a de forte probabilité que celle-ci devienne une zone conquise (système de box englobant)
    ensuite tu peut appliquer plusieurs algorithme pour affiner ta recherche
    fait une recherche sur "winding Number test" ou "crossing number test"
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

Discussions similaires

  1. remplissage de zones de couleur avec scanline
    Par Basile le disciple dans le forum Débutant
    Réponses: 43
    Dernier message: 02/06/2013, 12h54
  2. [AC-2007] Remplissage de zones venant d'une liste déroulante
    Par fbourdon dans le forum IHM
    Réponses: 1
    Dernier message: 21/10/2009, 17h41
  3. Réponses: 21
    Dernier message: 02/06/2009, 19h02
  4. remplissage de zones de textes à partir d'une base
    Par metwa dans le forum Débuter
    Réponses: 3
    Dernier message: 19/04/2008, 13h23
  5. Remplissage d'une zone d'un canvas
    Par ulysse66x dans le forum Composants VCL
    Réponses: 5
    Dernier message: 31/01/2004, 13h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo