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.

http://www.rama.demon.co.uk/Dreadlands%20EQEMu%20Map%20visualisation.jpg

[mattmeck]

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]

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 :D

[Derision]

Now we need some Windows binaries :D

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]

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.

[Zandig]

I've downloaded the latest Win32 release: EQEmu-0.7.0-1065

==11/29/2007
FatherNitwit: (Derision) Fix BestZ pathing cleanup code top stop hopping.
FatherNitwit: (Derision) New fix-z-on-load feature.

and tested a few zones that always drove me mad with the hopping:

fieldofbone
frontiermtns

The mobs are still hopping like mad in these zones.
I'll test out some other zones soon.

[Derision]

I've downloaded the latest Win32 release: EQEmu-0.7.0-1065

and tested a few zones that always drove me mad with the hopping:

fieldofbone
frontiermtns

The mobs are still hopping like mad in these zones.
I'll test out some other zones soon.

Yes, the Win32 release has been compiled with two of the three features disabled, so you will still get hopping between waypoints. You could try
the Zone.exe that Rogean posted a little earlier in this thread, or I will attempt to build a Win32 release with all 3 options enabled in the next few days.

[Zandig]

Yes, the Win32 release has been compiled with two of the three features disabled, so you will still get hopping between waypoints. You could try
the Zone.exe that Rogean posted a little earlier in this thread, or I will attempt to build a Win32 release with all 3 options enabled in the next few days.

Thanks Derision,

I will give that a try.

A proper Win32 release with all the options enabled would be greatly appreciated.

[fathernitwit]

OK, by popular demand (aka one dude who cant build), I reworked this stuff to be runtime configurable using the rules system.

[Zandig]

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.

Tested various zones and it looks really good so far.
Hopping is gone.
What a sweet fix!

[krusher]

I have created a wiki page listing the new rules required for the pathing Z fix.

Krusher

[Cripp]

to make the rules work(or to even compile properly).. need to add them to the rulesys..

--- ruletypes.h 2007/11/14 06:13:36 1.11
+++ ruletypes.h 2007/12/01 18:11:14 1.12
@@ -84,6 +84,17 @@
RULE_BOOL (NPC, UseItemBonusesForNonPets, true)
RULE_CATEGORY_END()

+RULE_CATEGORY( Map )
+RULE_BOOL ( Map, FixPathingZAtWaypoints, false )
+RULE_BOOL ( Map, FixPathingZWhenMoving, false )
+RULE_BOOL ( Map, FixPathingZOnSendTo, false )
+RULE_BOOL ( Map, FixPathingZWhenLoading, false )
+RULE_REAL ( Map, FixPathingZMaxDeltaSendTo, 20.0 )
+RULE_REAL ( Map, FixPathingZMaxDeltaLoading, 20.0 )
+RULE_REAL ( Map, FixPathingZMaxDeltaMoving, 20.0 )
+RULE_REAL ( Map, FixPathingZMaxDeltaWaypoint, 20.0 )
+RULE_CATEGORY_END()
+
#undef RULE_CATEGORY
#undef RULE_INT
#undef RULE_REAL
--- waypoints.cpp 2007/11/30 19:06:27 1.6
+++ waypoints.cpp 2007/12/01 18:11:14 1.7
@@ -31,6 +31,7 @@
#include "parser.h"
#include "StringIDs.h"
#include "../common/MiscFunctions.h"
+#include "../common/rulesys.h"
#include "features.h"

