Pets and NPC's follow paths, can player?

[ShoniShilent]

for now, my bot uses strict waypoint paths to move around. i carefully select waypoint locations and space them appropriately to prevent the character from getting stuck on a hill or within a building or beside a cliff, etc. it works pretty well. if the bot is hunting MOBS to kill, it won't attack them if they are further away than a certain distance. however, it would be a nice thing to create some sort of broader 'roaming' type waypoints such that the character could venture further out, etc. or when it died it could get back to it's body without having to make a 'spirit' waypoint path for such a reason.

i have noticed that if you command a pet to stay and then walk (even into buildings) and then command the pet to come to you, it will walk up steps, and go around obstacles to get to you. just as annoying, the enemies will follow you ceaselessly into all kinds of nooks and crannies to get to you. is it possible to somehow send a new x,y,z, coordinate to some sort of function that will create a 'path' that we can get ahold of to use similar to the way NPC's do?

are there any good/suggested threads/sites regarding pathing (or alternate pathing when a character is 'stuck' or is trying to get around obstacles). i am looking for optimization and people who have already found ingenious ways around this, rather than trying to reinvent the wheel.

it would be cool to send an x,y,z coord to some sort of function and then watch your character move to that spot on it's own. i know this is probably a pipe dream-

[Cypher]

So what you're asking for, is the NPCs path generation function?

Thats an interesting question, but unfortunately my answer may be disappointing.

Now, I have NOT looked into this, so I may be wrong, but as far as I am aware, the NPC paths are generated on the server. Would make sense too.

To verify this. I suggest diving into the source code of mangos (huge thanks to all of the devs that work on that project) or another established emulator, and checking.

[UnknOwned]

Originally Posted by Cypher

So what you're asking for, is the NPCs path generation function?

Thats an interesting question, but unfortunately my answer may be disappointing.

Now, I have NOT looked into this, so I may be wrong, but as far as I am aware, the NPC paths are generated on the server. Would make sense too.

To verify this. I suggest diving into the source code of mangos (huge thanks to all of the devs that work on that project) or another established emulator, and checking.

Unfortunately most EMU's suck at pathing, mobs flying in the air or walking through objects. I tbh havent seen a EMU yet that does proper pathing for NPC's.

I remember once trying to figure if WoW contained a pathing engine. For example when a warrior uses "Charge" it will smoothly walk around obstacles. However thoes "spell paths" are also generated serverside.

[Cypher]

Originally Posted by UnknOwned

Unfortunately most EMU's suck at pathing, mobs flying in the air or walking through objects. I tbh havent seen a EMU yet that does proper pathing for NPC's.

I remember once trying to figure if WoW contained a pathing engine. For example when a warrior uses "Charge" it will smoothly walk around obstacles. However thoes "spell paths" are also generated serverside.

Yes I assumed they would be, but you've brought up another interesting point. Collision and surface detection is clientside. Charge paths ignore whether the surface is walkable or not from the clients point of view (ie if the terrain is too steep etc). So even if you were to find a clientside function that generates spell paths you'd be screwed by things like this anyway.

[ShoniShilent]

thanks guys. it was just a thought. probably it is created server side as you stated.

[apollo0510]

Hi Shoni !

A standard approach to your problem is:

- create a bitmap that is representing the area you are in with a reasonable resolution.
- Each time you experience a collsion (char should move, but it does not move in the correct direction), mark the position in the bitmap.
- Use an optimized floodfill algorithm to search the shortest possible way to your destination. Optimize in a way, that the fill algorithm should try first the best direction (normal floodfill would always start to search in the stupid same direction).
- Optimize the bitmap so that you do not use one bitmap for the whole world. Instead use a tree that divides world space recursively into sectors of reasonable size that finally contain small bitmaps.

This system will learn where to go and where not.

Tricky thing is to teach it how to avoid jumping off the cliffs ^^.

Greetings

Apollo

[Cypher]

Originally Posted by apollo0510

Hi Shoni !

A standard approach to your problem is:

- create a bitmap that is representing the area you are in with a reasonable resolution.
- Each time you experience a collsion (char should move, but it does not move in the correct direction), mark the position in the bitmap.
- Use an optimized floodfill algorithm to search the shortest possible way to your destination. Optimize in a way, that the fill algorithm should try first the best direction (normal floodfill would always start to search in the stupid same direction).
- Optimize the bitmap so that you do not use one bitmap for the whole world. Instead use a tree that divides world space recursively into sectors of reasonable size that finally contain small bitmaps.

This system will learn where to go and where not.

Tricky thing is to teach it how to avoid jumping off the cliffs ^^.

Greetings

Apollo

Much better than that would be a navmesh generated either by hand or automatically generated with a tool, then using a pathfinding algorithm on that data to get where you want.

OpenBot for example uses a (poorly implemented) hand-generated navmesh. PPather for Glider uses a (very poorly implemented) automatically generated navmesh.

[apollo0510]

Hi Cypher !

True, for long distance travel, a navigation mesh ist the most compact and precise form you can have. But that navmesh wont hinder your toon to hopelessly get stuck somewhere thats not described in the mesh. navigation can only be as good as the mesh is.

Personally I think a combination of a mesh describing secure travel routes combined with a self learning collision map is the best solution.

If you try to send your toon to the next town with only the collision map method, it would try all kind of idiotic ways, before it finally would find a way through the walls of the town.

On the other way, your travel mesh would not help a bit if your toon is automatically hunting, and it is again and again stupidly running against that little tree in its way.

Greetings

Apollo

[Cypher]

Originally Posted by apollo0510

Hi Cypher !

True, for long distance travel, a navigation mesh ist the most compact and precise form you can have. But that navmesh wont hinder your toon to hopelessly get stuck somewhere thats not described in the mesh. navigation can only be as good as the mesh is.

Personally I think a combination of a mesh describing secure travel routes combined with a self learning collision map is the best solution.

If you try to send your toon to the next town with only the collision map method, it would try all kind of idiotic ways, before it finally would find a way through the walls of the town.

On the other way, your travel mesh would not help a bit if your toon is automatically hunting, and it is again and again stupidly running against that little tree in its way.

Greetings

Apollo

To address your points:

Pregenerated meshes (if implemented well) should pretty much never get lost or stuck, the rare cases they do can be addressed with a basic collision and climb hack (nothing obvious, just so you don't get caught on signs that pop up or tiny little hills).

If your navmesh is generated by hand it should be recording new points into the mesh as it travels and so would be able to find its way back anyway if it wandered off the beaten path.

Also, the fact you think that a mesh would be mutually exclusive to good collision detection that doesn't rely on what is basically glorified pixel scanning makes me question your methodology.

GameObjects can be detected by enumerating the linked object list, worldobjects by reading the data from the ADTs. If your both is written well it should be able to detect most obstacles, and even if you didn't do that a collision hack is easy to do and possible to implement in a way undetectable by warden (in its current state).

Futhermore, even if you didn't want to do memory reading for collision detection, a simple "i'm at point xyz and am stuck, i'm going to try and avoid the obstacle, moving backwards, strafing, trying again, etc" would get you out with the same accuracy as your 'bitmap method' while allowing you to blacklist the point on your mesh and save the new connections for next time. Basically, a well-generated navmesh coupled with a well-written bot can for the most part 'take care of itself'.

[apollo0510]

Originally Posted by Cypher

To address your points:

Pregenerated meshes (if implemented well) should pretty much never get lost or stuck, the rare cases they do can be addressed with a basic collision and climb hack (nothing obvious, just so you don't get caught on signs that pop up or tiny little hills).

If your navmesh is generated by hand it should be recording new points into the mesh as it travels and so would be able to find its way back anyway if it wandered off the beaten path.

Also, the fact you think that a mesh would be mutually exclusive to good collision detection that doesn't rely on what is basically glorified pixel scanning makes me question your methodology.

GameObjects can be detected by enumerating the linked object list, worldobjects by reading the data from the ADTs. If your both is written well it should be able to detect most obstacles, and even if you didn't do that a collision hack is easy to do and possible to implement in a way undetectable by warden (in its current state).

Futhermore, even if you didn't want to do memory reading for collision detection, a simple "i'm at point xyz and am stuck, i'm going to try and avoid the obstacle, moving backwards, strafing, trying again, etc" would get you out with the same accuracy as your 'bitmap method' while allowing you to blacklist the point on your mesh and save the new connections for next time. Basically, a well-generated navmesh coupled with a well-written bot can for the most part 'take care of itself'.

Hi Cypher.

You are right, if you consider Glider to do intelligent farming. What you are talking about is a bot that follows exactly a given path. I hate to see bots running around like that. It is so obvious that they are botting.

I am throwing my toons into the wilderness and tell them:

Farm everthing you can in a given radius from this safe spot with some rules:
- There are objects on a blacklist that you have to keep distance from
- Keep actively a distance from elites.
- Keep actively a distance from groups of mobs.
- Kill red targets first, then yellow ones.
- Kill nearest targets first.
- Run away from hostile players.

The result looks very natural. In no way is this toon running in a circle.

I have to admit, that I am not (yet) so deeply into the WoW engine, that I can detect obstacles from memory reading. That would of course help a lot.
But there are twoo things that identify a toon immediately as a farmbot:
- running on a (small ) defined path in a circle.
- doing the same mistake again and again.

But, hey, why should we all have the same aproach ?

Greetings

Apollo


Edit: I cannot help but make a note on your suggestion to create a self learning mesh. Did you try that ? You must prevent the mesh from degeneration, the new meshpoints must make sense, that seems very complicated to me. And as a second note, I tried in the past to work around collision with random evasive manouvers. The problem was always - sooner or later the char found a way out, but it looked so stupid, especially when it was blocked from more than one side (like facing into the corner of two walls).

[Cypher]

Originally Posted by apollo0510

Hi Cypher.

You are right, if you consider Glider to do intelligent farming. What you are talking about is a bot that follows exactly a given path. I hate to see bots running around like that. It is so obvious that they are botting.

I am throwing my toons into the wilderness and tell them:

Farm everthing you can in a given radius from this safe spot with some rules:
- There are objects on a blacklist that you have to keep distance from
- Keep actively a distance from elites.
- Keep actively a distance from groups of mobs.
- Kill red targets first, then yellow ones.
- Kill nearest targets first.
- Run away from hostile players.

The result looks very natural. In no way is this toon running in a circle.

I have to admit, that I am not (yet) so deeply into the WoW engine, that I can detect obstacles from memory reading. That would of course help a lot.
But there are twoo things that identify a toon immediately as a farmbot:
- running on a (small ) defined path in a circle.
- doing the same mistake again and again.

But, hey, why should we all have the same aproach ?

Greetings

Apollo

No, that is NOT what I'm talking about.

Do you have any idea what a navmesh is? The whole point of a navmesh is you use a pathfinding algorithm to get wherever you need to go DYNAMICALLY. There are no set paths, they are generated on the fly. You are obviously thinking of waypoints which are VERY different.

Please go pick up a book on game ai programming or pathfinding/navigation.

[luciferc]

Just an Idea.

Get a Private server just an empty one that has all the game objects on it.

Then do a speedhack and get your Bot to make a perfect nav-mesh but even at those speeds would take a while :O.

[apollo0510]

Originally Posted by Cypher

No, that is NOT what I'm talking about.
Please go pick up a book on game ai programming or pathfinding/navigation.

oops. *starts searching*

Edit: Ok. I see what you call navmesh. Hehe. Sure that is much better than the pixel approach. Use big dynamic triangles in 3d space instead of pixels .. and here you go. Sorry for assuming you were talking about waypoints.

[Shynd]

You load the map and all obstacles into your program, then use like an A* or Djikstra (spelling?) algorithm to dynamically find the shortest (or easiest) path between two or more points. That, I believe, is what Cypher is talking about. Instead of creating a huge database of waypoints, you create paths as needed.

[Cypher]

Originally Posted by Shynd

You load the map and all obstacles into your program, then use like an A* or Djikstra (spelling?) algorithm to dynamically find the shortest (or easiest) path between two or more points. That, I believe, is what Cypher is talking about. Instead of creating a huge database of waypoints, you create paths as needed.

DINGDINGDINGDING!

We have a winner!