Jump to content
  • Advertisement
Sign in to follow this  
calculemus1988

How do you maintain a navmesh in RTS game?

This topic is 2518 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

How do you maintain a navmesh in RTS game?

In RTS you constantly build and destroy buildings. That means you need to update your navmesh through the game.

I have done hierarchical pathfinding with two graphs, one finer and one coarser, on static map that does not change, from the book Programming Game AI by Example. I have not worked with navmeshes so far. I have no experience with maintaining a graph or mesh either, as in RTS games. Any articles or books you can recommend on the topic I would gladly read.

Thank you

Share this post


Link to post
Share on other sites
Advertisement
I have seen all sorts of articles around that deal with the dynamic modification of navmeshes. It's not trivial, however. Implementing something like Recast might be the best bet.

Share this post


Link to post
Share on other sites
It is much more complex than the pathfinding I did in "Programming Game AI by Example". I doubt I will find a book where NavMesh implementation is given and explained. But it seems the AI Game WIsdom series contains a lot of information on NavMeshes. As soon as I get some money next week I am ordering all 4.

In my RTS project so far I got the selection system and steering behaviors. Next is the pathfinding system, seems I will spend two months or so on this.

Edit: I decided to go with Recast and Detour. I will spend way too much time on pathfinding myself and I won't get the game done till October which is my deadline. If you guys can recommend some tutorials/articles or whatever on Recast and Detour please, there is no documentation for it which makes things hard.

Share this post


Link to post
Share on other sites
I decided to do my own pathfinding. I provide a short description of what I plan to do, feel free to comment.

1. Only two types of objects can change the navmesh at runtime. Trees and buildings.

2. Trees - when a tree is cut down a rectangle will be added to the navmesh, at position where the tree was so that the area is now walkable. Each minute I will do a check if I can join some rectangles for fallen trees. This way I wont lose performance and I will make sure that I dont get lot of small rectangles in the navmesh for the trees that were cut down. So that is all about trees, easy right?

3. Buildings - As in Warcraft, you can position the building at discrete positions, which means I will use a grid. There are two cases, a building is created or destroyed. When a building is destroyed it is easy, just add one rectangle(representing this building's area) to the navmesh. When a building is created it will occupy a rectangle in my grid so basically I will just cut off the cells that are inside this building's area, which will be fast to test. Then I will add the triangles around the building as in this image. http://postimage.org/image/5pnq53dzb/ So you can just walk on the green area, the yellow is the building. This is the only case where I will use triangles in my navmesh. Everything else will be done with rectangles that fit in a grid so that intersections tests are easy, when you try to create a building and update the navmesh. So the main part of the job will be dealing with the different cases of rectangle intersections. Restricting myself to a grid and not using triangles will make things easier. Well actually instead of thinking about cases, I should find myself some computational geometry algorithm that partitions a surface into rectangles. Not quadrangulation algorithm, I need only rectangles which are quads yes, but with vertical and horizontal lines only.

Here is the process of creating a building: http://postimage.org/image/bzde0j8vf/

A question I have is will this cause me problems? http://postimage.org/image/wow6dzpuj/
I mean can I have two rectangles that share a side with one rectangle, or I will have to split the big rectangle like in the image below ?

Thanks for any comments

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!