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...

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.