Projet Mist2D

Montrez-nous vos talents !

Modérateur : L'équipe

Avatar de l’utilisateur
Hedge
Messages : 9255
Inscription : 20 juin 2011, 02:25
Sexe : ♂ Masculin
Localisation : Paris
Contact :

Re: Projet Mist2D

Message par Hedge »

C'est génial ça avance carrément bien tout ça!!! Fier de suivre l'évolution d'un tel projet! J'aurai adoré pouvoir t'aider!
Avatar de l’utilisateur
DonAkaVega
Messages : 338
Inscription : 23 avr. 2013, 10:28
Sexe : ♂ Masculin
Localisation : Gard

Re: Projet Mist2D

Message par DonAkaVega »

Très content de voir que ça avance. Et plutôt bien en plus :D
Hedge a écrit :J'aurai adoré pouvoir t'aider!
Tu pourras toujours aider les créateurs qui se serviront de Mist2D au niveau des scénarios, toi qui en rêves tant :P
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

Merci, avoir déjà votre soutien à tous m'aide beaucoup à continuer ce projet titanesque dans lequel je me suis lancé ;).
Image
Avatar de l’utilisateur
Leiaa
Messages : 5091
Inscription : 18 déc. 2011, 18:08
Sexe : ♀ Féminin
Localisation : Montargis

Re: Projet Mist2D

Message par Leiaa »

Même si je ne commente pas systématiquement l'avancement de ton projet
sache que je le suis avec grand intérêt, donc bravo pour ce qui est
accompli puis bon courage pour la suite. ;)
Image
Leiaa Norimaki sur Facebook
Avatar de l’utilisateur
Toryudo
Messages : 845
Inscription : 19 juin 2011, 21:36
Sexe : ♂ Masculin
Contact :

Re: Projet Mist2D

Message par Toryudo »

Juste pour savoir... tu vérifies tous les 1/60e de secondes les coordonnées de chaque vaisseau et chacun de leurs tirs par rapport aux coordonnées de ton propre vaisseau, c'est ça ? Et pour ça, tu vérifies par rapport à la coordonnée x1, x2, y1 et y2 qui forment la hitbox de ton vaisseau, exact ?

Sachant que certains Manic shooter ont des centaines de tir à l'écran, je me suis toujours demandé comment on pouvait comparer 500 hitbox de tirs avec la hitbox de notre propre vaisseau en répété 60 fois par secondes...
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

Leiaa a écrit :Même si je ne commente pas systématiquement l'avancement de ton projet
sache que je le suis avec grand intérêt, donc bravo pour ce qui est
accompli puis bon courage pour la suite. ;)
Pas de soucis Leiaa et ... Merci :D.

Toryudo a écrit :Juste pour savoir... tu vérifies tous les 1/60e de secondes les coordonnées de chaque vaisseau et chacun de leurs tirs par rapport aux coordonnées de ton propre vaisseau, c'est ça ? Et pour ça, tu vérifies par rapport à la coordonnée x1, x2, y1 et y2 qui forment la hitbox de ton vaisseau, exact ?

Sachant que certains Manic shooter ont des centaines de tir à l'écran, je me suis toujours demandé comment on pouvait comparer 500 hitbox de tirs avec la hitbox de notre propre vaisseau en répété 60 fois par secondes...
Je vais être un peu plus technique, je m'excuse d'avance pour ceux qui ne comprendront rien :/.
Spoiler :
C'est bien ce que je fais en pratique.

Les développeurs peuvent "demander" à Mist de vérifier 2 types de collisions: collision entre 2 éléments, et collisions entre 2 ensembles d'éléments. Ces éléments peuvent être de différentes nature (boites, points, droite, courbe, ...).

Quand on a besoin de savoir si une collision a eu lieu entre 2 éléments, on ne peut pas faire d'optimisation (on ne peut pas faire mieux que de simplement tester la collision). En revanche, si je veux savoir si 1 élément rentre en collision avec un ensemble d'éléments, là on peut optimiser.

