Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
4  
"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. –  Nicol Bolas May 29 '12 at 6:17
    
You can't find a path between points unless you know their connectivity. That's basic graph theory. –  Byte56 May 29 '12 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. –  Roy T. May 29 '12 at 6:49
    
Well thanks anyway for answering my question, time to get busy. –  user16655 May 29 '12 at 7:25
1  
@RoyT. That's still generating a graph with connectivity, it's simply abstracted away. –  Byte56 May 29 '12 at 16:18

1 Answer 1

up vote 1 down vote accepted

A* works on most any node graph, not just tiles. So long as you can compute a heuristic for the cost to travel between two nodes (distance in most simple cases works fine), you can use A*.

The problem with finding the closest node to the selected point can be solved by doing a simple ray test (assuming relatively flat terrain). If the user picks a point, find the closest nodes that are "visible" from the selected point.

You can use that same approach (in an O(n^2) algorithm) to automatically generate connections between nodes you've placed.

It will be up to you to make sure that the nodes are placed close enough to each other and in all "crevices" in the map to ensure that the ray tests work (proximity may be particularly important of you have very "hilly" terrain).

You're going to want the ray tests anyway during patting to smooth out the paths.

share|improve this answer
    
Thanks so much, finally got A* implemented in the mod (using a graph), works great now, no strange patterns and avoids dead ends. –  user16655 May 30 '12 at 8:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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