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