Olá galera, aqui vou explicar o básico do funcionamento do Pathfinding, pois apesar de ser muito útil não existem muitos tutoriais em português explicando sobre ele.
O que é Pathfinding?
Pathfinding é uma maneira de buscar a trajetória de um ponto a outro pela rota mais curta sem passar por cima de locais bloqueados, como paredes, rios e etc.
Onde aplicar?
É muito usado como auxiliar na criação de jogos onde os personagens requerem uma capacidade maior de inteligência de navegação pelo mapa.
Imagine jogos como Sol Survivor feito em XNA sem esse recurso, você ordenaria que suas tropas atacassem o inimigo e eles iriam direto para o rio sem ter ideia de que caminho seguir.
Funcionamento
Existem muitas fórmulas para Pathfinding, vou explicar aqui uma das mais usadas, que é a fórmula Manhattan.
Fórmula: F = G + H
F é a soma de G + H, o caminho para o ponto final é encontrado apartir do menor resultado.
G é o valor gasto do ponto de partida para um determinado quadrado da grade.
H é a distância estimada (ignorando todas as barreiras) para se chegar no ponto de destino.
Nos baseando na imagem acima, vamos imaginar que nosso ponto inicial é o quadrado verde, e temos que chegar até o quadrado vermelho, iremos atribuir 10 pontos de distância em G para um caminho na ortogonal, ou seja, na horizontal ou na vertical e 14 para um movimento diagonal. Usamos esses números porque a distância real para mover na diagonal é a raiz quadrada de 2, aproximadamente 0.4 maior que o valor da movimentação ortogonal nesse nosso caso.
Para guardarmos o caminho, precisamos criar uma lista de caminhos abertos e outra lista para os caminhos fechados que são aqueles que já foram verificados.
Olhando para a imagem acima, veja que os quadrados em azul são os novos que devem entrar na lista aberta, o quadrado verde é o quadrado atual de verificação e os quadrados marrons representam as paredes e serão ignorados.
Após selecionar os quadrados que irão para a lista aberta é executada a fórmula Manhattan trazendo os valores que serão guardados dentro deles, esses valores estão exemplificados nos quadrados azuis acima na seguinte ordem:
O valor que fica na direita inferior do quadrado representa o H que é a distancia que ele está do quadrado vermelho.
O valor que fica na esquerda inferior representa o G, seu valor é o total da soma entre o valor G do pai mais 10 caso ortogonal ou 14 para diagonal.
E finalmente F, que é o total da soma de G + H.
Assim ficamos como abaixo:
ListaAberta = 8 (quadrados em azuis);
ListaFechada = 1 (o quadrado atual vai para a lista fechada);
Depois de calcular todos valores da lista aberta, verificamos qual dos quadrados tem o menor valor em F, assim, pegamos esse e jogamos para quadrado corrente, executamos os mesmos procedimentos citados acima até chegar no quadrado final.
E caso nossa ListAberta seja igual a zero e não tivermos encontrado nosso quadrado final, significa que nosso quadrado inicial está em um local fechado.
Vamos traduzir em código o que foi falado
namespace Pathfinding{ #region Using Statements using System; using System.Collections.Generic; using System.Linq; using System.Text; using Microsoft.Xna.Framework; #endregion public class PathfindingManager { #region Fields /// <summary> /// Direções que o quadrado corrente deve verificar /// </summary> private readonly sbyte[,] direction = new sbyte[8, 2] { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 }, { 1, -1 }, { 1, 1 }, { -1, 1 }, { -1, -1 } }; #endregion #region Constructor /// <summary> /// Iniciamos nosso PathfindingManager com a matriz onde faremos a busca /// </summary> /// <param name="matriz">Matriz atual onde o Pathfinding deve fazer as buscas</param> public PathfindingManager(byte[,] matriz) { this.Matriz = matriz; this.OpenList = new NodeCollection(); this.ClosedList = new NodeCollection(); } #endregion #region Enum /// <summary> /// Tipos de busca /// </summary> public enum FindType { /// <summary> /// Se for ortogonal deve rodar nos 4 primeiros indices da instancia de direções /// </summary> Orthogonal = 4, /// <summary> /// Se for diagonal deve rodar por todos os indices da instancia de direções /// </summary> Diagonal = 8 } #endregion #region Properties /// <summary> /// Gets or sets OpenList /// </summary> public NodeCollection OpenList { get; set; } /// <summary> /// Gets or sets ClosedList /// </summary> public NodeCollection ClosedList { get; set; } /// <summary> /// Gets or sets Matriz /// </summary> public byte[,] Matriz { get; set; } /// <summary> /// Gets or sets CurrentNode /// </summary> public NodeFactory CurrentNode { get; set; } #endregion #region Public Methods /// <summary> /// Faz uma busca para retorna a rota entre os dois pontos /// </summary> /// <param name="start">Nó inicial</param> /// <param name="target">Nó alvo</param> /// <param name="type">Tipo de procura</param> /// <returns>Retorna a rota entre os dois pontos</returns> public NodeCollection PathFinder(NodeFactory start, NodeFactory target, FindType type) { var route = new NodeCollection(); this.OpenList = new NodeCollection(); this.ClosedList = new NodeCollection(); this.CurrentNode = this.ManhattanSum(start, target); this.CurrentNode.G = 0; this.CurrentNode.F = this.CurrentNode.H; // Executa os algoritimos iniciais this.NodeAlgorithms(this.CurrentNode, target, type); // Rode enquanto existir elementos dentro da lista aberta while (this.OpenList.Count > 0) { this.CurrentNode = this.NodeAlgorithms(this.CurrentNode, target, type); // Se nó corrent for igual a nulo saimos fora do lupe pois não encontramos nosso alvo if (this.CurrentNode == null) { break; } // Caso o nó corrent for uma ao ponto final descobrimos que foi encontrado nosso alvo if (this.CurrentNode.Point.X == target.Point.X && this.CurrentNode.Point.Y == target.Point.Y) { // Pegamos a rota fazendo um retrocesso pelos pais de cada nó route = this.GetRoute(this.CurrentNode); return route; } } return route; } /// <summary> /// Pega a rota do nó requerido /// </summary> /// <param name="node">Nó atual</param> /// <returns>Coleção de nós indicando o caminho</returns> public NodeCollection GetRoute(NodeFactory node) { var route = new NodeCollection(); NodeFactory currentNode = node; do { route.Add(currentNode); currentNode = currentNode.Parent; } while (currentNode != null); route.Reverse(); return route; } #endregion #region Private Methods /// <summary> /// Pega o nó com o menos valor em F /// </summary> /// <returns>Retorna o próximo nó</returns> private NodeFactory GetNextNode() { var nodes = from n in this.OpenList orderby n.F ascending select n; return nodes.Count() > 0 ? nodes.First() : null; } /// <summary> /// Checa se o nó já exite na lista fechada /// </summary> /// <param name="node">Nó para checar</param> /// <returns>Retorna um valor boleano</returns> private bool CheckClosedNodeExistis(NodeFactory node) { if (this.ClosedList.Exists(o => o.Point.X == node.Point.X && o.Point.Y == node.Point.Y)) { return true; } else { return false; } } /// <summary> /// Checa se o nó já exite na lista aberta /// </summary> /// <param name="node">Nó para checar</param> /// <returns>Retorna um valor boleano</returns> private bool CheckOpenNodeExistis(NodeFactory node) { if (this.OpenList.Exists(o => o.Point.X == node.Point.X && o.Point.Y == node.Point.Y)) { return true; } else { return false; } } /// <summary> /// Executa a formula Manhattan, responsável por descobrir a menos distância entre os pontos /// </summary> /// <param name="node">Nó corrente</param> /// <param name="target">Nó alvo</param> /// <returns>Retorna um nó com os valores já somados</returns> private NodeFactory ManhattanSum(NodeFactory node, NodeFactory target) { node.H = (Math.Abs(node.Point.X - target.Point.X) * 10) + (Math.Abs(node.Point.Y - target.Point.Y) * 10); node.G = (node.Parent != null ? node.Parent.G : 0) + 10; node.F = node.G + node.H; return node; } /// <summary> /// Executa todos os algoritimos necessários no nó atual /// </summary> /// <param name="node">Nó atual</param> /// <param name="target">Nó alvo</param> /// <param name="type">Tipo de busca</param> /// <returns>Retorna o novo nó para continuar a busca</returns> private NodeFactory NodeAlgorithms(NodeFactory node, NodeFactory target, FindType type) { // Check if not existir in Closed list for add new node if (!this.CheckClosedNodeExistis(node)) { this.OpenList.Remove(node); this.ClosedList.Add(node); } // Faz um loop nas direções escolhidas for (int d = 0; d < Convert.ToInt16(type); d++) { var dirx = this.direction[d, 0]; var diry = this.direction[d, 1]; // Cria um novo nó para possivelmente coloca-lo na lista var newnode = new Node() { Point = new Point(node.Point.X + dirx, node.Point.Y + diry), Parent = node }; // Se X or Y for menor que 0 então vamos para o proximo item do laço if (newnode.Point.X < 0 || newnode.Point.Y < 0 || newnode.Point.X > Matriz.GetUpperBound(0) || newnode.Point.Y > Matriz.GetUpperBound(1)) { continue; } // Checa se o novo nó não está no local de uma parede, caso não, continua o processo normalmente, caso sim ignora-o para verificar o próximo nó if (this.Matriz[newnode.Point.X, newnode.Point.Y] != Convert.ToByte(NodeFactory.NodeType.Wall)) { if (!this.CheckOpenNodeExistis(newnode) && !this.CheckClosedNodeExistis(newnode)) { this.OpenList.Add(this.ManhattanSum(newnode, target)); } } } return this.GetNextNode(); } #endregion } } Bom é isso, até o próximo tutorial galera, valeu!!
Abraços!! |