yet another navmesh implementation

[pendra]

Here's another update.

The nav mesh is basically done. I implemented some simple string pulling and a few other optimizations. It works, and I've actually used it to drive a character around in the game without running into things for the most part, though any human observer watching my character move around for more than a few minutes could spot it as a bot if they knew anything about AI. It does some odd things, since I'm finding a shortest path and then following it like a waypoint graph, so I hug corners, rub along walls, etc. It very rarely actually gets stuck, but it's often pushing up against stuff when moving around in cities, sort of looks like a blind guy trying to get around by feel. Outside in more open country it looks a lot better.

I have hitherto been trying to avoid implementing a "local situational awareness" engine in my system, instead relying on tricks to embed or augment my navigation mesh with the necessary information for real world pathfinding, such as locations of mobs, roads, various POI, etc. I've blown a ton of time on it and I'm still not happy with the results, so I've decided to give up on that approach and implement a proper local navigation system. This is how humans navigate, so if I want human like behavior I should do it in the same way. Easily said, but very hard to accomplish.

Here's the basic idea. Suppose you, as a human player, want to take your character from Elwynn Forest to Grizzly Hills in Northrend. How do you do it? Do you think about every tree, mob, fence, etc, before you even start? No, of course not, you get a general idea of where you're going to go, which areas you'll go through, which flight paths you'll take, etc, and then you watch out for stuff along the way and adjust as necessary.

With a local navigation system, my agent can work the same way. We still use the nav mesh to generate a path to wherever we want to go, but rather than take that path as gospel and follow it like a waypoint graph, it is instead just taken as a rough idea of how to get there, and we generally follow it while adjusting as necessary based on local conditions.

The agent maintains a radar as it moves around, say 100yds [3x3 MNCK grid] This radar will contain everything that you get via the object manager, like mobs, dynamic objects like chairs, doors, etc. In addition, the agent can cast rays into the nav mesh to figure out which areas within the radar radius can be walked through, sort of like TraceLine but out of process and way faster since it's effectively 2D ray casting on the nav mesh. Since it's only looking at a 3x3 tile area of the nav mesh at any given time, there's typically <50 polygons in the radar, so ray casts are stupid fast.

Using this information the bot can follow the predetermined path while also deviating as necessary to stay a comfortable distance from obstacles, avoid aggroing mobs, etc. Since the radar is just a Quadtree of entities separate from the nav mesh, it can be updated in real time, mobs can move, etc, no problems are presented. It makes the whole process way more elegant. It is also possible to deal with dynamic moving collidable objects elegantly, as long as they aren't so big that they invalidate the long range path find.

Adding local navigation also allows the agent to use more advanced tactics than just "go to this location". It can chase fleeing mobs without aggroing other mobs, even if they move, it can act in a coordinated manner with other agents, like "dot up", "spread out", "stand behind the boss", etc. Decent PvP play would be possible. Lots of cool stuff.

Of course, all that is great on paper but actually getting it all to WORK is another matter all together. The implementation becomes way more complex. So far I'm just getting started. My first goal is to implement a sandbox to play with the techniques without having to do it in WoW with a real agent.

Here's a webpage with some local navigation/steering demos if you want to get an idea for the kind of stuff I'm talking about. They even have an open source implementation of some of their ideas I'm hoping I can borrow to some extent.

Steering Behaviors For Autonomous Characters

[namreeb]

I have hitherto been trying to avoid implementing a "local situational awareness" engine in my system, instead relying on tricks to embed or augment my navigation mesh with the necessary information for real world pathfinding, such as locations of mobs, roads, various POI, etc. I've blown a ton of time on it and I'm still not happy with the results, so I've decided to give up on that approach and implement a proper local navigation system.

Can you be a little more specific here with the problems you encountered? I am at a similar *******, and I was thinking the system you're describing as inadequate should be sufficient for us (though obviously a local steering mechanism such as what you describe is more sophisticated). My reasoning is this: in a situation where we want to avoid hostile mobs, we are usually doing only one thing -- going to/from a grind area. In this case, we are in transit to a vendor/mailbox/etc. and are attempting to avoid running through a pack of mobs that will kill us. Now, as you have demonstrated with a previous screen shot, it is possible to mark an area's hostility. This should be done as a function of mob level relative to our own, as well as the mob group density. It should however still derive a universal cost, because sometimes despite there being a huge pack of mobs it may be more efficient to run through them.

