Discussion :

[QUENTINQUENTIN]

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

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 :

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 :


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 :

- comment déterminer la zone intérieure de la zone extérieure :

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 :

- il risque d'y avoir plusieurs zone intérieure :

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 :

- 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

[pseudocode]

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.

[anapurna]

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"