Some thoughts on setting up zone movement points

ScotchTape · #1 03-22-2002, 01:58 AM

Entre development thoughts on movement.

When I think of pathing points, I think of a collection of points in a zone that mobs follow giving the illusion of movement. Perhaps this could at some later point even be scripted, such that

SPAWN 0
AT TIME T
MOVE TO X1, Y1, Z1
AT TIME T+10
MOVE TO X2,Y2,Z2

but scripting is a later thing.

Right now, unless the active build has it, I don't see any movement code of this nature built in yet. So I'm going to put out some thoughts on it, as I haven't had a chance to sit down and do it.

I was thinking that a zone needs to have a collection of path points, and that within a zone there are two kinds of movement: spawngroup based movement (e.g., a group of goblin peons in RE that walk about) or spawn based movement (e.g., mooto in misty). I was thinking that there need be only a few points setup for the mob, and that the pathfind algorithm will move the mob from point a to point b at time interval (movement_timer, which is already defined in the code, but is more concerned with attack). Therefore, there needs to be a way to determine what the next movement point needs to be (which might be helpful later for triggers), along with coordinate information, and a relation to the spawn2 table. With all the above in mind, I have the following mysql SQL (not all SQL is the same ;o) table:

Code:

CREATE TABLE path_points(
  id int(11) NOT NULL auto_increment,
  spawnID int(11) NOT NULL default '0',
  zone varchar(16) NOT NULL default '',
  x float NOT NULL default '0',
  y float NOT NULL default '0',
  z float NOT NULL default '0',
  step int NOT NULL default '0',
  primary key (id)
 );

This table will then have all the necessary data. The next step, I'm thinking, would be to put in the necessary code to buffer the table contents when the zone loads. But we also need a structure to contain all the data from the table.

struct PathPoint {
float x; // x location to move to
float y; // y location to move to
float z; // z location to move to
int step; // step (a) in linear sequence of (a)
int spawnid; // id of the spawn
};

Now the entity object will need to be aware of what the last step it took was, so a quick property of Get/Set LastStep would be necessary.

Now the pathpoints need to be loaded. I'm thinking a linked list that has at least the following signature:

Public:
PathPoint* MovementPoints(float x, float y, float z, int step, int spawnid);

And then the linked list should be stuck into the zone class, such that the zone can do the movement checks every so often, which might be best defined by one of the existing timers or perhaps a new one, so that people might be able to control how often this occurs (for slower machines) or -1 to turn it off completely.

Next, the actual check comes up.

An iteration loop of the zone movementpoints with and another nested loop of the npcs, or maybe any entity? But I'm pretty sure only one of the derived classes has the x,y SendTo() method (which will need to be changed to an overload version x,y,z). I'm going to dip into some pseudo code now :)

Code:

if (timer-says-do-movement-for-zone)
while (!at-zone-movementpoints-iteration-end)
	while (!at-npclist-end)
		if (zone->movementpoints-contains-spawnid)
			{
			pathpoint pp = checkstep(spawnid,spawnstep);
 //return the struct with the coordinates to move to based on the spawns spawnid and current step
			spawn->SendTo(pp.x,pp.y,pp.z);
			}
//end whiles
freeupusedmemory()

That, I think and in theory, would cover much of the core issues surrounding zone movement.

ScotchTape · #2 03-23-2002, 11:44 AM

A few minor deviations from the original and most of what I have up there seems to be working, aside from a couple (small) problems.

Does anyone know how to get the optimal z-coordinate of an entity? Right now I have the queen klaknak walking about in space. Talk about floating bugs! <G>

The other problem seems to be the pure drain that it takes on the server to do this. A fully populated zone, erm, kinda grinds slowly to a hault. Is there a way to spawn an npc_type directly?

-ST

Malevolent · #3 03-23-2002, 02:58 PM

According to my tests, stuff moves across the screen. While a bit rough, it gets the job done (for now). This will put together a data structure that allows one to setup a way to move npc types around a zone. Currently, the data is not persistent and only loads the points when the zone is booted. Is there really a good reason to make persistent pathing points? Anyway, here is the code, hope it helps!

database structure:

Code:

