Pathing Question And Offer To Help DevTeam

[Glasswalker]

Hello... I am an experienced C/C++ coder who used to be a huge EQ addict... since my discovery of this project I have been interested in getting back into the game... And I would love to help out on development of the emu... (anyone on the dev team contact me at: glasswalker@cogeco.ca if you are interested)

But I would just like to aska quick question in regards to pathing for now...

How does EQ impliment pathing? could it not be a string of values as a database field tied to that specific spawn? that way it is part of the db, it is a relatively small amount of data, and it does not require fancy editors... Also people could simply capture moving mobs in each zone and use a simply filter to break down their paths and store the waypoints...

My idea is this: could you not simply write the following functions: (pseudocode)

SetFollowTarget(TargetName)
{
Store the Follow target into the player struct
set a flag in playerstruct for "follow mode"
}

DoFollowTarget()
{
Read in Player's Followmode flag
if followmode=true then:
Read in player's current follow targetname
Find TargetName's X,Y,Z
SetWayPoint(X,Y,Z)
endif
}

StopFollowing()
{
Read in Player's Followmode flag
if followmode=true then:
Set Followmode flag to false
endif
}

SetWayPoint(X,Y,Z,WalkMode)
{
Store The Waypoint Info into the Player Struct for X,Y,Z, and the walkmode. (walk/run)
Set a flag in the playerstruct for "autopilot mode"
}

DoGotoWaypoint()
{
Read in the waypointflag from playerstruct
if autopilot flag is true then:
read in target x,y,z and walkmode from playerstruct
Calc a vector to those coords from current x,y,z
Set current facing to that vector
Calculate direct distance.
If directly in front of me is an obstacle (building, zone wall, whatever) Then:
Modify my vector to the left/right (attempt simple obstacle avoidance)
endif
if distance > attack range then:
Toggle on the ingame walk/run command for this player/entity to move at designated speed.
elseif distance <= attack range then:
Toggle off the walk/run command
StopAutoPilot()
endif
}

StopAutoPilot()
{
Read in Player's Autopilot flag
if autopilot=true then:
Set autopilot flag to false
endif
}

The above code would quite nicely in most 3d environment... The mobs would have issues with getting around zone walls and houses and such... but they would eventually do it... and if I remember correctly the obstacle avoidance in the actual eq is pretty crappy anyway... :)

Also, now wandering mobs is easy simply provide a string of waypoints... There could be a function to maintain the current path, and if the mob strays from it it remembers the last waypoint... so when it is done chasing someone or whatever it resumes back to it's last target. That would also make it easy to store the path data in the database...

Also, would it be possible to add a function to set a flag in the database that disables all god like commands to basic users... (so you could actually run a normal server without users running rampant with whatever items they want and whatnot... maybe a database table of the advanced # commands of the emu, and associated access levels needed? this way serverops could customize what different access levels could do...

I would gladly help code this too... Anyway... let me know what you think, any feedback you might have, and if you are interested in the help on the dev team...

[devn00b]

lol sure that sounds nice.

how about collision avoidance? can do that without loading 3d modles of the zone (walls, hills ect).
id imagine that would increase the minimum req. of the eqmu by alot.

less you where to put this info in the db.
a huge pain in the ass that would be.

there was somone else long ago that tryed pathing (malv.) w/o the 3d map it was a huge pain in the ass.

mobs would path through walls, under the world, above it ect.

im no coder, and im not part of the dev team so dont take my word for it. these are just things that i have had told to me several times when i have asked about it.

[Glasswalker]

Well... The obstacle avoidance could be done using a 2d map (like the ones from showeq) basically showing a line where there is an impassable obstacle at ground level... but also, the obstacle avoidance is really not even needed... as long as you use the actual walk/run function of the game, if they walk into a wall, they walk into a wall :) the mobs in the real eq don't do a good job of this anyway, and besides... if it is following you closely, it shouldn't get stuck badly anyway... The obstacle avoidance thing would be something to work on for the long run, but even without that the above should work for what is needed for now... providing follow routines (for players, and good mob chasing routines) and providing the waypoint scripting for wandering mobs...

anyway it would still be more complicated than the above, that was just a basic overview of what could be done... I need to hear back from the dev team to see if it is feasable...

