Zone wide NODE-based path finding discussions

[Raddiux]

Well ok, I was bored today, so I thought i'd try to see if I could break down how a node system would work in EQ. And I must admit, its a lot harder than it seems. I kept coming up with possibilities that i'm not sure how I would solve. One thing I should add is that this pathfinding is only needed in indoor zones, or zones that need very elaborate pathing. I don't see how a zone like the karanas would need special pathing (except for fear). Here are 3 examples that I came up with, and please excuse my shitty drawings. Please keep in mind that i do not have all the answers here. I am hoping that you guys can help solve some of these issues. The previous discussions can be found here:

http://www.eqemulator.net/forums/viewtopic.php?t=18171


EXAMPLE A

http://members.bellatlantic.net/~doa/Image1.png

Lets start with a simple one. This would be the first, and easiest example to follow. The setting would be a typical "maze" type dungeon, as found in say guk. The MOB has to get to the player by using the nodes set throughout the map.

The first condition that needs to be stated is that when the mob has LOS to the player, it can then "break off" the node system and move directly towards the player to attack. In this case, the mob does not have LOS to the player, so it must make use of the nodes to navigate. I suppose the first thing that would have to be done is for the mob to check LOS to all nodes in the zone (or nearby radius?). This tells the mob which nodes it has access to. In this case, the MOB would realize it has access to nodes 'A' and 'C', but not 'B'.

Then a distance check would have to be done from the MOB to all nodes that the mob has LOS to, so it knows which ones are the closest and which are the farthest. In this case, 'A' is the closest, so the mob can successfully move to it. However, a distance check has to be done to all nodes that the MOB has LOS against the player, to see which node would actually bring it closest to the player. In this case, 'A' would bring it closer to the player. Now the mob is at node 'A'. I suppose the mob should always move to the closest node available to it which also brings it closer to the player. Meaning, the mob should NOT skip over node 'A' and go directly to 'C'

Using the same formula, the above happens all over again. LOS is checked to all nodes. This time, 'B' and 'C' have LOS. This time, 'B' is closer to the mob, but 'C' brings it closer to the player. I guess that means there has to be another if statement that says if there is more than 1 node available with LOS, it must move towards the one that brings it closer to the player, and is also the node closest to the mob. The final step of course is that the mob moves to point 'C', where it now has direct LOS to the player and can move towards the player to engage it. Now lets try something a bit harder.



EXAMPLE B

http://members.bellatlantic.net/~doa/Image2.png

In this example, there is a body of water, or lava, or chasm, whatever, between the mob and the player. The mob must get to the player by going around the water, it can NOT go through it. The main issue here is that from the start, the mob already has direct LOS to the player. If the mob were to follow the rules set in the first example, then it would walk straight through the water to get to the player, which it must not. So that rule either needs to be changed or deleted. Perhaps only within a certain distance is the mob allowed to engage if it has direct LOS? I'm not really sure.

Lets just say that the MOB has to get within 5 feet of the player in direct LOS before it breaks off to engage. So lets start using the rules from before: First the mob does a LOS check to all nodes. In this case, all nodes are in direct LOS. Yet not all nodes are valid targets to move to, since they would lead through the water. Using the distance check, the mob then sees which nodes are the closest to it, and then which of those nodes would bring it closest to the player. Here, both 'A' and 'B' are the exact same distance away from the mob. However, 'B' is closer to the player than 'A' is, so the mob moves to 'B'. This loop continues on, until the mob reaches point 'F' where it has now satisfied the 5 feet condition and can engage the player.

Now for a tricky one.


EXAMPLE C

http://members.bellatlantic.net/~doa/Image3.png

Here, the player is up on a ledge, looking down at the mob. The mob has to get to the player by going up on to the ramp and going around to get to him. This example is interesting because in this case, the mob would actually have to move AWAY from the player at some points before it can start moving closer.

Lets just say that the mob does have LOS to the player, but is not within the necessary 5 feet to engage it. The mob does a LOS check to all nodes, and finds that 'A', 'B', 'C', and 'D' are available. (note that its important for the nodes to be placed properly in cases like this). It then does distance checks to see which of those nodes its closest to, and which would bring it closer to the player. The first problem here comes up. Either 'A' or 'B' are closer to the player, yet they would do nothing to bring the mob closer to the player. The mob SHOULD move to point 'D', but using the current rules, there is no way for the mob to realize this.

I am honestly not sure how to solve this problem. I realize that I am trying to reinvent the wheel here, since I am 100% sure that issues like this have been solved before dozens of times over in other games. Hell, there might even be an open source node pathing kit or something out there, lol. One issue I hear quite often is that doing all these LOS and distance checks would eat the CPU. I'm just curious, but for mob agro, how often does LOS checks take place? It seems to me that every mob in the zone would have to be doing LOS checks to every player in the zone, constantly, every second. Isn't this demanding on the CPU?