CREATE TABLE path_points(
  id int(11) NOT NULL auto_increment,
  npctypeid int(11) NOT NULL default '0',	//from table npc_types, using key (id)
  zone varchar(16) NOT NULL default '',		//short zone name
  x float NOT NULL default '0',
  y float NOT NULL default '0',
  z float NOT NULL default '0',
  MoveRate float NOT NULL default '0',		//float representing how fast the critter needs to move
  step int NOT NULL default '0',		//what step in the linear sequence are we?
  primary key (id)
 );

insert into path_points(npctypeid,zone,x,y,z,MoveRate,step) values ('4057','misty',-200,-200,0,1.00,0);
insert into path_points(npctypeid,zone,x,y,z,MoveRate,step) values ('4057','misty',-100,-100,0,1.00,1);

Changes to zone.h

Code:

///////////////////////
//Malevolent:
//Data structure that contains information about a zone's pathing points
struct PathPoint {
	float x;
	float y;
	float z;
	int step;
	float movement_increment; //float value to increase movement value by
	int NPC_TypeID;	  //maybe make this an array of ints, so more than 1 npc can use a path?
};


Public:

LinkedList&lt;PathPoint*> PathPointsList; //Malevolent: pathing points collection

Changes to zone.cpp

Code:

///////////////////////////////
//Malevolent: PathPoint, load data
bool Database::PopulateZonePathPoint(char* zone_name, LinkedList&lt;PathPoint*> &amp;PathPointsList, int32 repopdelay) {
	//, LinkedList&lt;PathPoint*> &amp;PathPointsList, int32 repopdelay
	
	char errbuf[MYSQL_ERRMSG_SIZE];
	char* query = 0;
	MYSQL_RES *result;
	MYSQL_ROW row;

	MakeAnyLenString(&amp;query, "SELECT x, y, z, zone, npctypeid, MoveRate FROM path_points WHERE zone='%s'", zone_name);

	if (RunQuery(query, strlen(query), errbuf, &amp;result))
	{
		delete[] query;
		while(row = mysql_fetch_row(result))
		{
			PathPoint* pp = new PathPoint;
			
			ZonePoint* zp = new ZonePoint;
			pp->x = atof(row[0]);			//x coordinate to move to
			pp->y = atof(row[1]);			//y coordinate to move to
			pp->z = atof(row[2]);		 //z coordinate currently not used
			pp->movement_increment = atof(row[5]);	//movement incremental value (how far to move the critter)
			pp->NPC_TypeID = atoi(row[4]);	//the *npc_type* to move...todo: make it the spawn id
			
			PathPointsList.Insert(pp);

		}
		mysql_free_result(result);
	}
	else
	{
		cerr &lt;&lt; "Error in PopulateZonePathPoints query '" &lt;&lt; query &lt;&lt; "' " &lt;&lt; errbuf &lt;&lt; endl;
		delete[] query;
		return false;
	}

	return true;
}

Changes to npc.cpp

Code:

//////////////////////////////
//Malevolent:
//Walk npc to one of the pathpoints setup for it in db
void NPC::PathPointSendTo()
{

	//Build list
	LinkedListIterator&lt;PathPoint*> iterator(zone->PathPointsList);	
	iterator.Reset();

	while(iterator.MoreElements())	
	{

		PathPoint* pp = iterator.GetData();
			
		if (this->GetPathPointStep() == pp->step)	/// are we on the right step? 
		if (this->GetNPCTypeID() == pp->NPC_TypeID)	///make sure that the npc matches
		{

			//todo: find a better way to get there--maybe add a flag to use different pathfinding techniques?

			if (pp->x > this->GetX())
			{			
				this->x_pos=this->GetX()+pp->movement_increment;
			}

			if (pp->y > this->GetY())
			{			
				this->y_pos=this->GetY()+pp->movement_increment;			
			}

			//what's a good way to check for optimal z coordinate?
			this->z_pos=0;
			
			//lastly, check to ensure that we haven't completed out objective
			//and if so, then increase the step value
			if ((pp->x &lt; this->GetX()) &amp;&amp; pp->y &lt; this->GetY())
				this->SetPathPointStep(this->GetPathPointStep()+1);

			//Update spawn position. Don't use fale as it kills performance
			SendPosUpdate(true);

			//todo some way to reset the step counter (after respawn or after ticks, or maybe just let it loop, /shrug?)
		
		} //end if 

		iterator.Advance();		
		
	}//end while
	
}

