5

I'm working on a point-and-click test game and have made a ton of progress through research and finding other stack overflow answers about this-or-that, but this is the first time I can't seem to find anything related to my question.

My plan is to implement PatrolJS into my project for pathfinding, and it seems like I shouldn't have any problem getting it working after this issue is solved. I have my environment as well as some NPC characters in my scene. I have the mouse interaction in 3d space able to select and store data about what is clicked on. I am able to move my character to the click positions. I believe my problem will come in registering clicks into the pathfinding area.

Here a visual representation of my question:

enter image description here

Here, you can see my environment simplified down to one color, as well as the area I am currently defining for my navmesh area. The player will be able to click anywhere on the 3d environment/NPC's etc to interact with/view/use elements in the environment. That clicking works already, returning me with the point in 3d space that the mouse/ray intersects with, and giving me any information about those elements clicked on that I have defined.

What I need some guidance with is, how can I get returned the most nearby point on the separate navmesh object to what was clicked in the environment object(s)? Say I click on some part of one of the tables. I want to be able to find the absolute closest Vector 3 point on the navmesh object. That way, if someone interacts with elements off of the navigable area, I can still define an endpoint and feed that into PatrolJS.

3
  • I can provide help, but it will need pictures/illustrations that I can't provide at the moment because I'm at work. I'll try to see if I can do that when I get home Jul 12, 2016 at 20:20
  • Check my somewhat related question here, I think you will find some useful things in there...
    – Wilt
    Jul 13, 2016 at 11:45
  • Can the player only move on the 2D plane? This would reduce it to a 2D problem, right? Jul 13, 2016 at 11:56

1 Answer 1

7

Given a mesh made out of n triangles and a point p you can find the closest point from the mesh to p using brute force in O(n), the algorithm is as follows

  • For each triangle t that belongs to the mesh
    • project p onto the plane defined by t, let proj be this point
    • if proj lies on t then it's the closest point to p, store the distance from proj to p
    • if proj lies outside the triangle then compute the closest point to proj for each of the 3 sides of the triangle, store the distances from each of these points to p
  • The overall answer is the point whose distance is closest to p

THREE.js Demo

1
  • Thank you! Using your suggestion, I was able to get exactly the behavior I was looking for. The demo really helped out a lot, too. Thanks for taking the time. Anyone else that needs a similar result, check this answer^.
    – Case Silva
    Jul 15, 2016 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.