static inline float ABS(float x) {

Edit:: im not sure if this was already added to the nightly builds or not.. but it wasnt in cvs.

[Zandig]

OK, by popular demand (aka one dude who cant build), I reworked this stuff to be runtime configurable using the rules system.


I have created a wiki page listing the new rules required for the pathing Z fix.

Krusher

Thanks all.
Tested with 0.7.0-1068 and it works a treat.

[moydock]

Thanks guys, really excited about this new feature.

[moydock]

Working great, only problem i've noticed is when a mob goes up a steep hill or maybe it's just a certain change in his z coordinate, he goes under the world. However he does pop back up after a couple seconds. Still a huge improvement.

I may have not set it up right though, not exactly sure what the 'rule system' is.

[Zandig]

I may have not set it up right though, not exactly sure what the 'rule system' is.

It has to be set up in the database.

Here is how I have mine set up (working very well):

rule_sets
http://img216.imageshack.us/img216/6335/rulesetsnz6.th.jpg (http://img216.imageshack.us/my.php?image=rulesetsnz6.jpg)

rule_values
http://img229.imageshack.us/img229/3307/rulevalueskj5.th.jpg (http://img229.imageshack.us/my.php?image=rulevalueskj5.jpg)

Thats all there is to it!

[moydock]

Sweet thanks, got it working, still seeing them go under when climbing steep hills. Not sure if that's fixable. I haven't upgraded to the newest build though, didn't see any fixes in the log. Btw do you know what the Map:FixPathingZatWaypoints is for?

[Derision]

still seeing them go under when climbing steep hills. Not sure if that's fixable.


I've seen this happen in Dreadlands where one waypoint is on one side of a large mountain
and the next waypoint is on the other side. The movement code plots a vector between the
two waypoints which goes right through the middle of the mountain (under the world).

The BestZ code as currently implemented takes the mobs current Z position and looks downward to find the ground. If the mob is already under the world, it will either do nothing, or in the worst case, e.g. Dreadlands, which for some reason has an invisible 'floor' under the world at Z=-210, it will push the mob even further down.

I just made a quick hack to the code to make the BestZ code look up instead of down, and in the
case of the particular mob I was looking at in Dreadlands which pathed over a steep hill, it seemed
to have the desired effect of stopping it going under the world, i.e. if it was under the world, it pushed
it back up to the ground level.

The next step is to have the code look up AND down and decide which direction to push the mob.

I don't have a lot of time to play with this much at the moment, but if I find something which seems
to work reliably, I'll post a further patch.

[Derision]

still seeing them go under when climbing steep hills. Not sure if that's fixable.

If you're using the PEQ Ykesha DB could you give me some test cases of mobs that path under the world, i.e. which zone they are in, then target them and do #npcstats and #wpinfo and give me the NPCID and Grid number ?

[moydock]

If you're using the PEQ Ykesha DB could you give me some test cases of mobs that path under the world, i.e. which zone they are in, then target them and do #npcstats and #wpinfo and give me the NPCID and Grid number ?

I'm actually using a custom db so no help there. But I can tell you this, there seems to be a height which they reach, and they always go through the hill at that height. It also seems to be the height they would normally 'hop' up to before the fix. I'm guessing this point is the z coord of the WP they're headed to.

So what if you forced the z coord of the waypoint a mob is headed to always be the highest point in the zone. Then they wouldn't go through hills and the z-fix already in place would keep them on the ground. Would that work?

[Derision]

So what if you forced the z coord of the waypoint a mob is headed to always be the highest point in the zone. Then they wouldn't go through hills and the z-fix already in place would keep them on the ground. Would that work?

The first problem I see with that is zones with multiple ground levels, e.g. dungeons, or Kelethin, with the city in the trees.

The code does already try and compensate for a small movement under the ground. If it can't find a BestZ on the first attempt, it bumps the mob up by 10 Z units and tries again.

The amount it tries to move the mob up on the second attempt (10 units) is not currently configurable by the rules system. I'll see if tuning this number (increasing it) helps with the steep hill problem. This would be a less CPU intensive solution then my previous thought, and if it works, we could make this a configurable parameter in the rules system.

[Angelox]

This is a great Improvement over what we had -
It always seemed to me there were much more "hoppers" when the grids were packet spawned, than when I laid them out my self.
On thing still remains, is the water hoppers - a good example is in Dagnor's Cauldron, where there are many surface swimmers, all will bounce up and down constantly.
If you go to the small isle in the middle, you can follow the roamers into the water and watch them hop

[Derision]

If you go to the small isle in the middle, you can follow the roamers into the water and watch them hop

I see what you mean. I tried a few tweaks without much success. Even if I did tweak the code to stop the hopping, as it stands, the code would keep the mob at the surface of the water, or make it follow the contours of the bottom of the lake. Although the client knows when a player is underwater, I don't believe the server can tell (from a few quick greps for the words water/air/drowning etc.)

A more complete solution would be to add an extra table to the database. Each row would contain the zone number and the co-ordinates of a 3D cube defining underwater areas (with multiple rows for zones with multiple distinct areas of water).

This should allow the BestZ code to quickly check if the mob is underwater and not force it to the bottom or top of the water. I will experiment with this if I have some free time over the holidays.

[Angelox]

Cavedude had mentioned one temporary solution was to give the swimmers the levitation spell - This keeps them steady at what ever grid they are on. Problem is these mobs in Cauldron go in and out of water, so they float on land, and it doesn't look right.
What I'm thinking is. what code is related to levitate? maybe make an "in water" exception and apply what ever it is that removes the "gravity" in Levitate, while swimming. There must be some code that tells the NPC he is in water and this puts him in "swim-mode" (they start swimming while in water). Maybe you can exploit this and use it to eliminate the hopping too (while in swim mode, don't use Z coord).