[DeletedUser]

If we were ever going to do pathing it would be 3d maps due to the Z coordinate, its very important the NPC follows that Z coord properly (or they jump, or fall under world, EQ client is very picky). The way people get onto the dev team is they show examples of their work by programming for the emu outside of the team. I mean real code, not what is above, thats chicken scratch :)

[quester]

I can tell you exactly how EQ handles pathing, because I worked on EQ.

EQ uses a very (VERY) simple A* pathing algorithm, with fixed hand added PPOINTS for each zone.

The level designer literally runs through the zone with the client, using slash commands to add/delete ppoints in the level. Its sick, but thats how it works.

There are, IIRC (this was .. what.. nearly 3 or so years ago), 4 different types of PPOINT nodes. Land, Air, Water.. and a special "area" known as Wide Open. Wide Opens allow a mob to simply go straight from point A to point B if both points are in the wide open.

Land, Air, Water points are pretty much what they sound like.

ppoints are in groups, with each gropu limited to a certain number of points for efficiency.. Can't recall how many points. Each gropu can be connected to another group by shared ppoints. A mob can only move from one gropu to another through these connected points. This is why you see shitty pathing where a mob will run AWAY down a ways to a certain point then back up. Its goign to the nearest connector.

There was also a limit to the total number of ppoints, again a number I don't remember. In fact, Plain of Hate is only about half ppiinted (The other half we sealed off), because we ran out of points!

The pathing is a very simplified A* that chooses the next closest ppoint to move to based on its current ppoint and the ppoint closest to the target destination. Taking into account connecters between pppint routes, and ppoint types (If the mob has to travel through water, it can do so only on water ppoints). IIRC, Air points were never used while I Was there (I left before Kunark).

[kathgar]

God, no wonder PoH is pathing hell

[DeletedUser]

bump to where it should be.

interesting topic and the thing that would get EQEMu a lot of love is pathing.

;) i think they get enough love anyways

[quester]

I'm in the middle of doing pets at the monet, or I would jump over here and work on this. But only have time for one thing at a time :)

The best, and easiest thing to do, for now, would be tom implement wide opens. That would allow a lot of zones to be properly set up. Many of the outdoor zones, like karanas, commons, ro's, etc, are done using wide opens.

[DeletedUser]

maybe you could add an eqemu command that adds ppoints.

#ppoints
----------------
#ppoints add #
1: water
2: air
3: land

When it adds one it gives it a number. (The latest one of each one you place in the zone)

i.e:
#ppoints add 1
-- Ppoint added, #1 --

Thus becomes:
#ppoints delete #
Number being the number of the ppoint added.

And all of this is saved into a .cfg file or something that could be read by however you would get pathing to work, I would definitely help.

[quester]

That's essentially how the ppoints are created in real eq. Although the client used is slightly different.. You use an overlay GM menu to set the type of ppoints being manipulated. Then you just drop them as you move around, and if you want to delete one, you just go stand by it and delete.

But essentially, yeah thats the idea. However, I think we should do wide opens first, only because they are easiest to implement. A mob in a wide open, simply takes a direct path from current position to target position, assuming both points are in the same wide open. The easiest way to handle wide opens in the emu would be to just add a wide open with a specified size from the current position. In real eq, you can actually define the box points to make the wide open, but then youhave issues with concave vs convex geometry, non equal sides,etc.. It is really much more than we really need. I'd just add a command that says "Define a wide open from this point, with a size of 100 units".. and use a square.

So if you were standing at 0,0 in the zone, and typed "#pathadd wideopen 100", a wide open would be established that went from -100,-100, to 100,100.

[DeletedUser]

good idea. :D

[quester]

As a side note.. in case someone gets to this code before me..

In real eq, the pathing is stored in a seperate pathing file. Iwould recommened the same here. It just keeps thrings clean.

Alternatively, we could even store a zones pathign info into the database.

[DeletedUser]

i was thinking of the zones .cfg files.

[kathgar]

