Pathing Question And Offer To Help DevTeam

[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

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)