[Derision]

There must be some code that tells the NPC he is in water and this puts him in "swim-mode" (they start swimming while in water).

I am fairly sure that there is code in the client that 'knows' that an NPC is in water and turns on the swimming animation, rather than the server telling it. If this is the case, I don't know whether there is some information in the zone S3D/EQG file that the client uses, or whether the client has some hard-coded information.

Maybe I'll try making a zone with Windcatcher's OpenZone with some areas of water and see if the client detects when a player is underwater. If it does, then there must be some information in the S3D that I can extract and use.

[Cripp]

ive also noticed that mobs that stand on docks or in little huts are pulled through and stuck to the actual ground so they either under water or there head is sticking through the floor...

im possibly gona try and add a way to disable fixZ for selected NPCs

as for water hopping... could check if NPC is in water or not(if possible).. and if its in water walk in a straight line..
(maybe, just an idea)

[cavedude]

I think an ignorefixz column or something such would be a good addition to npc_types. I too, have found that mobs get glued to the ground when they should be on rocks, huts, chairs, etc. This column would allow us to place exceptions on a per mob basis. The initial setup would be nuts of course, but once most of those mobs are corrected everything will look a lot better. Better yet, the column could be put in spawn2, so any mob that has those spawn points will be effected.

As for mobs in the water... there currently is no way for us to tell where water exists in the map. That's why you can fish anywhere in a zone, and why we can't keep fish from leaving ponds and such. However, if a way of determining where water is can be found, that would enable us to correct fishing, prevent fish and the like from leaving water, and help prevent the hopping under water and/or sticking to the bottom if fixedz is enabled.

[Cripp]

heres what i came up with today...

--- mob.h 2007/12/17 02:26:10 1.25
+++ mob.h 2007/12/19 18:08:39 1.26
@@ -902,8 +902,11 @@
// uint32 guildeqid; // guild's EQ ID, 0-511, 0xFFFFFFFF = none

int8 light;
-
+#ifdef CRIPP_Z
+ sint16 fixedZ;
+#else
float fixedZ;
+#endif
EmuAppearance _appearance;
int8 pRunAnimSpeed;
--- npc.cpp 2007/12/17 02:26:10 1.20
+++ npc.cpp 2007/12/19 18:08:39 1.21
@@ -152,6 +152,9 @@
guard_z = 0;
guard_heading = 0;
swarmInfoPtr = NULL;
+#ifdef CRIPP_Z
+ fixz = 1;
+#endif

