I am working on a small 2D game and my goal is to make the AI as the most proficient feature of the game. The space in which in the my characters will move within is continuous just like in 3D or RTS games. I studied some books/surfed the internet and I decided that implementing navigational meshes to represent search spaces seems to be the most appropriate technique.

But, I am new at this and I have few questions for which I have not been able to find satisfactory answers.

**(i)** Is it necessary for the navmesh polygons to be convex?

**(ii)** If I have a point(x,y) in my 2D world and I have the navigational meshes specified for the level, how do I know on which mesh polygon I am currently standing on(localization)?

My guess: If I have 'n' number of polygons in my level and each of them are specified with their own set of vertices, then this becomes a O(n) problem in the worst case. I would have to check each polygon for the existence of that point within it.

**(iii)** How do I generate a graph data structure from the navmesh for the A* pathfinding algorithm to use?

My guess: From my understanding, this becomes a O(n²) problem in the worst case, provided that we have 'n' number of polygons in the level and each polygon has its own set of vertices. For each polygon, I would have to look at every other polygon in the worst case and find if anyone of the pairs shares at least one vertex with each other. If they do, then they become neighboring nodes.

**(iv)** For heuristic calculations(euclidean distance) and conversion from graph node to game position, which point in a polygon should I use?

My guess: The centroid of a convex navmesh polygon seems to be the most appropriate choice. If we have 'n' number of vertices for a polygon, then from my understanding, calculating the point of centroid seems to become a O(n) problem.

That is all the questions I have right now. Kindly, please also give me some tips on to how should I organize the data of navmesh polygons into a meaningful data structure?

Any help will be greatly appreciated,

Thank you.