10-01-2017, 10:34 AM
Le moins de tests possibles par rapport à quoi? Que testes-tu? Le déplacement d'un joueur? Dans ce cas, je ne pense pas que les centaines (voire milliers) de gens qui ont bossé sur ce problème se soient trompés en utilisant des arbres binaires...
Car si tu cherches à savoir si un point est dans un arbre (ou autre élément solide), l'arbre binaire sera vite parcouru (voire la variante "on descend l'arbre jusqu'à tomber sur un noeud marqué "pas obstacle", ou "obstacle"; s'il est marqué "mélange", on descend encore"). Pour un segment, tu auras à peu près le même principe (tu vas simplement te retrouver avec plusieurs segments lorsque tu descendra assez bas dans l'arbre).
Après, d'un point de vue pratique (pour la curiosité, c'est bien, mais je sais que tu vas vouloir en faire un jeu en prod derrière):
- T'as vraiment besoin de cette optimisation avant même de sortir l'alpha de TMI?
- Pourquoi ne pas prendre un FW qui gèrera ton canvas plutôt que de réinventer des trucs et devoir implanter du code système en boucle au lieu de te concentrer sur le coeur de jeu?
- Qu'est ce qui te fait dire que juste limiter le nombre de rectangles soit le plus optimal? Une machine traite très bien une grande quantité de données simples, du même type, et très mal les petites quantités de données complexes et spécifiques.
- Si t'en as la possibilité, il existe des fonctions géométriques en MySQL qui font ce genre de calcul, et très vite même sur de grandes quantités de data (mais je crois que t'es en canvas coté client là, donc pas sûr que ce soit utilisable, mais il existe surement ce genre de FW de calcul en JS)
Car si tu cherches à savoir si un point est dans un arbre (ou autre élément solide), l'arbre binaire sera vite parcouru (voire la variante "on descend l'arbre jusqu'à tomber sur un noeud marqué "pas obstacle", ou "obstacle"; s'il est marqué "mélange", on descend encore"). Pour un segment, tu auras à peu près le même principe (tu vas simplement te retrouver avec plusieurs segments lorsque tu descendra assez bas dans l'arbre).
Après, d'un point de vue pratique (pour la curiosité, c'est bien, mais je sais que tu vas vouloir en faire un jeu en prod derrière):
- T'as vraiment besoin de cette optimisation avant même de sortir l'alpha de TMI?
- Pourquoi ne pas prendre un FW qui gèrera ton canvas plutôt que de réinventer des trucs et devoir implanter du code système en boucle au lieu de te concentrer sur le coeur de jeu?
- Qu'est ce qui te fait dire que juste limiter le nombre de rectangles soit le plus optimal? Une machine traite très bien une grande quantité de données simples, du même type, et très mal les petites quantités de données complexes et spécifiques.
- Si t'en as la possibilité, il existe des fonctions géométriques en MySQL qui font ce genre de calcul, et très vite même sur de grandes quantités de data (mais je crois que t'es en canvas coté client là, donc pas sûr que ce soit utilisable, mais il existe surement ce genre de FW de calcul en JS)