Generic Questions on CTM / Breadcrumb Waypoint System

[draco1219]

Hello everyone,

I just had a few questions regarding CTM that I was hoping someone could shed some light on. Right now, my application is fully in process and I am calling the ClickToMove function directly from my EndScene hook and everything is working perfectly.

I also am using a breadcrumb navigation system developed around Apoc's great article: http://www.mmowned.com/forums/world-...b-pathing.html

As I said before everything is working correctly and I can traverse a navigation waypoint system outlined above.

Here are my questions:

1) I am thinking about adding in a rudimentary unsticking system into my movement/navigation. I am trying to start simple and came up with a simple system which identifies when I've stopped moving and haven't reached my target location. It will then calculate a point which is directly 5-10 yards away to my left or right and will move there and then attempt to resume movement to my intended location.

Questions:

1a) When I calculate the new point to try to use to navigate around the object, I am simply taking my currently location and offsetting the X or Y position. At this point I have no way of knowing (in its current state) what the Z location is of that new location. At this time, should I be calling ClickToMove passing it my new Location struct with a blank Z axis or ...?

1b) It seems that when I pass a location (X,Y,Z struct) to the CTM function with the Z value set to 0.0f it works fine. If I'm not "flying" and just staying on the ground for movement, is there any benefits or drawbacks of providing or not providing a Z value? If I incorrectly set a Z value for a position, can this potential send up some "red flags" that the CTM call did not come from the client/user actually clicking?

2) When people use breadcrumb/CTM navigation, do they normally add randomization (maybe adding a yard or 2 to the X/Y locations) so that it's not so obvious that a player is ALWAYS clicking in the same locations? I'm probably reading into this too much, but I was just wondering what other people do.


Thanks again for your responses, I very much appreciate it.

[reggggg]

Hello everyone,
1a) When I calculate the new point to try to use to navigate around the object, I am simply taking my currently location and offsetting the X or Y position. At this point I have no way of knowing (in its current state) what the Z location is of that new location. At this time, should I be calling ClickToMove passing it my new Location struct with a blank Z axis or ...?

You need the Z coordinate or else it will try to move towards the X,Y,0. Single X,Y pairs can have multiple Z coordinates (imagine a multi-story building). This is a total headache to solve without navigation meshes or a tonne of workarounds. Simply taking the highest or the closest Z coordinate to your own will not be reliable. To find Z coordinates you can raycast directly downwards from, for example, the sky, and see where it collides with terrain.

1b) It seems that when I pass a location (X,Y,Z struct) to the CTM function with the Z value set to 0.0f it works fine. If I'm not "flying" and just staying on the ground for movement, is there any benefits or drawbacks of providing or not providing a Z value? If I incorrectly set a Z value for a position, can this potential send up some "red flags" that the CTM call did not come from the client/user actually clicking?

If it works, it is a fluke. My guess is that it succeeds to move towards the right place because you are on the ground and cannot fly up or down anyway. That said, if you try swimming it should screw up pretty badly. As for detection through CTMing, bots like HonorBuddy use CTM in a way that is impossible for normal users to do (like picking coordinates midair), and they haven't been caught for this yet.

2) When people use breadcrumb/CTM navigation, do they normally add randomization (maybe adding a yard or 2 to the X/Y locations) so that it's not so obvious that a player is ALWAYS clicking in the same locations? I'm probably reading into this too much, but I was just wondering what other people do.

You can, but you have to be wary of this as sometimes you need pretty precise navigation in some places.

[draco1219]

You need the Z coordinate or else it will try to move towards the X,Y,0. Single X,Y pairs can have multiple Z coordinates (imagine a multi-story building). This is a total headache to solve without navigation meshes or a tonne of workarounds. Simply taking the highest or the closest Z coordinate to your own will not be reliable. To find Z coordinates you can raycast directly downwards from, for example, the sky, and see where it collides with terrain.


If it works, it is a fluke. My guess is that it succeeds to move towards the right place because you are on the ground and cannot fly up or down anyway. That said, if you try swimming it should screw up pretty badly. As for detection through CTMing, bots like HonorBuddy use CTM in a way that is impossible for normal users to do (like picking coordinates midair), and they haven't been caught for this yet.

You can, but you have to be wary of this as sometimes you need pretty precise navigation in some places.

Hmm, I wonder what other people do for their "unsticking" logic who use CTM. Maybe it's better to Set the movement flags and strafe left/right and then try the location again instead of computing a new location to unstick?

So is CTM still the best method for breadcrumb style waypoint system? Or is it better to use another method like setting the movement bits and doing timed movements?

[JuJuBoSc]

CTM is the best method if you don't want to care about calculation that's all

[draco1219]

CTM is the best method if you don't want to care about calculation that's all

How about situations where you need to get unstuck or get in range of a mob? It seems good for when you have pre-defined locations, but what about creating locations on the fly? For example, I know a mob is 50yds away and I want to move close to 30 yds away to pull, with the Z situation I described above, how can you create a location on the fly and not have the Z location off?

Thanks again for your response!

[reggggg]

in the absence of a navigation mesh, and with an obstacle between yourself and the destination, i have successfully used the following solution

1) Generate many points 90 degrees to my front (both pitch and yaw), with 5 degree or so intervals, and then at a range of distances (I think I did from 5 to 200 with a smallish interval).
2) Test if any of these have line of sight to your wanted destination.
3) Of the ones that do have line of sight, find the one that will result in the shortest distance needed to move and use it as an intermediary point to your destination.

Obviously, you can extend this past one step, maybe doing a depth-first search, but it is an expensive operation to do stuff like this dynamically (with TraceLine). That is why people use Recast and Detour to make the calculations less complex (note it needs a few changes to it for it to support true 3D navigation instead of 2.5D)