I suppose its reasons like this why no one would want to tackle adding nodes to eqemu. Still, I find it facinating and challenging, and I'd love to hear others comments about how they think node pathing should be done.

[m0oni9]

This would likely be done with a graph. There are two ways to generate this graph: 1) Manually set connections between nodes, 2) Automatically set connections between nodes (based on LOS, perhaps)

Either way, you will end up with a graph with similar properties, each node having these attributes:
links to adjacent nodes
distance to adjacent nodes
some sort of direction vector to adjacent nodes
node type
arbitrary data
CPU usage: You would not check nodes as often as you are thinking. It would be possible to store in the Mob class (for instance) the node that a player or mob is at/connected to. So, just find a path from Mob A's node to Mob B's node, probably using the infamous travelling salesman algorithm. You could also likely cache results from past checks for even more speed. In addition, a mob may only need to do a check when either its or its target's "connected to" node changes.

When to use adjacent nodes, and when to use target node: Nodes may have different types. Some nodes may be flagged as "sticky" -- you may only path to adjacent nodes when coming from this node. A node may be flagged as "free" -- go destination node if it is visible. Of course, then there is the problem of having multiple types in one area. This may be solved with using "free areas" or "sticky areas" in conjunction with nodes.

There are still plenty of problems with this system, I imagine, but maybe that gives you something more to go on.

[fathernitwit]

This does exist for this reason: Nobody is going to make pathing grids for every zone.

It cannot be done automatically because the emu has a VERY bad perception of the zone geometry due to the fact that the zones are converted out of the s3d files, and many in-world objects are not included in that set.

Grids like you describe would have to be pre-generated, they are too expensive to calculate at run time... and the maps we have are not accurate enough to generate automatically.

If you want to see an example of how bad the emu's ability to obey zone geometry are, try uncommenting ENABLE_FEAR_PATHING in features.h. It works for open zones, somewhat... but hallways and crap, it works very bad. I spent days on this one, and the results were not satisfactory at all.

If grids were to magically print up out of the ground, then this would be great. It is very cheap to use the grids, if we had them.

[RangerDown]

Something that bears mentioning here too, since one of your examples used water: the server-side maps don't have water areas. The server has absolutely no idea where water is in the zone.

I have no clue of the technicalities behind the S3D files or the resulting MAP's that were made from them, but I'm gonna guess that if it was easy to extract water from the S3D's, the maps would already have them 8)

In your example, the mob probably would've gunned straight for the player, swimming through the water, as the server wouldn't have seen the water as a barrier to LOS. But contrary to what you seem to suggest, that's actually normal behavior in a lot of EQLive zones: mobs aren't afraid to get a little wet if it means some xp from that juicy player kill :P

[m0oni9]

It cannot be done automatically because the emu has a VERY bad perception of the zone geometry due to the fact that the zones are converted out of the s3d files, and many in-world objects are not included in that set.
I don't know if we're agreeing or not. My suggestion would be to have manually created nodes, but with either manual or automatic connections. In either case, the initial grid (I am calling it graph) calculation should not be too intensive, though it will probably be O(n!) -- given, I do not know how efficient an average LOS check is. The graph will need to be generated at zone boot, but thereafter the brunt of the work would be finding a path from node A to node B.

What I kind of had in mind was automatic connections from pre-generated nodes. This way, someone may be able to create hotkeys (ie: "Node Type 1", "Node Type 2"), and go about the zone, hitting the keys where appropriate. Afterward, a script would generate nodes from the log file, used for inserting into the DB, or maybe a ".path" file. It may even pre-calculate the node connections.

The biggest problem I see with the system, other than getting it all to work well :D, is the potential hit of finding a path between nodes. It could also take up a nice chunk of memory.

[Raddiux]

Rangerdown: The water should have nothing to do with it. As long as that scenero was in a dungeon (outdoor zones don't really need this node pathing), the mob should always be stuck to the assigned path, moving from node to node (train tracks I used to call them when I first started playing EQ). Since there were no nodes placed in the water in my example, the mob should not have even considered walking there. It doesn't matter that we can't tell where water is - when the nodes are manually placed, WE know where the water is, and can place nodes around water, lava, whatever, when needed.

fathernitwit: My idea was that nodes would be places manually by us in a similar fashion like what m0oni9 described : a simple # command which places a node (and perhaps also spawns a mob in that loc, so you can see where you've placed them, and do LOS checks to mobs you've already placed). I for one am 100% willing to places nodes throughout dungeons if it means we can have proper pathing and fear support in them.

The only 2 things i'm not sure of is:

1.) how expensive would this be on the CPU? If it can't be done in realtime, then perhaps some kind of script can be run after all the nodes are placed to spit out a grid file which has pre-calculated distances and LOS checks to nodes throughout the zone

