Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
|
nova:saut [2015/11/22 18:12] apeiron |
— (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. | ||