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.

I'm not going to answer all your questions because I don't know a whole lot about navigation meshes. But your estimates of the complexity of algorithms are kind of high. Just about any space-partitioning method will bring down figuring out which polygon you are on to O(log(n)). Generating the graph structure can be done offline and its complexity doesn't matter a whole lot, but I still doubt it's worse than O(n*log(n)) if you use a space-partitioning method.

I'm not going to answer all your questions because I don't know a whole lot about navigation meshes. But your estimates of the complexity of algorithms are kind of high. Just about any space-partitioning method will bring down figuring out which polygon you are on to O(log(n)). Generating the graph structure can be done offline and its complexity doesn't matter a whole lot, but I still doubt it's worse than O(n*log(n)) if you use a space-partitioning method.

I did not knew about space partitioning method. Isn't this comes in hierarchical path finding? The game on which I am working on is not that complex or big. There are simple static walls and obstacles to be placed in the level. Maybe, I did exaggerated on algorithmic complexities of the problem but I did so with my understanding of the problem's solution.