I''ve not heard the term ''beacons'' used in reference to pathfinding. Do you mean waypoints? If so, then you can simply treat a complete path from start to goal as a set of n+1 paths (where there are n beacons between start and goal).

Of course, this assumes that the beacons have a given sequence.

If you want to find the shortest length path that passes through each beacon IN ANY ORDER and goes from start to goal, then you need to look up methods for solving the Travelling Salesman Problem.

Cheers,

Tim

Maybe you are reffering to pathfinding through visibility nodes?
The word "beacon" seems close enough.

Pathfinding through visibility nodes doesnt have many differences to normal grid pathfinding. As a visibility node I refeer to a structure that at each point keeps a list of all the directly visible structures of it''s kind.

The way I implemented it is as follows (for a racing game AI): I first set the nodes(or beacons) through my tool, usually in such a way that they discribe the big objects in the world (surround them with nodes that form a closed shape). This way when in real time the car does a visibility check with a target and FALSE is returned, it can pathfind through the nodes to find a path that will look much more natural than just tracing the shape around until a clear path is availiable to the target. Specifically for the pathfind algorithm:
First of all I use A* without an active closed list (I found that it doesnt give much to the specific implementation). You might want to experiment with something less expensive.

Secondly, the main difference with the normal A* implementation is that instead of creating your successors by moving in your matrix(grid) up, down etc. you just move inside the visibility list of each VisNode.

Thirdly there are two ways to attach at each point your target and current position to the visibility chart you created with the tool in order to pathfind: You can create temporary VisNodes at the two points (so you start from your current position and end in the target) or make a function that desides on the best start node, pick it and stop pathfinding when the BestNode can see the target. I would suggest the second way as with that you avoid many problems and you can also make cool things as f.i. to peek the start node by taking your speed and bearing into account.

Hope I helped, excusse my English, I''m neither English or awake(yet!)

vanliv

John has a great site here with an example exe and source of how to code a pathfinding routine with beacons or waypoints:
http://hjem.sol.no/johncl/shorpath.htm
I've also translated this to QBasic - mail me if want a copy

The pathfinder makes a waypoint whenever a direction change is called for. Couple this with the fact it also doesn't use a closed list and you have a very fast pathfinder if all you need to do is avoid obstacles (ie. not take into account different ground types)

The predetermined path could be stored economically as directions and length to travel instead of every x,y location on the route, eg.
"X,Y Start",East4,Southeast9,East3,South3,Southeast3,"X,Y end".



Edited by - Decker on June 24, 2001 8:10:29 PM

So... since you recalculate the waypoints/beacons each time you pick a new start/finish point, what makes this approach better than A* in any situation? It would appear that you use a breadth-first search to generate the beacons anyway, which means that you would normally have found an optimal path with A* in less time than it would take to generate the beacons. Just asking, because I don''t see the point, besides being ''interesting''.