Discussion :

[zoltix]

Hello,
Je suis en train de revoir les bases d'algo. Pour ce faire, Je me suis décidé de refaire la fourmi de Langton.
Tout fonctionne bien mais je suis tombé sur internet sur du code que j'ai du mal à comprendre car ce sont des manipulations de matrice.

Mon objectif est de comprendre cette manipulation matricielle, je n’ai pas ces connaissances. J’aimerai les acquérir.

Pour faire très court, il y a une fourmi qui doit se déplacer dans une grille.
1. Si la fourmi est sur une case blanche, elle effectue une rotation vers la gauche; si elle est sur une case noire, elle effectue une rotation vers la droite ;
2. La fourmi inverse la couleur de la case sur laquelle elle se trouve (blanc devient noir et réciproquement);
3. La fourmi avance d’une case dans la direction de son orientation.

Mon souci c'est de comprendre.

Dans le code je rencontré

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
# Rotation Matrices
clock = np.matrix([[0, 1], [-1, 0]])
counter = np.matrix([[0, -1], [1, 0]])

La fourmi bouge avec une addition de matrice

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 pos[:] = pos + direction

et la direction est modifiée par une multiplication de matrice selon le sens

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 direction[:] = clock * direction

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 direction[:] = counter * direction

J'aimerai comprendre quelles sont ces propriétés/règles de matrice qui permette de faire ce type de manipulation.



Voici le code complet.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import numpy as np
from matplotlib import pyplot as plt
from matplotlib import animation
 
# Initialize the Simulation
 
dim = 100
a = np.matrix(np.zeros((dim, dim)))
pos = np.matrix([[dim // 2], [dim // 2]])  # current position of ant
direction = np.matrix([[1], [0]])  # direction ant is currently moving
 
# Rotation Matrices
clock = np.matrix([[0, 1], [-1, 0]])
counter = np.matrix([[0, -1], [1, 0]])
 
 
def takestep(a, pos, direction):
    pos[:] = pos + direction
    if a[pos[0, 0], pos[1, 0]] == 0:  # landed on white
        a[pos[0, 0], pos[1, 0]] = 1 # put a black 
        direction[:] = clock * direction
    else:
        a[pos[0, 0], pos[1, 0]] = 0
        direction[:] = counter * direction
 
fig = plt.figure(figsize=(10, 10))
im = plt.imshow(a, interpolation='none', vmin=0, vmax=10)
 
def animate(i):
    takestep(a, pos, direction)
    im.set_data(a)
    return [im]
 
 
anim = animation.FuncAnimation(fig, animate,
                               frames=12000, interval=0, blit=True,
                               repeat=False)
plt.show()

Merci de votre aide.

[zoltix]

J'ai trouvé sur wikipédia ce que je recherche mais j'aimerais bien trouver une vulgarisation de ce truc là.

https://fr.m.wikipedia.org/wiki/Matrice_de_rotation

[lg_53]

Malheureusement pour toi cela n'est pas de l'algorithmique mais des mathématiques ! De l'algèbre linéaire (dit aussi parfois algèbre matriciel) même pour être plus précis. Pour comprendre pourquoi une matrice de rotation est bien une matrice de rotation, il faut savoir multiplier une matrice par un vecteur. La formule est la suivante. Considérons une matrice M comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
M = [[a, b],
   [c,d]]

et un vecteur colonne x comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
x = [ x1,
   x2 ]

(ne prenez pas cela comme du code, ce sont des formules mathématiques). Alors le produit de la matrice M par le vecteur x, est donné par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
M * x = [ a*x1 + b*x2 ,
         c*x1  + d*x2]

Maintenant mettez les matrices donnés, faite le calcul à la main en prenant les 4 vecteurs directions, et vérifier que le résultat est bien à chaque fois une rotation du vecteur x de départ.