Mapping (Pathing etc.)

[luciferc]

So for Pathing etc. what is the best way?

I've ruled out reading the terrain (Aka PPather).

But say i am talking about Openbot. Where you would run around and path.

After pathing it would follow that but slowly the path would grow outwards more, well at least it looked like that to me.

So

#1 What is the best Algorithm (A*, Djit, etc.) for Wow Pathing.

#2 How would you go about storing the Path data? (-1 No Walk, 0 NotPathed, 1 Yes)

#3 When storing the path data how would go about calculating long paths?
I was thinking Like grids of 500M or something like that, stored in a bin file or something like that. OR just make a path file for each waypoint area which could be an option.

I've been looking @ diffrent pathing options and still have these questions since most Algorithms have +'s and minuses and i can think of the best way to store path data that uses up the least memory so hoping someone has some good ideas :P.

[UnknOwned]

So for Pathing etc. what is the best way?

I've ruled out reading the terrain (Aka PPather).

But say i am talking about Openbot. Where you would run around and path.

After pathing it would follow that but slowly the path would grow outwards more, well at least it looked like that to me.

So

#1 What is the best Algorithm (A*, Djit, etc.) for Wow Pathing.

#2 How would you go about storing the Path data? (-1 No Walk, 0 NotPathed, 1 Yes)

#3 When storing the path data how would go about calculating long paths?
I was thinking Like grids of 500M or something like that, stored in a bin file or something like that. OR just make a path file for each waypoint area which could be an option.

I've been looking @ diffrent pathing options and still have these questions since most Algorithms have +'s and minuses and i can think of the best way to store path data that uses up the least memory so hoping someone has some good ideas :P.

1
First of all i would say that most algorithms would do. It all depends on your needs. Openbot uses Dijkstra and ppather uses A*.


2
Well there is no need to add data that is not there (Not Pathed), blacklisting certain areas can be a smart move but if you stay within your predefined paths there would be no need for it.

3
You could say one file is smart, but if you **** up you might end up having to do it all over again. But that also depends on how the user can interact with the predefined data.

MPQ based pathing is by far the best but is also quite a project to get into.
Having things predefined is also better than "on the fly" as you can see with Ppather's extremely slow pathing finding across serval ADT's.

Im sure someone here could post you some great tuts on game navigation and pathing. Also keep an eye out for the upcomming AutoIt bot API.
[WIP] - Thermo Panther - WoW Bot - AutoIt Forums

[Apoc]

A* is great when you have a lot of pathing information (I.E: reading from the MPQ's, where you have a full predefined set of data to work with.) Dijkstra really shines when you have fragmented data (I.E: Open-Bot's nav system)

Either way, I suggest you take the time to generate a nav mesh from the MPQ's. This way you'll always know where you can/can't go, and not worry about silly user errors. Plus, the pathfinding is that much faster since you can write the pathfinder around your data, instead of your data around the pathfinder.

Granted, generating a nav mesh is no small task (and takes up quite a bit of HDD space), you'll be happier you went the better route in the end.

For the love of god, don't do what PPather does. Single file reading each time you need a path is just stupid. Not to mention the lack of caching what data they've found to some sort of workable file format to make loading easier the next time a path is needed. Dynamic MPQ reading like PPather will kill performance, and hinder your ability to generate longer paths across multiple zones. (In comparison, PPather (if it can even do it) takes about 80-120 seconds to generate a path from IF -> SW. A pre-generated nav mesh takes about 80-120ms. Most of which is spent loading the data into memory.)

[luciferc]

So for mesh's you mean one large file correct?

I was wondering how i would store it.

int Matrix's?

How would i know the bounds / limits etc. idk

[Shynd]

If you do go the MPQ way, see if you can track down which textures make up roads and parse the ADT files for those textures, thus automatically creating waypoints between all of the major areas. If you manage that, pathfinding even across an entire continent will be simple because each 'node' will just be a bend / change of angle in the road, so you don't have to loop through every single ****ing x/z tile in the map. To fill in the blanks, you use Djikstra to search all x/z tiles around you until it lands on a road, then you path to that road and take the roads to wherever you need to be. Generating the path will be far, far faster and it'll look much more human.

The only hard part is mapping the roads, which you COULD (I suppose) do by hand.

[akh]

So for mesh's you mean one large file correct?

I was wondering how i would store it.

int Matrix's?

How would i know the bounds / limits etc. idk

If you plan to have an algorithm that can calculate paths in 3d I will surgest that you take a look at octrees. By using this datastructure you can store information about your 3d environment without allocating the whole grid.
(I use octrees with dim 512x512x512 pr. ADT, if I had used 3d arrays it would have been 128 mb, but usually an octree only takes up 2-3 mb)

More info here: Octree - Wikipedia, the free encyclopedia

[typedef]

How do they even set waypoints in a the game, is it done xyz or that right click to move crap

[luciferc]

Watched that auto it pathing system but it had no code to look @.

