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



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



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



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.