Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Prochaine révision
Révision précédente
fr:conception:nova-online [2016/04/25 14:38]
apeiron créée
— (Version actuelle)
Ligne 1: Ligne 1:
-//Cet article est dans la continuité de mon article de vulgarisation sur les [[vulgarisation:​distance|distances]],​ en particulier le cas p = 2.// 
  
-Contrairement à $d_1$ et surtout $d_\infty$ qui se prêtent bien aux grilles, $d_2$ est certes plus naturelle mais posera problème pour une implémentation dans un jeu comme Nova. 
- 
-====== Le problème ====== 
- 
-Nous avons un vaisseau situé au centre d'une case et nous voulons afficher toutes les cases à portée de saut, c'est à dire situées à une certaine distance du centre de la case (prenons 6 pour le moment). La question revient plus ou moins à décider si on va arrondir $d_2(A,B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}$ au supérieur ou à l'​inférieur. Par exemple, en jouant avec [[https://​donatstudios.com/​PixelCircleGenerator|ce site]] vous vous apercevrez que l'​auteur a choisi d'​arrondir au supérieur : 
- 
-{{ ::​sautsup.png?​300 |}} 
- 
-Pour être franc, esthétiquement ce choix me choque : ce n'est pas très rond. Formalisons donc un peu le problème pour comprendre ce qu'il se passe. Nous traçons le cercle de centre $(0,0)$ et de rayon $s \in \mathbb{N}$ (la distance de saut, exprimée en nombre de cases). Nous pouvons donc définir le disque des points à l'​intérieur du cercle : 
- 
-$$D_s = \{(x,y) \in \mathbb{R}^2\ |\ \sqrt{x^2 +y^2} \le s\}$$ 
- 
-Le problème est bien sûr que nous devons penser en terme de cases et non de points du plan. Nous allons donc assimiler une case à son centre, et nous dirons que la case $(x,y)$ sera affichée si le point à coordonnées entières $(x,y) \in \mathbb{N}^2$ vérifie $\sqrt{x^2 +y^2} \le s$. Dit autrement, une case sera affichée si le centre de la case est dans le disque $D_s$. 
- 
-Avec cette définition,​ on s'​aperçoit immédiatement que sur les bords nord, sud, est et ouest du cercle il ne devrait y avoir qu'une case d'​affichée,​ contrairement au dessin précédent où nous voyons cinq cases pour $s = 6$. En effet le centre de la case $(6,0)$ à l'est est pile dans le disque, mais les centres des cases au dessus et en dessous ne devraient pas y être, puisque $\sqrt{6^2 +1^2} > 6$ et $\sqrt{6^2 +(-1)^2} > 6$. En regardant un peu le code source, on s'​aperçoit que c'est parce que ce n'est pas $6$ qui a été pris comme rayon du cercle, mais $6.5$. C'est pour cela que j'ai parlé d'​arrondi au supérieur. En fait, nous aurions dû plutôt avoir ceci : 
- 
-{{ ::​sautmath.png?​300 |}} 
- 
-À ce stade, force est de constater que la solution mathématiquement juste est encore plus hideuse que l'​autre,​ surtout les cases toutes seules au nord, au sud, à l'est et à l'​ouest. Comme dans [[nova|Nova]] nous nous intéresserons à de petites ($s \le 10$) valeurs de saut, nous pouvons envisager d'​utiliser plutôt la condition $\sqrt{x^2 +y^2} \le s + \epsilon$, où $\epsilon$ est petit et à régler au jugé. Avec $\epsilon = 0$ nous retrouvons la solution mathématiquement juste, et avec $\epsilon = 0.5$ nous retrouvons la solution du site susnommé. Il ne reste qu'à prendre une valeur satisfaisante sur le plan esthétique... 
- 
-====== Le programme ====== 
- 
-Après réflexion, je suis en fait parti sur $\sqrt{x^2 + y^2} \le \sqrt{s^2 + \delta}$ au lieu de $\sqrt{x^2 + y^2} \le s + \epsilon$, car quand $s$ devient grand l'​erreur devient négligeable au carré au lieu de juste négligeable. Il ne reste qu'à fixer $\delta$ de façon à ce que le dessin soit satisfaisant pour les premières valeurs. Après test $\delta = 1$ est suffisant. J'​obtiens donc la condition $x^2 + y^2 \le s^2 + 1$ qui est assez simple à calculer. De plus, cela m'a aidé à faire des tests, vu que $\LaTeX$ est quand même plus à l'aise avec les entiers. 
- 
-{{:​saut-01.png?​135|portée = 1}} 
-{{:​saut-02.png?​135|portée = 2}} 
-{{:​saut-03.png?​135|portée = 3}} 
-{{:​saut-04.png?​135|portée = 4}} 
-{{::​saut-05.png?​135|portée = 5}} 
-{{::​saut-06.png?​135|portée = 6}} 
-{{::​saut-07.png?​135|portée = 7}} 
-{{::​saut-08.png?​135|portée = 8}} 
-{{::​saut-09.png?​135|portée = 9}} 
-{{::​saut-10.png?​135|portée = 10}} 
- 
-Voici le code que j'ai utilisé pour générer ces images : 
- 
-<​file>​ 
-\PassOptionsToPackage{dvipsnames}{xcolor} 
-\documentclass[tikz]{standalone} 
-\usepackage{lmodern} 
-\usepackage[T1]{fontenc} 
-\usepackage[french]{babel} 
-\usepackage[utf8]{inputenc} 
-\usepackage{contour} 
-\usepackage{tikz} 
-\usepackage{multido} 
-\usepackage{ifthen} 
-\usepackage[nomessages]{fp} 
- 
-\newcommand{\maxSaut}{10} 
- 
-\begin{document} 
-\multido{\iSaut=1+1}{\maxSaut}{ 
- \FPeval{\iSautCarre}{clip(\iSaut*\iSaut+1)} 
- \FPeval{\zone}{clip(2*\iSaut+1)} 
- \begin{tikzpicture}[scale=1.0] 
- \fill[black] (-\iSaut-1,​-\iSaut-1) rectangle (\iSaut+2,​\iSaut+2) ; 
- \multido{\i=-\iSaut+1}{\zone}{ 
- \multido{\ii=-\iSaut+1}{\zone}{ 
- \FPeval{\normeCarre}{clip(\i*\i+\ii*\ii)} 
- \ifthenelse{\normeCarre<​\iSautCarre \OR \normeCarre=\iSautCarre}{ 
- \fill[Green] (\i,\ii) -- (\i,\ii+1) -- (\i+1,​\ii+1) -- (\i+1,\ii) -- cycle; 
- }{} 
- } 
- } 
- \fill[blue] (0,0) -- (0,1) -- (1,1) -- (1,0) -- cycle; 
- \draw[white] (-\iSaut-1,​-\iSaut-1) grid (\iSaut+2,​\iSaut+2) ; 
- \draw[blue,​ ultra thick] (0.5,0.5) circle (\iSaut) ; 
- \end{tikzpicture} 
-} 
-\end{document} 
-</​file>​ 
- 
-Quelques précisions : 
-  * Dans multido la première lettre du nom de la variable indique le type, d'où le fait que j'ai appelé les variables i et ii et non i et j. 
-  * tikz fait bien des évaluations,​ mais pas multido ou ifthen, d'où mes \FPeval (package fp) pour définir mes variables. 
-  * grid met automatiquement les coins aux coordonnées entières, ce qui explique pourquoi le centre du cercle est en $(0.5,​0.5)$. 
- 
-Pour l'​algorithme lui-même, exprimé en C par exemple, ça donnerait quelque chose de la forme : 
- 
-<​file>​ 
-void afficherPortee(int xVaisseau, int yVaisseau, int portee) { 
- for (xCase = xVaisseau-portee ; xCase <= xVaisseau+portee ; xCase++) 
- for (yCase = yVaisseau-portee ; yCase <= yVaisseau+portee ; yCase++) 
- if ((xCase-xVaisseau)*(xCase-xVaisseau) + (yCase-yVaisseau)*(yCase-yVaisseau) <= portee*portee + 1) 
- afficher(xCase,​yCase);​ 
-} 
-</​file>​ 
- 
-où la fonction << afficher >> dépend de l'​interface choisie.