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.