<cough> in the DB<cough> Anyways, the main problem with pathing is we dont' have the power capt'n! There is also the wandering pathing and the pathing to avoid objects(so they dont' get stuck in a wall, or run through a wall) both of which severly hamper the CPU/mem usage =/

[quester]

<cough> in the DB<cough> Anyways, the main problem with pathing is we dont' have the power capt'n! There is also the wandering pathing and the pathing to avoid objects(so they dont' get stuck in a wall, or run through a wall) both of which severly hamper the CPU/mem usage =/

Which is why I suggested we do it the same way Live EQ does it.

That is WHY Live EQ uses such a simple and pathetic pathing algorithm. Because it is less overhead. Live EQ doesn't even CARE about walls and structures. It doesn't even know they exist.

[DeletedUser]

hmm, what if its a wide area though. its open to wander. Is there some sort of way to restrict it from going to the area of a wall.

In EQLive, i've seen some mobs walk into walls.. mainly because of lag which would make sense but also because they are not in that area.. its a weird bug.

Example:
In city of mist, monsters on the top area of the zone, im guessing they fall sort of and they fall onto the ground and start walking, they usually just walk into walls then disappear.. im guessing they dont fall its just a bug. But what if it does run into a wall? what would happen sense it doesnt know what it is.

As for Glasswalker, this would be a great thing to start if you are going to show work to EQEMu. Just a suggestion ;)

[quester]

hmm, what if its a wide area though. its open to wander. Is there some sort of way to restrict it from going to the area of a wall.

It doesn't know it walked into a wall, and keeps going. Let me try to explain what happens from both points of view.


|
a | b
|


You are going from point A to point B. There is a wall between you. SERVER side, you don't see this wall. You go straight from A to B as if the wall wasn't there. CIENT side, when you get to the wall, your model will be shown hung up on the wall. You aren't really hung up.. but the client sees the wall, does the collision detection and hangs you on the wall. Then next movement update packet tells the client you are past the wall because you never stopped in reality.

This is what happens in wide opens. Server side, the mob just keeps walking merrily along, because it never saw the wall. Client side, it appears to hang in the wall because of client side collision detection, because the client predicts movement based on last known vecotr.. As soon as the client gets the next movement packet though, it updates the position. This is why you see mobs that sometimes look like they are hung up on a wall or structure. A good example, if the Hermit hut in SK. There is a Gnoll who always walks right into the wal.. appears to be hung up on the wall for a bit, then pops to the other side. In reality, the Gnoll never stopped. He walked right "through the hut", because he doesn't even know it is there.

In more complicated zones, the problem of obstructions is moot, because the pathing is designed to prevent them from getting hung up. In other words, while the server doesn't know this hallway takes a right turn up ahead, it doesn't matter. Because the pathing takes a right turn, and thats all it needs.

Did I make it any clearer?

[Trumpcard]

Perfectly..

That explains why cutting corners to try to lose a mob never helped me a bit...

The server doesnt care.. He's stll chewing a hole in your ass, even if the client might disagree..

[DeletedUser]

Im sure that the EQLive servers follow some sort of map that just has pathing rules that they follow, I doubt a EQEMu developer has the time or expertise to work on it. Theres so many other things that need to be worked on, be happy mobs move. At one time they just stood still and faced you when you attacked them.

[quester]

Im sure that the EQLive servers follow some sort of map that just has pathing rules that they follow

All it follows is the path points as defined. The map of the zone structures, gemoetry, is NOT used. Or at least, never used to be used.

It just isn't needed.

If a hallway goes straight, then turns right.. The mob doesn't need to know this, because his path points do the same thing.

[quester]

It is really just this simple... A mob can only move from one ppoint to an adjacent ppoint. Those ppoints are placed, in such a way to avoid obstacles in a zone. Those ppoints are placed in 3 dimensions to avoid Z problems. Those ppoints are ALL a mob needs to do pathing.

In Wide Opens, NO geometry is taken into account. A straight line from A to B is used, assuming BOTH points are inside the same wide open.

It CAN be done in the emu, and without the overhead you all seem to think it will cause. A* pathing is very rudimentary, and easy on the resources as long as you don't go overboard with it. Yes, a zone with 1k wandering mobs would be a killer. Yes, on lower end systems here, you would have to keep the number of roamers down.. probably couldn't do as many as live EQ. But you can still have roamers, and you can still have pathing so that statics when tagged will follow proper pathing.

[kathgar]

most people run 5-10 zones on one computer, that isn't even dedicated as a server easily get way too amny mobs

[mByte]

Sounds interesting.

I would also create it as a file of its own just like the quest.

[DeletedUser]

Image,
I have to disagree, in a whole hearted opinion. Your right about being greatful they move and all, but pathing in my opinion is one of the bigger things the emulator needs.

[Trumpcard]

Well, we shoould consider implementing a waypoint system in, then experiment with using it. 1st case would be a fleeing mob just to test it out. Its a simple case, isolated, and it would allow us to put some thought into the implementation before we just have a zone of wandering mobs.

Put in some simple logic to determine whether to flee or not based on level relative to the player, hitpoints, then on a successful flee check, move to the nearest waypoint and start a traversal. I would think load the waypoints from the database then pull them into the memory space when the zone loads. The waypoints themselves won't take up alot of memory, we'll just have to experiment with the movement logic a bit to keep it from being to intensive.

Mobs would need to be identified as wanderers or not. Guess a boolean flag in the database would take of take, spawngroups would need to be divided into wanderer groups and stationary groups.

Just thinking outloud..

[DeletedUser]

Why should we hack something in when we can do it right? We will need a map eventually, to map arena coordinates, then within the map we can set waypoints (or fog of war sort of thing), along with the ability to setup pathing for boats.

[DeletedUser]

rofl boats :)


