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]

Originally Posted by 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.

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]

Originally Posted by KhaN

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]

Originally Posted by KhaN

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.