2.) How would the path-finding algorithm work once the nodes are in place? I still can't figure out how to handle Example C which I listed above. Any of you guys have any ideas?

[m0oni9]

perhaps some kind of script can be run after all the nodes are placed to spit out a grid file which has pre-calculated distances and LOS checks to nodes throughout the zone
That is the general idea. You do not need a LOS check, though, because a "connected" node implies that it is visible.

2.) How would the path-finding algorithm work once the nodes are in place? I still can't figure out how to handle Example C which I listed above. Any of you guys have any ideas?
Once connections between nodes are worked out, it is the travelling salesman problem. To find the shortest distance between two nodes, the solution can be intensive. AFAIK nobody has come up to a better solution yet. However, there may be other ways to help alleviate this problem, ie: a grid overlay on the zone, each node belonging to a section of the grid, and finding sub-paths.

This is how the graph would look for your example C. All lines are bi-directional. I added node Z in place of your mob. The mob and player nodes are not REAL nodes, but instead each have a link to the node that they are "at."
http://home.comcast.net/~moofn/blah/pathg1.gif
The hardest part would seem to be finding a way to provide for auto node connection. For instance, if I have logged nodes A, B, and C, all visible, but only want travel possible from A<-->B<-->C, how do I accomplish this if I do not manually set connections? Labelling nodes may help with this (and labels could be thrown out after graph construction), but there may be better ways.

[animepimp]

To automatically set paths between nodes you could use the existing LOS and distance calculation methods as the node is created. When you as a GM create the node it'll make sure there is a mob at each other node within say 15' and then check LOS between you and them. Then it'll list all the nodes that it found LOS to and give you a chance to delete ones you don't actually have LOS to or ones that have an uncrossable barrier in the way. Once you've deleted invalid connections it adds the node and the connections to the DB and you move on.

Its a lot of work, but only needs to be done once per zone before it can be distributed and then each mob's path would be a subsection of the graph of nodes. And I picked 15' because really these need to be fairly close together so that the mob can't leave the nodes til he is very close and there is an extremely low probability of there being an object in the way.

It should be fairly resource low to store all these in the DB since each one entry would only consist of ID, X, Y, Z and a list of connected IDs. We could cut down on the server processor load by increasing the DB size quite a bit by simply calculating the shortest route to each node within agro range once after all the nodes are entered. This would be quite a bit more space, but not too horibly much if the nodes are too dense since if agro radius was 60' there would be probably 20-25 nodes in that raidus and each node would have a list of 20-25 paths which would be only about 30-40 bytes apiece since all it would store would be 5-10 node IDs. Of course on large zones this gets to be quite a huge number to store. I don't know what the current processor/memory load is right now so people that do can weight the options.

[m0oni9]

To automatically set paths between nodes you could use the existing LOS and distance calculation methods as the node is created.
If a path should only go from A<-->B<-->C (ie: no connection between A and C), and all points have LOS to each other, how will the server know that the A<-->C connection is not valid?

Would you be able to restate the other paragraphs, or create something visually? Maybe I am just dense, but I am a little lost with them.

[fathernitwit]

dont worry about the algorithm for how it would be done in the server, thats the least of our problems. They would prolly be stored similar to the maps in some sort of spacial data structure with everything of fixed length/limit (specifically the number of connections).

There are several problems with building the grids in the first place:
1. There is no way to visualize them in the client, so no way to really see what your doing.
2. Auto-connecting is not trivial... theres a lot of things which will affect this... specifically hills, holes, hallways, etc. You pointed out a very good case above too... with your picture... C---A---B... unless those three points were perfectly colinear (not possible with player-collected data), the connector cannot automatically choose to not connect B and C withouth extensive spacial calculations.
3. The collected points would have to exist at about eye level on the player, and not on the floor, otherwise a small step or bump in the zone will cause two points to be disconnected.
4. I would say were looking at 400+ man hours to path out zones... and then theres no trivial way to debug them once they are made, and no way to tell the quality of what was made.


Honestly, to get around these problems, somebody would need to take the (now defunct IMO) freaku/openEQ stuff, finish a bunch of work on it, and then build in visualization code to draw the grids.

[animepimp]

Lets say A, B, and C are in a line and its supposed to go from A->B->C. The only way it would know to not create a connection between them would be if they were spaced out far enoguh past the automatic connection area. Like if A is 10' from B which is 10' from C it won't create a connection A->C because they are 20' apart which is more than the 15' limit. If they were all within the radius then the server would automatically find lines between each of them and when you create C output "Found connection to B. Found connection to A." Then you would do a command to tell it not to connect to A.