see what i mean? a lot of the little things needed eventually will lead into pathing. thats why its one of the major things.

Half of the people that I know that play EQEMu say pathing is mainly the reason it fails to compare to VI servers, what good is it having NPCS stand still.

[quester]

How many times do I need to say this? YOU DONT NEED A MAP, you only need your PPOINTS and wide-open definitions. THATS IT.

[DeletedUser]

Map map map? :)

[DeletedUser]

lol:p

[quester]

Sorry.. i've had a really bad night/day.. didn't really sleep.

Got mice in my apartment.. Caught 4 so far.. I hope thats all there is.

[DeletedUser]

Im not trying to be rude about this, but along with functionality you want it to be user friendly.

[quester]

User friendly? Granted pathing a zone in real EQ wasn't "fun", but it wasn't hard either. Just takes time.

I'm confused.. on one hand you are complaining that pathing is gogin to be too much of a resource strain, and on the other hand you want to do it using a map, and more advanced pathing algorithsm so that ts user friendly, thus using more resources.

You can't have both :p

The way we did it in real EQ is the way it should be done here. It was done that way for the specific reason as to use a little resources as possible on a zone server. The same goal here.

[DeletedUser]

The way 'we' did it in EQ? We dont know how they did it in EQ, we need to talk to a programmer that works on the EQ server to prove that.

I dont see how you can use waypoints to properly path a NPC to a target, on EQLive they are aware of the exact X/Y/Z, you can not do that with waypoints.

[DeletedUser]

Quester was an EQ programmer a long time ago, as he says.

[DeletedUser]

I can name 50 people that have said they worked for SoE :P

[quester]

I worked on EQ and left shortly before Kunark.

Believe me or not, doesn't really affect me in any way.

If you look back, I think on the first page of this topic, I explained exactly how pathign in "real eq" works. I don't have time to retype it all up again right now, but re-read what I posted, and if you still have any questions, I will be back later and can answer them.

In short, the developer lays PPOINTS along the map where he wants mobs to travel. Each PPOINT is a point in 3D space, thus it has a z coordinate. There is no gemoetry map of the zone, there are no calculations to determine obstacle avoidance. The pathing takes care of all that, at least it does when it is pathed right. This method uses very little resources. I did something very similiar with a Neverwinter Nights server, and on my machine, with about 100 wandering NPCs, using a pathing I wrote in NWScript, there was very little hit AT ALL on the resources. And that was implementing the system in the NWN scripting language which is obviously slower and has more overhead.

Anyways, I gotta run for the moment. I'll be able to check the net in about 2 hours or so. Maybe less.

[DeletedUser]

Quester, sense you seem to know a lot about pathing, and have programmed on it, and also done work with NWN on it, could you make an example? Lay some ppoints over arena with a custom mob and let it run around the center part.

