Node Based Navigation - find closest node in direction

Hey everyone,

I ran into a problem which I can't solve for a few hours now...
I'm building like a node-based navigation system, where the player will be navigated from node to node.
When I set a new target destination (red T), the player (green P) should find the closest node in the direction of the target. At the end, the player would get the shortest path (blue line) to the target. This path will be different depending on the players current position.

I tried several methods, but couldn't get it to work. My issue is not the code, it's the logic I can't get right now

The best I can think of right now is to build 2 lists from all nodes:
- first list will be ordered by distance to player
- second list will be ordered by distance to target
Then compare the two lists and get the best match of both lists? There should be a better solution to this, right?!?

Summary:
- Get closest node to player (Vector3.sqrMagnitude)
- Check if closest node is closest towards target?
- Check if there is a better node available?

Any suggestions I could try?
Thanks in advance!

Best, Markus

 

Did you consider the A* algorithm? I'm no expert on pathfinding algorithms, but your problem sounds like it could be solved with A*.

 

Hmm...I don‘t think I can use A* for this, because the nodes can be places everywhere without a fixed grid for the algorithm to work with. Maybe project the nodes onto a virtual grid? :/

 

a* does not have to be an actual grid
https://en.wikipedia.org/wiki/Shortest_path_problem

 

Oh yeah, you're right. Let me do some tests, but I'm sure this will work. Thanks to both of you!

 

ya most demos and examples do seem to be grid based tho
tho lots of docs explain is with non-grid nodes first

someone asked on stack with only one answer
https://gamedev.stackexchange.com/q...athfinding-on-a-non-grid-non-node-terrain-map
this is JavaScript and not really astar but is a 'simple' node based example
http://eloquentjavascript.net/07_robot.html