A* Pathfinding com NavMesh

February 25, 2012 in AI, Pathfinding, Português, Tutorials

Estou escrevendo este post pois é um tanto quanto difícil encontrar materiais sobre A* com navmesh. A maioria dos artigos na web são e inglês e descrevem a rotina de uma forma bem genérica e qualitativa. O objetivo deste post é facilitar um pouco a vida dos programadores de jogos que não falam inglês ou que tem uma certa dificuldade com as explicações genéricas da maior parte dos artigos na internet.

Neste post vou descrever passo a passo como funciona a rotina de um A* quando trabalhamos com navmeshes. Para entender o conceito é necessário que você já esteja familiarizado com o A* para grids. Caso ainda não tenha total compreendimento do A*, por favor, leia este artigo para iniciantes antes de continuar. Nas partes com código vou utilizar a linguagem Blitz3D a qual tem uma sintaxe derivada do basic e portanto é de fácil entendimento. De qualquer forma, você pode programar o seu algorítimo na linguagem que preferir.

Antes de começar você já deve ter os seus navmeshes mapeados. Eles podem ser qualquer polígono, com a única condição de ser obrigatoriamente convexo. Eu recomendo fortemente que se utilize triângulos. Apesar de não ser a forma mais rápida de rodar, é de fato, a forma mais fácil de programar. Neste tutorial eu vou utilizar este método. Você pode mapeá-los de inúmeras formas, desde a simplicidade de fazer isso a mão ou criar algorítimos sofisticados para mapear automaticamente (pretendo escrever sobre isso mais tarde). O importante neste tutorial é que a estrutura dos seus navmeshes contenha as posições das três vértices que compõem cada triângulo do seu navmesh. Em B3D você pode guardar esse dados facilmente desta forma:

 Type Triangulo
…….Field Vertice1X#, Vertice1Y
…….Field Vertice2X#, Vertice2Y
…….Field Vertice3X#, Vertice3Y#
End Type
(obs: você pode utilizar BlitzArrays se preferir)

Com todos os triângulos mapeados é hora de abordar o problema. Podemos explicar a problemática através da seguinte imagem:

Seu NavMesh com um ponto inicial e um ponto final

Seu objetivo aqui é simples: Conseguir encontrar o caminho mais curto do ponto inicial até o ponto final, de forma que, o caminho só seja válido se estiver dentro do NavMesh. Para isso, vamos dar uma olhada mais próxima dos pontos inicial e final.

A probabilidade do início ou fim do caminho estarem exatamente sobre a vértice de algum triângulo é praticamente nula. Por este motivo, nós temos que ter uma rotina para descobrir em qual triângulo cada pontos está situado.

Um método fácil é criar uma função chamada PontoEstaNoTriangulo( args ). Você fornece a esta função as coordenadas das três vértices do triângulo juntamente com a coordenada do ponto em questão. Esta função deverá retornar VERDADEIRO se o ponto estiver dentro do triângulo e FALSO caso não esteja. Existe uma maneira bem simples e barata (em termos de processamento) de fazer isso. Utiliza-se produtos vetoriais para verificar se o ponto está dentro da geometria ou não. Este algorítimo está descrito neste artigo (em inglês). Caso não consiga entender o método, por favor, deixe um comentário no post que posso explicar mais detalhadamente. Há outra maneira de realizar está tarefa. Ela envolve calcular a área de alguns triângulos criados por estas vértices e compara-las. Eu fortemente desaconselho está opção. Pode parecer uma solução fácil, mas ela é muito cara em termos de processamento e o limite de casa decimais da variável utilizada pode levar a resultados incorretos. Utilize o algorítimo sugerido acima.

