Comment fonctionne le PathFinding dans Minecraft ?
Depuis la version 1.2, Minecraft a intégré un mécanisme de Path Finding. Le Path Finding, c’est ce qui permet par exemple aux monstres d’éviter les obstacles afin de parvenir à un point (vous en général). Cela a un avantage: les loups et les animaux qui vous suivent ne tombent plus dans la lave, mais les zombies, creepers et autres squelettes vous atteindrons beaucoup plus facilement.
Qu’est ce que c’est ? Le Path Finding ne date pas d’hier. C’est en fait un d’algorithme de recherche du plus court chemin, en tenant compte d’obstacles. Les deux algos les plus connus et les plus efficaces sont nommés l’algorithme de Dijkstra et l’algorithme A*.
Un site permet d’illustrer le fonctionnement de ces algorithmes en image. Il est très facile de virtualiser un bout de map Minecraft sur la grille, afin d’y comprendre le fonctionnement du Path Finding utilisé par les monstres. Ici, le point vert serait la position du monstre, et le point rouge serait votre position. Les différents obstacles, dans le jeu, peuvent être:
- un dénivelé en montée de deux blocs ou plus: montagnes, murs, arbres, …
- une fosse
- des blocs de lave / d’eau
Le principe de ces algorithmes est d’analyser toutes les « cases » que l’on peut explorer (elles sont matérialisées en bleu sur ce site). La recherche s’arrête lorsque l’on a atteint la case, on détecte alors le chemin le plus court qui permet d’y accéder (en général, un seul). Il est très important de trouver l’algorithme le plus rapide, le plus efficace et le moins gourmand en ressources: en effet, celui-ci est appliqué pour chaque monstre, et pour chaque position du joueur à atteindre (!).
Steve a du souci à se faire ! Vous aussi, essayez-vous au Path Finding !
(source)