What nav do you use?

[mrlolguy]

Hi all-

Been leeching here for a while, finally started writing my own bot as of yesterday (uni holidays FTW!). You have inspired and enlightened me to no end.

The bot is currently finding appropriate enemies and running up then dpsing them down without a hitch. I'm simulating key presses for input and targeting by using the write to mem -> targetlasttarget method; and want to get a bit more smart.

Anyway- From a reasonable beginners perspective (Done quite a bit of algos/AI/Maths at uni, but NO Graphics) I'm trying to get a hold of what the status quo for navigation is.

What do you guys use (Navmesh/Pather/Waypoints/Other)? Think it was worth the effort over a simpler method?

Thanks for your wisdom.

[mnbvc]

the coolest method is surely recast and detour, but depending on what exactly you want to do a simple waypoint system can be sufficient

[mrlolguy]

the coolest method is surely recast and detour, but depending on what exactly you want to do a simple waypoint system can be sufficient

From my current research, navmesh seems to take a VERY long time to get off the ground, so I think I'll try and write a waypoint system for now. I have found a few nice cs classes on these forums. (You guys are feking awesome!) Hopefully this works out to be easy!

[caytchen]

Don't ever use waypoints. If you need something simple, build a simple mapper and add A* on top of it.

Or extract the map data and shove it into Recast to build a mesh from it, then use Detour to get paths. (recastnavigation - Project Hosting on Google Code) Remember to not use the binaries, instead grab the source from SVN and compile it yourself. Binaries are _really_ outdated.
Note you can skip the "extract the map data" part by using Flowerews stuff at wowmapper - Project Hosting on Google Code, though I can't recommend it if you're looking to understand the underlying file formats. There is however a bunch of information at WoW.Dev Wiki and it makes for a nice coding exercise.

Or, if you're too lazy for any of these options, use Pather. There is a 3.3.5 compatible version around Omega-Bot forums I think.
Mandatory safety note:
- the code is complete and utter crap.
- it's dead slow, consumes a lot of memory and is verbose.
- it might not find a path even though a valid one exists and it might find a path that is not traversable.
- it might randomly crash, hang up and kill your cat.
You've been warned.

[mrlolguy]

Pather sounded easy, but noone ever posted on these forums mentioning it, and now I guess I know why. Those problems must be utterly catastrophic haha. Does it read MPQs on the fly or something? thats what I sort of gathered. But I'm kinda new.

Don't ever use waypoints. If you need something simple, build a simple mapper and add A* on top of it.

Any way I can get the 2D world map out of the MPQs? I figure if I make a mask for it with OK/not OK zones as a per coord 2d array of bools I'd pretty quickly have a 2d navmap. I'd just be able to grey over the bad areas with 1s and do that manually... Is that what you meant by your first statement cay, or am I reading too far into that haha..

[caytchen]

You kinda read too far into that Basically what you do is create boxes around your current XYZ position when walking around in the game and connect those boxes to other boxes nearby that location. Then if you need a path, you look for a box that contains the start point and a box that contains the end point, and then use A* to find the shortest path between those two over all boxes.

[Cypher]

I don't know if you've ever used it, but what Caytchen is describing is what OpenBot did.

[eLaps]

Any way I can get the 2D world map out of the MPQs?

The "real" maps are in "Textures/Minimap/". The hash table is in "Textures/Minimap/md5translate.trs".
The BLP format is described here.
At 0xce06d0 is the map name (untested, 3.3.5.12340).

Basically what you do is create boxes around your current XYZ position when walking around in the game and connect those boxes to other boxes nearby that location.

Beware of the pits.

[streppel]

how big would you make those boxes? 1 yard? smaller? bigger?
i'm planning on using a navmesh for my bot too(at least for ground navigation,for flyig i'd use WP then due to the fact that i'd have to flag the points in the air only for chars with flying mount etc...more complex then what it gives back^^) so this would be great to know.
i thought about ~2 or 3 yards between the boxes,but i'm open to any suggestion. ofc the smaller the distance is,the more accurate the pathes will be,but there has to be a point where mem usage is more important then accuracy

[Robske]

Don't ever use waypoints. If you need something simple, build a simple mapper and add A* on top of it.