Com a sua função escrita, o que você precisa fazer é testar o ponto de início e o ponto de final com todos os triângulos do seu navmesh até encontrar a quais triângulos eles estão situados. A primeira vista pode parecer uma tarefa pesada de se calcular, no entanto ela só é realizada uma vez durante todo o calculo do caminho. Depois desta analise você pode ter três tipos de resultados e é importante analisar o significado de cada um deles.

  1. Ambos os pontos estão situados no mesmo triângulo
    Este resultado quer dizer que é possível ir em linha reta do ponto inicial ao final (o que com certeza é o menor caminho entre eles). Neste caso você não precisa calcular um caminho e sim apenas retornar uma linha reta como resultado.
  2. Para um ou ambos os pontos não foi encontrado um triângulo
    Isso significa que um ou ambos os pontos estão fora do navmesh. Minha solução neste caso é simplesmente abortar o cálculo e não retornar nenhum caminho. Entretanto, você pode fazer alguma função para lidar com erro como esse (por exemplo: um caminho em linha reta até o navmesh mais próximo e depois calcular o caminho normalmente).
  3. Os pontos estão em triângulo diferentes
    Neste caso você deve calcular o caminho utilizando a metodologia abaixo.

 

Voila! Você encontrou o triângulo do ponto inicial

Sabendo em qual triângulo seu ponto inicial está localizado, você pode adicionado a lista fechada e colocar todos os pontos adjacentes a ele (vértices do triângulo) na lista aberta. Lembre-se de colocar o ponto inicial como pai das vértices na lista aberta. Fazendo este procedimento, você chegará a algo assim:

Pontos adjacentes ao ponto inicial

Para cada ponto enviado para a lista aberta, calcule o custo G e H dele. Você pode encontrar na internet várias formas de calcula-los. Neste caso vou utilizar a distância euclidiana (em linha reta) do ponto até o ponto inicial como o custo G e a distância euclidiana do ponto até o ponto final como custo H. Com certeza não é a melhor solução, mas funciona! Após realizado os cálculos, encontre o ponto que contém o menor valor de F, onde F = G + H.

Para o ponto encontrado repita o procedimento anterior (enviar para a lista fechada, enviar para a lista aberta os pontos adjacentes, calcular os valores de G e H e encontrar o ponto com o menor F). A única questão de atenção aqui é em colocar uma condição para os pontos na lista fechada nunca serem enviados para a lista aberta. Eles já foram analisados e não precisamos analisá-los novamente.

Caso algum ponto que você esteja tentando enviar para a lista aberta já estiver lá, apenas cacule novamente o valor  do custo G. Caso ele seja menor do que o custo atual, substitua na lista. Dica: Na hora de calcular o custo G, não se esqueça que ele é a soma da distância do ponto inicial até a vértice 2 mais a distância da vértice 2 até a vértice a ser calculada.

Pontos adjacentes a vértice 2

Repetindo o processo você saberá que terminou quando você adicionar a lista fechada qualquer uma das vértices do triângulo que contém o ponto final. Quando você chegar nesta situação o seu próximo caminho é apenas uma linha reta da vértice adicionada até o ponto final.

Último ponto calculado

Exatamente como fazemos no algorítimo para grids, devemos realizar uma backtracking  para descobrir o caminho até o ponto. Isso é realizado começando do ponto final e voltando (através dos pontos pais) até o ponto inicial. Depois disso é só retornar o caminho encontrado para o personagem seguir.

Caminho final e backtracking

Você provavelmente irá notar que este algorítimo retorna um caminho encostado as paredes. Este é um fenômeno natural dos navmeshes. Para conserta-lo você pode criar uma outra análise após o caminho ser gerado que faz o seguinte:

Se é possivel ir em linha reta do ponto 1 até o ponto 3. Então, deletar o ponto 2 (pois é inútil).

Utilizando a lógica acima, você terá o caminho mais curto do ponto inicial ao final. Entretanto, isso ainda parece um pouco robótico. Se quiser simular caminhos que pareçam mais humanos, sugiro a leitura do seguinte artigo The AI Systems of Left 4 Dead (em inglês) escrito pelo Michael Booth, onde ele descreve como foram criados alguns dos sistemas de inteligência artificial do Left 4 Dead.

Caminho gerado sem nenhuma otimização

Ficamos por aqui pessoal! Caso ainda tenha alguma duvida, deixe um comentário abaixo que irei responder assim que possível.

