Waypoints instead of A* pathfinding - how to ?

Blitz3D Forums/Blitz3D Programming/Waypoints instead of A* pathfinding - how to ?

semar (Posted 2009) [#1]

All, suppose you have a 3D level (for example a .b3D level). You go through the level, and put waypoints around, that the opponents can use to move through the level. The question is, how to use such waypoints ? For example. Waypoint A 'sees' waypoint B. B 'sees' C. So A can't see C directly, but can reach B to reach C. How can I translate this in code ? How can make it procedurally, without using a path finding A* algo, which requires usually a big matrix ? I want the characters in the game, follow a path to go from waypoint A to waypoint H for instance. A and H are not directly in view, but all the in-between waypoints are all in a table, from which an algo can find the appropriate path to reach the target - for ex. A-B,B-D,D-L,L-H. How would you accomplish that ? Suggestions and thoughts are very welcome. Regards, Sergio.

_Skully (Posted 2009) [#2]

Personally, I would create the waypoints and give them a destination... in other words, when the opponents hit the waypoint it gives them a destination to seek. If its a chain then just make the waypoint destination the next waypoint... but you will still need to consider direction... I'd say allow a waypoint to have different destinations based on the normal of the opponents movement... that would allow you to have waypoints that act as patrol runs Your still going to need to have a pathfinding system though... for in between waypoints... otherwise the opponents would look like they are hung on a laundry line

Gabriel (Posted 2009) [#3]

Your premise is flawed. A* is just a graph search algorithm and as such, it doesn't care whether you have a big matrix or a handful of nodes. The choice of search algorithm usually depends on what information you're trying to get out rather than what you're trying to put in. For example, A* is generally regarded as the best search when you have a known start and end node. Dijkstra's Algorithm is usually used when you have multiple target nodes and want to find the nearest one. Breadth-first is more usually used when you need a full list of possible paths, limited only by distance from the start point. (EG: Hex wargames might use it.) If you're looking for a specific path from a known point to a known point and you don't want A* (note that I haven't seen a good reason for you not to use A*, but I'm going to assume that there is one) then the next most common alternative would be Dijkstra's Algorithm. It uses no heuristic, which means it tends to explore more nodes than A* and as such it's generally slower than A* when searching for a path between two known nodes. So if you really can't use A* then I'd try Dijkstra's, but I'd really need a good reason not to use A* if it were me. EDIT: In case you really do want to use Dijkstra's algorithm, here's some information on it: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

semar (Posted 2009) [#4]

Thanks for the answers so far. @Gabriel, yes I'm also a fan of A* pathfinding, but I'm only concerned on the huge dimension matrix I have to build up to obtain a functional path finding, when the level reaches a consistent dimension. With waypoints I can just mark the relevant passages, and let the charachters follow it when needed. Thanks for the link. Sergio.

Duckstab[o] (Posted 2009) [#5]

You can also combine Waypoints and A* to allow higher resolution pathings but only working on the smallest area for the A* and Pathing for Area jumps [edit] you got it :)

Ross C (Posted 2009) [#6]

Well, if your nodes are for the player only, you could build up a lookup table so to speak, of all paths to particular destinations. Only problem you will have is if other entities are in the way. You don't really have a way of checking this. A* is pretty quick with just waypoints. I had it working with types (Which is bloody sloooow).