Improved NPC Grid/AI pathing

[Raddiux]

This is actually 2 seperate requests, so i'll break them apart.

1.) On EQlive, when a mob spawns, it moves on a grid system, so that it appears to have realistic movement by not bumping into trees and walls and stuff. For an outdoor zone, when a player attacks a mob, the mob follows the player in no relation to the grid. It just goes straight for the player, through trees, etc, yet thats the way its done on Live so I see no problem there.. However, in a dungeon/City, when a player attacks a mob, the mob navigates the dungeon/city using ONLY the grid, otherwise it would be walking through a ton of walls and creating trains. Once the mob gets close to the player, it "branches out" off the grid at the closest point between the grid and the player. If the player dies, the mob returns to the grid using the same closest point method, and then uses the grid to navigate back to its spawn point.

Now, i've spoken with Rangerdown and he has informed me that EQemu does not work like this. Mobs simply follow players in dungeons, as they would in an outdoor zone. He mentioned that this would be a difficult fix because it would involve doing a ton of checks against the zone geometry using the MAP files, which would be very CPU intensive. However, I don't believe thats how EQlive does it. On Live, the mobs seem to be "locked" to a grid (but only in dungeons, cities and other indoor zones), and use the grid to navigate the zone, and at every waypoint they do a simple distance check between them and the player to determine which direction to take for the next waypoint. Only once they get very close to the player do they pop off the grid and move towards the player apart from the grid. This is the same way that Unreal uses its grid system for mob/bot AI, and its actually very easy on the CPU in comparisson to Quake3 bots which have to "know" the zone geometry to be able to move around. I could be wrong, but it doesn't seem very difficult to impliment. All that would be needed is some kind of flag associated with each zone in the database that would inform the server to do either outdoor mob AI or indoor mob AI for the zone (since outdoor zones don't use this special AI), and some simple distance checks to tell the mob which waypoint to move to depending on distance to the player. Let me know if i'm wrong on this.



2.) On EQlive, mobs seem to use a dual grid system. For example, take the bats that spawn in lower guk by the bedroom. They are stationary, so on EQemu, they would only need one waypoint, since they don't patrol or anything. But once a player attacks them on EQlive, they seem to have access to some kind of zone wide grid, which tells them how to navigate the zone (as described in #1). On EQemu, all they would have access to is that single waypoint, which would do nothing for helping them navigate the zone. I guess the way this should be done is to have 2 kinds of grids for each zone - (1) a mob grid used to tell mobs added to that specific grid how to patrol and move around when idle and (2) a zone wide grid which all mobs have access to, to show them how to move around the dungeon. This seems to be the way EQ does it, at least from what i've observed. This probably wouldn't be too difficult to impliment I don't think, and would need some database adjustments for each zone to specificy the number of the zonewide grid. The only problem I see is that currently grids are limited to 50 waypoints, which might not be enough for most zones.

Any comments if any of this is feasible? Cause it would certainly help to make EQemu a lot more realistic.

[RangerDown]

First I'll argue a couple of points then I'll get to the read discussion These counterarguments are by no means any more of fact than your assertions, just based on *my* observations vs. yours. Only SOE knows the whole truth.

Outdoor zones have waypoints just like indoor zones do. Line of Sight from the mob to you dictates when the mob breaks off the grid and goes directly to you. In an outdoor zone the mob will likely have direct LoS to you during most or all of the chase so it appears he doesn't follow any pathing rules when in fact he's following them exactly as intended. We've all seen the case where even in an outdoor zone, as you pull the mob back to camp he might -- for a split second -- detour to the right or left before coming back toward you. That speck of dirt made him lose sight of you :P

To clarify -- at least if you're using the PEQ databases -- stationary mobs don't have any waypoint assigned to them. They do remember their original spawn location, and this is especially important for a gating mob. When their target zones or dies, they usually walk back to their spawn point.

Finally, the "2 table" grid system was put in place to eliminate the 50 waypoint limitation. You can have an indefinite number of waypoints to a specific grid now -- there is one table for grids and a child table for the waypoints within the grids.

Now to the meat of the discussion.

The grid system as currently implemented is really the reverse of how it should be implemented if smart pathing calculations are to be done. Currently there are grids in the zone, and within those grids are waypoints. It would need to be the other way around -- the zone has a shitload of waypoints all over the place that define valid spots a mob could travel to in its quest to get from point A to a point B it doesn't yet have line of sight to. And the various patrol grids would take a subset of those waypoints and line them up.