// SaveSpawnSpot();
--- npc.h 2007/12/17 02:26:10 1.15
+++ npc.h 2007/12/19 18:08:39 1.16
@@ -225,6 +225,9 @@
//aza77 GWFear
void SpawnFearGridNPC(const char* feargrids, float in_x, float in_y, float in_z);
#endif
+#ifdef CRIPP_Z
+ sint16 fixz;
+#endif

protected:
--- spawn2.cpp 2006/11/01 20:36:21 1.3
+++ spawn2.cpp 2007/12/19 18:08:39 1.4
@@ -67,7 +67,11 @@
Spawn2::Spawn2(int32 in_spawn2_id, int32 spawngroup_id,
float in_x, float in_y, float in_z, float in_heading,
int32 respawn, int32 variance, int32 timeleft, int32 grid,
+#ifdef CRIPP_Z
+ uint16 in_cond_id, sint16 in_min_value, sint16 fixZhop)
+#else
uint16 in_cond_id, sint16 in_min_value)
+#endif
: timer(100000)
{
spawn2_id = in_spawn2_id;
@@ -82,6 +86,9 @@
condition_id = in_cond_id;
condition_min_value = in_min_value;
npcthis = NULL;
+#ifdef CRIPP_Z
+ FixedZ = fixZhop;
+#endif

if(timeleft == 0xFFFFFFFF) {
//special disable timeleft
@@ -169,6 +176,9 @@
npcthis = npc;
npc->AddLootTable();
npc->SetSp2(spawngroup_id_);
+#ifdef CRIPP_Z
+ npc->fixz = FixedZ;
+#endif
entity_list.AddNPC(npc);
//this limit add must be done after the AddNPC since we need the entity ID.
entity_list.LimitAddNPC(npc);
@@ -229,7 +239,11 @@
MYSQL_RES *result;
MYSQL_ROW row;

+#ifdef CRIPP_Z
+ MakeAnyLenString(&query, "SELECT id, spawngroupID, x, y, z, heading, respawntime, variance, pathgrid, timeleft, _condition, cond_value, fixZ FROM spawn2 WHERE zone='%s'", zone_name);
+#else
MakeAnyLenString(&query, "SELECT id, spawngroupID, x, y, z, heading, respawntime, variance, pathgrid, timeleft, _condition, cond_value FROM spawn2 WHERE zone='%s'", zone_name);
+#endif

if (RunQuery(query, strlen(query), errbuf, &result))
{
@@ -237,7 +251,11 @@
while((row = mysql_fetch_row(result)))
{
Spawn2* newSpawn = 0;
+#ifdef CRIPP_Z
+ newSpawn = new Spawn2(atoi(row[0]), atoi(row[1]), atof(row[2]), atof(row[3]), atof(row[4]), atof(row[5]), atoi(row[6]), atoi(row[7]), atoi(row[9]), atoi(row[8]), atoi(row[10]), atoi(row[11]), atoi(row[12]));
+#else
newSpawn = new Spawn2(atoi(row[0]), atoi(row[1]), atof(row[2]), atof(row[3]), atof(row[4]), atof(row[5]), atoi(row[6]), atoi(row[7]), atoi(row[9]), atoi(row[8]), atoi(row[10]), atoi(row[11]));
+#endif
//newSpawn->Repop(repopdelay);
spawn2_list.Insert( newSpawn );
}
@@ -260,12 +278,20 @@
MYSQL_RES *result;
MYSQL_ROW row;

+#ifdef CRIPP_Z
+ if (RunQuery(query, MakeAnyLenString(&query, "SELECT id, spawngroupID, x, y, z, heading, respawntime, variance, pathgrid, _condition, cond_value, fixZ FROM spawn2 WHERE id=%i", spawn2id), errbuf, &result))
+#else
if (RunQuery(query, MakeAnyLenString(&query, "SELECT id, spawngroupID, x, y, z, heading, respawntime, variance, pathgrid, _condition, cond_value FROM spawn2 WHERE id=%i", spawn2id), errbuf, &result))
+#endif
{
if (mysql_num_rows(result) == 1)
{
row = mysql_fetch_row(result);
+#ifdef CRIPP_Z
+ Spawn2* newSpawn = new Spawn2(atoi(row[0]), atoi(row[1]), atof(row[2]), atof(row[3]), atof(row[4]), atof(row[5]), atoi(row[6]), atoi(row[7]), timeleft, atoi(row[8]), atoi(row[9]), atoi(row[10]), atoi(row[11]));
+#else
Spawn2* newSpawn = new Spawn2(atoi(row[0]), atoi(row[1]), atof(row[2]), atof(row[3]), atof(row[4]), atof(row[5]), atoi(row[6]), atoi(row[7]), timeleft, atoi(row[8]), atoi(row[9]), atoi(row[10]));
+#endif
spawn2_list.Insert( newSpawn );
mysql_free_result(result);
safe_delete_array(query);
--- spawn2.h 2006/06/20 02:36:21 1.2
+++ spawn2.h 2007/12/19 18:08:40 1.3
@@ -35,7 +35,11 @@
float x, float y, float z, float heading,
int32 respawn, int32 variance,
int32 timeleft = 0, int32 grid = 0,
+#ifdef CRIPP_Z
+ uint16 cond_id = SC_AlwaysEnabled, sint16 min_value = 0, sint16 fixZhop = 1);
+#else
uint16 cond_id = SC_AlwaysEnabled, sint16 min_value = 0);
+#endif
~Spawn2();

void LoadGrid();
@@ -74,6 +78,9 @@
int32 grid_;
uint16 condition_id;
sint16 condition_min_value;
+#ifdef CRIPP
+ sint16 FixedZ;
+#endif
};

class SpawnCondition {
--- waypoints.cpp 2007/12/01 18:11:14 1.7
+++ waypoints.cpp 2007/12/19 18:08:40 1.8
@@ -670,7 +670,9 @@
newwp.x = atof(row[0]);
newwp.y = atof(row[1]);
newwp.z = atof(row[2]);

if(zone->map != NULL && RuleB(Map, FixPathingZWhenLoading) ) {
// Experimental. This code will send any waypoint that is 'in the air' down to ground level.

@@ -685,14 +687,17 @@
float newz = zone->map->FindBestZ(n, dest, NULL, NULL);
// The following test is a sanity check. 45 is an arbitrary value, chosen during testing
// because all the Z co-ordinates of the waypoints in The Grey where <45 units above the ground.
if( (newz > -2000) && ABS(newz-dest.z) < RuleR(Map, FixPathingZMaxDeltaLoading)) {
#ifdef CRIPP_Z
if (fixz != 0) {
#endif
newwp.z = newz+1;
// printf("Updated Z for Grid %d, Waypoint %d from %.3f to %.3f\n", grid, newwp.index,dest.z,newwp.z);
#ifdef CRIPP_Z
}
#endif
}
//else if(newz > -2000)
// printf("Delta Z %.3f too big for Grid %d, Waypoint %d from %.3f to %.3f\n", ABS(newz-dest.z), grid, newwp.index,dest.z,newz);
}
}

newwp.pause = atoi(row[3]);
Waypoints.push_back(newwp);

added definition CRIPP_Z to toggle to default or not... just incase it didnt work.. but i tested once and it seemed to work..

let me know :)

EDIT:: forgot.. you have to add column in spawn2 table... fixZ tinyint[4] 0 no null default 1

[cavedude]

Sweet! I'll try this out on my test box when I get home.

[Bishop4351]

Mental note to install EQ at work for "testing".

[Derision]

As for mobs in the water... there currently is no way for us to tell where water exists in the map.

I found this old post by Windcatcher:

http://www.eqemulator.net/forums/showthread.php?t=12235&highlight=.wld

Which talks about how water/lava region information is stored in the zone S3D file. Maybe with this, along with the OpenZone source code, and the .WLD reference linked here:

http://www.eqemulator.net/forums/showthread.php?t=11094&highlight=.wld

I might be able to figure out how to extract this information from the S3D into a format that can be loaded and used in the emulator. I'll give it a shot.

[narcberry]

Or instead of doing it right you could hack the solution. "Fix it quick now so we can fix it again later", that's always been my motto:

Apply fixz code only to mobs whose previous position conformed to the fixz code. IE, mobs that start on the ground stay on the ground. Mobs that start out on rocks or swimming are left alone.


Okay, I'll shut up now. Oh, and awesome work.

[Cripp]

did a little more testing.. and i guess my little fix can only disable fixZ for the whole zone because...

float newz = zone->map->FindBestZ(n, dest, NULL, NULL);

...it loads the bestZ for the whole zone not just the mob i guess..


gonna try it with FixZWhenLoading disables and on SendTo/onWayPoints enabled..

might have to add a few more checks in waypoints.cpp too.. ill keep posted.

[Cripp]

ahh found way to make it work..

waypoints.cpp..
--- waypoints.cpp 2007/12/01 18:11:14 1.7
+++ waypoints.cpp 2007/12/19 18:08:40 1.8
@@ -670,7 +670,9 @@
newwp.x = atof(row[0]);
newwp.y = atof(row[1]);
newwp.z = atof(row[2]);

if(zone->map != NULL && RuleB(Map, FixPathingZWhenLoading) ) {
// Experimental. This code will send any waypoint that is 'in the air' down to ground level.

@@ -685,14 +687,17 @@
float newz = zone->map->FindBestZ(n, dest, NULL, NULL);
// The following test is a sanity check. 45 is an arbitrary value, chosen during testing
// because all the Z co-ordinates of the waypoints in The Grey where <45 units above the ground.
if( (newz > -2000) && ABS(newz-dest.z) < RuleR(Map, FixPathingZMaxDeltaLoading)) {
#ifdef CRIPP_Z
if (fixz != 0) {
#endif
newwp.z = newz+1;
// printf("Updated Z for Grid %d, Waypoint %d from %.3f to %.3f\n", grid, newwp.index,dest.z,newwp.z);
#ifdef CRIPP_Z
}
#endif
}
//else if(newz > -2000)
// printf("Delta Z %.3f too big for Grid %d, Waypoint %d from %.3f to %.3f\n", ABS(newz-dest.z), grid, newwp.index,dest.z,newz);
}
}

