MOB Line Of Sight

[fathernitwit]

Hello,

So it is officially bothering me that mobs come flying through the ceiling in dungeons... so im going to take a look at fixing it..

what is the current status of whatever exists?
Is there pathfinding and/or LOS code allready somewhere? was there old map-reading crap somewhere? or is it all basically non-existent at this time?

Does anybody have ideas on how they were thinking of implementing it?

Any information would be greatly appriciated, hopefully it will save me some time and make me more productive :)

[killspree]

WR has/had line of sight, but I don't know if it was ever added to cvs.

[govtcheeze]

This is probably the best thread on the subject:

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

[fathernitwit]

OK,

well I am going to make the assumption that the LOS crap in the zone server works for now... so the issue is getting map files from the zones...

I have used DZoneConverter to get a .wld file (which is strangely in the old file format, not the luclin file format)... I have a wld file reader reading that guy in... now to produce a map. (I decided to go for wld->map, and skip an intermediate format, unless somebody tells me a reason otherwise.)

I have taken a look at the map format, and it appears to be a simple quad tree.

It startes with two unsigned long counters of vertexes and faces.
Then, theres an array of vertexes, followed by an array of faces (which use the vertexes), followed by a recursive quad tree structure, dividing x and y.
structures for vertex and face (from map.h)

struct VERTEX {
unsigned long order;
float x, y, z;
};

struct FACE {
unsigned long a, b, c; //vertexs
float nx, ny, nz, nd;
};


the quad tree starts with:

struct nodeHeader {
float minx;
float miny;
float maxx;
float maxy;
unsigned long nfaces;
};

if nfaces is not 0, then it is immediately followed by an array of unsigned longs representing offsets into the faces array which are faces in that node of the quad tree.
if nfaces is 0, then it is a branch node. The next byte contains basically a bit-based counter of which nodes that quadtree node is split into. And it is then followed by recursive instances of nodes, starting with a node header.


So, the file format isnt going to be that bad... I will code up a quad tree tomorrow. It isnt going to be an 'optimal' quad tree... but it shouldent be too difficult to get done. I just hope DZoneConverter is actually spitting up the correct .wld file...

[fathernitwit]

well,

I have a program to generate a good (i hope) quadtree from a .wld file... and then write it out into the .map format... man, i forgot how much work a quadtree really is... damned cube-triangle intersection!


I dont know about the other version (zone2map), but mine is spitting out pretty big files... theres ~2Mb of pure vertex and face data in the zone files (that I looked at), so I dont see how they could be any smaller than that...

Does anybody have any clue if 'they' were trimming the data somehow?

Anyways, eqemu will read in the map file, and reproduce the quadtree. Once it is loaded, it pisses off spawns, im not sure exatly how, but the zone is pretty much empty with a few exceptions, and once I saw all the MOBs piled up in one place, unable to move.

I am looking at the mob aggro code now.. it dosent seem to use this map at all... and whatever is using it, is broken... so I might just change the way it works...

I am not 100% convinced that the way that it is set up right now actualy works, or works very well.. it seems to just find the 'tallest' object in the current quadtree node, and sees if it can see over it... dosent make a lot of sense to me.

The way I am looking at doing it is a ray from the MOB (head) to the target (head/center, something), and seeing if that line intersects any of the faces in the node that the MOB is in and the node that the target is in.

[sotonin]

Winter's Roar apparently has it working. And supposedly the same code is in the CVS. Who knows if that is true or not though because it was never used in the cvs. There may be outdated los code in the cvs. Maybe Wiz will help you out with his los code, then again maybe not.

I will say this, if you can get LOS working in the cvs it will be the single greatest thing accomplish in a while ) LOS is one of the biggest flaws with eqemu at the moment.

looking forward to it.

[govtcheeze]

Following the directions in the post I linked, I created a map file of gukbottom and verified it was loaded successfully in the zone output. However, when I attacked a frog in the bottom of the zone, I created a huge train from all directions.

This leads me to believe either
a) the instructions for creating the files are incorrect
b) the code does not support map files correctly

I believe it is the second, since the file was loaded in correctly.

[Wiz]

I wrote a fairly well-functioning LOS the other day - also have combat pathing code using it.

