8 pièce(s) jointe(s)
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" :
Pièce jointe 244821
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 :
Pièce jointe 244826
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 :
Pièce jointe 244833
Un problème qui me semblait assez simple à première vue :nono:
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
