En este tutorial veremos cómo implementar un grafo genérico en Unity sobre el que aplicaremos el algoritmo de búsqueda de caminos con el algoritmo A*.

Índice

Requisitos

• Haber leído Introducción al Algoritmo A* o tener conocimiento previo del mismo.
• Unity, cualquier versión debería valer.
• Conocimientos de C#. Recomendado:
  • Tipos genéricos.
  • Herencia.
  • Conocimiento básico de los tipos de listas.

Si nunca has trabajado con tipos genéricos o herencias, puede que este tutorial te resulte complicado de entender, pero puede ser una buena manera de introducirte a estos conceptos. Puedes dejar en los comentarios las dudas o problemas que te encuentres e intentaré solucionártelas en el menor tiempo posible.

Objetivos

1. Crear una estructura de datos que represente un Grafo.
2. Este Grafo debe ser genérico, pero muy extensible; debería ser la base de todos los grafos que utilicemos.
3. Debe incluir una implementación de A* para buscar caminos. Esta implementación nos permitirá especificar una función heurística (si quisiéramos) para adaptarse a nuestra implementación.

Razonamiento

Tenemos mil maneras a la hora de implementar la búsqueda de caminos en nuestro proyecto. Un acercamiento muy común es hacerlo de manera específica para el problema que tengamos entre manos. Imaginemos un juego donde:

• El personaje principal viaja de una ciudad a otra. Tenemos un mapa con varios puntos de interés, y queremos encontrar el camino más corto entre dos de ellos.
• Nuestros NPCs caminan por el escenario a su entojo, y deben evitar los obstáculos.
• Nuestro personaje se mueve cuando hacemos click en la pantalla, debe encontrar el camino hasta donde hayamos hecho click.

Si implementáramos un A* para cada una de estas mecánicas, tendríamos tres algoritmos diferentes que mantener. Lo ideal sería tener uno para los tres capaz de adaptarse a las necesidades de cada mecánica. Con esto conseguiríamos:

• Un código más fácil de mantener – sólo hay que arreglar bugs en un sitio, y los arreglos sirven para todas las mecánicas que lo utilicen.
• Un código más robusto – al arreglar bugs en un sólo sitio, es más difícil que se rompa a largo plazo porque lo habremos revisado muchas más veces.
• Un código más escalable y flexible – no tendríamos que cambiar la base, puesto que esta base sería lo suficiente flexible para cualquier cosa. Por tanto, hay menos código que adaptar.

Grafo Genérico

Primero, necesitamos crear la estructura sobre la que se sostendrá todo.

Un grafo se constituye a partir de dos pilares fundamentales: el Nodo y la Arista. Por tanto, serán dos clases; Node y Edge. Puedes crear estas clases en archivos diferentes o en el mismo donde vayas a implementar la clase del grafo; Graph. Yo he decidido hacerlo todo en el mismo archivo.

Node

public class Node
{	
}

Para que cada nodo sea único deberemos darles un identificador. Vamos a utilizar un entero llamado _index, que representará su posición dentro del array del grafo al que pertenece.

public class Node
{
	private int _index;
}

También necesitaremos guardar las aristas que salgan de este nodo. Para ello, utilizaremos sus identificadores, que también serán enteros, los cuáles guardaremos en una lista.

public class Node
{
	private int _index;
	private List<int> _edges = new List<int>();
}

Fíjate en que son atributos privados. Esto quiere decir que cuando heredemos de la clase Node nunca podremos acceder a ellos, ¡ni nos interesa! Son datos delicados, nunca deberíamos poder modificarlos salvo que sea absolutamente necesario, y pasando por los canales adecuados.

Pero sí que necesitamos comprobarlos de alguna manera, así que haremos ambos atributos accesibles de manera externa.

public class Node
{
	private int _index;
	private List<int> _edges = new List<int>();

	public int Index { get => _index; }
	public List<int> Edges { get => _edges; }
}

También necesitamos alguna manera de decirle al Nodo cuál es su índice. Éste no tendríamos por qué saberlo en el momento de su creación, así que necesitaremos una función Init.

public class Node
{
	...

	public Node() { }

	public void Init(int index)
	{
		_index = index;
	}
}

Por último, nos queda proporcionar las funciones que nos permitirán añadir y quitar aristas al Nodo, cerciorándonos de no repetirlas nunca:

public class Node
{
	...

	public void AddEdge(int edgeIndex)
	{
		if (!_edges.Contains(edgeIndex))
		{
			_edges.Add(edgeIndex);
		}
	}

	public void RemoveEdge(int edgeIndex)
	{
		_edges.Remove(edgeIndex);
	}
}

Con esto, el nodo estaría terminado.

Edge

public class Edge
{
}

Esta clase será muy parecida a Node.

Para empezar, necesitaremos identificarla de alguna manera. Igual que antes, utilizaremos su índice en el array del grafo que tiene todas las aristas para identificarla.

public class Edge
{
	private int _index;
}

Una arista conecta dos nodos. Por tanto, necesita una referencia a ambos. Para ello, guardaremos en un array de dos posiciones los índices de esos nodos, que los identificarán de manera exclusiva. Es decir; dos nodos nunca tendrán el mismo índice.

public class Edge
{
	private int _index;
	private int[] _nodes = new int[2];
}

Igual que antes, estos atributos serán privados para proteger la integridad de la estructura después de heredarla. Pero sí proporcionaremos una forma pública de ver la información:

public class Edge
{
	private int _index;
	private int[] _nodes = new int[2];

	public int Index { get => _index; }
	public int[] Nodes { get => _nodes; }
}

Además, necesitaremos una manera de decirle a la arista cuál es su identificador. Como con Nodo, lo más probable es que no sepamos este valor en el momento de crear el objeto, así que le daremos un método Init para hacerlo después:

public class Edge
{
	...

	public Edge() { }

	public void Init(int index)
	{
		_index = index;
	}
}

También necesitamos indicarle qué nodos va a unir. Para ello, crearemos un método llamado SetNodes al que le pasaremos dos valores enteros, representando los índices de cada nodo, llamados from y to.

Estos nombres no son triviales, y su orden en el array tampoco. Lo que nos están indicando es la dirección de la arista, lo cuál es una necesidad de los grafos dirigidos. Para el resto de grafos, tener esta distinción no será un problema de dirección, pero sí nos dará facilidad para construir y atravesar el grafo.

public class Edge
{	
	...

	public void SetNodes(int from, int to)
	{
		_nodes[0] = from;
		_nodes[1] = to;
	}
}

Por último, vamos a añadirle una función de consulta que nos devuelva el peso de la arista, lo cuál será útil si queremos hacer grafos ponderados, un uso muy común con A*.

El valor que devolverá esta consulta siempre será 1, pero la haremos virtual para que las clases herederas puedan implementar su propia fórmula de cálculo.

public class Edge
{
	...

	public virtual float GetWeight()
	{
		return 1f;
	}
}

Y así, Edge queda terminada.

Graph

La clase que hará todo esto posible.

La base

Debemos comenzar definiéndola como una clase genérica. Las clases genéricas operan sobre clases proporcionadas por quien las utiliza, sin importar qué clases sean éstas o sus atributos. Puedes identificarlas porque hay que declararlas con el tipo de la clase que van a manejar, como List<T> o Dictionary<T1, T2>.

Para crear nuestra clase genérica, escribiremos:

using System;
using System.Collections.Generic;

public class Graph<N, E> 
{
}

N y E son los identificadores internos de la clase para los dos tipos genéricos que aceptará.

Sin embargo, como muchas clases genéricas, no queremos que la nuestra pueda operar con cualquier clase. Queremos que opere sólo con Node y Edge, o con alguna de sus clases hijas.

Para definir esta restricción utilizaremos la palabra clave where, y añadiremos new() para indicarle al compilador que las clases que esperamos tienen constructores que no aceptan atributos.

public class Graph<N, E>
	where N : Node, new()
	where E : Edge, new()

Así, N pasa a representar a Node, y E pasa a representar a Edge.

Ahora ya podemos guardar estos valores dentro de nuestra clase. Utilizaremos dos listas (genéricas 😉 ) para guardarlos.

public class Graph<N, E>
	where N : Node, new()
	where E : Edge, new()
{
	private List<N> _nodes;
	private List<E> _edges;
}

Como con Node y Edge, crearemos propiedades que nos permitan acceder a estas listas desde fuera sin modificarlas:

public class Graph<N, E>
	where N : Node, new()
	where E : Edge, new()
{
	private List<N> _nodes;
	private List<E> _edges;

	public List<N> Nodes { get => _nodes; }
	public List<E> Edges { get => _edges; }
}

