Experimental Code: Stop mobs hopping when pathing - FindBestZ tweaks

[Derision]

This is for those people who don't like to see mobs hopping vertically when pathing.

I've spent the past few days tweaking the 'FindBestZ' code so that mobs stay on the ground when moving. It seems to work quite well, so I thought I would put it out there for anyone interested to try it out.

(For those that don't know, the FindBestZ code attempts to use the geometry data in the zone .map file to ensure mobs stay on the ground while moving).

Diffs against the 1062 source, along with the three changed source files
(Map.cpp, waypoints.cpp and features.h) can be found here:

www.rama.demon.co.uk/BestZPatch.zip

No Windows binaries as I use Linux for playing with EQEmu.

The changes in features.h are just to enable the defines related to fixing pathing when moving, along with a new define I added, ASSIGN_BESTZ_WAYPOINTS_ON_LOAD, which, if defined, causes BestZ to be applied to waypoints as they are loaded from the database.

Notes:

What I did find while testing was that the Facelist array in the eastwastes map appears to be corrupt. This was causing a crash, so I added a check for this in FindBestZ, in the same way that is currently done in the LOS code.

Of course, this means that FindBestZ won't work for Eastern Wastes. There may be other map files that are 'corrupt' in a similar manner, although I didn't come across any others in my limited testing.

I guess this code will break pathing in underwater zones, e.g. Kedge, where mobs are actually not meant to move along the floor. I guess you could add a column to the zone table to enable/disable this code on a per zone basis. This could also be helpful to reduce CPU load for zones where the pathing correction isn't required, e.g. zones that are mostly flat or zones where the waypoints have been made by hand to avoid hopping.

[Derision]

Just in case anyone was curious what the MAP files actually contain, during my work on this I wrote a little Visual C++ 8.0 / OpenGL app so I could visualise it (3D geometry is not really my thing).

The image below shows the triangles contained in the dreadlands.map file, looking from the tunnel to Firiona Vie out across the zone (the box in the middle is Karnor Castle).

The text shows the X,Y,Z position you are viewing from, along with the Node (bounding box). The next line shows some info about the bounding box and finally the BestZ, i.e. the elevation of the ground at the X,Y position you are at.

The app is not user friendly (need to hard code the path to the zone file as well as the X,Y,Z position you want to look from, otherwise I would have posted the code for that too.

Nice work!!

[moydock]

Very nice, does this also fix mobs going under the world while attempting to path over hills? If so, you are my hero! If not, still very nice .

[Diuretic]

Aye, this is fascinating work! The problem's obviously less easy to solve than I originally thought.

Thanks again for the eye opener.

[Derision]

Originally Posted by moydock

Does this also fix mobs going under the world while attempting to path over hills?

I hope so, however I can't say for sure that it fixes all such occurrences as I only checked a limited number of mobs in a limited number of zones.

If you can give me some specific examples of where this occurs, I can check those out for you.

[Zandig]

Awesome!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!

I've wanted to see some solid work on this for quite a while.
Excellent job.

Now we need some Windows binaries

[Derision]

Originally Posted by Zandig

Now we need some Windows binaries

I have yet to have any feedback from anyone who has actually said they have compiled and tried this code. If I find time over the weekend, I'll install the necessary software on a Windows box to make some binaries for you to try it out.

[KLS]

Do you have any idea where the crash in question occurs in the code?

Corrupt or not there's probably safe-checks that can be put in place to prevent it if we know where it's at.

[Rogean]

Http://www.rogean.com/Zone-BestZ.exe

Haven't tested it myself. Test it out and let me know how it works out. If it looks good I'll commit to code.

[Derision]

Originally Posted by KLS

Do you have any idea where the crash in question occurs in the code?

Corrupt or not there's probably safe-checks that can be put in place to prevent it if we know where it's at.

Hi KLS,

No crashes occur because I copied the check from:

bool Map::LineIntersectsNode( NodeRef node_r, VERTEX p1, VERTEX p2, VERTEX *result, FACE **on)

which is called by the LOS checking code

  unsigned long *cfl = mFaceLists + _node->faces.offset;

        for(i = 0; i < _node->faces.count; i++) {
                if(*cfl > m_Faces)
                        continue;       //watch for invalid lists, they seem to happen

The if(*cfl > m_Faces) checks for the corrupt data that I saw in the eastwastes.map file. I assume this check was put in by FNW when that code was written.

I put the same check in the FindBestZ code to avoid the crash there, so there is nothing else required (other than maybe fixing the program that generates the .map files (azone?).

[rojadruid]

if this does work and stops the mobs from hopping all we need now is the actuallt pathing in "apath" figured out. I have been looking at it for awhile now and I am not making any heads or tails on it and I gave up about a mnth ago figuring it was hopeless.

[KLS]

Yeah it would be azone that generates them, alright I'll look at it when I take a look at the other stuff posted on the forums in the next couple days.

[fathernitwit]

Nice. I have comitted a cleaned up version of this code.... hopefully it still works. I disabled the two old options by default in features.h, but enabled the new "fix-at-load-time" feature, as it seems like a good compromise.

My only real concern about this is the somewhat arbitrary nature of a lot of the constants in there... 10, 20, 45, etc... We might want to either make them a rule, so people can easily change them, or else put some serious thought into deciding on good universal values...

My last thought is that if this in fact turns out to be a rock solid fix for the z hopping problem, then we should prolly take it one step further. One of the things I was trying to accomplish with apathing was to be able to load, fix, and then re-save the pathing data into the database... this way we only consume the CPU time once... it shouldent be all that hard to accomplish, the big concern is how to be sure that it is actually producing the right data... we dont want to run it against the official dbs unless we are quite sure it isnt going to mangle a bunch of paths... one challenge with stuff like this is trying to figure out how to detect such failues... as in most cases the mobs are then just way under the ground, and nobody will ever notice (unless its a named mob).... just a thought.

-FNW

[moydock]

I'm excited about this but man... I've already designed a large part of my DB with grids that won't make npc's go through hills. So much work! At least this will make the rest of my work much easier.