I'll paste it here for reference. It essentially draws an angle to the target and checks for blockers.


bool Mob::CheckCoordLos(float cur_x, float cur_y, float cur_z, float trg_x, float trg_y, float trg_z, float perwalk_x, float perwalk_y, float perwalk_z) {
if (zone->map == 0)
{
return true;
}
float dist_x = cur_x - trg_x;
if (dist_x < 0)
dist_x *= -1;
float dist_y = cur_y - trg_y;
if (dist_y < 0)
dist_y *= -1;
float dist_z = cur_z - trg_z;
if (dist_z < 0)
dist_z *= -1;
if (dist_x <= dist_y && dist_z <= dist_y)
{
perwalk_x /= (dist_y/dist_x);
perwalk_z /= (dist_y/dist_z);
}
else if (dist_y <= dist_x && dist_z <= dist_x)
{
perwalk_y /= (dist_x/dist_y);
perwalk_z /= (dist_x/dist_z);
}
else if (dist_y <= dist_z && dist_x <= dist_z)
{
perwalk_y /= (dist_z/dist_y);
perwalk_x /= (dist_z/dist_x);
}
int steps = 300000; //Just a safety check to prevent endless loops.
while (steps > 0) {
steps--;
//X traj
if (cur_x < trg_x)
{
if (cur_x + perwalk_x < trg_x)
cur_x += perwalk_x;
else
cur_x = trg_x;
}
if (cur_x > trg_x)
{
if (cur_x - perwalk_x > trg_x)
cur_x -= perwalk_x;
else
cur_x = trg_x;
}
//Y traj
if (cur_y < trg_y)
{
if (cur_y + perwalk_y < trg_y)
cur_y += perwalk_y;
else
cur_y = trg_y;
}
if (cur_y > trg_y)
{
if (cur_y - perwalk_y > trg_y)
cur_y -= perwalk_y;
else
cur_y = trg_y;
}
//Z traj
if (cur_z < trg_z)
{
if (cur_z + perwalk_z < trg_z)
cur_z += perwalk_z;
else
cur_z = trg_z;
}
if (cur_z > trg_z)
{
if (cur_z - perwalk_z > trg_z)
cur_z -= perwalk_z;
else
cur_z = trg_z;
}
PNODE pnode = zone->map->SeekNode( zone->map->GetRoot(), cur_x, cur_y );
if (pnode != 0)
{
int *iface = zone->map->SeekFace( pnode, cur_x, cur_y );
if (*iface == -1) {
return false;
}
float tmp_z = 0;
float best_z = -999999;

while(*iface != -1)
{
tmp_z = zone->map->GetFaceHeight( *iface, cur_x, cur_y );
if (tmp_z-1 <= cur_z && tmp_z > best_z)
{
best_z = tmp_z;
}
iface++;
}
if (best_z == -999999)
{
return false;
}

int diff = (best_z) - (cur_z);
if (diff <= 1 && diff >= -1)
{
return false;
}

}
if (cur_y == trg_y && cur_x == trg_x && cur_z == trg_z)
{
return true;
}
}
return true;
}

Rogean should be putting this into the source, but he's lazy.

[Wiz]

well,

I have a program to generate a good (i hope) quadtree from a .wld file... and then write it out into the .map format... man, i forgot how much work a quadtree really is... damned cube-triangle intersection!


I dont know about the other version (zone2map), but mine is spitting out pretty big files... theres ~2Mb of pure vertex and face data in the zone files (that I looked at), so I dont see how they could be any smaller than that...

Does anybody have any clue if 'they' were trimming the data somehow?

Anyways, eqemu will read in the map file, and reproduce the quadtree. Once it is loaded, it pisses off spawns, im not sure exatly how, but the zone is pretty much empty with a few exceptions, and once I saw all the MOBs piled up in one place, unable to move.

I am looking at the mob aggro code now.. it dosent seem to use this map at all... and whatever is using it, is broken... so I might just change the way it works...

I am not 100% convinced that the way that it is set up right now actualy works, or works very well.. it seems to just find the 'tallest' object in the current quadtree node, and sees if it can see over it... dosent make a lot of sense to me.