Par exemple, imagine que le vaisseau se trouve tout à gauche, et que la boite englobante des tirs ennemis se trouve tout à droite. Si mon vaisseau ne se trouve pas dans cette boite englobante, alors je sais qu'il n'est en collision avec aucun tir (et ce, en ne testant la collision qu'avec 1 seule boite).

Une manière d'optimiser la recherche est donc de procéder par boites englobantes de plus en plus localisées. Si j'ai une collision avec la grande boite, je la découpe en 2/4 sous-boite et j'élimine les tirs qui se trouvent dans les boites avec lesquelles je ne suis pas en collision. C'est une recherche en arbre.

C'est une technique que j'ai apprise dans un cours d'infographie. Pour faire le rendu en 3D, on envoie des "rayons de lumières" dans chaque pixel de l'écran vers le monde 3D, et on le fait "rebondir" d'objet en objet pour connaitre la couleur qui sera affichée par ce pixel. Là on parle d'une collision entre 1 élément des centaines de milliers de polygones, c'est pour ça qu'ils ont besoin de techniques super efficace comme celle que je t'ai décrite pour s'en sortir.

La question que je me pose encore concernant cet algorithme est de savoir si on peut l'adapter efficacement pour vérifier les collisions entre 2 ensembles (et non 1 élément >< 1 ensemble). Pour l'instant, la solution la plus satisfaisante serait d'itérer sur les éléments d'1 des 2 ensembles (le plus petit) et d'utiliser cet algorithme à chaque itération, mais je réfléchis toujours à un algorithme qui pourrait comparer directement les 2 arbres.

Actuellement, Mist n'utilise pas cet algorithme optimal car il n'est utile que dans des cas assez spécifique (comme un Manic Shooter). Mist se contente donc de tester exhaustivement toutes les collisions possibles. Je préfère me laisser encore un peu de temps pour réfléchir à un meilleur algorithme, et me concentrer sur d'autres choses pour le moment.

L'optimisation "ultime" que j'aimerais intégrer à terme serait de vérifier s'il y a eu une collision entre 2 frames, car si 2 éléments se déplacent trop rapidement, ils pourraient se croiser sans se toucher ni au temps 't', ni au temps '(t + 1)'. En travaillant en 60 fps, on limite fortement les risques, mais c'est toujours possible.
En bref, on peut développer des méthodes vraiment très poussées pour gérer les collisions, mais les développeurs eux n'ont pas besoin de le savoir. Ils peuvent demander les tests de collisions qu'ils veulent à Mist, mais ils ne peuvent pas modifier les méthodes utilisées (moins de liberté, mais plus de garanties sur le bon fonctionnement du jeu).
Image
Avatar de l’utilisateur
Toryudo
Messages : 845
Inscription : 19 juin 2011, 21:36
Sexe : ♂ Masculin
Contact :

Re: Projet Mist2D

Message par Toryudo »

Eh ben... :/
Oui, je n'ai pas trouvé de meilleure réponse ! Enfin, je vois un peu mieux la principe maintenant. Et de toute façon, même dans les Manics Shooter, le frame rate baisse quand il y a trop de tirs... Alors j'imagine qu'il n'y a même pas de technique ultime si efficace que ça. Ils finiront bien par trouver mieux que mieux de toute façon, on peut compter là dessus :)

En tout cas, bonne chance pour la suite !
Avatar de l’utilisateur
perchu
Meilleur détective hedg.fr
Meilleur détective hedg.fr
Messages : 1860
Inscription : 18 déc. 2012, 21:08

Re: Projet Mist2D

Message par perchu »

Félicitation pour ton projet, j’espère que tu trouveras le temps de l'avancer encore plus, j'ai vraiment envie de jouer avec tes librairies.
Toryudo a écrit : Oui, je n'ai pas trouvé de meilleure réponse ! Enfin, je vois un peu mieux la principe maintenant. Et de toute façon, même dans les Manics Shooter, le frame rate baisse quand il y a trop de tirs...
La baisse de frame rate n'est pas dû réellement à la gestion de collision dans les maniac shooter, mais plus à la quantité d’élément à l'écran, dans un maniac shooter, tu ne gères souvent la collision qu'autour de ton vaisseau, donc tu ne géres "que" les éléments proches du vaisseau. Le ralentissement est dû au nombre de sprites à afficher et maintenant avec les cartes graphiques surpuissantes, ce ralentissement est émulé. Pour te donner une idée, tu prends une console dos, elle travaille plus vite en arrière plan car il n'y a pas de texte à afficher ou encore en 3D tu prends un jeu type counter strike par exemple et tu te colles à un mur, tu auras alors tes fps qui montent.
Image
TimeSpinner: Castlevania DS :o
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

