Better Breadcrumb Pathing

[amadmonk]

"Breadcrumb" pathing is waypoint pathing where the waypoints are laid down by watching another unit move. At some interval, your pathing library records a "breadcrumb" of the unit's position, and makes that the next waypoint in the chain. Then your bot follows the breadcrumbs (get it?) to get to the unit you're following.

It's far less sophisticated than something like, say, a nav mesh, but it's FAR easier to code and lighter weight (and, IMO, error prone).

One challenge is how to decide when to lay down a new breadcrumb. Working on my bot this weekend, I had a realization that may seem obvious to some, but it helped me greatly optimize my breadcrumbs algorithm: you only need to deposit a new crumb if the facing of the unit you're following has changed from the previous crumb's facing.

In other words, if the unit I'm following goes from point A to point B and never changes facing, that implies that you B is "reachable" from A by traveling in a straight line. If B is reachable from A by traveling in a straight line, then you don't need to record any of the intermediate points in between A and B. To get from A to B, you simply go to A, face B, and start walking.

One advantage of this -- of using facing changes to trigger breadcrumb deposition (creating new crumbs) -- is that you don't have to do time or distance calculations between crumbs; just check for the combination of (Unit is moving) and (Unit facing changed). If those two conditions happened, drop a crumb. These are simple conditionals -- no sqrt involved! -- so the processing cost of breadcrumb deposition is small.

Another advantage is that turn radiusing (making sure you cut turns at exactly the same rate/angle that the unit you're following does, which can be very important in complex terrain) just happens automatically; you only need to deposit crumbs if the unit's heading changes, so you should track the turn characteristics exactly. Using a distance- or interval-based deposition algorithm often has problems with tightly-radiused turns (or decreasing-radius turns, etc.).

Just figured I'd share that tidbit for anyone who can make use of it and isn't already doing it

[mindwalkr]

I think the only time this will fail is when the toon running that profile has a slower rate-of-turn. In which case, it will swing wide of the next crumb before finishing the previous turn (assuming this is done while still moving).

I believe moving faster than the profile was recorded should have the same effect.

Easy test: record a profile with a 100% mount and turn-while-moving ... see if you can follow the turn with a 280% or 310% mount.

[amadmonk]

Yeah, true, I assume similar turn characteristics between follower and followed (since I almost exclusively use this for bots following each other).

Of course, my turns are always instant, so this probably doesn't affect me. But if someone was running this algorithm using e.g. keyboard or mouse turning, that could be an issue. Good point!

[Nesox]

make sure you take jumps into account aswell other than that it seems fine

[amadmonk]

make sure you take jumps into account aswell other than that it seems fine

You mean actual physical jumps... pressed the space bar? Good point. I'll figure out how to track that (isn't that in the unit movement flags?) and mimic it.

I was thinking about teleports or things like the Blink spell, also. I don't think that there's a way that breadcrumb pathing can deal with that, is there... for that you need a real pather.

Edit: I thought about this a little bit, and realized that if I mark up my breadcrumbs with the movement flags at each position (which includes things like jumping/flying/swimming/etc.), and then make changes in those flags another conditional (or maybe just changes in parts of the flags: jump status/fly-swim status/etc.), and update my SetFacing method to do pitch changes in addition to yaw changes, my breadcrumbs pather should work for free in 3D as well as 2D. In fact, if I look for changes in IsFlying and mimic those in the following bot, I should be able to get free pathing in places like Oculus, as well.

[MaiN]

Can you tell me when a square root is required for any other way of breadcrumb laying?

[Kryso]

Can you tell me when a square root is required for any other way of breadcrumb laying?

distance?

The message you have entered is too short. Please lengthen your message to at least 10 characters.

[amadmonk]

distance?

The message you have entered is too short. Please lengthen your message to at least 10 characters.

^This. "Distance from last crumb to next crumb."

Edit: I guess I could do Manhattan distance, but my solution is more elegant, IMO

[MaiN]

^This. "Distance from last crumb to next crumb."

Edit: I guess I could do Manhattan distance, but my solution is more elegant, IMO

Uhmm.. No?

if (Vector3.DistanceSqr(v1, v2) <= 5*5)

99% of times you use distance you don't have to use the square root.

[amadmonk]

Uhmm.. No?

Ummm... yes? My code is more elegant because it doesn't rely upon artificial metrics like distance or time. It matches breadcrumb density to "event density" (where "event" means "something interesting occurring in the movement profile of the unit I'm following") exactly, whereas a distance based solution can have issues on tight turns, like I mentioned. Yes, you can dial back the breadcrumb spacing to the point where almost all turns are handled, but then you're just brute-forcing the problem (which is the anti-definition of "elegant" )

