Alternate paths to a target?

[Maleficus]

I'm working on the tricky problem of getting the bots to try different routes to a target. There can be multiple routes (anywhere from 2, to 10 or more on some maps). The problem: I use A* pathfinding, which always finds the shortest route, but not necessarily the most INTERESTING route. This has been leading to the bots being VERY predictable: I know which way they'll attack, and which way they'll retreat from.

Looking for some ideas or inspiration on how to get Frtiz to mix it up a little. I'm working on some ideas, but I'm open to more!

[Pierre-Marie Baty]

well, A* returns the shortest route, yes... UNLESS you weighten the waypoints

By giving them a cost and taking that in account during pathfinding, you can make dangerous routes appear longer to the pathfinder while safer routes will appear shorter. See what I mean ? Currently your pathfinder only sums up the distances between waypoints I suppose. Well just make it sum up the kills/death ratio per team for each waypoint also. Each time a player is killed, see what are the nearest waypoints and add to these waypoints' danger values.

Look at sPlOrYgOn's POD-bot for Counter-Strike: each time you frag the bots on a particular route, the next round they take others and manage to outflank you pretty well.

[stefanhendriks]

agreed. Though its tougher then you think to get a good heuristic. Sometimes you overweight things. Sometimes you don't have any effect.

I tried various stuff with this. But all i can say is, be a very good math guru or just play with the values I prefer the latter, its just more fun.

[@$3.1415rin]

math guru's normally cannot tell you what to do in such a situation, they often only can tell you if your solution is correct, optimal, or if a solution exists at all

in JoeBOT XP, i havn't any randomization yet, because the task system for the squads isnt ready yet. a squad just choses a random location and then they go there. the only cost penalties are at the moment connections where bots got previously stuck and connection which are already run along by teammates to avoid running in one line like ducks. random doesnt look that stupid

[Pierre-Marie Baty]

also, why do you want ALL the squad members move at the same time ?
When I'll put squad code in mine, I'll let only one squad member advance at a time, while all the others will be covering him.
Oh and also, if you want bots not to walk all in line like little ducks following their momma, you get this for free when you have one individual navmesh for each bot

[@$3.1415rin]

at round start it's often nice to have the squad move at once. and for real room cleaning like behaviours it's too early ... not yet enough infrastructure, as you might have read the the "misc bot stuff" thread

individual mavmesh ... and you tell me that's for free ? ok, when ignoring mem usage and cache coverage of you memory you are working on, that might be right ...

[Maleficus]

The problem is: in wolf, the total number of paths a bot may want to use is not static, like in CS. In Wolf, where you spawn, and where your goal is may change several times over the course of one match (your spawn moves back/forward, the goal moves to a diff location, etc). So, you have the problem of some nodes (that may no longer be "valid") being taken into account if you just blindly start playing with weights.

An example of this, which happens with Wolfbot, is bots blowing the walls on BEACH, but instead of just running straight for the docs, wander around the beach some (which is a worthless waste that no human would do), because in the bots mind - the nodes on the beach are just as valid as they were before the walls were blown.

So how do you know what path will take you to the target REALISTICALLY: thats the problem I'm grappling with. Sure, you might be random, but in a stupid way that no human would ever do. Thats one nice thing about CS: your spawn area and goal areas are static, so you can play with nodes along the path, and get pretty good results.

I think I may have an alternate system that works better for Wolf in the works, I'll have to see.

[Pierre-Marie Baty]

Originally Posted by Maleficus

The problem is: in wolf, the total number of paths a bot may want to use is not static, like in CS. In Wolf, where you spawn, and where your goal is may change several times over the course of one match (your spawn moves back/forward, the goal moves to a diff location, etc). So, you have the problem of some nodes (that may no longer be "valid") being taken into account if you just blindly start playing with weights.

I don't see how it can be a problem ; look, in Day of Defeat for example, or in Team Fortress Classic on maps like Warpath, the spawn points advance on the map along with the front line. A* can handle that just fine. And in CS, same thing, when a terrorist has lost the bomb it can be at any location through the map, and the other bots can still go and pick it up without problems. Same in Opposing Force CTF when a player has lost the flag.

All you need to do is not to flag *waypoints* as goals (like in POD-bot for example), but the goal entities themselves. Then, a little helper function will tell you in realtime what is the closest waypoint to the entity you're interested in. After that, just use this particular waypoint and your bot's origin as the start and goal coordinates.

The remaining problem is the reachability of two nodes ; like, for example, a door that opens only under certain circumstances. You need to flag this in the connectivity info between your waypoints. A good idea would be also to store a pointer to the activating entity, or similar info for a bot to work out easily what it has to do to reach the next waypoint (push a button, wait for an event, etc...). Of course, these actions must be included in the final cost computation. This way, you get smart bots that open doors and work out obstacles only when 1°) it's possible and 2°) there's an advantage for them.

[Brainz]

Advancing spawns in DoD? Yeah, its possible, but I've yet to see a map that uses it, and I was a huge fan of custom maps. Even ran a custom server at one point. but never seen a map with advancing spawns. You thinking of BF1942 by any chance?