Creamos el constructor de la clase para inicializar estos valores. No nos hace falta pasarle ningún parámetro:

public class Graph<N, E>
	where N : Node, new()
	where E : Edge, new()
{
	...
	public Graph()
	{
		_nodes = new List<N>();
		_edges = new List<E>();
	}
}

Añadir nodos

Los grafos se componen de nodos y aristas, así que debemos darle una forma de añadir nuevos. Sin embargo, no vamos a hacer lo de crear uno e indicarle que lo guarde; esto podría dar lugar a errores ya que podríamos recibir un nodo «manchado», con el índice ya asignado.

En vez de eso, vamos a hacer que sea el propio grafo quien cree un nodo limpio y nos lo devuelva por si necesitáramos hacerle algo más. Lo inicializaremos siempre con el valor que adquirirá cuando se añada a la lista; es decir, el total de objetos en ella:

public N AddNode()
{
	N node = new N();
	node.Init(_nodes.Count);
	_nodes.Add(node);

	return node;
}

Añadir aristas

Las aristas harán algo parecido. Querremos que sea el grafo quien cree las aristas para asegurar que son únicas, pero mientras que un nodo puede existir por su cuenta, sólo en el vacío sin estar conectado a otros nodos, la existencia de las aristas depende absolutamente de la presencia de los nodos a los que conecta. Por ello, ya en la función que crea una arista, le asignaremos a qué nodos une:

public E AddEdge(int from, int to)
{
	E edge = new E();
	edge.Init(_edges.Count);
	edge.SetNodes(from, to);
	_edges.Add(edge);

	return edge;
}

¡Atención! Esto significa que deberemos notificar al nodo de que se le ha añadido una arista después de crearla, utilizando la arista devuelta.
Podríamos hacerlo directamente en la función, pero eso rompería la regla de la mínima unidad funcional, además de penalizarnos al crear ciertos grafos dirigidos.

Borrar aristas

Para borrar una arista, haremos el proceso contrario; informaremos a los nodos de que esta arista ha dejado de existir (ahora sí, no queremos guardar información imprecisa) y convertiremos su puesto en la lista a null.

public void RemoveEdge(E edge)
{
	_nodes[edge.Nodes[0]].RemoveEdge(edge.Index);
	_nodes[edge.Nodes[1]].RemoveEdge(edge.Index);
	_edges[edge.Index] = null;
}

¿Por qué a null? Para no corromper el resto de la información. Si lo quitáramos de la lista, todas las aristas que estuvieran después de ésta verían su índice modificado en -1, y deberíamos hacernos cargo de actualizarlas todas, además de los nodos conectados a éstas, como otra información externa al grafo que pudiéramos tener. Es mucho más sencillo simplemente nullificar la posición.

Una posible mejora sería que AddEdge buscara una posición nula antes de añadir el objeto edge. Así no tendríamos que agrandar la lista y nos salvaríamos unos cuántos bytes de memoria. Depende de cuán a menudo vayas a destruir y crear aristas en tu proyecto.

Borrar nodos

Para borrar Nodos, el proceso es parecido. Ya que una arista no puede existir sin sus dos nodos, nos ayudaremos de la función RemoveEdge que acabamos de crear para asegurar que la información siempre es consistente.

public void RemoveNode(N node)
{
	for (int i = 0; i < node.Edges.Count; ++i)
	{
		RemoveEdge(_edges[node.Edges[i]]);
	}

	_nodes[node.Index] = null;
}

Y lo creas o no, ¡ya estaría! Esta es la implementación más básica de un grafo genérico.

Algoritmo A*

Si no has leído todavía Introducción al Algoritmo A* y no sabes muy bien de qué va el tema, te recomiendo que pares un ratito ahora para echarle un vistazo.

AStarPath

Como os contaba en la teoría, para implementar el Algoritmo A* necesitamos una estructura capaz de guardar el camino que hemos seguido hasta el momento. En la universidad nos enseñan a hacerlo en el propio nodo, ya que es la forma más fácil de enseñarnos el algoritmo y hacer el ejercicio, pero en la vida real y especialmente en los videojuegos, es problemático. A menudo tendremos varios personajes que viajan o se entrecruzan dentro del mismo grafo; si permeáramos el camino de varios agentes en el grafo de manera asíncrona, algo muy común en inteligencia artificial, estaríamos modificando el camino de otros agentes. Un lío, vaya. La única forma de solventarlo sería que cada agente tuviera su copia del grafo, lo cuál es muy, muy ineficiente.