Well this is a bit extreme. There are a couple of examples where a set of user-defined waypoints is the most optimal choice, Gathering bots who use flying mounts for example.
Even a grinding bot can be effective with simple waypoints and a decent 'breadcrumb' system.

My current implementation of a navmesh (which is definitely the wrong word for it) uses a simple graph of waypoint nodes which I record manually by running around. (I run a couple of optimalisation algorithms over the graph to remove excess nodes when I'm done) It's not the best solution as I have to map everything myself... but it's the best I can come up with because I'm too much of a dumb**** to create a real navmesh

[caytchen]

Well this is a bit extreme. There are a couple of examples where a set of user-defined waypoints is the most optimal choice, Gathering bots who use flying mounts for example.
Even a grinding bot can be effective with simple waypoints and a decent 'breadcrumb' system.

I see where this is overengineered for the case of flying, but then flying navigation is a whole different game anyway. If you have waypoints, all you basically need is to add A* on top of it. In fact, your waypoint graph sounds alot like what I had in mind
And yes, this is what OpenBot did, but it used LavishNav so it's not really a good reference. And don't be fooled by the simplicity, I've built a 1-80 hands free bot on this simple scheme (though refined with some collision magic).
Nowadays, with all the public information and even code out there, and with RecastDetour, building a NavMesh is like a week of work. Hell, next week someone might just do the last and final step and release finished meshs for Detour.

[Därkness]

My bot isn't very complete/good, but im currently using the method Robske is, a bunch of user-recorded waypoints that are linked togather in a "mesh" + A* pathfinding. Im working on a visual editor so I can edit work between 2 points, etc.

[Apoc]

I see where this is overengineered for the case of flying, but then flying navigation is a whole different game anyway. If you have waypoints, all you basically need is to add A* on top of it. In fact, your waypoint graph sounds alot like what I had in mind
And yes, this is what OpenBot did, but it used LavishNav so it's not really a good reference. And don't be fooled by the simplicity, I've built a 1-80 hands free bot on this simple scheme (though refined with some collision magic).
Nowadays, with all the public information and even code out there, and with RecastDetour, building a NavMesh is like a week of work. Hell, next week someone might just do the last and final step and release finished meshs for Detour.

LavishNav was just a simple wrapper around a 3D regionized-mesh. It supported most 3D objects (spheres, boxes, etc) and allowed you to use A* or Dijkstra to find paths. Honestly; it's just another form of a nav 'mesh'. Just because all the complicated tidbits were hidden away in a very well designed wrapper, doesn't mean OB should be excluded. (It's still one of the few 'production' bots to use a nav mesh)

Lastly; nobody will release 'finished' meshes for Detour. It's impossible, since everyone's needs are different. Not to mention that R+D don't support flight boxes, so it's completely out of the question for WoW unless you like to stay grounded. (Which means places like the floating instances, etc are off limits unless you do some magic with jump links)

[caytchen]

LavishNav was just a simple wrapper around a 3D regionized-mesh. It supported most 3D objects (spheres, boxes, etc) and allowed you to use A* or Dijkstra to find paths. Honestly; it's just another form of a nav 'mesh'. Just because all the complicated tidbits were hidden away in a very well designed wrapper, doesn't mean OB should be excluded. (It's still one of the few 'production' bots to use a nav mesh)

Lastly; nobody will release 'finished' meshes for Detour. It's impossible, since everyone's needs are different. Not to mention that R+D don't support flight boxes, so it's completely out of the question for WoW unless you like to stay grounded. (Which means places like the floating instances, etc are off limits unless you do some magic with jump links)

And that wrapper is closed source.

Take a look at the bot landscape, I think everyones needs are pretty much the same: shortest path from A to B, exclude or include water. Down the road you may want to make roads cheaper and enemy ridden areas more expensive, and Detour provides that.
Since you mentioned jump links, flightmaster and other means of transportation can be abstracted away from the original mesh and handled transparently. (does any commercial bot out there even do flightpaths and intercontinental?)

[mrlolguy]

Is there any complete guide for the MPQ->Detour Process? I have found a few posts about doing so, but ATM I have little to no idea how I should be reading the ADTs... I managed to find .trimesh files for Honorbuddy on the internet, anyone had any success in reading those? Theyre just garbled numbers so I figured it might just be an array of doubles written to a file as-is, but had no luck in getting useful results reading in that method.