Cerca de camins

La cerca de camins en informàtica, és una tècnica d'intel·ligència artificial per calcular el moviment dels personatges d'un videojoc per a establir la ruta més adequada o natural entre un punt i un altre, tenint en compte les propietats de l'escenari, com ara els obstacles i les condicions del terreny de pas.[1] En l'argot informàtic, de vegades es fa servir el terme anglès pathfinding.

Exemple senzill en un mapa de dues dimensions: el cami vermell des de l'inici punt verd cap a la destinació blau amb un obstacle en gris

És relacionat amb el problema del camí més curt, tenint en compte criteris com el més curt, més barat, més ràpid i la capacitat de l'objecte o de la persona que s'ha de desplaçar. Si él principi és senzill, com l'ensenya l'exemple, en la realitat l'execució pot esdevenir força complex quan els obstacles són mòbils (com altres personatges o èquip), quan es pot vèncer els obstacles, mitjançant certes condicions (aigua, sorra…) i que not tots els personatges tenen la mateixa força o enèrgia. Esdevé encara més complicat s'ha de calcular el camí més eficient en un ambient real (per exemple el camí del recol·lector en un magatzem o la ruta d'un cotxe, no només utilitzant un mapa, però també les dades variables del trànsit o dels obres). Ans al contrari dels jocs, en la realitat no és coneixen totes les dades de la persona o l'objecte que es deplaça.[2]

ReferènciesModifica

  1. «Cerca de camins». Terminologia dels videojocs. TERMCAT. [Consulta: 1r març 2021].
  2. Ma, Hang; Koenig, Sven «AI Buzzwords Explained: Multi-Agent Path Finding (MAPF)». AI Matters, 2017, pàg. 15-19.