npc.cpp, within ::Process() right before the final return true;

Code:

	//Malevolent
	//Walk through the zone pathing points
	//if the target is not engaged and if the movement timer says its ok
	if(!this->IsEngaged()&amp;&amp;movement_timer->Check())
	{
	this->PathPointSendTo();
		return true;
	}

npc.cpp in npc::npc

Code:

    SetPathPointStep(0); //always start out at step 0 for a new npc

npc.h

Code:

public:
	void PathPointSendTo();
	uint32	GetPathPointStep()		{ return PathPointStep; }
	void    SetPathPointStep(int step_value);
Protected:
	uint32  PathPointStep;

--MV

(formerly known as ScotchTape)

Malevolent · #4 03-24-2002, 01:16 PM

I was curious where the npc was heading off to, so I built into client.cpp a small filter that gives you an update as to what the npc is up to. In the future, maybe one could lookup a particular step #? I'm open to some ideas on this.

Code:

//Malevolent
		//Pathpointinfo look up on target NPC
		else if (strcasecmp(sep.arg[0], "#pathpointinfo") == 0)
		{
			
			if (target != 0 &amp;&amp; target->IsNPC())
			{
				Message(0,"Requesting pathpoints..");
					
				LinkedListIterator&lt;PathPoint*> iter(zone->PathPointsList);	
				iter.Reset();

				while(iter.MoreElements())	
				{

					PathPoint* pp = iter.GetData();
	
					if (target->GetNPCTypeID() == pp->NPC_TypeID)	///make sure that the npc matches
					{
						//What is the npc type id as defined by the table npc_types column: id
						Message(0,"NPC Type ID: %i",pp->NPC_TypeID);
						//What is the integer step of the critter - a step defining where the critter is at in a sequence of linear(n) steps
						Message(0,"Series Step: %i",pp->step);
						//How far can the critter move? 0.5f to 1.5f seem to be generally ok
						Message(0,"Movement per tick: %f",pp->movement_increment);
						//What is the ultimate destination of the critter?
						Message(0, "Destination: x: %f, y:%f z:disabled",pp->x,pp->y);	
						//What is the current location of the critter 
						Message(0, "Current: x:%f,y:%f,z:%f",target->GetX(), target->GetY(), target->GetZ());
					}
						
				iter.Advance();		
		
				}//end while
				
				Message(0,"Completed pathpoints lookup.");
				iter.Reset();
				
			}
		}

Now then, in theory, it would be possible to script movement for objects using this pathpoint scheme. For example, boats come to mind. Instead of moving bugs, you'd have boats. But, they would need a unique entry in npc_types to work properly (which they should anyway according to drawde's setup).

--MV

Shawn319 · #5 03-24-2002, 02:06 PM

Try joining that chat room. i'm sure the Dev's would love to see some more of your code...

Malevolent · #6 03-24-2002, 02:21 PM

Quote:

Originally Posted by Shawn319

Try joining that chat room. i'm sure the Dev's would love to see some more of your code...

I'm not that kind of programmer, honest! <g> ;)

I'll likely be popping in there sometime this week. I don't want to be reinventing the wheel with what ever is going to be included in 2.6/7.

--MV

Shawn319 · #7 03-24-2002, 02:22 PM

ehh i'm sure u can contribute something hehe.. thats what opensource is for!

Lyenu X`Arie · #8 03-24-2002, 09:06 PM

I've been holding back but.. your ideas are very well organised ScotchTape, good work there. Also Malevolent, your code is very nice, but alass I have tried it myself.

Malevolent · #9 03-25-2002, 01:39 AM

Ah well, so long as the npcs move now. Its all good, it gave me a chance to figure out the design of the emu codebase the good way (which happens to be the hard way

.

I think I best join that chat then before embarking on the next round of AI that I've been wanting to stash in the codebase.

--MV

AcydRx · #10 03-31-2002, 05:38 AM

Malevolent, man.. I love you! You really should hang out in the #EQEmu. lol. Everyone there probably loves you. You got the Animal Instinct code and this.. Dang.. You rock, man. :) I haven't added the code to my own yet, but I have a feeling it'll work. lol.