But it operates by nodes and waypoints i have seen so how would i go about storing them / creating. And for trees and stuff if i only use nodes and waypoints between how will i travel to mobs that are for melle (aka tracking objects that are in your way and you've found)

[Apoc]

Shynd; parsing the terrain texture is easy, and a good thing to jump on while you're in the files. I set extra weight on roads and other non-mob paths to give the 'illusion' of a normal player trying to avoid mobs.

And akh, an octree would be good if you're dynamically reading the MPQ's, since you'd be hard pressed for memory at that point, however, with a pre-generated nav mesh, octrees are most definitely not the way to go. (My nav system uses files split into 3MB files. It's a micro/macro combo nav mesh. Macro being that it knows which files to connect for longer paths, and micro for the actual smaller, more specific points to move to) If you already have a generated mesh, you're better off using a system of "blocks" to use as navigable regions. Using straight points is quite a bad idea. (E.g: each region in the nav mesh is navigable, anything outside of a defined region should be avoided.)

[luciferc]

So your talking about like Okay Blocks of 1x1 etc?

If thats what your saying then how do i know the bounds etc. for the area?

Rather than doing waypoints etc. way

[Apoc]

So your talking about like Okay Blocks of 1x1 etc?

If thats what your saying then how do i know the bounds etc. for the area?

Rather than doing waypoints etc. way

Nav mesh != waypoints. They're pretty much the opposite.

A nav mesh is a.. mesh... of navigable regions. Waypoints are pretty much "you can go here, then there, then there, in that order" type thing.

As for the "blocks", that's entirely up to you. I did variable sized regions so that I could do large (max size was 500x500x500, min is 1x1x1 [or close to a 'point']). This means anywhere that there is a region, you can path to it. Once you get somewhere outside of the region, it's either non-traversable, or somewhere blacklisted. (Regions have flags specifically for that. [BitMasks ftw!])

As for the bounds of the area, I usually have each specific area split into 4-5 files of nav data. (Usually 4 blocks, NW, NE, SW, SE, sometimes 5 if it's an area with large ranging Z values) Then just figure out how to "connect" each area.

[akh]

Shynd; parsing the terrain texture is easy, and a good thing to jump on while you're in the files. I set extra weight on roads and other non-mob paths to give the 'illusion' of a normal player trying to avoid mobs.

And akh, an octree would be good if you're dynamically reading the MPQ's, since you'd be hard pressed for memory at that point, however, with a pre-generated nav mesh, octrees are most definitely not the way to go. (My nav system uses files split into 3MB files. It's a micro/macro combo nav mesh. Macro being that it knows which files to connect for longer paths, and micro for the actual smaller, more specific points to move to) If you already have a generated mesh, you're better off using a system of "blocks" to use as navigable regions. Using straight points is quite a bad idea. (E.g: each region in the nav mesh is navigable, anything outside of a defined region should be avoided.)

I have looked into the navigation meshes and as you pointed out it seems to be the optimal way to store information about the "walkable" areas. One of the better reads were this article, which clearly shows how superior nav meshes are compared to waypoints.

When I tried to find information on how you actually build a nav mesh, there was supprisingly few hits. I found a book called "AI Programming Wisdom" on google books, and there was a section called "Building a Near-Optimal Navigation Mesh" which was great.

Now I have a couple of questions.
First, do your mesh consist of only triangles or do you use n-sided polygons?
Secondly how do you reprecent that the toon can move in a 3d space, e.g. in areas with water, and areas where flying is permitted?

[Apoc]

I have looked into the navigation meshes and as you pointed out it seems to be the optimal way to store information about the "walkable" areas. One of the better reads were this article, which clearly shows how superior nav meshes are compared to waypoints.

When I tried to find information on how you actually build a nav mesh, there was supprisingly few hits. I found a book called "AI Programming Wisdom" on google books, and there was a section called "Building a Near-Optimal Navigation Mesh" which was great.

Now I have a couple of questions.
First, do your mesh consist of only triangles or do you use n-sided polygons?
Secondly how do you reprecent that the toon can move in a 3d space, e.g. in areas with water, and areas where flying is permitted?

I use 2d boxes for most areas, 3d boxes for areas where the z axis changes. (I.E: going up ramps, around staircases, etc) I find it more efficient to store a small flag in each region that can tell whether said region contains a Z axis, and some other small information. (You save a shitload of HDD space. And memory too )

Areas with water are again, boxes, anything within the 3d box can be navigated. Though water has lower weight than normal terrain. And obviously lava and harmful terrain types have very very low weight. (They can be traversed, but should be avoided if at all possible.)

And yes, AI Game Programming Wisdom is an awesome series of books. (I actually used parts of those books to create the GOAP system in OB.NET. Though, the mesh I did from trial/error and a lot of thinking and messing around.)

Actually building the nav mesh is kind of difficult if you have no prior experience with nav meshes. (Thankfully, I was an Open-Bot dev, so I had enough experience with nav meshes to get my head around the concept and think of a practical way of doing things. [P.S: Thanks Lax!])

[luciferc]

So after seeing all this i came up with this idea XD



And then i made a picture of it. I even wrote my name in it :O.

And if anyone says its not to scale i will ****ing kill you i know it isn't.

[UnknOwned]

So after seeing all this i came up with this idea XD



And then i made a picture of it. I even wrote my name in it :O.

And if anyone says its not to scale i will ****ing kill you i know it isn't.

Seem like you got it right.


Now the only problem with that being that it is 2D and imagine you going up stairs that overlap each other or go into caves that are "under" the terrain..
This was also a weakness of OpenBot with a 2D mesh.