I'm working on an open-source bots addition/modification for the FPS game Return to Castle Wolfenstein (forums at ubersoldat.3.forumer.com). The bots use waypoints for their primary navigation, and I've implemented A* as a pathfinding mechanism along these waypoints/paths. As a design issue, though, I would prefer that the bots not always take the shortest waypoint-path to reach their destination (ie, there are usually multiple possible paths between any two given waypoints, but A* will always find the shortest). I have been playing with the pathfinding to try to create more varied paths, but I would welcome any suggestions about ways to possibly implement this. Some of my ideas so far: -Tweak the A* heuristic by a random amount each time a new path must be calculated (I realize this can lead to no path being found) -Only let the A* algorithm run for a specific amount of time and then stop it, *before* it has found a full path, and just returning the best path it has created so far (with how the waypoints are placed, this would likely still be on a valid path to the goal) -Pathfind randomly (at least not A*) from the goal a certain distance in any direction (still along waypoint paths), and then try to construct an A* path to that waypoint (and then on to the goal) And a perhaps less realistic option - use a genetic algorithm to evolve a path to the goal, but only allow it to run for a specified, relatively small number of generations. I realize genetic algorithms aren't generally considered great for real-time pathing with modern computers, but even only allowing the the algorithm to run for a few hundred generations (which is fast enough to be unnoticed) still generates at least a good start to a valid path, if not the whole path. And given the random starting state of the population, this virtually guarantees varied paths. I'm in the process of testing this now (a big thanks to fups for his excellent book), and so far it seems to work better than I had expected. The main issue I have is determining a valid crossover operator for order-dependent pathing. If anyone has any ideas or suggestions about these or any other methods to create varying paths, I would really appreciate your help :)

Generate the shortest path, remove a random waypoint from it (or link from one waypoint to another, as long as it's part of this path) and generate a new path around it. repeat as needed.

Quote:Original post by TeamWhore
-Tweak the A* heuristic by a random amount each time a new path must be calculated (I realize this can lead to no path being found)

I'm not sure that would allow the algorithm to keep working. You could slightly randomise the cost for entering each waypoint. In fact if you did this with some sort of predictable noise-generator that deterministically modified the original cost of each waypoint by 50-150% (for example), it would work well.

Quote:-Only let the A* algorithm run for a specific amount of time and then stop it, *before* it has found a full path, and just returning the best path it has created so far (with how the waypoints are placed, this would likely still be on a valid path to the goal)

I don't know how random this is likely to look though. Maybe try it, but it wouldn't be the solution I'd attempt.

Quote:-Pathfind randomly (at least not A*) from the goal a certain distance in any direction (still along waypoint paths), and then try to construct an A* path to that waypoint (and then on to the goal)

That'll give you a path that looks wobbly along the first half and then direct along the second half; probably not good enough.

Apart from the use of procedural noise I mentioned above, I concur with C-Junkie in that fuzzifying the best path is another useful approach.

Create a semi-random cost map over your area, which puts false costs on to transitions between locations. Ideally make it lie about simple routines and truthful about more obscure ones. For example, make the main paths in your dungeon higher cost than the back alleys...

Then just use unmodified A* to find the "best" path using these false costs, and it will do what you want?

Mark

If you just need a random choice in situations when there are multiple "good enough" alternative paths from A to B, it suffices to:
- detect (or manually mark) the bottleneck waypoint identifying each unique path from A to B (for example, for a room with multiple doors, you mark the waypoints representing each of the doors as 'bottleneck').
- before each A* search, add a random visiting cost component for each of the bottleneck nodes

This way, the you'll get logical variations in the paths instead of really random variations (such as zigzagging through a room where a straight line path would be the only sensible option).

Unreal Tournament implements something along these lines:
http://wiki.beyondunreal.com/wiki/AlternatePath
although it seems in UT some paths are forced to visit a bottlenekc waypoint / alternatepath node, which may cause troubles.

William

Hi,

Why not use some other algorithm? you could try a modified depth first search and then take the first path to the goal.

Hi everyone, thanks for all the help so far. I'll work on adding these ideas in, and hopefully I can get it to work.

ray_intellect - part of what I'm asking for is ideas for other algorithms to use; I just mention A* a lot because that's what I have in place currently. I'm not committed to using it, it's just what I've thought about the most so far. I'm fairly new to pathfinding/AI programming, so I figure more experienced people will have better and more plausible ideas that what I would come up with. There is also *so* much information about pathfinding available, that I decided it would be better to ask for help, rather than the guess-and-pray method (which I use too much to be good) :)