Two choices of Navigation

[wanyancan]

It appeared that several threads before this discussed about the nav mesh navigation scheme. From what I understand, it looks more like the game AI developer's way of thinking: build the path from the known knowledge of the whole space. The advantage is accurate and large scale. However, it takes extra efforts to calculate them especially when the target is extraordinary far away, and need to calculate the meshes from the scene model file.

There's another way of thinking the problem, from a robot designer's perspective(we're building the 'bot', right? ). Assume that what we can get is only a camera which can detect the obstacle ahead(use TraceLine or other detection method such as the changing of position over pulses). From this view, the navigation becomes a local navigation problem. And there's already a simple and elegant way of doing it (30 years ago) which adapts the concept of potential field from static electromagnetic filed solution. Assume that the target is an negative charge, and obstacle is a positive charge. Then the E-field vector's direction will always points from the positive charge to the negative. And the direction of path can be directly calculated from the charge distributions (here, the target and obstacles). More about this concept can be found here (Visual navigation and obstacle avoidance using a steering potential function, google it). This method I think is more proper for out-process bot developer.

[pendra]

The approach you describe is common for 2D navigation with large, simple obstacles. Wow is 3D, so even if you're only walking you have to take obstacle height and contours of terrain into account. How do you tell the difference between a hill and a wall without casting a bunch of rays at it? Look at ppather for an example of somebody trying to do that.

The whole point of the nav mesh is to avoid having to cast thousands of rays every time you move in order to figure out where is safe to go. I would be quite surprised if you beat HPA* on a graph for path finding speed by doing ray casting.

The local nav approaches involving line of sight/obstacle avoidance work much better when you can provide them with quasi-2D obstacle geometry, imo, so to use a potential field approach you probably want to compute a simplified walkable space and then perform the local nav within that space.

[wanyancan]

I forgot to mention that actually we can introduce randomization and dynamically building the list of obstacles. Every time you move (fly as well, therefore I don't think this method is for 2D nav only), you can detect the none-changing of position (without casting a bunch of rays) no matter of whether hitting a wall or a hill. Adding the position in front of you as an obstacle and adding another randomized temporary point as new target, then re-calculate the direction based on the new information. No matter how it may seemingly be slow and lagging, the bot can actually get the destination without too much tries in my testing! I found that this randomization is amazingly useful when doing other thing such as clicking on the screen to loot target like the fishing blob as well!

[Apoc]

Here's the major drawback to an insect based pathing system.

Caves.

Yup.

[wanyancan]

Yep, true.
It's a local navigation, so works inside cave...
Actually there was once my 80 dru was farming in a cave at The Storm Peaks, and somehow died(most likely by PvP) and can't get back with the ghost mount...

[darrensmith0125]

How easy is it to test a system which uses a traceline type implementation, Is there any complication creating a local world to test against?

With a navmesh you can test outside of the game using the real data until you are happy it is working. If you find a scenario in game that is an issue it can be set up and tested very quickly as you know the coords.

[amadmonk]

Remember that potential fields are only useful for *local* navigation, not generalized pathfinding.

Potential fields (which I've been investigating for my bots) really solve a different problem than navmeshes do.

Navmeshes actually have issues at the small scale, just like PF's do at the large scale.

[nitrogrlie]

I'll add that in addition to obstacles you would also have to ray-cast for holes in the world (aka edges of islands) otherwise your bot might walk of the edge thinking it can simply walk from one island edge to another because there is no obstacles in the way forgetting that there is no ground in between either. :P

[amadmonk]

Yeah, when I was doing raycasting for local pathing, I was constantly raycasting both forwards and down. It wasn't pretty, but it sorta worked. Actually it wasn't even pathfinding, it was just an "am I blocked?" function.

Pathfinding implies that the algorithm can actually FIND a better path; afaik only things like navmeshes and waypoints can do that.

[vulcanaoc]

I tinkered with a TraceLine navigation system for a few days, and was met with limited success and a plethora of problems.

My initial idea took two points as input, a start point, and an endpoint, and potentially generated a list of points that connected the two. The algorithm was recursive, and used a series of TraceLines between a 'last good point' and the endpoint. If an intersection was found, I used TraceLine raycasting to check for perpendicular vantage points that produced a 'move around object' effect. Obviously, many flaws were embedded in the concept, and the algorithm would fail or just take too long to compute if a complex set of obstacles and terrain existed between the start and end points. Another issue that was particularly hard to eliminate was ensuring that the point list didn't contain points that were unreachable for a character. For example, sometimes a point would be ON a large tree that was even slightly concave, whereas it should have been on the ground below the tree.

The technique was plausible for navigating into line of sight of nearby objects, but its moderately high potential to fail limited its usefulness even in this situation.

If the source code I have isn't too mangled, I'm willing to share it with anyone interested.