Un jeu vidéo est un processus de création complexe qui demande des compétences dans un tas de domaines liés de près ou de loin. Ce n’est pas pour rien que les projets modernes sont conçus en équipes spécialisés, soit dans la programmation pure et dure, la physique, l’art, la musique, etc. Quand on le fait par passion et que l’on est seul, le découragement peut survenir à tout moment. Mais moi, cette solitude me stimule au contraire. C’est le défi qui me motive. Et cette semaine j’ai réalisé que j’étais loin de voir la lumière au bout du tunnel…
Comme je l’ai mentionné dans mon premier billet, je travail sur les mathématiques vectoriels et matricielles. En fait, j’ai pas mal fini d’implanter les classes de ces deux concepts. Les vecteurs sont la base des mouvements dans un jeu vidéo. Ils représentent une position et une direction ce qui est en soit suffisant pour que l’ordinateur dessine une image à l’écran. Je ne parlerai pas des matrices, car j’avoue que leurs utilités me laissent perplexe pour le moment. Pour revenir au vecteurs, maintenant que leur implémentation est fini, il faut passer à la prochaine étape soit le mécanisme de collision entre les entités. Ça ne sera pas évident à faire car je dois complètement refaire mon système de sprites (élément de jeu, qui bouge généralement). La raison est que la première fois, je n’étais pas au courant de l’approche vectoriel et j’ai donc tout programmé avec des représentations bêtes de positions (x,y) à l’écran. Avec des entiers. Apparemment, ça ne fonctionne pas comme cela. Je dois donc refaire mes classes de sprites pour que leurs mouvements soient basés sur des manipulations de vecteurs. Et à chaque fois qu’une sprite bouge, le système doit vérifier s’il entre en collision avec une autre. Ce calcul devient vite fastidieux. S’il y a 1000 sprites à l’écran (remarquez qu’on a rarement 1000 sprites), cela représente 1000x1000 soit 1000000 de vérification par frame. Normalement on vise 60 frames par secondes pour que le jeu paraisse fluide. Donc 60 millions de calculs par secondes… Le CPU vient vite surchargé si le code n’est pas optimisé. Une fonction qui revient souvent dans le calcul vectoriel est la racine carrée d’un nombre puisque la géométrie vectorielle est basée sur le triangle droit et le théorème de Pythagore. Hors, nativement, la racine carrée est coûteuse en temps CPU. Heureusement on peut estimer la racine carrée plus rapidement avec assez de précision pour que l’optimisation en vaille la peine. J’ai basé mon algorithme sur la méthode des Babyloniens et de Bakhshali. J’ai trouvé tout cela sur Wikipedia, je suis loin d’être un génie. Voici donc mon code qui remplacera la racine carré native et le temps d’exécutions pour 100 millions d’opérations.
Ici, je montre la méthode Babylonienne, c’est celle que j’ai adopté. Elle est précise et 17 fois plus rapide que la méthode native. Cette méthode est implémenté dans la boucle for. La difficulté que j’ai eu, était qu’il fallait fournir à la formule un estimé de la racine carré du nombre cherché. Alors j’ai utilisé une variable globale cfaROOT qui contient toute les racines carrées de 1 à 100. C’est à cela que sert la série de test if. Dépendamment du nombre, on trouve la racine carrée pré calculée dans cfaROOT, et on la modifie selon l’amplitude du nombre. Par exemple, la racine de 100 est 10. La racine de 10000 est de 100. Donc 10 fois plus. C’est ce que fait la série de tests, ils déterminent la racine approximative la plus près, et elle est utilisé dans le calcule Babylonien pour être précisé. Avec deux itérations de la méthode Babylonienne, j’obtiens une précision à 5 chiffres après le point. 17 fois plus rapidement, je le rappel.
Ok, ça suffit. Je vous ai assez assommé avec des explications nébuleuses. Lorsque je travail sur mon projet, je partage mon temps en deux (je vous épargne les obligations parentale). Le matin, programmation. L’après-midi, création, graphisme, concept. Cette semaine j’ai donc sortie mes crayons et je me suis mis à gribouiller. J’avais dessiné une ébauche de scène où l’on voit deux personnages à la recherche d'un engin perdu. Un vaisseau de combat avec des possibilités de voyage dans le temps, enfin on verra. Dans le ciel, en avant de la lune, on voit la silhouette d’un vaisseau orbital qui fera office de base à mes protagonistes. J’ai planché sur ce vaisseau orbital. À force de zigonnage, j’en suis venu à ce concept :
Ici on voit le vaisseau en deux positions. Contracté, il est en mode hyperespace. Étiré, il est en mode orbital. Je ne suis pas sûr encore de ces fonctions et du pourquoi de ces deux modes, mais en travaillant dessus des idées me sont venus quand à l’histoire globale du jeu. J’ai même pensé à faire de ce vaisseau le fleuron de l’ANUQ, l’armée des nations unifiées du Québec. Première force militaire mondiale…. Je vais y coller la fleur de lys en quelque part comme logo. J’aime autant ne pas trop en dire sur l’histoire pour le moment, ça change à toutes les deux secondes dans ma tête. Enfin, dites moi ce que vous en pensé. Vous pouvez aussi aller me voir sur mon compte Deviant Art.
Comme je l’ai mentionné dans mon premier billet, je travail sur les mathématiques vectoriels et matricielles. En fait, j’ai pas mal fini d’implanter les classes de ces deux concepts. Les vecteurs sont la base des mouvements dans un jeu vidéo. Ils représentent une position et une direction ce qui est en soit suffisant pour que l’ordinateur dessine une image à l’écran. Je ne parlerai pas des matrices, car j’avoue que leurs utilités me laissent perplexe pour le moment. Pour revenir au vecteurs, maintenant que leur implémentation est fini, il faut passer à la prochaine étape soit le mécanisme de collision entre les entités. Ça ne sera pas évident à faire car je dois complètement refaire mon système de sprites (élément de jeu, qui bouge généralement). La raison est que la première fois, je n’étais pas au courant de l’approche vectoriel et j’ai donc tout programmé avec des représentations bêtes de positions (x,y) à l’écran. Avec des entiers. Apparemment, ça ne fonctionne pas comme cela. Je dois donc refaire mes classes de sprites pour que leurs mouvements soient basés sur des manipulations de vecteurs. Et à chaque fois qu’une sprite bouge, le système doit vérifier s’il entre en collision avec une autre. Ce calcul devient vite fastidieux. S’il y a 1000 sprites à l’écran (remarquez qu’on a rarement 1000 sprites), cela représente 1000x1000 soit 1000000 de vérification par frame. Normalement on vise 60 frames par secondes pour que le jeu paraisse fluide. Donc 60 millions de calculs par secondes… Le CPU vient vite surchargé si le code n’est pas optimisé. Une fonction qui revient souvent dans le calcul vectoriel est la racine carrée d’un nombre puisque la géométrie vectorielle est basée sur le triangle droit et le théorème de Pythagore. Hors, nativement, la racine carrée est coûteuse en temps CPU. Heureusement on peut estimer la racine carrée plus rapidement avec assez de précision pour que l’optimisation en vaille la peine. J’ai basé mon algorithme sur la méthode des Babyloniens et de Bakhshali. J’ai trouvé tout cela sur Wikipedia, je suis loin d’être un génie. Voici donc mon code qui remplacera la racine carré native et le temps d’exécutions pour 100 millions d’opérations.
// Racine carré pour les nombres 0 à 99 inclusivement.
private static final float[] cfaROOT =
{0.0f, 1.0f, 1.4142135f, 1.7320508f, 2.0f, 2.236068f, 2.4494898f, 2.6457512f, 2.828427f, 3.0f,…etc
….
/**
* Retourne la racine carrée d'un nombre. Il s'agit d'une approximation Babylonienne.
* Plus précise que la méthode Bakhshali.
*
Méthode préférée, précise et rapide.
*
Temps = 625ms/1000000it. Comparé à 594ms pour Math.pow().
* @link http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
*
Time javagame2d = 93203ms - Answer = 724.88336 , pour 100000000it, pour Math.pow()
*
Time javagame2d = 5547ms - Answer = 724.88336 , pour 100000000it, pour Math2D.squareRoot_Babylonian()
*/
public static float squareRoot_Babylonian(float fNumber, int iIteration){
if (fNumber < 0) { return Float.NaN; } // Négatif.
float fRoot = 0;
if (fNumber >= 1000000) { return Math2D.squareRoot(fNumber); }
else if (fNumber >= 10000) { fRoot = cfaROOT[floor(fNumber / 10000)] * 100; }
else if (fNumber >= 100) { fRoot = cfaROOT[floor(fNumber / 100)] * 10; }
else if (fNumber >= 1) { fRoot = cfaROOT[floor(fNumber)]; }
else if (fNumber >= 0.01) { fRoot = cfaROOT[floor(fNumber * 100)] / 10; }
else if (fNumber >= 0.0001) { fRoot = cfaROOT[floor(fNumber * 10000)] / 100; }
else if (fNumber >= 0.000001) { fRoot = cfaROOT[floor(fNumber * 1000000)] / 1000; }
else { return Math2D.squareRoot(fNumber); }
for (int i = 0; i < iIteration; i++) {
fRoot = (fRoot + (fNumber / fRoot)) / 2;
}
return fRoot;
}
Ici, je montre la méthode Babylonienne, c’est celle que j’ai adopté. Elle est précise et 17 fois plus rapide que la méthode native. Cette méthode est implémenté dans la boucle for. La difficulté que j’ai eu, était qu’il fallait fournir à la formule un estimé de la racine carré du nombre cherché. Alors j’ai utilisé une variable globale cfaROOT qui contient toute les racines carrées de 1 à 100. C’est à cela que sert la série de test if. Dépendamment du nombre, on trouve la racine carrée pré calculée dans cfaROOT, et on la modifie selon l’amplitude du nombre. Par exemple, la racine de 100 est 10. La racine de 10000 est de 100. Donc 10 fois plus. C’est ce que fait la série de tests, ils déterminent la racine approximative la plus près, et elle est utilisé dans le calcule Babylonien pour être précisé. Avec deux itérations de la méthode Babylonienne, j’obtiens une précision à 5 chiffres après le point. 17 fois plus rapidement, je le rappel.
Ok, ça suffit. Je vous ai assez assommé avec des explications nébuleuses. Lorsque je travail sur mon projet, je partage mon temps en deux (je vous épargne les obligations parentale). Le matin, programmation. L’après-midi, création, graphisme, concept. Cette semaine j’ai donc sortie mes crayons et je me suis mis à gribouiller. J’avais dessiné une ébauche de scène où l’on voit deux personnages à la recherche d'un engin perdu. Un vaisseau de combat avec des possibilités de voyage dans le temps, enfin on verra. Dans le ciel, en avant de la lune, on voit la silhouette d’un vaisseau orbital qui fera office de base à mes protagonistes. J’ai planché sur ce vaisseau orbital. À force de zigonnage, j’en suis venu à ce concept :
Ici on voit le vaisseau en deux positions. Contracté, il est en mode hyperespace. Étiré, il est en mode orbital. Je ne suis pas sûr encore de ces fonctions et du pourquoi de ces deux modes, mais en travaillant dessus des idées me sont venus quand à l’histoire globale du jeu. J’ai même pensé à faire de ce vaisseau le fleuron de l’ANUQ, l’armée des nations unifiées du Québec. Première force militaire mondiale…. Je vais y coller la fleur de lys en quelque part comme logo. J’aime autant ne pas trop en dire sur l’histoire pour le moment, ça change à toutes les deux secondes dans ma tête. Enfin, dites moi ce que vous en pensé. Vous pouvez aussi aller me voir sur mon compte Deviant Art.
Bonjour, Je ne suivrai pas ce blog, vu que c'est hors de mes champs d'expertise, mais il se trouve que je peut au moins recommender un site, sur lequel je suis tombé un jour:
RépondreSupprimerhttp://www.indiegames.com/blog/2006/10/string_theory.html
Le jeu mentionné sur la page de ce lien est vraiment très ingénieux.
Aussi, je reccomende de mettre au moins une façon de te rejoindre par courriel sur ton blog, car j'ai cherché, et n'ai rien trouvé.
Bonne chance!
-Creaturiste
Merci de la suggestion. Ce que j'aimerais vraiment trouver, ces d'autres bloggers qui développent des jeux. Histoire d'échanger des techniques.
RépondreSupprimerEt quitte à suivre mon travail sur blogspot, tu peux toujours aller voir mon évolution artistique sur Deviant Art.