I have to write a simple 3D game in which I would like to implement an agent that can navigate through a map that has walls and simple static obstacles...

Now, I have studied the A* algorithm and was able to successfully write my own algorithm in c++... The algorithm runs on a rectangular grid with all the grids of being the same size... and can calculate optimal paths using euclidean distance as the heuristic...

Well, I have searched the internet and some game programming books and saw that just writing an A* algorithm is not enough, I need to have search space representation which in my case is a rectangular grid, translation of agents and 3D world knowledge between the algorithm and the game...

I was looking into some search space representation techniques and one of the most popular being navmesh and waypoints... I have read that pathfinding using waypoints in not recommended anymore and navmesh is the most popular among current AI developers...

Now, my issue is that I have never worked or programmed nav meshes before and this is the first time I am writing a game that has an AI component or NPCs...

How should I approach this? should I start by how to automatically generate navigation meshes for a level? or adjusting my algorithm to support navigation meshes?

I would gladly appreciate any advice...

I'm not quite sure what your question is? If it's trying to get pathfinding to work in 3D games, your rectangular grid should be workable, as most pathing cases (even in 3D games) tend to have a topology that maps down easily to 2D space.

What are you trying to consider as a part of your A* search and what is necessary for your game? You don't always need to have full 3D world knowledge represented in your search space. Most of the time, the 3D information involved is just portions of the walkable geometry so the game can map from the playable 3D space down to a representative graph for the pathing problem that is being solved, which often ignores most of the other 3D aspects of the game.

I am rather a confusing individual... My point was that I would like to do this from scratch (as I did basic A*) so I could learn and understand the algorithm and the techniques... and I searched for Navigation meshes on the internet and several game programming books (including game programming gems, AI game wisdom). They don't give me any guidance about where to get started for this for newbies like me... but they describe a lot of different techniques and algorithms...

What you have described in your post is that I should stick with the rectangular grid... and it automatically does answers a lot of questions for me if I stick with a rectangular grid with each being of fixed equal size...

Implementing a navmesh is a fairly complex task. You need to solve several distinct problems:

• Generating the mesh itself, which is nontrivial and many large papers have been written about techniques for this
• Simplifying the mesh, which is important for performance and for accuracy in many cases
• Path finding, which is easy enough if you already have a generalized A* implementation
• Path following, which depends highly on the game you're trying to make

Virtually none of this stuff is general-purpose aside from the path-finding portion. The constraints vary wildly between types of games, and you need to have a pretty good understanding of a specific game's constraints to make a really good implementation of the algorithms. Navmeshes are not just a singular technique, they're a family of techniques with a few common elements.

Your best bet is to make a game or tech demo, even if it's a painfully simple one, so you can narrow down the problem space and find a set of navmesh techniques that are suitable to that specific case. Once you know what problem you're trying to solve, understanding and working from the existing literature becomes a lot easier.

Sticking to a rectangular grid/mesh can be easy from the initial implementation point of view, but they aren't without their own problems. You have to consider the needs of your game to reach a good solution. If your game's actual play space is grid based then the rectangular grid solution should work quite well, but if you have a full 3D continuous game space, you'll probably find lots of potential problems with using a grid (How do you generate the grid? What resolution? How many nodes are necessary to get good coverage/accuracy?).

Going with a triangulated mesh isn't a clear win either. Given a 3D game, you could use some of the level geometry as a starting point for your triangulation, but you have to solve a lot of different problems (many of which don't have clear right answers/solutions) to get something that would be usable for your game. If you have the expertise and the capability, you can have the mesh and it will give you a lot of nice properties, but getting the mesh in the first place is often very difficult.

Check out Recast/Detour https://github.com/memononen/recastnavigation. It's a very nice (so I've heard, never used it myself, but the features look impressive) navigation mesh generation library and if I'm not mistaken, it was used in Killzone: Shadow Fall! The source is available so you can take a look at some of the techniques used.

If you're learning the basics of A*, pathfinding, and path following, I would highly recommend sticking to the rectangular grid as a starting point. If you do in fact have a 3D game, it probably won't be ideal but it's simple enough that it should get you going and have you focused on getting a complete workable solution for AI agents to reason about your world and path through it. Once you complete this, you could move on to having some sort of triangulated mesh. If so, I would recommend reading up on Delaunay triangulations and more specifically, constrained Delaunay triangulations.

As the other people have already said, depending on your needs, just use the retangular grids.

If you are set into using nav meshes or is doing that for study purposes I definitely would recomend you to take a look at this site:

http://www.critterai.org/book/export/html/2

It is a very detailed explaination on how recast works, definitely worth the time.

Read through this thread, it has some valuable information: http://www.gamedev.net/topic/648438-how-to-do-starcraft-2-pathfinding/

Specifically, check out critterAI's website: http://www.critterai.org

For instance, here is a study he wrote on navmesh generation:

http://www.critterai.org/book/export/html/2