Jump to content

  • Log In with Google      Sign In   
  • Create Account





Navigation mesh picking

Posted by O-san, in Programming 29 March 2013 · 686 views

My navigation mesh picking routine have been fairly straight forward up until now. I have shot a ray from the mouse cursor into the scene and selected the point that intersects the mesh closest to the camera. This works fine 90% of the time. Recently however a new and more complicated solution was needed.

As mentioned in the previous post I have started building maps with more than one floor. This raises a problem since my navigation mesh is not split up into different floors, its just one big mesh for the entire map.


Posted Image


In the above example the house has one main floor and a small loft. The loft floor and stairs are overlapping the ground mesh outside the building. If I used the closest intersection point on the ray selection the player would always walk to the stairs, this is not always desired. For instance if the player were behind or outside the building... then the roof would be visible and the stairs would be obscured. In that case I have reasoned it's more desirable to pick the intersection point that is obscured, in other words... the ground behind the building, not the closest point.

New solution with a problem
Now I figured that this was pretty easy to solve. Just select the point that is further away if the player is outside (not underneath a roof), else pick the closest point if the loft is visible (i.e. the player is underneath a roof).

This worked fine for the above case. Now come the next house..


Posted Image


As you can see.. this house has an even more complex navigation mesh. The entire second floor lay on top of the first floor making the new solution broken. The second floor's mesh would always be used because it would always be the closest. However, it would still be possible to walk behind the house if the player were outside the building.

Second try...
Well, now I came to understand that I needed to split the building into more "roofs" and detect exactly which roof the player was below. Sounds confusing? It was at first.

Posted Image


I figured I would need to know where the players feet were in order to fix this and luckily I already had that position. I also needed to know which roof the player was standing on. Well I knew that too because I had already done the fading of the different floors which used the same objects. Some bullet points to decide on the correct intersection point (the green point in the above picture):
  • Disregard points that are too far below the players feet but still underneath the roof object (makes it possible to click stairs going down).
  • Always use a point that is outside the roofs X/Y components if only a single hit is returned (the user clicked outside the building and wants to get out).
  • Select the point that is closest to the players feet z component if there are multiple hits.
There are still certain cases when the picking is a bit awkward. For instance when the player clicks an area of a second floor that borders the outside of the building. This will result in a intersection point outside the building due to that the navigation mesh is built to account for the player width. This width can be seen around the entire mesh as an offset from the walls. It only becomes a problem when the mesh borders nothing (for instance a second floor bordering air). When an intersection point lays on the ground plane or is inside a building this issue has been taken care of with another method.. I won't go into this now, I think this post is enough elaborate as it is.. ;)

The second picking routine might be a bit overkill as I easily could... and in most cases probably will use entirely new maps for the interiors of larger buildings and floors (think castles, dungeons etc.).

Well, that's all, thanks for reading again!




These are the kinds of problems I find enjoyable to solve. I've been doing gamedev for long enough now that the "obvious" problems (the foundational technical issues, in other words) are technologically solved and boring to tackle, but these little edge cases and implementation-specific problems still pose for me a creative challenge.
Also, I don't know if I've said it before or not, but this project looks awesome.

Latest Visitors

PARTNERS