# Pathfinding using nodes/waypoints without connecting them?

I've been doing some research on pathfinding lately because I want to code a game modification for a game (won't say which exactly) and what I've done is defined a huge list of 3D vectors where a player can possibly go to. The thing is, I want to implement some sort of pathfinding system which can navigate from one of the points in the list to the other.

I've read some tutorials and websites about pathfinding like A* and Dijkstra's algorithm but all those examples seems to use tiles/squares and are all in 2D environments...

So far, I'm performing some simple distance checks (for example, checking for any points that are less than 100 units away from the current one) and sight/bullet checks (to see if the point is walkable/accessible) and selecting the best point according to distance from the destination. This seems to work most of the time, however there are times where it may try to navigate along a dead end and just fail or it might do some strange, unneeded zig-zags as well as taking really long routes.

Have you guys got any ideas of any algorithms I could implement as well as provide some psuedo-code? That would be so great. I want to avoid having to define vertexes/edges or connecting these points because I find that the maps are so large/vast, it'd be too much trouble. I would only do that if it were a last resort.

• "I want to avoid having to define vertexes/edges or connecting these points" I'd suggest getting over that. The whole point of pathfinding is to reduce the problem from "search the terrain" to a much more easily solved "search a graph" problem. Graphs are vertices with connected edges. You can't have a graph with just vertices in it. There's no such thing as a free lunch. May 29, 2012 at 6:17
• You can't find a path between points unless you know their connectivity. That's basic graph theory. May 29, 2012 at 6:17
• I disagree. In the unreal engine you could drop apples to hint where playes could walk and the engine would generate a navigation mesh itself. So it is possible to do this. However the unreal engine didn't only consider the apple but also the meshes around that to get a better cover. Anyway maybe the algorithm is out there somewhere. May 29, 2012 at 6:49
• Well thanks anyway for answering my question, time to get busy. May 29, 2012 at 7:25
• @RoyT. That's still generating a graph with connectivity, it's simply abstracted away. May 29, 2012 at 16:18