Our other movement is inside grind areas, or going from one to the other. In this case, who cares about avoiding mobs? Sure between one grind area and another we may pickup some agro, but we can define the area transition behavior to either path around mob areas or attempt to run through them, etc.

Of course, all that is great on paper but actually getting it all to WORK is another matter all together. The implementation becomes way more complex. So far I'm just getting started. My first goal is to implement a sandbox to play with the techniques without having to do it in WoW with a real agent.

Also would like to hear more thoughts about this sandbox idea. Is it really worth the time investment to do something like that? It seems like you could spend less time making your bot easier to reload in WoW (as in, ejecting it and cleaning up after yourself so you can just reinject w/o restarting, logging in, etc.).

[amadmonk]

Also would like to hear more thoughts about this sandbox idea. Is it really worth the time investment to do something like that? It seems like you could spend less time making your bot easier to reload in WoW (as in, ejecting it and cleaning up after yourself so you can just reinject w/o restarting, logging in, etc.).

I can't, at all, speak to the navmesh stuff, but I can definitely speak to the sandbox stuff. With an emulator server (MangOS is easy to set up), you can play with steering behaviors to your heart's content, and you won't get banned. Similarly, you can toggle godmode on (well, .gm on) and you know you won't get aggro (if you don't want to deal with it while testing something).

In the long run, sandboxing WoW is probably harder than just running an emu and the real game client.

[Sednogmah]

Similarly, you can toggle godmode on (well, .gm on) and you know you won't get aggro (if you don't want to deal with it while testing something)

Another very useful option with MaNGOS is to increase your character's speed up to ten times the normal run speed. Even though this only affects the run speed and not, for example, gravity, it's still great to test your path finding code quickly.

- Select your character
.amodify speed 10

[pendra]

Can you be a little more specific here with the problems you encountered? I am at a similar *******, and I was thinking the system you're describing as inadequate should be sufficient for us (though obviously a local steering mechanism such as what you describe is more sophisticated). My reasoning is this: in a situation where we want to avoid hostile mobs, we are usually doing only one thing -- going to/from a grind area. In this case, we are in transit to a vendor/mailbox/etc. and are attempting to avoid running through a pack of mobs that will kill us. Now, as you have demonstrated with a previous screen shot, it is possible to mark an area's hostility. This should be done as a function of mob level relative to our own, as well as the mob group density. It should however still derive a universal cost, because sometimes despite there being a huge pack of mobs it may be more efficient to run through them.

I think if you implemented some kind of anti-wall-hugging heuristic in your string pull you could probably get away with it in your case, provided you have some control over where you set up your grinding areas and you don't mind if your character looks a little bit botty [still far less than using a waypoint graph].

An idea for an anti-wall-hugging heuristic would be to do something like this:

1) A* to find a sequence of polygons
2) Expand the sequence of polygons perpendicularly to the path by including the adjacent polygons that are fully connected to the path. This gives you a 'wider' channel for the funnel.
3) Run a modified funnel algorithm that pretends the agent has a bigger radius than it really does, and does "as well as possible" to stay within the enlarged radius. This will cause you to stay away from things when yo can, but still be able to get through narrow doors and stuff.

In my situation, I feel this is not an entirely adequate solution since my goal is a bit different than yours -- I want to write a bot that plays like a human player in a completely believable way and can go anywhere in the game that is needed to do quests, etc, so I really want it to "just work".

Also would like to hear more thoughts about this sandbox idea. Is it really worth the time investment to do something like that? It seems like you could spend less time making your bot easier to reload in WoW (as in, ejecting it and cleaning up after yourself so you can just reinject w/o restarting, logging in, etc.).

All I mean is the ability to play with the bot's navigation logic without actually running a wow client at all. I don't think the extra effort will be too bad, since most of it is just in visualizing the results and I want to have that anyway. My ultimate goal for this bot is that I don't look at the real client at all, everything is done via the bot interface which has it's own GUI centered around the nav mesh.

