Pathing (Fear pathing, possible tool) discussion.

[Derision]

My current experiment is to look into the feasibility of extending OpenEQ (written by Daeken_bb, gxti and maybe others) into a sort of 'Pathing Correction Tool'.

Here's a picture of what I have got working so far:

http://www.rama.demon.co.uk/PathingTool.jpg

All it does at the moment is load the map and grids for a particular zone, draw a pyramid at each waypoint on
a particular grid (patrol grids only at the moment) with lines connecting the waypoints in sequence.

You can 'fly' from one waypoint to the next by clicking a button. When you reach a waypoint, it will stop and rotate you to face
the next waypoint in the grid.

The Red and Blue pyramids in the screenshot are your current and next waypoints. There is a button which will
move your current waypoint to the BestZ location. The smaller green pyramids are just other waypoints on
this grid.

There is lots left to do, e.g. buttons to insert a new waypoint between the current and next, move the
current waypoint to where you are standing, apply BestZ to the entire grid in one go rather than one
waypoint at a time, save the grid back to the database, etc, etc.

My thinking is that using OpenEQ as a base like this, it is easier than using the real game client to visualise
exactly where and what the problems are, e.g. paths that attempt to go under the ground, through walls etc and fix them.

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.

[Wizzel]

Looks amazing.

[eq4me]

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]

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.


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.

[fathernitwit]

My thinking is that using OpenEQ as a base like this, it is easier than using the real game client to visualise
exactly where and what the problems are, e.g. paths that attempt to go under the ground, through walls etc and fix them.

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.

This is a very good idea. I had considered this, but gave up long before I got anything useful out of it. Your conclusion about having "good" paths as input is dead on. apathing relies completely on existing spawn and pathing data (since what else do we have?). garbage in, garbage out.

One thing you might want to throw in to the pathing visualizer would be some way to detect when a path or waypoint is under the ground (even slightly) or in the sky. Waypoints are not too hard, as you saw in the zone code (just bump them up a notch and try again). The more valuable test in this sort of client would be testing if the line between two points is crossing any solid boundaries. There are many cases in hilly areas where mobs path up a hill between two distant waypoints and fall through the floor.

The other thing I wanted to point out is another concept I added to apathing. There is a whole system set up for "fear hints". This is a way to feed good data into apathing to improve its results. Right now, the algorithm considers all hint points to be golden, and will try not to reduce them out or destroy them, so you have to be careful with them, but we could add a flag to indicate how important a point is. The idea behind the golden points was to manually set up major junction points (hallway cornders, arches, doorways, etc...) to help the resulting paths come out cleaner. Another concept which might be worth adding (cant remember if I did it or not), would be the idea of a "hint grid", which would allow you to add entire paths to the data, manyally created via openEQ or whatever, to be factored into apathing's calculations.

Final though would be that as you continue, it might be a reasonable step to tie apathing in with openeq, so you could click a button and have apathing run in hte background on the latest data, and then visualize the resulting fear grid (in both the overview like apathing spits out in PNG format, as well as your 3d view) so the user can see how things look.

[narcberry]

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]

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).

http://www.rama.demon.co.uk/pathing1.jpg

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!

[Derision]

I forgot to say that my focus on developing this is primarily aggro-pathing (to stop mobs running through walls when they are aggroed), but it could potentially be used for less random fear-pathing, and also for roaming NPCs by just specifying a start and end patrol point, rather than all the waypoints along the path.

[YeahlightEQC]

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 (http://www.xvid.org/Downloads.15.0.html) 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).

[ChaosSlayer]

ok you MUST tell me how did you managed to pull entire zone like that? =)

[Yeahlight]

Easy enough =p

Client Commands
else if (strcasecmp(sep.arg[0], "#pullzone") == 0 && admin >= 255)
{
for(int i = 0; i < 500; i++)
{
Mob* sictar = entity_list.GetMob(i);
if (sictar && sictar->IsNPC())
{
sictar->CastToNPC()->AddToHateList(this, 0, 100000);
}
}
}

[Derision]

I cannot imagine anything outperforming preprocessed A* pathing: www.eqcprices.com/SebPull.avi (requires XViD (http://www.xvid.org/Downloads.15.0.html) 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).

Your work looks fantastic. If you should ever decide to Open Source your pathing code for EQC, it would certainly be welcome here :)

[trevius]

Wow, that is really amazing pathing lol! I can only imagine what else you guys might have working!

[So_1337]

That was very impressive.

[AndMetal]

I just added a similar command to #pullzone into Revision 125, #aggrozone, that pulls all NPCs in the zone:

http://www.andmetal.net/eqemu/aggrozone.jpg

Enjoy :D