Ya sabéis que yo no creo en las soluciones perfectas; incluso el algoritmo más depurado tiene dos mejores soluciones que intercambian tiempo y espacio.

En este caso, la solución que yo os propongo es tener una estructura de datos, una clase, que crearemos para cada nodo que visitemos al buscar el camino.

En la teoría, os daba este pseudocódigo:

clase AStarPath:
    Nodo: N
    Coste: float
    Previo: AStarPath

    función EsIgualQue que toma otro:AStarPath y devuelve bool
        devuelve este.Nodo es igual a otro.Nodo

En C#, vamos a escribir esta clase dentro de la propia clase del Grafo Genérico, y la haremos privada, para que nunca pueda utilizarse fuera de ella.

private class AStarPath
{
	public N Node;
	public float Cost;

	public AStarPath Previous;

	public AStarPath(N node)
	{
		Node = node;
	}

	public override bool Equals(object obj)
	{
		if (obj is AStarPath)
		{
			return Equals((AStarPath)obj);
		}

		return base.Equals(obj);
	}
	
	public bool Equals(AStarPath other)
	{
		return other.Node.Index == this.Node.Index;
	}
}

• Node es un nodo del grafo, el nodo que acabamos de visitar.
• Cost será el coste de llegar desde el punto de origen, donde se encuentra el agente ahora mismo, hasta el nodo de este AStarPath.
• Previous es el punto del camino anterior, del que venimos. Es otro AStarPath, de manera que podemos acceder al Nodo que representa en el grafo también.
• Equals, una función especial que nos permite comparar dos objetos. Creamos las dos, puesto que en nuestro código sólo compararemos contra AStarPath, pero las listas utilizarán el método más abierto cuando comparen contra sus objetos.

AStar

En la teoría os daba este pseudocódigo para el algoritmo:

algoritmo A* que toma A:Nodo, B:Nodo y devuelve Lista:Nodos

primerNodo := AStarPath(A)
últimoNodo := AStarPath(B)

listaAbierta := ListaOrdenada:Nodos de Menor a Mayor, debe poder repetir valores
listaCerrada := Lista:Nodos

pivote := primerNodo
pivote.Anterior := nulo
pivote.Coste := 0

listaAbierta añade pivote

while listaAbierta no esté vacía y pivote no sea últinoNodo:
    pivote := listaAbierta[0]
    listaAbierta quita nodo en posición 0
    listaCerrada añade pivote

    si pivote no es últimoNodo:
        nodoPivote := pivote.Nodo
        
        for i entre 0 y el número de vecinos de nodoPivote:
            otroNodo := vecino i de nodoPivote
            vecino := AStarPath(otroNodo)
            
            si listaCerrada no contiene vecino y listaAbierta no contiene vecino:
                vecino.Previo := pivote
                vecino.Coste := pivote.Coste + distancia(vecino, B)
                listaAbierta añade vecino ordenado por el valor vecino.Coste

Vamos a desgranarlo y escribirlo paso a paso, y añadir algunas medidas de seguridad.

Lo primero, la firma de la función:

algoritmo A* que toma A:Nodo, B:Nodo y devuelve Lista:Nodos

Traducida a C#, sería:

public List<N> AStar(N start, N end)
{
}

Antes de meternos al grueso del algoritmo, hay algunos casos que podemos solucionar directamente. No sólo será más eficiente así, sino que nos ahorraremos quebraderos de cabeza en el futuro.

Caso 1: start o end, o ambos, son nulos. No hay camino posible si uno de ellos es nulo, por lo que devolveremos un camino nulo que podremos gestionar desde la clase que hizo la llamada.

if (start == null || end == null)
{
	return null;
}

Caso 2: start y end son el mismo nodo. En este caso, sólo hay un camino posible, el propio nodo.

if (start == end)
{
	return new List<N>() { start };
}

Inicializar las variables

Vamos a inicializar las variables del algoritmo. Corresponden a esta parte del pseudocódigo.

primerNodo := AStarPath(A)
últimoNodo := AStarPath(B)

