Hi all!! Do you know if there''s a web site, an usenet thread or anything else that talks about Pre-Calculated pathfinding using beacons?. I''m designing the pathfind algorithm for my CRPG (for RTS combat) & I want to look at every possibility. I''ve some ideas but i want more!!!! Thanks in advance! RRC²Soft

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.

>> Maybe you are reffering to pathfinding through visibility nodes?

Yes.

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

Thanks for your reply, vanliv ^_-
Also i''m making some tests for placing my "beacons" automatically, using a Java applet. I''m using corner detection (If i''m in a corner, put a beacon). I''ll post it in my website when finished.

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

Thanks all for your help ^_^
I''ve ended the Java applet that shows the pathfinding using beacons. take a look at http://www.geocities.com/rrc2soft/eng/doc/AStarEn.html

Hoping to be useful to somebody ^_-
Rodrigo (1/2 RRC²Soft)

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''.

Beacons are calculated and stored during mapmaking (and also the adjacent beacons for every beacon). So the only thing that it''s calculated in run-time is adjacents for start & end point.
I think (not sure, of course )that this method is better than A* since it expand less tiles (the search is made with A* itself but changing the "adjacent seeking" method [Not NWSE, take''em from pre-calculated table of adjacent beacons])

NOTE1: Since beacons are precalculated during mapmaking, this can be a problem with a map that "changes itself" (think of a combat terrain that can be modified by spells -> energy field!!!)