newwp.pause = atoi(row[3]);
Waypoints.push_back(newwp);

instead of old..



edit: untested as of now... going to test now will edit with results.

edit2: just tested with similar results... gona mess around till i get something working then ill post =D

edit3: kinda stumped :( edited all posts to what im working with currently(changed all boolean to sint, etc.)..

im a noob haxor, someone help me out :P

[narcberry]

This is great work and all but I think it is distracting from what should really be developed, a pathing function. Fixing the z is just a temporary fix. We need proper pathing. When we do we will throw away all these fixes. And throwing away all of those man-hours makes for a lot of these: <insert tear emoticon here (no tear emoticon is maybe even sadder /tear)>

I am working on a couple pathing algorithms and am wondering if anyone has done some work on this already?

I'm using 2 strategies to reduce the complexity of the pathing algorithm:
(1) weighing node paths based on location between point a and b. (2) reducing the data set by pathing between the larger map subspaces then fine tuning the path.

The 3d rendering on page1 shows the triangles in the map to be grouped into larger square regions. You can build paths based on these larger square regions first by drawing a line between persuer and persuant than dropping it onto the map. Then building a path inside each square from entry to exit point.

This is really succesful for maps that dont require much pathing such as the karanas. But it has troubles in dungeons, where pathing is actually needed. I'm still looking at possible ways to break maps up into smaller 3d spaces that make sense as a graph. This will have to be done when a zone loads, since it is sucks the life force from any cpu. The first time a zone loads this 3d map could be generated and saved for future use.

My problem is this next step is like... a lot of work. I'm wondering if it wouldn't be better to just build path maps by hand.

Or be lazy and have zones listen to player movements and mutate pathing maps from those coordinates.



Either way, this is problem #1 in the emulator and should get more attention.

[Derision]

As for mobs in the water... there currently is no way for us to tell where water exists in the map.


I spent a couple of days working on the water detection and it's looking good (albeit frustrating
at times working with the WLD data!).