The way I am looking at doing it is a ray from the MOB (head) to the target (head/center, something), and seeing if that line intersects any of the faces in the node that the MOB is in and the node that the target is in.

Contact me in IRC. I'm pretty much the expert on map files nowadays, and have written a lot of stuff with them.

[KhaN]

Contact me in IRC. I'm pretty much the expert on map files nowadays, and have written a lot of stuff with them.
WHY the hell use those damn fuck map file when you can directly read informations from WLD files (convert dsconverter code to C++, not that hard). Afterall, map files only contain infos from WLD, so why use map files when you can directly use the source, aka WLD ?

Im sorry, but i dont understand this logic ...

[Wiz]

Contact me in IRC. I'm pretty much the expert on map files nowadays, and have written a lot of stuff with them.
WHY the hell use those damn fuck map file when you can directly read informations from WLD files (convert dsconverter code to C++, not that hard). Afterall, map files only contain infos from WLD, so why use map files when you can directly use the source, aka WLD ?

Im sorry, but i dont understand this logic ...

So why haven't you already written .wld reading functions?

[KhaN]

So why haven't you already written .wld reading functions?
Because we have 35 class to code for EQA and LOS is far from being first in our todo list ? Dont get me wrong, but WC already made half the job with its DSConverter, i just dont get this logic of not working with the source (WLD). Everytime a new zone will come out, you will have to do your map file, add it to your server directory, and blablabla ... this doesnt make sense.

[Wiz]

So why haven't you already written .wld reading functions?
Because we have 35 class to code for EQA and LOS is far from being first in our todo list ? Dont get me wrong, but WC already made half the job with its DSConverter, i just dont get this logic of not working with the source (WLD). Everytime a new zone will come out, you will have to do your map file, add it to your server directory, and blablabla ... this doesnt make sense.

I'm gonna take a wild guess here.

1) Because noone has written any finished code for it. I could try, but I don't have the time to figure out an entire file format either right now.

2) Aren't WLD files considerably larger and bulkier? You'd have to read pretty much the entire file into memory, aka extra RAM. .map provides everything you need, really.

Complaining about others not solving something you have no intention of solving yourself is a pretty lame way to go.

[melquiades]

1) Because noone has written any finished code for it. I could try, but I don't have the time to figure out an entire file format either right now.
It's perfectly correct, but does not answer the 'take the information from the source' argument, which is quite valuable in CompSci afaik


2) Aren't WLD files considerably larger and bulkier? You'd have to read pretty much the entire file into memory, aka extra RAM. .map provides everything you need, really.

After processing you get and keep what you need, that is a space partition. No need to keep file format structure and logic. basically, if you get the same info, you get the same size, whether from WLD or MAP files.

No need to complain about the offer you made. Actually noone can pretend do everything in EQEMu, so its sane to post comments about someone's offer to do something, if it is contributive point of view that can save time, now or later. Thus the point about WLD files. [/quote]

[KhaN]

Complaining about others not solving something you have no intention of solving yourself is a pretty lame way to go.

Yeah, look like you read only what you really want to read, i never said i dont want to resolve the LOS problem, i just have a todo list and as my server isnt playable, LOS isnt one of my priority, this is called "organisation", kk thx~

Concerning WLD, you would only need to read fragments, im not a WLD expert, but im pretty sure WC could explain better here. Also, you cannot convert a post luclin zone to a map file, so you would fix only LOS for "old world".

But i will just drop, i really dont want this to turn in a flame post, i pretty much estimate you Wiz, but like always you are always right, and others are always wrong.

[Wiz]

Complaining about others not solving something you have no intention of solving yourself is a pretty lame way to go.

Yeah, look like you read only what you really want to read, i never said i dont want to resolve the LOS problem, i just have a todo list and as my server isnt playable, LOS isnt one of my priority, this is called "organisation", kk thx~

Concerning WLD, you would only need to read fragments, im not a WLD expert, but im pretty sure WC could explain better here. Also, you cannot convert a post luclin zone to a map file, so you would fix only LOS for "old world".

But i will just drop, i really dont want this to turn in a flame post, i pretty much estimate you Wiz, but like always you are always right, and others are always wrong.

I think you're pretty much right about the .wld files, but you went into this with a fairly snippy and insulting tone, so I'm not sure why you expected a nice answer.