Just a bit curious. it would make a nice program if you could lay them around on a map. (like spawns in admin tool)

[DeletedUser]

quester imagine this, go to east karana and check out the hills on the left of the paths, walk up every single way possible (a NPC would have to be aware of the x/y/z to follow you in each method), how should we do this?

I see you pointed out that you ran out of points for PoH. Plane of Hate is nothing compared to skyshrine and other various zones (especially luclin).

[BootyBill]

Alot of 3d design work tells me questor might be right. What he is saying that the smoother and more controlled the path is, the more points you add to it. Juts like anti-aliasing, the more points, the smoother and more math intensive.

The point on the npc that is actually moving in 3d space along that path of points does not care about x,y,z planes. It simply follows the rules you set forth by following points laid out before it. The mob would obviously simply draw a straight line between two points even if it was dropping down a set of stairs mostly on the Z axis.

You would simply add more distance between the points and only use them at 90 degree corners etc in dungeons to lighten the amount of points needed. Skyshrine is no more or less difficult than any other zone, it would just take more time to place the points.

The theory appears viable regardless of the circumstances.

I would still much rather see dragons with "real" game AE and melee though lol! Sorry = ) I will go back to my lurking = )

Bill

[Minuss]

I didnt read above posts but why dont you make a pathing like for the bots in halflife for example... To add waypoints, you run on the map and push a button, it add a point of a way usable by the npc... You could do this for npcs, you can set up single or multiple ways for the same npc and ways that are used for multiple npcs... The point on the map store the coords ( x,y,z) wheres the npcs can go...
was just an idea :p maybe someone talk about it be4...

[a_Guest03]

Image, quester is saying that there are open area waypoints where you set an area with points, and the mobs travel wherever they want in the area designated as open area. Everywhere else, they must follow a path set by waypoints where they must be followed in sequence.

[Windcatcher]

Quester, is this what you have in mind?


Unit Pathing;

Interface

Const
MAX_POINTS = 256; // Arbitrary
MAX_GROUPS = 256; // Arbitrary

Type
TPPointType = (pptLand,pptWater,pptAir,pptWideOpen);
PPPointGroup = ^TPPointGroup; // C would just use a pointer but Pascal uses these weird constructs :)
TXYZPoint = Record
X,Y,Z: Single; // XYZ coordinates (equivalent to "float")
End;
TPPoint = Record
XYZ : TXYZPoint;
_Type : TPPointType; // Type of PPoint
Group : PPPointGroup; // Pointer to this group
OtherGroup : PPPointGroup; // Connector to another group, or Nil if this point doesn't connect anywhere
End;
TPPointGroup = Array[0..MAX_POINTS - 1] Of TPPoint; // In Delphi I would use open arrays, which are
TZoneGroups = Array[0..MAX_GROUPS - 1] Of TPPointGroup; // dynamically allocatable...

Var
ZoneGroups : TZoneGroups;

Function FindNextPoint(Source,Dest: TXYZPoint; CanTraverse: Set Of TPPointType): TXYZPoint;

Implementation

Function FindNextPoint(Source,Dest: TXYZPoint; CanTraverse: Set Of TPPointType): TXYZPoint;
// ---------------------------------------------------------------------------------
// Given a source point and a desired destination point, return the next point to which
// something can move.
// ---------------------------------------------------------------------------------
Var
SourcePt : TPPoint;
DestPt : TPPoint;

// Returning a pointer to the TPPoint is less intuitive, but more efficient when
// implementing this in the server
Procedure FindNearestPPoint(Const XYZ: TXYZPoint): TPPoint;
Begin
.
.
.
End; // FindNearestPoint

Begin
.
. // Implement the pathing algorithm here, something I'm not familiar with...
.
// Find the nearest TPPoint to the source and destination coordinates

SourcePt := FindNearestPoint(Source);
DestPt := FindNearestPoint(Dest);

// Attempt to traverse the distance