I modified Azone to build the BSP tree from the 0x21 fragment as well as process the 0x22 and 0x29 region
fragments. I then wrote a function which given hard-coded X,Y,Z co-ordinates would walk the BSP tree to
the leaf node those co-ordinates are in and return whether or not the co-ordinates are in a special region (water, lava).

I then transplanted the code into Daeken's Openeq (aka freaku) source so I could fly around
zones and test it better with a visual on-screen indication of whether the code thought I was under water.
It seems to work well (I would say flawlessly, but it needs more testing).

Next step is to optimise it/tidy up the code , mod azone to write out a 'water map' file and then put some code
into EQEmu to make use of it. This could be used for fishing quite easily by projecting forward and down from
the player and testing whether the hypothetical end of the fishing line is under water.

One thing I noticed is that although some zone files have the 'special regions' flagged as either water
or lava, some don't, so I will probably have to make azone accept another parameter telling it whether
to mark the regions as water or lava by default if there is no indication in the WLD file of what the region
is.

I have only tested zones in S3d format so far, so I don't know whether this can be adapted to work with newer zones in EQG format.

[Derision]

Well, the creation of the 'water maps' by azone and the processing of them in the emulator is done. I modified the existing #bestz command to tell you whether the code thinks you are in water/lava or nowhere special (on the ground) for debugging purposes:

Ground
http://www.rama.demon.co.uk/onland.jpg

Water

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

Lava

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

I modified waypoints.cpp to not use BestZ when the mobs where in water or headed to a point in water, but they are still hopping in the Cauldron. Not sure why that is, but I will look into further to see whether it is fixable in code.

If it isn't, I'll post what I've done anyway, as I'm sure it will come in handy for fishing at least!

[cavedude]

I've been waiting for this for ages, top notch work!

[Derision]

Cavedude had mentioned one temporary solution was to give the swimmers the levitation spell - This keeps them steady at what ever grid they are on.

I only just realised what a problem pathing in water was, even without the BestZ code. I.e. the client appears to make all the mobs sink to the bottom of the water. You can see this in powater at -232.25,-699.5,-98.125 ... mobs being put in a particular spot by the server, then sinking, and then popping up again when the server sends the next movement update.

I added an extra field to the Mob class, inWater, initialised to false. In the waypoint movement routine, I put a check to see if the mob is underwater and it wasn't previosly (Mob->inWater==false). If this is the case, it puts flymode 1 on the mob and sets Mob->inWater=true.

Likewise if the mob is not in water when it was on the last check, it turns the flymode off.

This seems to help in Powater and Kedge. The mobs hop once after the zone is loaded until they pass through the waypoint routine the first time, and then they swim as they should without the client making them sink. It won't help with static mobs which aren't on grids. They will just spawn and fall to the bottom and stay there. I guess I could put some code in the NPC spawn routine to check if they are in water and turn the flymode 1 on at that point. This would work for the static spawns and stop the initial hop for the wanderers.

I don't know whether there is any downside to doing this. Needs more testing. I wonder how the live servers handle it?

[Derision]