listaAbierta := ListaOrdenada:Nodos de Menor a Mayor, debe poder repetir valores
listaCerrada := Lista:Nodos

pivote := primerNodo
pivote.Anterior := nulo
pivote.Coste := 0

listaAbierta añade pivote

Las dos primeras; primerNodo y últimoNodo, son muy sencillas

AStarPath firstNode = new AStarPath(start);
AStarPath lastNode = new AStarPath(end);

Para listaAbierta necesitamos una lista genérica que se ordene sola. Podemos implementar la nuestra, o podemos utilizar SortedList, proporcionada por el propio lenguaje. Yo utilizaré esta última:

SortedList<float, AStarPath> openList = new SortedList<float, AStarPath>();

Pero surge un pequeño problema; SortedList no permite, en principio, tener claves duplicadas, y nos es crítico que lo haga para que el algoritmo funcione bien. La solución es inicializar la lista proporcionándole y comparador de claves duplicadas, para que pueda gestionarlas. C# también nos proporciona esta clase:

SortedList<float, AStarPath> openList = new SortedList<float, AStarPath>(new DuplicateKeyComparer<float>());

El resto de variables son mucho más sencillas:

List<AStarPath> closedList = new List<AStarPath>();

AStarPath pivot = firstNode;
pivot.Previous = null;
pivot.Cost = 0f;

Bucle principal

while listaAbierta no esté vacía y pivote no sea últinoNodo:
    pivote := listaAbierta[0]
    listaAbierta quita nodo en posición 0
    listaCerrada añade pivote

    si pivote no es últimoNodo:
        nodoPivote := pivote.Nodo
        
        for i entre 0 y el número de vecinos de nodoPivote:
            otroNodo := vecino i de nodoPivote
            vecino := AStarPath(otroNodo)
            
            si listaCerrada no contiene vecino y listaAbierta no contiene vecino:
                vecino.Previo := pivote
                vecino.Coste := pivote.Coste + distancia(vecino, B)
                listaAbierta añade vecino ordenado por el valor vecino.Coste

Empezamos declarando el bucle while y guardando en el pivote la primera posición de la lista abierta, a la cuál le quitamos ese objeto. Añadimos pivote a la lista cerrada.