If (SourcePt._Type In CanTraverse) And (DestPt._Type In CanTraverse) Then
Begin
If (SourcePt._Type = pptWideOpen) And (DestPt._Type = pptWideOpen) And (SourcePt.Group = DestPt.Group) Then
Begin
// Both are in the same wide open area; simply move in a straight line
End
Else
Begin
// Find the nearest available destination, according to the A* pathing algorithm
End;
End
Else
Begin
// Can't traverse; do something else here
End;
End; // FindNextPoint

End.

[Trumpcard]

Ahhhh..
I see... I was wondering how you would seperate those out..

Open points versus group assigned points.. That way a wandering mob could be tied to a group of waypoints, or in an open waypoint area.. Big open zones (say the Karanas) could have a limited number of waypoints, basically just vertex points across the maps, and the mob could either traverse them in a random waypoint to waypoint fashion. In grouped waypoint areas, they would need to follow a least cost traversal.. I knew that Dystras algorithem would come in handy oneday ! lol..

I would think in the open zones it would be easy to implement, just make a file or database layout with a list of waypoints, then have the mobs that are assigned as wanderers randomly move between them. The client should take care of the z axis.

In more limited areas you would need to define the waypoints as you walked it, and assign it to a waypoint group, then tie specific mobs to that waypoint group.

I could see an ingame #waypoint <waypointgroup> that would dump the loc. when you hit it, and tie it to that waypoint group identifer.

[Bardboy]

A* Algorithm for Programmers (http://www.programmersheaven.com/art.asp?ArtID=858&URL=http%3A%2F%2Fwww.geocities.c om%2FSiliconValley%2FLakes%2F4929%2Fastar.html)

Hope this helps anyone out there interested in doing this.
I am thrilled to even see this subject discussed at all. Good luck Devs!

edit: thought id throw in a link to this page: Programmers Heaven (source code articles on navigation and movement) (http://www.programmersheaven.com/zone8/articles/article393.htm)

[DeletedUser]

<grins>

[RedFox]

Hello
I was asked by a friend (who's a huge EQ fan) to stop by and offer some help in pathfinding
:)

Won't be able to do any actual code (unless you guys really need it) as I havn't got EQ personally.
But I have alot of experience creating fast pathfinding system
(excuse the plug but..) http://www.foxbot.net if you want to see what I can do

I'd be pleased to offer any assitance you guys need.

If you want to go for waypoints (as its simple..but requires someone to build them for all the zones..) then you can use a 'shortest path' lookup table for the monsters...whilst its running finding the shortest path takes no time atall, as its just a lookup.
The cost comes from the table taking up quit a bit of memory..may be a problem for 100+ zones running at ones with about 800wpts on each zone..would need about 150meg of RAM (though dunno if that many wpts would be used/that many zones can be run at once)

Theirs are ways of only precomputing parts of the table, and working the rest out on the fly (very slight increase in CPU usage for a reduction in the amount of RAM used)

Then you can use A* (or other stuff) for pure searching (no RAM useage, but lots of CPU needed) for working it all out as and when its needed.

Don't know exactly what the monsters need to do when it comes to path finding.. (I take it they don't need todo complex things like flancking buildings or taking things other than the shortest route to a destination)

Seems like it should be pretty simple as they don't need to take into account any level data atall...just follow paths (waypoints) :)

Oh, I also know a reasonable amount about code optimisation and processor load balancing, so anything I can do to help their aswell, let me know.

RedFox

[a_Guest03]

That's very insightful, RedFox! Simple waypoints sound the best, with no intelligence for flanking, etc.

[BootyBill]

Thanks for offering your help. It will be nice to eventually implement this to make the server more like the real game. Hopefully the developers will take you up on your offer.

Bill

[quester]

Sorry guys.. I was out of touch last week.. Family is down for the Holidays.. and top that off, just picked up a nice contract for my company. ARG!

I'm going to go through and catch up on whats in this thread, and the rest of the forums. Gimme a few hours.

[quester]

Ok read through things...

EQ uses avery simple A* algorithm to determine the next ppoint to use, as I stated earlier. ppoints are layed out in groups, with both a finite number of points per group, and a finite numnber of groups. This is to reduce overhead. I dont' recall the actuall numbers for each, and has been pointed out there are a lot more complex zones now so the numbers have probably changed. Hell for all I know the entire system was rewritten, but i'm going on what I worked with during the early days (pre kunark).

The simple explanation of how it work sis thus:
Mob determines what ppoint it is closest to
Mob determines what ppoint is closest to its destination/target
If destination ppoint is NOT in the same group as the mobs location, then its destination point is instead moved to the CONNECTOR point. A connecter point is a ppoint that connects two groups together.
Mob determines which adjacent ppoint to its location is in the right direction, anbd moves to that ppoint

Rinse and repeat as needed.

Wide opens, work different. A wide open simply says that a mob can move directly from its current location to its target in a straight X,Y,Z line as long as both points are in the same wide open. Wide opens CAN be used on varied height terrain, but it should only be used with minor changes. Any major hills or other height changes should be actually pathed out to prevent mobs from falling under the world. Found this out the hard way early in development when we tried to use wide opens completely in areas like commons, karanas.. only to end up with a lot of mobs under the world because of the hilly areas. Believe it or not though, a lot of mobs STILL do end up under the world in those areas hehe.

Let me try to illustrate an example where you can see this algorithm in play. I'm guessing that a lot of people here have gone through Crushbone, and many of you may have seen the really funny pathing that is in that zone. It does a good job of showing you how it works. For example: stand on one side of a moat, and attack an orc that is on the other side. Depending on your positioning, the orc will run one wya or the other, down to a bridge (Not always the NEAREST bridge lol), then cross the bridge, then run back up. The way that zone was pathed, most all of the bridges contain connecter ppoints. You are in one group, the orc in another. The bridge is the connection between the 2 groups. You can also see it in the entrance when you tag an orc, and it runs over and away form you, then back down the middle. In this case, its typically all one group (depending on where you are), but the spawn points for the mobs believe it or not are NOT on ppoints. So the orcs have to first move to a ppoint, then start the chain.

Hopefully this clears things up a bit?

[RedFox]

Sounds pretty similar to a system I'm working with at the moment.
With my system I've pre calculated most of the route data, so picking the next place to visit (ppoint in the case of EQ), all thats required is a lookup.
Only requires a small amount of memory because of the way I've grouped it.

The grouping is also automatic..so it seems feasable that you could just place points on the zone, and then let the code decide howoto group them.
Open areas will need o be marked though :)
Hmm, perhaps what points their connected too would discribe weather they where in the open or not?
Lots of paths for open areas, and only a few for normal ones?!

