Algorithmique de la mobilité

↑ Accueil du cours


Marche Aléatoire dans une grille (Random Walk on a grid)

Dans ce modèle, l'espace est discrétisé comme une grille. Les noeuds se déplacent sur les intersections d'une grille virtuelle. À chaque étape, chaque noeud choisit aléatoirement une intersection parmi les intersections voisines de son intersection courante, et s'y rend. Nous allons d'abord coder ce comportement en utilisant une grille qui n'a pas d'existence propre (c.à.d. un simple jeu de coordonnées). Il est supposé que vous disposez déjà de la classe WaypointNode, dont nous réutiliserons le code ici.

Q1. Créer une classe MAGNode (pour Marche Aléatoire Grille) qui hérite de WaypointNode. On stockera la résolution de la grille sous forme d'un entier res qui indique l'espace entre deux sommets voisins de la grille (par exemple 50 ou 100).

Q2. Lorsque le noeud démarre, via onStart(), il est possible que sa position ne soit pas exactement sur la grille. Corriger sa position en arrondissant au sommet voisin le plus proche. (On peut faire ça en trois lignes, dont la plus longue fait 37 caractères.)

Q3. Écrire une méthode chooseNeighbor() dans laquelle vous choisissez un sommet aléatoire parmi les quatres sommets voisins de la grille, et fixez ce sommet comme destination. Pour mémoire, les sommets ne sont pas matérialisés ici, on joue juste avec les coordonnées.

Q4. Utiliser cette méthode chooseNeighbor() de sorte à choisir une nouvelle destination à chaque fois que la précédente est atteinte (ainsi qu'une fois au démarrage). Afin que la marche aléatoire reste dans la zone de simulation, on pourra utiliser la méthode wrapLocation() à chaque fois qu'une destination est atteinte.

Variante sans demi-tour (non-backtracking random walk)

Q5. Modifiez votre code pour permettre d'interdire ou d'autoriser (en fonction d'un booléen) la marche de faire demi-tour. Si cette option est activée, la marche n'aura pas le droit, par exemple, d'aller à gauche si son dernier mouvement était à droite, etc.