@perchu
J'ai aussi hâte de pouvoir sortir une première version pour que tout le monde puisse en profiter ;). Et je pense que tu as raison pour les Manic Shooters.
Image
Avatar de l’utilisateur
Toryudo
Messages : 845
Inscription : 19 juin 2011, 21:36
Sexe : ♂ Masculin
Contact :

Re: Projet Mist2D

Message par Toryudo »

perchu a écrit :Tu ne gères souvent la collision qu'autour de ton vaisseau, donc tu ne géres "que" les éléments proches du vaisseau.
Mais pareil, pour ça, tu es obligé de savoir si les tirs sont effectivement proche de ton vaisseau ou non. Donc, tu fais une pseudo détection de collision avec ta boite englobante qui déterminera les tirs possiblement en collision avec la véritable hitbox... non ?
Parce qu'ensuite, dès que tu bouges ton vaisseau, la boite est également bougée, donc il faut que tu reprennes tous tes calculs et que tu retrouves tous les tirs qui sont maintenant proche de ton vaisseau... Enfin, j'avoue, ça doit être une solution plus "graphique" que ce que j'imagine. Plus mathématique aussi.


Ce que je vois du fonctionnement normal, c'est un parcours d'une liste de tirs existants. Au mieux, tu as une liste de tirs existants et une liste de tirs proches et par rapport à la vitesse des tirs en général, tu sais qu'il faut, par exemple, au moins une seconde avant qu'un tir passe de l'état "existant" à l'état "possiblement proche" sans pour autant avoir touché ton vaisseau parce que pas assez rapide. Après, je ferais un parcours collision tous les 1/60 pour les tirs proche et une fois par seconde, je parcours la liste des tirs existants pour recréer une liste des tirs qui sont proches de mon vaisseau.
Ça pourrait marcher un truc pareil ?
Comme je ne suis pas le dieu des maths, je cherche toujours la solution qui serait la plus simple pour moi... ;)
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

Perso, ce que je ferais, ça serait de calculer toutes les distances tirs/vaisseau pour avoir un premier tri de tirs qui toucheraient potentiellement le vaisseau. Après, suivant la taille de cette liste, soit je testerais exhaustivement toutes les collisions restantes, soit j'utiliserais des boites englobantes pour en réduire le nombre avant de faire un test exhaustif.