[draco1219]

in the absence of a navigation mesh, and with an obstacle between yourself and the destination, i have successfully used the following solution

1) Generate many points 90 degrees to my front (both pitch and yaw), with 5 degree or so intervals, and then at a range of distances (I think I did from 5 to 200 with a smallish interval).
2) Test if any of these have line of sight to your wanted destination.
3) Of the ones that do have line of sight, find the one that will result in the shortest distance needed to move and use it as an intermediary point to your destination.

Obviously, you can extend this past one step, maybe doing a depth-first search, but it is an expensive operation to do stuff like this dynamically (with TraceLine). That is why people use Recast and Detour to make the calculations less complex (note it needs a few changes to it for it to support true 3D navigation instead of 2.5D)

Ahh ok I see. If I can do the calculations for facing/distances, is there any problem with using SetMovementFlag function to do movement over the CTM?

[draco1219]

I decided to stick with using CTM for movement (to move between breadcrumbs and to mobs/locations). I'd like to add additional stuck logic using movement other than CTM and I had a few questions.

I saw that there are LUA functions that can be called for movement but they are all protected. My question is, I currently use CastSpellByName LUA for casting spells and was thinking about using the movement ones as well (all protected). Are there any protected LUA functions which are NOT safe to call and are being monitored at this time? My gut feeling is saying no, since if there was any function it would probably be the CastSpell functions which are not monitored.

Thanks again for the help

[namreeb]

My understanding is that calling protected Lua functions does carry some amount of risk, but no one function more than the other. If this is true, and you're already calling some, then calling more shouldn't be any more risky. Might be wrong, though.

[caytchen]

Calling LUA stuff is pretty much risk-free. The only thing monitored by Warden is the protected functions check, but you don't need to patch that anyway.

[amadmonk]

I should mention that if you wait too long between depositing crumbs, you can end up with some REALLY degenerate cases if you have spaghetti paths, because most people simply do breadcrumb pathing by steering towards the "next" endpoint in the path. The "correct" way to do path-following steering behavior is to run a closest-point-on-path algorithm coupled with a chase-the-rabbit steering routine (cf Artificial Intelligence for Games, ch. 4). But this is far more complicated than the simple "point to the next nearest point" routine that most people use, so just be aware that you can't really "cut corners" on the path-seeking behavior unless you're prepared to debug some horrifically bad edge conditions.

[draco1219]

I should mention that if you wait too long between depositing crumbs, you can end up with some REALLY degenerate cases if you have spaghetti paths, because most people simply do breadcrumb pathing by steering towards the "next" endpoint in the path. The "correct" way to do path-following steering behavior is to run a closest-point-on-path algorithm coupled with a chase-the-rabbit steering routine (cf Artificial Intelligence for Games, ch. 4). But this is far more complicated than the simple "point to the next nearest point" routine that most people use, so just be aware that you can't really "cut corners" on the path-seeking behavior unless you're prepared to debug some horrifically bad edge conditions.

amadmonk,

Thanks for taking the time to post this. To keep it simple, I am just dropping a new breadcrumb each time the facing/heading changes or if 20 yards have been met since the last waypoint. I can't simply do facing and run to the next since I do CTM and it's possible if you run into a straight line that the next waypoint is out of range.

So far it works very well and I can traverse the entire path no problem. Problems arise when my bot is done killing the mobs at a waypoint and I need to return to the path and I need to return to the "closest" waypoint. Sometimes it's not in LOS and I get stuck. I put some rudimentary unsticking logic by using LUA to strafe left or right then try and resume. I guess it works OK, but I'm not terribly happy with it. I suppose the end result would be to use a navmesh completely, but I'm not 100% sure on how to do that yet.

Thanks again for all the responses guys!

[amadmonk]

amadmonk,

Thanks for taking the time to post this. To keep it simple, I am just dropping a new breadcrumb each time the facing/heading changes or if 20 yards have been met since the last waypoint. I can't simply do facing and run to the next since I do CTM and it's possible if you run into a straight line that the next waypoint is out of range.

So far it works very well and I can traverse the entire path no problem. Problems arise when my bot is done killing the mobs at a waypoint and I need to return to the path and I need to return to the "closest" waypoint. Sometimes it's not in LOS and I get stuck. I put some rudimentary unsticking logic by using LUA to strafe left or right then try and resume. I guess it works OK, but I'm not terribly happy with it. I suppose the end result would be to use a navmesh completely, but I'm not 100% sure on how to do that yet.

Thanks again for all the responses guys!

You're in the same boat I am. I understand HOW to add a navmesh, but it's a huge amount of extra code and work, and I've been putting it off, to be honest. However, cases like yours -- cases where the bot needs to know "can I get from point A to point B" -- are exactly the kinds of cases that a navmesh (or some overall pathfinding solution) is designed for, so it's getting harder and harder for me to put it off. I have a lot of ugly hacks for dealing with things like path to/from a mob to loot, path to/from a mob to melee, and so on -- and almost all of those would go away with a pathfinding lib.

Eventually, I'll give in and integrate namreeb's (or someone's) pather into my bot. Until then, I'm milking the breadcrumbs system for as much as it's worth.

BTW, using the closest line segment (instead of closest breadcrumb) calculation lets you avoid some of those cases where the nearest crumb is out of sight/range; as long as the nearest [I]path segment[I] is in range, you're good. You'll have to do a bit of vector math to do the calculation, but it's worth the effort.

[ostapus]

personally - by implementing navigation via recast/detour i got off huge headache w/ old nav system with the problems exactly you descrbing above.