Pathing Question And Offer To Help DevTeam - Page 4

DeletedUser · #46 11-19-2002, 09:45 AM

<grins>

RedFox · #47 11-22-2002, 10:35 AM

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 · #48 11-25-2002, 07:42 AM

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

BootyBill · #49 11-25-2002, 10:26 AM

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 · #50 11-26-2002, 07:09 AM

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 · #51 11-26-2002, 07:27 AM

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 · #52 11-26-2002, 10:57 AM

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 · #53 11-27-2002, 12:58 PM

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 · #54 11-27-2002, 09:16 PM

Quote:

Originally Posted by quester

... 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 · #55 11-28-2002, 03:09 AM

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 · #56 11-28-2002, 05:29 AM

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 · #57 11-28-2002, 07:17 AM

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 · #58 11-28-2002, 10:08 AM

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 · #59 11-28-2002, 10:59 AM

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 · #60 11-28-2002, 11:20 AM

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.