Referências

Tags: ,
No Comments »

A* with NavMesh Detailed

July 23, 2011 in AI, English, Pathfinding, Tutorials

I wrote this post because it’s really hard to find detailed material about A* with NavMesh, and also most of A* tutorials present either the grid-based algorithm or some vague reference to navmesh. My goal with this post is to provide some clean, ready-to-use information which AI game programmers can use to enhance their pathfinding algorithms.

On this post I will describe step-by-step how to implement a navmesh oriented pathfinding in your game. To understand this concept it’s mandatory that you fell comfortable with the grid-based A* algorithm. If you don`t fully understand the concept of A*, please take your time to read this article for beginners. Also, keep in your mind that when a reference to some code appears here, it will be in Blitz3D. This language is designed for game developing and it’s my favorite for prototyping. It’s also derived from basic so it’s pretty easy to understand.

Before you start, you need to create your navmesh. They can be anything, from triangles to polygons, the only constrain here is that each individual polygon must be convex. This is useful because it guarantees that any straight line inside a single node can be a valid path. I strongly recommend that you stick with the triangle approach. Might not be the most speed-friendly approach but it is, by far, the easiest to code.

There are several ways to create your navmesh map, you can try doing it manually or using algorithms that calculate them dynamically (which I intend to explain in some later post) . The important part here is that you have all of them mapped with the position of each triangle vertice. To store you navmesh map you can code a structure just like this:

Type Triangle
…….Field Vertice1X#,  Vertice1Y#
…….Field Vertice2X#,  Vertice2Y#
…….Field Vertice3X#, Vertice3Y#
End Type

Now that you have all of your polygons mapped, it’s time to make it work! An example of the problematic could be illustrated by the following example:

A NavMesh and two (Starting and Ending) points

Our objective here is simple. You need to find the shortest path from START to END and to be valid this path must be inside the navmesh. To achieve this, let’s take a closer look to our starting and ending points.

Normally, your starting/ending point is not on any vertice. So we need to find out in which triangle it is situated.  An easy method to do this is to call a function PointInsideTriangle(args). We provide this function with the triangle vertices and a point and it should returns true if the point is inside the triangle or false otherwise. There are several ways to code this, my favorite one works with cross products. This matematical approach is fast and reliable. Its algorithm is described on this website. There is in fact another way of doing the same thing. It involves computing some triangle areas and comparing them. Though this approach sounds easier, I strongly discourage you from using it. It’s very computing-intensive and the variable decimal precision can lead to errors. Instead use the algorithm described on the website above.

Now that we have you function coded, we must check our starting and ending point against all triangles into the navmesh until we find where they are located. It may sound like a very computing-intensive operation, and sure it is! The good news is that we only need to calculate this once for the entire path. After this analysis you can come up with any of those 3 results. It’s important to handle them carefully.

  1. Both point are located on the same triangle
    Good news! This means that we can use a straight line as our path and for sure this is the shortest way. No further intensive calculations necessary.
  2. One or both points are outside all triangles
    This means that one or both points are outside your navmesh. On this situation I would probably stop this path calculation and return just a null path. But it’s up to you! You can make a code to handle this kind of error.
  3. Both points are located on different triangles
    This means that we should proceed with our path calculation.

Voila! You found the first triangle!

Now that you know on which triangle your starting point is located you can add this point to the closed list and send all the adjacent points to the open list (and keep a record of its parent point – in this case the starting point). The adjacent points in this case is all the triangle vertices. Doing this you will get this:

Adjacent points of the starting point

For each point, calculate the G and H cost. You can find a lot of ways to calculate this on the internet, or just use the distance between the last point (starting point) and the vertice for G and the distance between the vertice and the ending point for H. It`s not the best coefficient but works! After you are done, selected the point with lower F cost (F = G + H).

Adjacent points of V2

Repeat the same process with this point (send its adjacent points to the open list and add the point to the closed list). If any point that you are trying to send to the open list is already there: Just check if the G cost from this new path is better than the former, if true, then change the G cost, and the point parent. Also, when calculating the G cost, remember that it is the G cost to the point V2 plus the Distance between V2 and the point you are calculating.