C'est le même principe que pour les techniques de tri: une technique optimale sera moins efficace qu'une technique naïve sur de toutes petites instances (ex: trier une dizaine d'éléments). Du coup, la meilleure façon de faire consiste à "combiner" les 2, en utilisant la méthode optimale pour faire "le gros" du boulot, et on termine avec une technique "naïve".

Mais honnêtement, je pense que c'est vraiment chercher la petite bête. Je ne crois pas que ça soit sur les tests de collisions que l'on perd le plus de temps (plus maintenant en tout cas, mais à l'époque ça pouvait jouer).
Image
Avatar de l’utilisateur
perchu
Meilleur détective hedg.fr
Meilleur détective hedg.fr
Messages : 1860
Inscription : 18 déc. 2012, 21:08

Re: Projet Mist2D

Message par perchu »

Toryudo a écrit : Mais pareil, pour ça, tu es obligé de savoir si les tirs sont effectivement proche de ton vaisseau ou non.
Et tu le sais car c'est le jeu/le dev qui a créer le tir, on sait comment ça part et comment ça réagit, donc on sait à l'avance finalement où est le tir, le jeu cheat :lol: .


Le problème des collisions est très complexe, tu as des bouquins juste pour ça mais il faut raisonner sur 2 facteurs, les frames et la puissance de calcul, tu parles souvent de 1/60 sûrement en referance au 60Hz. On a 60 frames par seconde, si tu veux calculer que sur une seul toute les 60 frames, il faut regarder de combien se déplace au max ton vaisseau entre 2 frames, soit n pixels, et de combien se déplace un tir, soit m pixels, le cas le plus merdique est que le vaisseau et le tir fonce l'un vers l'autre, donc m+n pixels, si tu regardes 1 fois toutes les 60 frames, il faut regarder dans un carré qui englobe un cercle rayon 60*(m+n), après c'est le cas parfait car derrière il faut voir si tu peux tout regarder sans perdre de puissance, j'entends par là que si tu regardes toutes les 60 images, s'il y a eu collision ou pas, tu peux avoir un ralentissement toutes les 60 images si le CPU est à la ramasse.

Après c'est clair que s'emmerder dessus, c'est chercher la petite bête mais c'est une question qui travaille les devs de jeux depuis plus de 30 ans.

Ma première idée de collision était d'utiliser des ombres et compter les pixels afin d'avoir la précision mais à chaque frame, ça consomme mine de rien, on sent que le jeu perd en fluidité face à un autre système. Désolé de pourrir ton sujet avec ça mais je trouve la conversation intéressante.
Image
TimeSpinner: Castlevania DS :o
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

Pas de soucis, je trouve aussi que c'est un sujet très intéressant ;). Je pense qu'elle était pertinente à une certaine époque comme la Nes et la Super Nes, mais aujourd'hui ça me semble dérisoire comparativement à la complexité du rendu en 3D où ce sont des millions de collisions qu'il faut vérifier à chaque frame. C'est pour ça aussi qu'aujourd'hui c'est d'autant plus accessible de faire de la 2D car on a plus besoin d'aller chercher des algo ultra performants pour faire ce genre de choses.

Pour en revenir à Mist, je pense que j'optimiserais tout à terme, notamment parce que travaillant dans l'IA, j'aimerais bien y intégrer de vraies IA (et ça, ça peut consommer beaucoup de ressources suivant les méthodes), et toutes ces optimisations me seront bien utiles pour y parvenir.
Image
Avatar de l’utilisateur
M. Resetti
Messages : 29
Inscription : 24 sept. 2013, 19:21

Re: Projet Mist2D

Message par M. Resetti »

Un projet très intéressant, j'avait une époque 'RPG Maker' donc c'est un univers que je connais bien. Et comme je suis assez exigeant, il y a toujours quelque chose qui me plais pas dans ce genre d'outil. J'ai tendance à préférer faire les choses moi même, donc ton idée est très sympa.

Question bête car j'ai peut être mal lu, tu as pas un site pour avoir des images de ce que ça donne, je pense pas avoir le temps pour tester moi même en ce moment^^
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

Merci pour ton message :).

Idéalement j'aimerais réussir à contenter tout le monde, en offrant beaucoup de possibilités pré-implémentée pour les débutant tout en permettant à ceux qui le souhaitent d'ajouter de nouvelles fonctionnalités en fonction de leurs besoins.

Je suis convaincu qu'il sera possible à moyen/long terme de créer une interface type "XXX Maker" pour simplifer encore d'avantage le développement, mais je ne peux malheureusement pas me dédoubler, donc je préfère me concentrer sur la base.

Il n'y a pas encore de site car je veux d'abord pouvoir proposer une version exploitable avec documentation et tutoriaux (sinon le site ne sert pas à grand chose). Idéalement, j'aimerais lancer tout ça pour mi-2014, mais il n'est pas impossible que ça soit plutôt vers fin 2014 (il y a toujours des imprévus :p).

Je ferai surement une petite MAJ pour faire le point courant décembre ;).
Image
Avatar de l’utilisateur
M. Resetti
Messages : 29
Inscription : 24 sept. 2013, 19:21

Re: Projet Mist2D

Message par M. Resetti »

J'ai essayé de le télécharger mais les liens ne répondent plus c'est normal? J'avais finalement bien envie de voire ce que ça donne maintenant que mon temps se libère^^
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

Oui c'est normal, j'ai supprimé les petites démo car elles datent un peu maintenant :p. Encore un peu de patience ;).
Image
Avatar de l’utilisateur
djidane535
Messages : 1975
Inscription : 31 juil. 2012, 11:54
Sexe : ♂ Masculin

Re: Projet Mist2D

Message par djidane535 »

J'ai mis à jour le premier post pour faire le point sur Mist2D ;).
Image
Avatar de l’utilisateur
DonAkaVega
Messages : 338
Inscription : 23 avr. 2013, 10:28
Sexe : ♂ Masculin
Localisation : Gard

Re: Projet Mist2D

Message par DonAkaVega »

Je suis très content de voir que le projet avance toujours.
Je le suis d'autant plus lorsque je découvre une date de sortie pour la première version. :)

Ca s'annonce de mieux en mieux. Continue comme ça l'ami ! :D
Avatar de l’utilisateur
captain-pipo

Re: Projet Mist2D

Message par captain-pipo »

Et ben on peut dire que tout ceci se précise.
Bravo djidane, beau boulot !
J'ai tout compris jusqu'à la partie technique ^^"

Bon courage pour la suite !
Répondre

Qui est en ligne ?

Utilisateurs parcourant ce forum : Aucun utilisateur inscrit et 3 invités