Graph et chemin

Pré-requis :
Avant de commencé lire, assurez vous d'avoir bien compris les bases des matrices.
Grâce a ce post vous comprendrez le lien entre les matrices et les tableaux.

Rappel : Comment est allouée la mémoire dans un ordinateur ?

Problème : un tableau est une zone fixe de la mémoire, on ne peut pas changer sa taille. Les tableau classique vont vite Mais diffice à gérer la mémoire si les données changent.

• liste chainée -> permet de permuter facilement les positions ⛔ Ne pas utiliser de liste de chainé pour stockée des baleur statique (10^3 moins rapide que le tableau classique)

Les Pointer

Les pointeurs permettent de checker une valeur en "la pointant". C'est une sorte "rapporteur", si l'on pointe mal il y a un risque.

• Un pointeur peut être pointer 😭

[case mémoire qui contient une valeure][pointeur]

• ( + ) Je peux ajouter et supprimer des valeurs à l’intérieur.
• ( - ) Lent. Elles sont beaucoup moins rapides que les tableaux.

Or, elle ne va que dans un sens.

Il peut y avoir un nombre illimité de pointeurs sur une valeur.

• ( + ) On peut aller dans tous les sens. C’est le plus rapide en termes d’opération de calculs.
• ( - ) C’est plus grand

-> Dessus de la pile = LIFO (Last In First Out)

La structure de la mémoire

Pour rappel, tout nos logiciels de 3D utilisent des graph et une façon de gérer la mémoire. Par exemple maya et houdini utilisent des graphs pour la modélisation alors que Blender et 3ds Max utilisent le sytème de piles.

La pile

• LIFO -> Last in first out

Arbre binaire

• Permet de de revenir en arrière facilement.

Graph direct acyclique

• il faut éviter au maximun ce genre de graph (par exemple sur maya lorsque l'on modélise), il ne permet pas de faire de boucle.

Chemin et graph

Maintenant que nous avons vu que pour gérer la mémoire il était possible d'utiliser des graphs regardons pour les déplacement dans les jeux vidéos.

heuritique = Calculer l'intéret d'aller vers ce point

Choix du chemin en fonction de :

• Chemin penilibilté
• chemin fourberie
• distance
• Danger [...]

BFS : parcourir le graphe en utilisant le chemin le plus prudent, On regarde petit à petit. (structure qui grignotte)

DFS : Je pars du bout je teste toutes les possibilité (bourrin)

• Génant si grande map

A star : Trouver le chemin qui semble être le plus rapide Il permet de trouver très rapidement un plus court chemin entre deux points avec d’éventuels obstacles. Il faut trouver le chemin qui semble le plus nous rapprocher de ce que nous recherchons.
Astar meilleur algorithme pour les chemin SAUF pour Le cas du peigne

BSP : algorithme

-> BSP (Binary Spatial Partition) : On construit le couloir avant la création du personnage. Il permet de séparer des choses.

• ( - ) Il est lié à des couloirs. C'est le même principe que le

  Loading...

  Pour rappel vous pouvez le voir ici L'AGORITHMIE, BASE DE TRI

Le logiciel Arnold subdivise la mémoire.

On cherche ou se trouve l'énemie.

Comment faire quand on a en a aucune idée ? On va utiliser la technique des quatris. Le principe est de s

On va subdiviser

Midmap :

En fonction de la distance on va afficher des textures différentes

• loins -> moins de résolution
• proche -> haute de résolution

Autres

discrétisé :
=>Transformer une chose en case (échantillonnage est un cas particulier de la discrétisation)
-> Transformer un espace ou une chose en forme simplifiées et régulières,

Antialiasing -> algorithme pour faire semblant que la droite est bien droite Pour chaque point les on arrondi les courbes