I had a PM about when I am going to release these changes I have been working on. I will put something out this week. It may not be in a form that is ready for merging into CVS, but at least it will give people who are interested a chance to test the changes and report on any issues etc.

[KLS]

If a solution like this were to come into usage I think we'd need to inevitably figure out how to create a water map from an .EQG file too.

[moydock]

Not sure if this has been fixed since build 1070 but my mobs still go under the world when trying to go through a hill, the hill can be little more than a bump too. What i've found is if you give precise waypoints, that only take him on a straight line, polygon to polygon, he will never go under the world. They can climb giant mountains like this without falling under the world. Is there a way a mob could calculate this himself when he sees there's a mountain in his way?

[Derision]

My mobs still go under the world when trying to go through a hill, the hill can be little more than a bump too. What i've found is if you give precise waypoints, that only take him on a straight line, polygon to polygon, he will never go under the world.

The issue with some zones is that the Verant/SOE designers put in a base ground mesh and then put mountains on top of that, so if a waypoint sends a mob under the ground, the BestZ code looks down and sees the lower ground level under the mountain and sends the mob down there.

I had experimented with further fixes to the BestZ code to look up and down and decide which was the more likely ground level the mob should be it, but it was getting messy, so I stopped work on that.

The tool I am currently working on it plots the paths between waypoints, looks for collisions and inserts extra waypoints to avoid the collisions. In very uneven terrain, it will put an extra waypoint on both edges of a polygon to lead the mob safetly across it. It also inserts extra waypoints to keep the mob close to the ground and not attempt to path through the air.

This is done 'offline' to reduce the overhead at runtime, however a grid that has, say 20 waypoints, can easily turn into one that has 200+ when processed like this, so there is extra overhead for the server in terms of extra memory to store the waypoints and CPU to process them, although I can't really quantify the latter.


It is really only designed for auto-fixing outdoor paths at the moment, but I haven't got an ETA as yet as although it fixes paths well in a lot of cases, there are still some cases where I set it off fixing a zone and it will find some unhandled set of geometry conditions or a bug where it gets into a loop. The job is then to analyse the set of conditions that causes that and put in logic to either to be able to fix that waypoint or to safetly exit the auto-fix routine to tell the user he will have to manually insert waypoints to get around it.

[moydock]

Great to hear man, this would be wonderful for designing new content. My #1 headache is waypoints. Don't give up! Don't let the hills win! <3

[Derision]

Don't give up! Don't let the hills win! <3


I've not given up, although there have been frustrating days that I wanted to, in fact I have worked on this every day for almost a month, often in work, when there is a quiet moment. It's taking
a lot longer than I thought, especially the outdoor auto-fix features which I am a concentrating most on. It's largely a case of one step forward, two steps back, although I am slowly
getting there. I've had to make a couple of mods to azone to fix some issues with the map files, and also to the LineIntersectsFace/Zone functions to cater for intersections right on the edge of a polygon (I've learned a LOT about 3D geometry doing this ... I didn't know what a Normal vector was a month ago :) )

I think I made a bit of a breakthrough today with a (on the face of it) reliable method of detecting if a point
is 'under the world', rather than just underground, based on the algorithm used for back-face culling. I am hoping this may lead to a reduction in the number of waypoints that need to be inserted
to make the path follow the ground, but I need to try this out next week.

Forgive the rambling, all I wanted to say was I am still on the case, but still no ETA (still several weeks off). What I will say is you will need Python/pygame installed to
use this (because OpenEQ uses those for it's UI, and I kept it, because although I didn't know Python, it was easier than building a new UI from scratch), and also you will
need to build new MAP files with a patched version of azone (I posted in the Development/Bugs section about one of the fixes required about a month ago, but there is one
more azone patch required that I haven't got around to posting yet).

For what it's worth, here's some current screenshots:

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

I added a mode to display the polys instead of textures:

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

And also an overhead view:

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