Anyways, if you want some assistance, then let me know :)

[Quinthalus]

I do very limited work in c+ and with 3d modeling but on a point to point system even in the open wouldnt the z-plane come into play due to the fact that the points would be at diff z-planes? Or would that apply with an open area point system?

[RedFox]

... Wide opens CAN be used on varied height terrain, but it should only be used with minor changes. Any major hills or other height changes should be actually pathed out to prevent mobs from falling under the world. Found this out the hard way early in development when we tried to use wide opens completely in areas like commons, karanas.. only to end up with a lot of mobs under the world because of the hilly areas. Believe it or not though, a lot of mobs STILL do end up under the world in those areas hehe.
....


Yes different z-planes come into play :)
Whenever placing a point, the x,y,z will be stored for it.
Not sure how many will need to be placed to stop them walking 'on air' though...perhaps just add points to the top and bottom of hills
But, dunno how the EQ engine works, the stuff I'm using has the 'bots' collide with the world (gravity etc), so I don't have to worry about them going over/under the world.
I guess thats not the case with EQ

[quester]

Well first off you have two situations. Wide opens and ppoiinted routes. Wide opens dont' use ppoints. An npc simply takes a straight line from point a to point b if both points are inside the wide open.

The issue with Z is this: The server does zero collision, or physics work. The npc is simply moved from one point to the next in a straight line (either with ppoints or not depending if its a wide open). The CLIENT however, will do collision and physics based on iterpolation of the npc's position and velocity vectors. Basiclly when ppointing a zone, you really need to use a lot of points, especially on hills and such. Because if you try to move an npc through the inside of a hill, while the clioent will do the proper physics and make the npc walk up the hill, if an update packet comes through when the npc is in the middle of the hill (INSIDE the hill because you didn't path up top of it), then the client will move the mob to that position and it will end up under the world. The system is not the best. In fact it sucks, and there isn't one single person on the eq dev team that complained about it. But it does work, and it is simple.