The thing is though - until someone is ready to code the usage of .wld files and fetch the exact same information,
we might as well use the .maps. If the information extracted is the same, the code is going to be same.

Really, though, you pretty much shot in with a "Hey, idiot, why the fuck are you doing it like that?". I suggest adjusting your tone for "suggestions", so they don't sound like outright complaints.

[Mongrel]

My zone viewer reads wld files (zone geometry) just fine and is written in C++. For zone geometry you really only need three or four types of fragments (0x21, 0x22 and 0x36 if my memory serves me right), though texture info might be handy as well (for zone borders and other transparent stuff), but the 0x31,0x30,0x05,0x04 and 0x03 fragments are reeeaaally easy to read.
Not sure though if it's fast enough for a zone bootup (loading times need to be fairly short).

[Wiz]

My zone viewer reads wld files (zone geometry) just fine and is written in C++. For zone geometry you really only need three or four types of fragments (0x21, 0x22 and 0x36 if my memory serves me right), though texture info might be handy as well (for zone borders and other transparent stuff), but the 0x31,0x30,0x05,0x04 and 0x03 fragments are reeeaaally easy to read.
Not sure though if it's fast enough for a zone bootup (loading times need to be fairly short).

What's the loading times? If nothing else, it could work for static servers.

If we could add texture reading so you can determine when it crosses a "hollow" wall or you're in water, that'd be a very nice addition.

[govtcheeze]

As this is a huge step in the right direction, I want to thank everyone who is working on this problem and Wiz for posting the code. It may not be the optimal, all-encompassing solution, but if it works just on SOME zones for now its a good thing. LOS is the last major flaw I see in emu, so any type of solution, whether temporary, working for only some zones, or whatever I see as A Good Thing <tm>.

[fathernitwit]

Also, you cannot convert a post luclin zone to a map file, so you would fix only LOS for "old world".

What is the reasoning behind this statement? Just because there are no programs allready to do it?


Here are my reasons for going from an intermediate file:
1. Somebody else allready wrote the LOS code... this has been proven to me to be wrong, since it dosent work very well.
2. It takes CONSIDERABLY longer to parse a .WLD file than reading in these map dudes... even though my map files are ending up larger. And there are a few places that I could make .map reading even faster.
3. It saves the quadtree directly, you dont have to calculate it. This is a very expensive operation. On big zones it takes up to 30 seconds for my machine to read a wld file and produce the quadtree. That wont work for zone bootups at all.
4. It increases the long term longevity of the conversion program. If the w3d/wld files change, somebody dosent need to touch the emu or conversion program, they can just change the util to extract the world object. Theres a lot more zone reading utils than any other 3rd party programs.

I also have not been able to find any C++ which will get a .wld out of a zone directly, without using the windows specific eqinside.dll. So there would be that step anyways on a zone update.


My original plan was to load directly from .wld and produce a quadtree, but something is majorly wrong with the old .wld reading code I have, because the bounding box of the zone is completely wrong (much larger)... so I am currently working off .obj files spit up from DZoneConverter. I havent been able to figure out how DZC is different than my own reading code, I looked it over pretty well.

[fathernitwit]

on a more pleasant tone.

I think I have zomething resembling LOS working...
- I can officially walk around crushbone castle and into the little nook in the middle without anything coming out from the inside.
- When I go inside, in close quarters, a few mobs hop through the walls, but they are close enough to almost accept it.
- There are a few mobs stuck rigth now, you have to practically stand on them to get them to attack you.

I am accomplishing this with, what I think is a much more accurate solution, checking to see if the ray from the mob to the target intersects anything in the world. This might prove to be too expensive, so we can figure out some approximation. The downfall is that I dont know that it is actually working, no idea how to really 'test' it besides impirical tests like I did.


I would REALLY appriciate input on how the hell I can debug thing thing. It is very difficult to debug because I dont know where my problems lie.
I have 3 very complex pieces of code:
- map reader
- quadtree generation (triangle-cube intersection)
- LOS checker (ray-triangle intersection)

