Jump to content
  • Advertisement
Sign in to follow this  
TeamWhore

Sub-optimal pathing

This topic is 5086 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 :)

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Find the shortest path,
find all other paths longer then the shortest path and shorter then the shortest path * x

make x small

pick one randomly

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
I would add noise to the function responible for estimating the distance to the destination. Actually I'd multiply the noise, so that it gets more random the farther away it is.

Share this post


Link to post
Share on other sites
You could design a simple exploration function, that records the number of paths chosen and every mod Y number of paths you instead use chosen a random path of the possible paths.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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) :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!