[RedFox]

Ok, so ppoints will probably store x,y,z..so they can travel from one to another..
How do 'wide opens' work? Assuming that a hill could be part of a wide open area...
Points or areas? :)

How do connections work with these? are they automatically generated when they points are placed?
They use a line of sight test, or just pick the closest points?!

Sorry for the questions..seing as I'm the one trying to help out..heh

If I can figure out a bit more, perhaps I could try working on some routing code?! :)
Someone else would have to plug it into EQ, but it'd be half done atleast

[quester]

Yes, ppoints store X,Y and Z. That's why you can do pathing using ONLY the ppoints without having the 3d zone geometry.

In "real eq", a wide open IIRC, was defined by dropping ppoints to create a bounding polygon, inside of which is adefined as a wide open. For the emu, I think it should be kept simpler, and instaed be done by simlpy defining a rectangle. IE #path add wideopen 100,100 500,500

As I stated earlier, wideopens should NOT be used to cover areas with any noticeable variance in Z axis because it will not be able to properly handle the pathing. That is a responsability of the person pathign the zone.

As for choosing points... routes are calculated in real-time, nearest adjacent poiint which moves the mob closer to the target point, takign into account conntections between groups.

Now, again, this is how EQ does it, but if you have suggestions for a better way, there is nothing preventing that from being done. Like I said.. no one was really happy with the pathign we used in EQ.. It sucked, had lots of problems, and dropped the burden of pathing on the developer. But it workd, it was low on resources, and it was easy to leave in.

[RedFox]

Having a rectangle would require alot less maths than a plygon.
Although I have it handy if any decides to use that.

So...are paths (or 'what ppoint can be reached from a ppoint') defined by the user (I'm thinking you may get into trouble when mobs try to run though coridoors...uhm, if they exist in EQ :p )

What I've been use to is knowing exactly what point is connected to what point...
I'd recomend that this be know before hand, as if its needed alot, lookups should be used instead of just searching for the next nearest point to a point (if you see what I mean). doing this would save on cpu cycles.
This could be done by just checking what (from a ppoint) what ppoint's exist around it in a circle.

If this data is known in a lookup before hand, then another table can be created for shortest path lookups.

For a mob to get from point a to point b, would then be a simple matter of a few lookups every time it reaches a point.
This would be the best meathod in my opinion, as it would run at exactly the same speed as it does without any navigation (at present).

:)

[Lurker_005]

Not a programer, just keep that in mind :p

Somehow either the client or server CAN handle hills/stairs/ramps without any points, otherwise mobs would not be able to follow a player if they simply went into the right terain. What about setting wide open areas with the Z above all hills ect inside the area? Will the client place the mob on the ground, or always place it in the plane of the wide open ppoint boundry polygon and let it fall to the ground?

For me it just seems like something is being overlooked.

[Quinthalus]

Well based on the info here I'm gonna start writing some code to see if we can get this to work. Might not be able to but its worth a try I'll post the code when i think its at least close to working hehe.

[DrEvil]

for the record, whoever decides to tackle pathing, I will become a major waypoint contributor. I am on Redfox's dev team for Foxbot and have done alot of waypointing for him.

[a_Guest03]

Let's get this conversation bumped back to the top. Can anyone resolve any of this now?

Somewhere, server or client, a map is accessed once you engage a mob and he/she is within proximity. I think waypoints are only used to deter mobs, to force them to act a certain way, like with corridors. People have watched as a lion engages you, climbs up a hill, and finally attacks you. It happens all the time!

I'm willing to believe that the map is stored on the server. I don't think the ShowEQers have seen data passed from the client explaining to the mob that the map is a certain way, and that it should respect it in certain spots, etc. Waypoints, for sure, are stored on the server.

I'm pretty sure that until a mob is triggered by aggro, it must respect all of its designated waypoints, and always respect some more restrictive ones, like walls.

Somehow, the mobs are aware of z-coordinates for ground, if the part of the level is designed to be land. Also, mobs are somehow aware of water (they never run through water at you, do they?)

So how can we use our current mapfiles for the client to make the server respect them?