Pathing Question And Offer To Help DevTeam
 

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...

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.

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...

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

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).

God, no wonder PoH is pathing hell

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

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.

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.

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.

good idea. :D

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.

i was thinking of the zones .cfg files.

<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.

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 ;)

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

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?

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..

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.

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.

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.

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

Sounds interesting.

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

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.

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..

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.

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.

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.

Map map map? :)

lol:p

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.

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

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.

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.

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

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

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.

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)

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).

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