I may be making it more difficult than it absolutely has to be, but for me this project is a lot more about the challenge of doing it right than it is about getting going quickly.

Of course, I will do some testing with the real client simultaneously, in which case I use Mangos. I've never botted on retail servers, I don't even own an account on retail atm. That's a much lower priority.

[RoKFenris]

An idea for an anti-wall-hugging heuristic would be to do something like this:

1) A* to find a sequence of polygons
2) Expand the sequence of polygons perpendicularly to the path by including the adjacent polygons that are fully connected to the path. This gives you a 'wider' channel for the funnel.
3) Run a modified funnel algorithm that pretends the agent has a bigger radius than it really does, and does "as well as possible" to stay within the enlarged radius. This will cause you to stay away from things when yo can, but still be able to get through narrow doors and stuff.

I'm not currently doing navigation, but I would probably go with just:

1) A* with the cost of all polygons adjacent to obstacles increased.
2) Smoothing the path, or feed it to a local solver to loosely follow; that OpenSteer thing linked a few posts above seems like a very good way to make movement behavior that is human like.

[pendra]

I'm not currently doing navigation, but I would probably go with just:

1) A* with the cost of all polygons adjacent to obstacles increased.
2) Smoothing the path, or feed it to a local solver to loosely follow; that OpenSteer thing linked a few posts above seems like a very good way to make movement behavior that is human like.

This works for avoiding trees and other obstacles in open country, but in major cities or other tight areas almost all of the polygons are adjacent to an obstacle, so all you find is a path that follows the wall and then occasionally bubbles out into the middle of the room and back to the wall again at the next door, which looks even worse.

I think for this to work you would have to force really small polygons so that all of your significant areas would have a lot of polygons that are not attached to obstacles. Some tweaks to the regionization algorithm might help, too.

As you mentioned, the OpenSteer approach seems the most likely to work to me, so that's the route I'm going. If you do that, I don't see any point in encoding "distance to wall" within the mesh, since you can pretty easily deal with more elegantly using local nav.

[L33ch]

O Woaahh, this is AWSOME!

Working on something like this, but i'm far behind you, just got stuff out of MPQ files and now i'm breaking my head over rendering.

movement was easy, got my chars all following my main, but it looks rather... meh.

I was wondering if you could point me at some ways to render WMO M2 and ADT files, cos currently i'm trying to understand the wowmodelviewer but that'll take a while :S


ohw, not sure how you implement the dangerous area's, but you could implement paths and have your bot run in the middle of it if moving to a location that's safer/easier to reach by road (players tend to walk in the middle of roads...)


eventually: i want to click on my rendered map and have my chars move there.
shouldn't be that hard, will cost some nights sleep, but doable seeing how others manage

keep up the awsome work


Edit:
Several hours later I managed to render my first ADT's, also i can now start to calculate positions that are walkable... I think...



for intrested: I got much help here: http://www.mpqnav.com/ as wowdev.org is down (was using that first)
mine reads from mpq though not extracted files, is that a bad thing? i think it's a waste to extract all mopaq's if you can just read em....

[namreeb]

checkout WoW.Dev Wiki

[miceiken]

Another very useful option with MaNGOS is to increase your character's speed up to ten times the normal run speed. Even though this only affects the run speed and not, for example, gravity, it's still great to test your path finding code quickly.

- Select your character
.amodify speed 10

As far as I recall, 7 is the normal run speed. Wouldn't that make 'ten times the normal run speed' 70?

[pendra]

I was wondering if you could point me at some ways to render WMO M2 and ADT files, cos currently i'm trying to understand the wowmodelviewer but that'll take a while :S

Use the Wow Dev wiki to get the MPQ format information. Everything you need should be there.

ohw, not sure how you implement the dangerous area's, but you could implement paths and have your bot run in the middle of it if moving to a location that's safer/easier to reach by road (players tend to walk in the middle of roads...)

Sure, at this point I'm using something along the lines of the extruded convex polygon areas in recast. You can represent any kind of area you want. Paths/Roads and "dangerous" are just two types of areas.

eventually: i want to click on my rendered map and have my chars move there.
shouldn't be that hard, will cost some nights sleep, but doable seeing how others manage

