Sign in to follow this  

a few questions regarding navigation meshes

This topic is 1509 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Edited by uzipaz

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

This topic is 1509 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this