Last point

You know you are finished, the time that you add to the closed list one of the vertices of the triangle that contains the ending point. To check this, you can find the 3 vertices of the ending triangle and check every time you add a point to the closed list.
When you find this vertice, your next point is just a straight line to the ending point, since you have a convex navmesh and you can draw a straight line between any 2 points inside it.

Backtracking

Just like the algorithm for grids, backtrack  your way to the starting point (using the parent points you recorded) and you will find you path.

You will notice that this algorithm provides a wall-hugging path, since it use the vertices to generate the path. You can fix this by deleting useless points (if you can go from A directly to C without falling off the NavMesh, then the point B is useless and you can delete it).

The next step is to implement it on your game!

 

Tags: ,
No Comments »

A* Pathfinding with NavMesh

July 22, 2011 in AI, English, Pathfinding, Tutorials

If you are looking for a detailed article about how to write your own navmesh pathfinder, click here. 

In the first post I showed my NavMesh Generator. Now it`s time to wrap everything up and build the pathfinding system.

First, I used a piece of code from the generator to load the map and the NavMesh into my world. Then I worked with some keys functions like:

  • OpenAdjacentPoints – You provide a particular point, and this function send to Open List all the points that are adjacent (can be travelled in a straight line). For example: If you provide a point that is the vertice of a triangle, it returns the next 2 vertices; or if you provide a point that is inside a triangle, it returns all of its vertices.
  • FindTriangle – You provide a point, and this function return the mesh (triangle) that contains this point. Useful for the starting and ending point of your pathfinding, since they are mostly inside a triangule and not on its vertices.
  • CanSeeEachOther – You provide 2 points and the function return true if this points can be connected by a straight line without falling off the NavMesh, or false otherwise.

With those function, it was pretty easy to implement the algorithm. Just send the first point to the Closed List and all his adjacents to the Open List, then select the point with lower f and send his adjacents to the open list, and so on.

Since I used only the vertices of the triangles to generate the path, my path was looking like a wall-hugging. To overcome this obstacle, I just implemented a kind of path optimization. For instance: If you path has 3 points (A, B and C), the algorithm check if you can go from point A directly to point C, without falling off the NavMesh (using the CanSeeEachOther function). If you can, then delete the point B (because it`s useless).

Unfortunately, my function CanSeeEachOther still doesen`t work 100% times. So, while I`m trying to fix it, I will not post the source code of the pathfinding.

Here are some screenshots:

NavMesh without Path-optimization

NavMesh without Path-optimization

NavMesh with Path-optimization - You can see my optimization is not so smart

 

Tags: ,
1 Comment »

NavMesh Generator

July 22, 2011 in AI, English, Pathfinding

Yesterday I started to wonder how difficult was to implement a A* with NavMesh system. So I started working, first in a NavMesh creator, then in the A* system itself.

My NavMesh Creator loading maps with the PX_MAP (an API to load Valve Hammer `s .map files), and PX_GUI for the menus. The result is shown below:

NavMesh Generator: First Screen

Adding a triangular mesh

Paths

Paths

Same image, but showing the NavMesh only

The concept of this generator is simple: A 3d pointer is inside the world and always attached to a surface. You move this pointer with your mouse and click to add a vertice on its location, and repeat the process. When you have added 3 vertices, the software creates a triangular mesh and store its vertices. Than you keep add new meshes, with the already placed vertices or placing new ones.

Using this application I could create .nav files. This file stores the vertices of every NavMesh in the world, and I use then for the next step: Building an A* Pathfinding.

You can download the NavMeshGenerator 1.0 and its source code.

Tags: , , ,
No Comments »

First Post

July 22, 2011 in Avisos, English

Hello Guys,

I’ve set up this website as a deposit for all my applications, softwares, tutorials and articles. I`m still trying to figure out how to categorize everything. But I will probably do that when I have more posts.

Thanks!

No Comments »