while (openList.Count > 0 && !pivot.Equals(lastNode))
{
	pivot = openList.Values[0];
	openList.RemoveAt(0);

	closedList.Add(pivot);

Comprobando que el pivote no sea ahora el nodo final, lo cuál terminaría nuestro trabajo, nos guardamos el nodo del pivote e iteramos sobre sus aristas.

if (!pivot.Equals(lastNode))
{
	N pivotNode = pivot.Node;
	for (int i = 0; i < pivotNode.Edges.Count; ++i)
	{

Debemos guardar el nodo vecino en una variable, y crear un AStarPath para él. Para ello, deberemos comprobar la arista y seleccionar el índice del nodo que no concuerde con el de nuestro pivote.

E edge = _edges[pivotNode.Edges[i]];
N otherNode = edge.Nodes[0] == pivotNode.Index ? _nodes[edge.Nodes[1]] 
						: _nodes[edge.Nodes[0]];

AStarPath neighbour = new AStarPath(otherNode);

Por último, comprobamos que no haya un AStarPath para este nodo ni en la lista cerrada ni en la abierta. Las funciones Contains de las listas utilizarán el Equals que sobrescribimos antes para AStarPath, de manera que sólo importa el nodo que guarde.

Si no está contenido, lo inicializamos con los datos nuevos y lo añadimos a la lista abierta. El coste, por el momento, será 1 por nodo atravesado.

if (!closedList.Contains(neighbour) && !openList.ContainsValue(neighbour))
{
	neighbour.Previous = pivot;
	neighbour.Cost = pivot.Cost + 1;
	openList.Add(neighbour.Cost, neighbour);
}

Devolver el camino

Con todo lo anterior, tendríamos una lista cerrada de nodos a atravesar para llegar de un punto A start a un punto B end, pero esta lista es de AStarPath, ¡no de Nodos!

Todo lo que tenemos que hacer es crear una lista de Nodos camino, y leer la lista cerrada, guardando los nodos de los AStarPath que hemos guardado. Esto nos llenará la lista de Nodos camino al revés, por lo que deberemos darle la vuelta antes de devolverla.

List<N> path = new List<N>();
if (pivot.Equals(lastNode))
{
	while (pivot.Previous != null)
	{
		path.Add(pivot.Node);
		pivot = pivot.Previous;
	}
	path.Add(firstNode.Node);
}

path.Reverse();
return path;

Con esto, ya tendríamos un algoritmo completamente funcional, pero todavía podemos mejorarlo un montón. Añadamos la…

Función heurística

Es la función que nos permite modificar el peso de los nodos para darles preferencia sobre otros. Es muy sencilla de añadir, y sólo requiere tres cambios.

El primero, pasar una función delegada Func<> que devuelva un valor flotante a nuestro algoritmo A*. Esta función debería recibir el nodo pivote, la arista que estamos consultando y el nodo vecino, y devolver el peso de ir del pivot al vecino atravesando la arista.

Func<> tendrá este aspecto:

Func<N, E, N, float>
// Primera N : pivote
// E : arista
// Segunda N : vecino
// float : el tipo del resultado devuelto

Y lo declaremos así:

public List<N> AStar(N start, N end, Func<N, E, N, float> heuristic = null)

Le daremos el valor nulo por defecto porque queremos que no haya necesidad de especificar la función heurística. Es un parámetro opcional.

Debemos añadir la siguiente comprobación antes de inicializar las variables de AStar, pero después de comprobar el Caso 1 y el Caso 2.

if (heuristic == null)
{
	heuristic = BasicHeuristic;
}

El último cambio será, precisamente, crear la función BasicHeuristic. Ésta podría devolver simplemente uno:

private float BasicHeuristic(N from, E edge, N to)
{
	return 1f;
}

¡Pero te quiero proponer algo mejor! ¿Recuerdas cuando implementamos Edge? Le dimos un peso, Weight, al que le asignamos el valor 1f por defecto. Es el momento de rescatar ese atributo y utilizarlo aquí:

private float BasicHeuristic(N from, E edge, N to)
{
	return edge.GetWeight();
}

De esta manera, si tienes un grafo de aristas ponderadas, ¡está todo listo!

Y en mi opinión así queda todo mucho más redondo y bonito, ¿no crees?

Utilizarlo en casos reales

En este artículo no vamos a entrar en cómo generar un grafo con posiciones dentro de Unity, pues se haría alargaría muchísimo y este texto ya es demasiado largo. Pero no quiero dejarte en la estacada, sin saber cómo usar estas herramientas.

En líneas generales, estos son los pasos a dar:

• Lo más probable es que tus Nodos representen posiciones en el espacio. Crea una clase que herede de Node, por ejemplo, PositionalNode, y dale los atributos que necesites.

public class PositionalNode : Node
{
	public Vector2 Position;

	public void SetData(Vector2 position)
	{
		Position = position;
	}
}

• A la hora de usar el grafo, utiliza PositionalNode (o la clase que vayas a utilizar) para declararlo.

_graph = new Graph<PositionalNode, Edge>();

• A la hora de crear los nodos, deberás inicializar su posición a mano.

PositionalNode n = _graph.AddNode();
n.SetData(new Vector2(row, col));

• ¡Recuerda que debes añadir las aristas a mano!

Edge e = _graph.AddEdge(left.Index, n.Index);
n.AddEdge(e.Index);
left.AddEdge(e.Index);  // Nodo a la izquierda de n

• Para buscar el camino entre dos puntos, todo lo que tienes que hacer es encontrar los nodos más cercanos a estos y llamar a AStar.

List<PositionalNode> path = _graph.AStar(
	GetClosestNode(A.position), 
	GetClosestNode(B.position), 
	DistanceHeuristic    // (Opcional) Función heurística
);
if (path == null || path.Count <= 1)
{
	return;
}

for (int i = 0; i < path.Count - 1; ++i)
{
	Gizmos.DrawWireSphere(path[i].Position, gizmosSize);
	Gizmos.DrawLine(path[i].Position, path[i+1].Position);
}

Siguientes pasos

¡Espero que te haya gustado y te haya servido de ayuda!

En Busca la Excusa no dejamos de buscar cualquier pretexto para seguir aprendiendo. Si te interesan los tutoriales de inteligencia artificial, te sugiero los siguientes artículos de mi blog:

• Programa un NPC desde 0
• Bases de la Generación Procedural
• La Inteligencia Artificial y las Máquinas Finitas