and I dont know which one is broken. I was having map scale problems forever (trying to read from .wld), and because of the errors at really close range, I think there are still some, but I cannot visualize this crap. My mobs that are stuck are seeing some random triangle in very close proximity to them which is not there.
It would be extremely useful if somebody could advise me on how I might try to visualize this crap on the client... any ideas on how I can get it to display SOMETHING.... I was thinking spawned items/people or anything... i just havent figured out what will work (and stay suspended in the air).

[RangerDown]

There is a #checklos command that might be helpful. Or at least, seems better than having to run around getting an aggro mob to attack you, specially since many mobs aren't aggro by default.

I assume that #checklos uses the same routines that the part of the AI that determines KOS does... but I'm not 100% certain on that.

[sotonin]

This is just a wild guess here, but are objects and such in the map files? Like a broken table or pot sitting on the ground... Perhaps some sort of item like this is in the way causing it to not see you? And as for the aggros. perhaps the geometry in the zone is somewhat poor and there's a small "seam" between two walls or such?

again, far fetched. Admittedly i don't know what I'm talking about. =)

[Mongrel]

What's the loading times? If nothing else, it could work for static servers.

Can't say that right now, since I'm also loading textures, objects and other stuff, but I would guess a second or two. It's quite fast, since it's really not that complex.

[bbum]

Also, you cannot convert a post luclin zone to a map file, so you would fix only LOS for "old world".

hey, sounds good enuf to me :P

[trevorsm7]

I would suggest that you write a quick little OpenGL/Direct3D viewer to pump out the triangle data so you can visualize it. It wouldn't really be too hard to throw together, and it would let you move around to the problem areas and see if there are any loose triangles in the way that shouldn't be there. This would pretty much tell you if 1) you're reading the map data correctly and 2) if your quadtree is okay.

If those were both okay, then you could try and put your LOS code into the viewer. You could have it set up so you input two points for your line, and have it draw the line in red if there's a blocker or green if it's okay.

[trevorsm7]

Oh, and by the way, how are you deciding when to have a MOB check its LOS? Are you checking for all PCs/NPCs within a certain radius and then doing the LOS check? Also, if you want any help with the Quadtree/triangle-object intersection stuff, I might be able to help a bit since I've been doing the same stuff with the 3D engine I'm working on.

[smogo]

checking for all PCs/NPCs within a certain radius and then doing the LOS check.

That would prolly be the most efficient in most zones, except maybe some dungeons / cities, where LOS can take out most radius checks. Aggro-radius is already in standard code btw.

As for the viewer, Mongrel had set up a quite nice one, and there is the freakU project going on. Both read from WLD files, though i know not if they use BSP or LOS (beyond OpenGL's internals) yet.

[jimbox114]

But everybody has to love walking through unrest and having 20 ghouls attack them?

[trevorsm7]

As for the viewer, Mongrel had set up a quite nice one, and there is the freakU project going on. Both read from WLD files, though i know not if they use BSP or LOS (beyond OpenGL's internals) yet.

I meant a viewer to check his .map file (not a wld file) so he could see if he was reading it in correctly/if he was partitioning the level right. It would be a good way to check each of the three possible problem areas (reading/quadtree/LOS), as well as display the data visually.

Then again, I'm not exactly sure what data is getting put into the .map file, since I've never messed with this zone converter program he's using. I'm assuming it's just pulling out the raw triangle (solid only) and vertex data--which would probably be all that's necessary for LOS checking.

[fathernitwit]

just as a quick update...
- I have been working with Wiz a bit and have gotten this working for all (that I know of) zones. Wiz is working on pathing using my new maps.
- I have just modified my .map format, so it needs more testing.
- Wiz and I are testing it, then we will release something.
- Having a hell of a time getting the zone converter program to work on windows.
- Reading from s3d directly into .map, which get read by zone.
- I have a command written to dump your current partition to an obj file so it can be viewed in a renderer, for debugging.

[Ausfox]

So the problem is that AI can't actually see the world and you have to tell it where the walls, etc are?

[govtcheeze]

This month old post no longer applies...LOS is working with 5.8.

[Ausfox]

So what your saying is because its done, your not allowed to improve or discuss it. :roll:

[mattmeck]

no he is saying the issues discussed in this thread are already fixxed so there isnt a pont in discussing fixxes for whats already fixxed.

Stop trying to start issues kkthx~