I would recommend you start by using recast & detour, and then modify/reimplement things as needed. You can get a long way with R&D, perhaps as far as you need to go. That way all you have to do is parse out the ADT, MPQ, and M2, and you're pretty much done.

[L33ch]

haha! wow.dev is reachable again for me! \o/ yesterday, couldn't...

I would recommend you start by using recast & detour, and then modify/reimplement things as needed. You can get a long way with R&D, perhaps as far as you need to go. That way all you have to do is parse out the ADT, MPQ, and M2, and you're pretty much done.

I downloaded R&D, It looks very nice
Also I managed to do the later you mentioned but... I have a tiny problem....

I'm a C# noob, junky, and addict... meaning i can either work on translating R&D from C (unless I, won't be the first time, misslooked and downloaded the wrong source) or... follow the mpqnav thingy through till i can pick it up on my own again...

also I'm Naïve and think that rendering was the hardest part, which is now behind me

currently my building phases look a bit like:

1 get and render ADT, WMO and M2 stuff
2 Scan for walkable area and map it (i.e. avoid trees and fences <- i'm here, long way to go >.>
3 implement clicking on the map and calculate a road (several waypoints)
4 add bad guys and rightclick = attack function (or something)
5 ???
6 proffit

This works for avoiding trees and other obstacles in open country, but in major cities or other tight areas almost all of the polygons are adjacent to an obstacle, so all you find is a path that follows the wall and then occasionally bubbles out into the middle of the room and back to the wall again at the next door, which looks even worse.

I think for this to work you would have to force really small polygons so that all of your significant areas would have a lot of polygons that are not attached to obstacles. Some tweaks to the regionization algorithm might help, too.

As you mentioned, the OpenSteer approach seems the most likely to work to me, so that's the route I'm going. If you do that, I don't see any point in encoding "distance to wall" within the mesh, since you can pretty easily deal with more elegantly using local nav.

seeing how the map of SW is sooooo detailed, can't you just calculate the distance of a given wall to the wall accross it and have the middle of that line be a waypoint? would be less wall huging~ish not sure if you've found a solution.

looking forward to any updates

[MaiN]

haha! wow.dev is reachable again for me! \o/ yesterday, couldn't...



I downloaded R&D, It looks very nice
Also I managed to do the later you mentioned but... I have a tiny problem....

I'm a C# noob, junky, and addict... meaning i can either work on translating R&D from C (unless I, won't be the first time, misslooked and downloaded the wrong source) or... follow the mpqnav thingy

R&D is C++. What I did was to wrap the whole library with C++/CLI so you can use it from managed code.

[pendra]

1 get and render ADT, WMO and M2 stuff
2 Scan for walkable area and map it (i.e. avoid trees and fences <- i'm here, long way to go >.>
3 implement clicking on the map and calculate a road (several waypoints)
4 add bad guys and rightclick = attack function (or something)
5 ???
6 proffit

Step (2) is >95% of the work. If all you care about is walking outside with some crude ability to avoid m2s/wmos entirely, you could just make your nav mesh include any ADT triangle which:

a) Does not collide with the bounding box of any M2/WMO
b) Has no water in the tile
c) Has a slope that is less than 50 degrees.

This will obviously not allow you to walk inside/over/under/near any models, but if you just want to be able to walk around outside it would work.

Otherwise, you need to use R&D or something like it. Surely, implementing a C# wrapper for R&D would be much easier than rewriting R&D in C#. You should only need to make a handful of R&D calls to build your mesh...

[hobbienoobie]

Using a conversion program from Tangible software it's possible to get a "partial" conversion of c++ files to C#.

The conversion is far from complete. The conversion program adds "warnings" and "todos" where it has problems with converting, but if one is just learning c++ and coming from a C# background, the side by side comparisons helps to see the similarity between the languages. That said, it's a heck of a lot better than hand coding the conversion even if you are a c++/C# pro. I am not recommending this as a substitute for a wrapper (as Pendra notes above). It's just to help with understanding for C++ virgins.

I've uploaded a conversion of R&D to a share site (it's from the google SVN and is from an now two week-ish old R&D commit-- all attributions to original writer intact). The moderators are of course welcome to take this link out if this kind of sharing is "inappropriate".

Converted.rar



HBNB