Pathing (Fear pathing, possible tool) discussion.

[eq4me]

Originally Posted by Derision

I had originally thought about using OpenEQ to visualise the paths generated by Apathing and look at
the fear pathing stuff, however as Apathing uses the existing grids/waypoints to generate it's paths,
I figured we really needed to fix all the waypoints before moving on to looking at fear paths, so that
Apathing is working from known 'good' data.

Regarding fear pathing I am pondering with the following idea for month but didn't even have time to look at the existing code.

Suppose we have some sort of fear path that must be visible from every part of the map. For every mob in the zone we can now calculate an straight path to the nearest visible point of this fear path. From there the mob will stay on the fear 'path' and moves further away from his original spawn point.
Of course you can't just use a path but more of an area or you would end up with huge amounts of waypoints for wide open zones, but this method would be rather light on CPU cycles and you can even use this pathing to let an Mob find back to his original path or spawnpoint.
Generating such an fear path/area might not be trivial. Maybe it would be better to have a simple tool that gives an rough template which can be refined by human intervention.

[Angelox]

Moved these posts to a new thread, so everyone will know it's about all pathing problems now.

[fathernitwit]

Originally Posted by eq4me

Suppose we have some sort of fear path that must be visible from every part of the map. For every mob in the zone we can now calculate an straight path to the nearest visible point of this fear path. From there the mob will stay on the fear 'path' and moves further away from his original spawn point.

This is exactly how fear pathing is implemented already. It is taken one step further in that once you get on the pre-calculated grid, you need to know where to go next. I organized everything into a giant tree with no loops (minimal spanning tree of all path edges), theoretically with the trunk of the tree being somewhere in the center of the map (but it could be anywhere). When a mob first hits the fear path, they will path up to the root of the tree, and then they will path down the longest path from there. back and forth. We may need to adjust this algorithm once its actually in use.

Originally Posted by eq4me

Of course you can't just use a path but more of an area or you would end up with huge amounts of waypoints for wide open zones, but this method would be rather light on CPU cycles and you can even use this pathing to let an Mob find back to his original path or spawnpoint.
Generating such an fear path/area might not be trivial. Maybe it would be better to have a simple tool that gives an rough template which can be refined by human intervention.

We will end up with huge amounts of waypoints, and its not a big deal since it is one instance per zone. But you hit on the real challenge, building the grids in the first place is the hard part.

[narcberry]

Originally Posted by fathernitwit

But you hit on the real challenge, building the grids in the first place is the hard part.

Isn't Derision getting that information from the map files? Or (Derision) are you just showing how you can manually build paths?

[Derision]

Originally Posted by narcberry

Isn't Derision getting that information from the map files? Or (Derision) are you just showing how you can manually build paths?

To clarify,

The tool I am working on right now is to enable the existing waypoints on grids that are used by roaming mobs to be corrected such that mobs don't attempt
to path under the world, through the air or through walls. You are correct, this is a manual process, although I hope to put enough features in the tool to make
this as painless a process as possible. My BestZ fix just tried to hide a part of this problem. The aim of this tool is to be able to fix the problem at source (in the database).

There is an existing tool that FNW wrote, Apathing, which takes these roaming grids and other information and interconnects them into one large grid, the idea being that this can be used for fear pathing and other general pathing problems (i.e. you aggro a mob, how does it get to you other than running straight at you).

The purpose of my tool is enable the grids used for roaming to be 'fixed' so that Apathing can use these to create a good interconnected grid that will hopefully work well for fear and any other uses it could be put to.

Once this tool is done, it is my intention to create another (or maybe an extension of the same one) to visualise and tweak the Apathing generated grid for fear pathing. I really only need one zone with fixed roaming grids before I can move on to that.

There is already some code in the emulator to use the path files that Apathing creates, although it has some issues, maybe due to bad waypoint info, maybe some bugs, probably a combination of the two. Search for #ifdef FEAR_PATHING in the zone source.

[narcberry]

Wow much thanks. That answers a lot of the questions I've been having.

[Derision]

I decided to revisit a generic pathing solution after I saw the devs over at EQClassic had something working.

Previously I had looked at solutions that didn't require placing manual waypoints, but gave up on that a few months ago.

I have been working on a solution that requires manually placing 'Pathing Nodes', then an automated routine
pre-calculates the connectivity between these nodes, based on LOS and 'Passable Terrain'. The ideal place for
putting nodes is at 'crossroads' between passages, corners, etc.

I instrumented my modified version of OpenEQ to place the nodes and calculate the connections.

This overhead shot shows the path between two abritrary points in SolB. Basically the algorithm looks
for the nearest pathing node which has LOS to the start point, the nearest pathing node which has LOS
to the end point, and then finds a route between the two pathing nodes
via the manually placed pathing nodes (if one exists).



The little red dots connected by red lines are the pathing nodes and interconnections. The Green line
is the path from the start point to the the nearest pathing node. The thick yellow line is the path between
nodes to the final pathing node, and the blue line is the route from the final path node to the final destination.

To be clear, I manually placed the pathing nodes (red dots), but the route was calculated automatically.

This is early days, and I have only had the path finding working in the OpenEQ based tool. Putting it into the game
won't be a problem. Whether it is efficient enough to handle pathing for a complete zone on a populated server
remains to be seen.

[trevius]

Wow, Derison! That looks and sounds really cool! The current way of laying out grids manually isn't way too bad, but anything to help make that easier and more automated would be awesome!

[YeahlightEQC]

Originally Posted by Derision

I decided to revisit a generic pathing solution after I saw the devs over at EQClassic had something working.

I cannot imagine anything outperforming preprocessed A* pathing: www.eqcprices.com/SebPull.avi (requires XViD codec). It is definitely the way to go and is not that costly if you design it properly (an extra 5MB per zone to store all the pathing data).