Ceci est une ancienne révision du document !

Table des matières

Cet article est dans la continuité de mon article de vulgarisation sur les 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 ce site vous vous apercevrez que l'auteur a choisi d'arrondir au supérieur :

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 :

À 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 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.

portée = 1 portée = 2 portée = 3 portée = 4 portée = 5 portée = 6 portée = 7 portée = 8 portée = 9 portée = 10

Voici le code que j'ai utilisé pour générer ces images : 

\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}

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 : 

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);
}

où la fonction « afficher » dépend de l'interface choisie.