[m0oni9]

1. There is no way to visualize them in the client, so no way to really see what your doing.
Your points are valid, and I would agree with the freaku/openEQ (or any zone viewer+node visualization tool) idea. This would provide for an interface many times better. Node connections could be toggled manual/automatic, could be manually added/deleted, etc. This would also allow for connecting two nodes that do not have LOS (ie: nodes on either side of a hill, a mob will just run from one to the other). If visualization can be solved, many other problems would seem to resolve themselves. I am not too concerned about the man hours, as immense as the number may seem.

I'm feeling some motivation coming on.. I am not volunteering, though. :D

[Raddiux]

1. There is no way to visualize them in the client, so no way to really see what your doing.


While it might not be the cleanest and most efficient way to place nodes, I do believe it can be adequately done through the client. Say for example that you want to place a node. You stand at the spot you want the node to be placed, and use some kind of #addnode command. The #addnode not only records the loc of the node you placed, but also spawns a skeleton at that exact loc. When you move onto the next place that you want to add a node, you can then look back and target the previous spawned skeleton and type #LOSnode which will check your current LOS @ 5 feet above the ground to 5 feet above the ground where the skeleton is (nodes shouldn't be locked to the ground but at eye level as you suggested). If you want to delete a node, just target the spawned skeleton and type #deletenode, which will check the loc of the targeted skeleton and reference the node also at that exact loc, and delete it. Though you'll never be able to physically see the connections being drawn, this should be decent enough to lay down nodes and do some testing to see how AI would behave under these conditions.

Note that I don't feel that this special pathing is necessary in large outdoor zones since its mostly just flat land anyway, and little to no walls to have to navigate around. Hell, on EQlive this pathing doesn't take place either, as I fondly remember hunting in Qeynos hills and having monsters agro on me, and try to run through the walls of the little cottage there. This node pathing should only really be necessary in dungeons and cities where there are a lot of thick zone geometry that needs to be intelligently navigated as to prevent a mob from walking through walls or falling through the floor and cause trains. Limiting the construction of nodes to only dungeons and cities. it probably won't be as difficult or lengthy a job as you might think.

The reason i brought this node system up is because I've done a bit of work in the past building levels in Unreal, monster AI there used a very similar system of laying node nodes which allowed mobs to navigate the level with great precision. Though i'd love to get a look at the AI code in Unreal to see how it works, I don't think that is available. I've found a bit of text from the old unreal technology site, which might give a bit of insight as to how their AI worked.

PathNode placement


You can place pathnodes manually, or you can use PATHS BUILD LOWOPT from the console to get a first pass placement done automatically. In any case, you must do a PATHS DEFINE from the console to create the connections between pathnodes.


To use the navigation system, a creature must first choose the best nearby node to "get on" the network. For performance reasons, creatures limit their search for path nodes to those within an 800 unit radius (see FSortedPathList::FindVisiblePaths in UnRoute.cpp). This is because the test to determine if a creature can reach a path is very expensive. However, once creatures are "on the network", travelling from pathnode to pathnode, they use the reachspec tables in each pathnode to determine reachable nodes. There is no distance limit for reachspecs, so paths may be defined between two pathnodes which are any arbitrary distance apart. For performance reasons, paths between distant pathnodes which have a suitable alternate
path using intermediate path nodes (with a low added cost) are culled from the path network.

I recommend that paths should be less than 700 units apart, so that creatures don't ever start off going in the wrong direction to get on the network. In addition, paths on stairs and ramps should be closer together (<350 apart) Given that, you should use the minimum number of paths needed to cover the area for which you want intelligent navigation. Note that all navigation points are equally used as paths, so there is no need to place pathnodes redundantly near patrolpoints, etc..

Paths should in general be placed at intersections, making sure that they have the maximum visibility in all potential directions. Paths need a line of sight to each other, clear to the width of the maximum width (2 * collisionradius) of creatures which will use this path. You should also place paths on ledges, with a line of sight to paths below, so that creatures can intelligently navigate jumping off ledgest. Vertical line of sight has no extent requirement.

[mysticalninjajesus]

I fondly remember hunting in Qeynos hills and having monsters agro on me, and try to run through the walls of the little cottage there.

yah you should try to fix that so they wait at the door or something lol, that would be pwn. instead mobs can run thru the walls. (maybe not in the qhills cottage but in commons they can)

[m0oni9]

While it might not be the cleanest and most efficient way to place nodes, I do believe it can be adequately done through the client.
After some reconsideration, I really do think that a secondary utility for node placement/linkage is the best choice. Yes, you could place mobs as nodes for use in the client, but how will connections between these nodes be visible? Paths must be able to be editted, as illustrated earlier. Mainly due to this reason, I am feeling that the client may not be adequate.