if (Vector3.DistanceSqr(v1, v2) <= 5*5)

99% of times you use distance you don't have to use the square root.

Yes, this is Manhattan distance ("3 blocks over, 2 blocks up == 5 blocks"). It's an adequate approximation for sqrt distance if all you're doing is comparing distances, but it can fall apart in some degenerate cases in 2D (and gets even worse in 3D). It's true that this would remove the only sqrt from the distance-based crumb dropping algorithm, but then you're still not much more efficient (you have one float comparison for distance versus one float comparison for heading, plus one flags comparison for my method, which is admittedly less efficient, but XOR-ing some flags is hardly something that's going to eat up your CPU). And still, my solution better matches the followed unit's profile.

[MaiN]

Ummm... yes? My code is more elegant because it doesn't rely upon artificial metrics like distance or time. It matches breadcrumb density to "event density" (where "event" means "something interesting occurring in the movement profile of the unit I'm following") exactly, whereas a distance based solution can have issues on tight turns, like I mentioned. Yes, you can dial back the breadcrumb spacing to the point where almost all turns are handled, but then you're just brute-forcing the problem (which is the anti-definition of "elegant" )



Yes, this is Manhattan distance ("3 blocks over, 2 blocks up == 5 blocks"). It's an adequate approximation for sqrt distance if all you're doing is comparing distances, but it can fall apart in some degenerate cases in 2D (and gets even worse in 3D). It's true that this would remove the only sqrt from the distance-based crumb dropping algorithm, but then you're still not much more efficient (you have one float comparison for distance versus one float comparison for heading, plus one flags comparison for my method, which is admittedly less efficient, but XOR-ing some flags is hardly something that's going to eat up your CPU). And still, my solution better matches the followed unit's profile.

Euclidean distance squared is NOT manhattan distance.
Manhattan distance is defined as |Dx| + |Dy| + |Dz|, while euclidean distance squared is defined as Dx^2 + Dy^2 + Dz^2.
All that still doesn't change that fact that there is no square root required. And it's not an approximation for distance comparing, it's just as accurate as calculating its square root when you only need to compare distance.

[amadmonk]

Oh you're correct, I missed the "Sqr" on the end of the function and thought it was a simple Manhattan distance check.

I think you're responding to the "no square roots" part of my post, and I'm responding to the "this way is more elegant" part, so we're talking past each other. So then we're both right -- there aren't any square roots required to get a reasonable comparable distance calculation, and using movement events for choosing when to deposit breadcrumbs is a more elegant solution to things like turn radiusing. Fair?

[MaiN]

Oh you're correct, I missed the "Sqr" on the end of the function and thought it was a simple Manhattan distance check.

I think you're responding to the "no square roots" part of my post, and I'm responding to the "this way is more elegant" part, so we're talking past each other. So then we're both right -- there aren't any square roots required to get a reasonable comparable distance calculation, and using movement events for choosing when to deposit breadcrumbs is a more elegant solution to things like turn radiusing. Fair?

Fair enough, your original post just made it seem like a square root was required for dropping a waypoint every X yards and that's incorrect. In any case I (would/do) use a navmesh! What's holding you back?

[Robske]

How does your system respond to targets who are using the mouse to move around?

From what I've gathered, moving like that causes a constant stream of MSG_MOVE_SET_FACING to leave the client. Assuming the server just spreads the packets around, wouldn't that cause a rather... saturated breadcrumb path?

(I may have misinterpreted your usage goals with this breadcrumb system - are you the sole creator of the paths or will you let all units participate?)

[amadmonk]

How does your system respond to targets who are using the mouse to move around?

From what I've gathered, moving like that causes a constant stream of MSG_MOVE_SET_FACING to leave the client. Assuming the server just spreads the packets around, wouldn't that cause a rather... saturated breadcrumb path?

(I may have misinterpreted your usage goals with this breadcrumb system - are you the sole creator of the paths or will you let all units participate?)

Well, I am the sole user, but I may use the system to set initial waypoints, and yes, I may use mouse move during that phase. I guess to handle the micro-variations you mention (assuming that, moving in a straight line, you would have lots of tiny, insignificant facing changes), I'd just use the "wiggle-room" version I originally mentioned. Instead of explicitly testing if facing1 == facing2, I'd check if abs(facing1 - facing2) > someSmallNumber.

And MaiN, I'd love to use a nav mesh but I just haven't had the time or technical knowledge to set one up yet. That may be changing soon...