How entities like enemies and NPC’s move from A to B is one of the key elements of game AI. For this project I have decided to use navmeshes.

What is a navmesh?

A navmesh is a representation of the game world in which walkable areas are stored as polygons. Obstacles get cut out of the navmesh to ensure the AI does not try to move to regions where it could or should not walk.

A navmesh representation in the current implementation looks somewhat like this:

A navmesh

The different colored polygons are walkable areas. Each area is convex. That means every point in an area can be reached from any other point in the same area by walking to it in a straight line. This makes pathfinding a lot easier since we now have to only find a path of colored areas from the start to the goal. The pink dots are the vertices of the polygons and the green lines are all possible connections between vertices for each individual polygon. Pathfinding from A to B now consists of these steps:

• Find the closest vertex to point A (va) & find the closest vertex to point B (vb).
• Run A* on the generated vertices and edges from va to vb.
• Return A ⇾ va ⇾ A*path… ⇾ bv ⇾ B as the final path.
• Shorten the path were possible (not implemented yet).

How it looks in the game

This is an example of a currently generated navmesh for a game world:

The game world	The corresponding navmesh

As is clearly visible, there are a couple of fairly wide polygons between the trees. This should not turn out to be an issue as the total number of polygons is reasonably close to optimal and path smoothing will make entities move more efficiently.

The entities will be able to use this navmesh to find a good path from A to B or determine that there is no such path.

Area transitions

Lastly, I want to talk about “areas” in the navmesh. It is important that an entity can recognize different terrain types. The entity can then avoid areas where it would be slow or even dangerous to move (like water or lava) and prefer areas that give a speed bonus (like roads).

The navmesh implements a way to define areas and their types and movement cost. With this information better paths can be found. Currently, there is one issue with this system though:

Path from A to B

The blue area is water. It slows the player down and should therefore be avoided. What’s currently happening is that while the area is perfectly avoided in the path itself, it does not take into account the width of the entity. The path goes along the edge between the water and the ground area. The entity would still touch the water and be slowed down or take damage if the area was lava.
This issue is what’s going to be addressed in the upcoming days of development.

Thanks for reading

That’s it for today. If you want to know more about what’s to come in the near future, check out the previous post. Bye.