Each waypoint has to also have some connection information about what other waypoints near to it are valid to go directly to. That right there probably means a child database table with a bazillion-jillion records in it :P Cuz each "connection" between one waypoint and another would be a record here. But it's necessary if we're trying to avoid the CPU expense of using the Map file. Let's give an example: you're on a hallway, and a ways in front of you the hallway takes a 90 degree turn. Assume there's a Waypoint A on the wing you're in, Waypoint B right on the elbow, and Waypoint C a little down the other wing. You have to define an A-B connection, and a B-C connection. In this setup, there is no A-C connection because it's an L-shaped hallway. BUT, if this were a wide open room, you would have your A-B and B-C connections, AND an A-C connection to let the mob know he's free to cut the corner if he feels like it.

And there's the ever-present requirement that we have to do this pathing WITHOUT a significant increase in CPU utilization. On the big boys -- like WR, S2K, and PEQ as well cuz Soto like to grow his epeen by watching 100+ static zones up at a time even when there's only 15 players online :P -- just a small increase in CPU usage for an individual zone means their overall CPU usage just doubled, tripled or even quadrupled. And that expense in CPU could easily translate to a notable increase in the $$$ they need to maintain hardware. We'd certainly have to code it in a way that we can have a server variable letting the server op turn smart pathing on or off.

As to what time frame you're looking at... well we all know the basic rules. There's a ton of features/bug fixes and only so many devs to go around -- many working on what little free time they have. Something else to watch out for: we will probably see a cut in both our userbase and "active" devs in the next several weeks as they go off to try EQ2 and WoW. Some will come back eventually -- some won't. And *this* kind of module is one that's gonna be complex so it takes loads and loads of time to implement and debug, all at a time when the project's resources are threatened by new eye candy on the horizon

[smogo]

just a short notice (as i have no definite opinion on how to do it ) :

i like the idea of shared paths ; i.e. get a grid over the zone, and a list of direct LOS connections between them. Then build path grids (and track / flee grids as well, when they are implemented) referencing theses 'safe path grids'

Data storage is not that big (say a few Kb per zone, even if 1 Mb, that does make much as compared to real time LOS computes), and it allows to first define safe paths based on zone geometry, then select a few of these to make a real mob pathing grid. CPU is really low (and limited to boot time) as compared to LOS algs.

Provided nodes will be shared by several mobs, as will segments, data storage shouldn't be that big (nor would maintenance complex) and it allows more flexibility in grid design : we could have pre-set grids (as we have already, i.e. wp1 then wp2 then wp3 ... with all pathing variants we already know), and also extend the system to tracking or fleeing systems

It's nice to have this discussion again

[Raddiux]

Hmm now that I think of it, maybe you are right about the outdoor zones thing. I don't remember 100% (and i should double check), but in SK, when you pull aviaks from their tower, I am pretty sure that they follow the circular path down/up to get you to, instead of just magically poping up/down on the z axis. But in most cases, you don't see a mob move along rigid lines in an outdoor zone like you can easily see them do in a dungeon. I'll have to do some more testing on live to make sure though.

The node concept sounds like a great idea. Nodes can be laid all throughout a zone which defines where a mob can and can't go (the same way done in Unreal). These nodes automatically become interconnected depending on where the mob needs to go. And waypoints can be used the same way they are used now - to define a mobs spawn points and patrol route.

As for dev's leaving, i'm not really too concerned about that. Look at UO emulators. How many MMORPG's have been released since UO's creation? Yet there are still literally dozens of UO emulators out there that are still being worked on. I can't imagine eqemu grinding to a hault just because of WoW and EQ2 (which aren't all that great, anyway). Thanks for replying ranger

[kathgar]

The grids are in no way meant to define pathing. NEVER. There are two kinds of 'pathing' people talk about. One is wandering. The other is the pathing you are talking about. There has been quite a lot of discussion about such things and you really need to look into it more. In your post you state they they would only have to do a simple distance check from the mob to the player to determine which path to take, this is not correct for all cases. I for one am for ditching the entire grid system as it is poorly designed AND poorly implemented.

[VooDooKenshin]

Radd

The Aviaks run right off thier platform because EQLive doesn't really take into account the Z axis. This is why mobs on the ground 300 feet below you can still wack on you when your in the treetops of Kelithin.

Anyway, because it doesn't really recognize the Z axis the Mob you pull from the tree thinks that it has DLoS on you even though it may not and makes a bee line for you.

Of course, try and cast on one of those suckers from the ground and low and behold "You can not see your target" pops up.

EQ Live did this on purpose because Wizards were taking advantage of the weak AI back in the day and aggroing MoBs then retreating to the safety of a high pearch that the MoB was either unable to get to physically or pathing was screwy and it could not go up elevators of course.

[Raddiux]

Can any dev's comment if this stuff is doable? It would be really nice to have correct pathing and fear support
Actually, I think WR just got fear support, so wouldn't that mean that they already have a similar system in place?

[sotonin]

WR lays down seperate grid systems for fear in each zone. Done by hand