Navigation by Longjumping

[Ghoul]

Hm, this board doesn't seem as active as it was at botman's forums. Or maybe it's because I just didn't check it as often then. Anyway, this isn't so much a problem as it is a question of opinion.

My bot, Grave Bot, is capable of using the longjump. Currently bots will use it in combat to do quick jumps behind the enemy, making them very difficult to keep track of. However, I also have been tinkering with the bots using the longjump for quicker navigation around levels.

The simplist method is: if distance to current waypoint < distance longjump jumps, do long jump. That however isn't very practical. I've found that with normal gravity (sv_gravity 800), a longjump will take a player about 540 units if they run, start a longjump, then take all hands off keyboard/mouse. That's a pretty far distance, especially when compared to the average distance between waypoints, which is maybe around 200 units. So, my above equation doesn't become useful if the distance between waypoints is 90% (estimate ) of the time less than 540.

Now, here comes my question, what kind of different method would you use? Planting out a seperate longjump waypoint "grid" seems uneconomical, and of course the simple distance check just doesn't cut it. Here's my thoughts: Starting at the current waypoint, loop forward through the waypoints required to get to the goal waypoint performing a few checks. The final waypoint chosen should be within line of sight for the bot, and not closer than 540 units. Example picture:



So, the purple blob, the bot, is at waypoint B. This bot has the longjump, so instead of just using the normal system and getting C as its next waypoint, it loops through C, then D, then E, etc. C through E are going to be too close, F is a candiate, but we don't know until we look farther, G is out of view. So, one waypoint back is F. The bot longjumps to F and then repeats the process.

So, sound like gold to you guys, or is this just dumb?

[sfx1999]

Why don't you try to make an equation in the form y = ax^2 + bx + c of 3 waypoints? It could work. Make sure you check for 0 divides and throw in straight line optimizations.

Please tell me you know how to do this, because it takes a while to explain.

[Ghoul]

This isn't for vertical checks, which is what I think you're talking about, otherwise I don't see how the quadratic equation applies. Am I missing something?

Oh, and does anybody have some resources about A* (well, I've found plenty on that actually), navmeshes, and automated generation of said navmeshes?

[botman]

You might want to have some concept of a radius around the waypoint to indicate how much area is clear. Waypoints that have a large radius of open space around them would be better candiates for a long jump direction than waypoints in narrow spaces.

You could start at the current point and do a recusive search outward (following the paths from each node to it's neighbors) and keep an average of how much "open space" each node had along with 2 or 3 of it's neighbors. This will give you a rough idea of how open or enclosed an area is and you can jump toward one of the more open areas.

botman

[Ghoul]

Hmm, yes that's true.

I've implemented my solution, and for the most part it seems to work well. One problem I've encountered thus far is clip brushes. Tracelines goes right through them, so the bot ends up thinking it can longjump to that point when it can't, and just longjumps against the wall.

I've also experienced some issues with gaps and pits. Normally a bot might just run off a ledge to drop onto a lower platform, passing over a pit between the two. This can be seen when trying to grab one of the longjump modules in Boot Camp (above the rocket launcher). However, with the current system the bot ends up locating a waypoint on the platform way before it's close to the edge, longjumps, and falls in the pit. The only way I can think to avoid this is to trace the distance of the longjump forward from the waypoint, then trace down to find ground level. If ground level is less than the ground level of the target longjump waypoint (with a 16 unit leeway or something), don't jump.

I also have to implement a parabola check so they don't leap into low ceilings, hehe.

I'll look into that radius suggestion, thanks botman.

[Pierre-Marie Baty]

Nope, save yourself a lot of pain.

Just use TraceHulls with head_hull instead of TraceLines.

TraceHulls are blocked by clip brushes and func_illusionaries, and they also have the size of a ducking player. They are perfect for testing a reachability from point A to point B, much better than firing a bunch of TraceLines to figure out whether there's room enough for a player to slip through.