Navigation System design process

[MaiN]

interesting approach, did you have to modify FindPath function to implement it ? How perfomance wise ? For a long path, say from BB to very Chapel - did you hit limitation on loaded tiles ?

thanks

I modified findPath, yes. The performance hasn't decreased by much really. I didn't hit the limitation on the loaded tiles (from Moonglade to Silithus it actually did, but I increased the max tile count).

[namreeb]

I forgot to mention. What ended up working best for us was to apply a flood-fill removal of mesh polygons which were not reachable from a collection of starting points (we used the coordinates of the racial starting points on both horde/alliance side for a given continent). This made the mesh data approximately 60% smaller and allows us to load an entire continent without taking up too much RAM.

[FenixTX2]

I've been working on this for a few weeks now. It's been up and down.

The system I am using is very similar in the way the BGP routing protocol abstracts it's paths. And allows me to maintain a very small memory footprint whilst also allowing even long distance paths to be generated in milliseconds.

I was testing it out this afternoon and noticed that my input geometry for the nav meshes varied quite a bit from what it should be.
Here's an example:



The image shows the entrance to the town hall in redridge. What we see in game as a short slope and then a wooden walk way appears in the adt files to be a bloody great big wall.

There are plenty of other examples - caves with blocked entrances etc.
What are the rest of you doing to mitigate this? Reading the geometry from the running client as you approach it?

This particular example appears to be an error stemming from my use of Flowerews' wowmapper.
Has anyone else encountered this problem?

[Flowerew]

Some other user (Madhatt3r) already reported that issue and I don't know where it's comming from, and I don't really have time to investigate the issue. I know that it has not always been this way. I used the exact same tile of Lakeshire to verify everything worked correctly back then, cause this tile has alot of rotations and stuff going on like doodads on top of each other, wmos with interior, water etc... but that was back in v3.3.3. Maybe someone can check if it's related to WoW's version. If it's not it's almost 100% certain something went wrong during revisions on my side, cause again: I had it working back then. Best regards

[caytchen]

MPQNav suffers the same problem. This is, however, an error in the parser. Proof attached, with geometry generated from my own parser. I'd love to tell you what exactly the error is, but honestly I have no idea. I didn't encounter this problem when following the wowdev resources.
The only thing you would ever have to mitigate is dynamic gameobjects, things like mailboxes, basically anything that will get brighter ingame if you hover over it.
I guess you could create a database and include those models in your static mesh generation, but thats pretty much overkill since there are two other, easier options: make regions with objects on them cost more at runtime and add some basic stuck handling to circumvent them. You'll need that anyway since CTM isn't perfectly accurate (stops ~0.25y short of the actual target) and your navigator will most likely steer for the next hotspot before you've reached your current one. While the error is small, it's amplified by the fact that you have complete mapping data and that pathfinding algorithms have this tendency to cut corners since they'll give you an optimal path. Thats something Mikko is looking into though, see his blog posts on visibility optimized graphs.
You could navigate with just moving forward and facing manually, but I've found CTM to work smoother at very low framerates, which is critical to operating multiple bots simultaneously.

[FenixTX2]

It's a shame that the MPQNav website went down it had some really useful insights. Although it's not perfect, i found a web archive of the mpqnav blog: MPQNav Public Blog | WOW Navigation from MPQ Files Hopefully someone will fiind that useful.

[MaiN]

I've been working on this for a few weeks now. It's been up and down.

The system I am using is very similar in the way the BGP routing protocol abstracts it's paths. And allows me to maintain a very small memory footprint whilst also allowing even long distance paths to be generated in milliseconds.

I was testing it out this afternoon and noticed that my input geometry for the nav meshes varied quite a bit from what it should be.
Here's an example:



The image shows the entrance to the town hall in redridge. What we see in game as a short slope and then a wooden walk way appears in the adt files to be a bloody great big wall.

There are plenty of other examples - caves with blocked entrances etc.
What are the rest of you doing to mitigate this? Reading the geometry from the running client as you approach it?

This particular example appears to be an error stemming from my use of Flowerews' wowmapper.
Has anyone else encountered this problem?

I don't have this problem either.

Looks like a problem with the parser.
It seems like the matrix transforms are wrong or something.
This is how I set the matrix up:

public Matrix IngameMatrix
{
    get
    {
        if (!_ingameMatrix.HasValue)
        {
            WMOPlacementInfo info = PlacementInfo;
            float xPos = -(info.Origin.Z - 17066.66666f);
            float yPos = -(info.Origin.X - 17066.66666f);
            float zPos = info.Origin.Y;
            var origin = new Vector3(xPos, yPos, zPos);

            float rotX = MathHelper.ToRadians(info.OrientationC);
            float rotY = MathHelper.ToRadians(info.OrientationA);
            float rotZ = MathHelper.ToRadians(info.OrientationB + 180);
            Matrix transformToParent = Matrix.CreateRotationX(rotX) *
                                       Matrix.CreateRotationY(rotY) *
                                       Matrix.CreateRotationZ(rotZ) *
                                       Matrix.CreateTranslation(origin);
            _ingameMatrix = transformToParent;
        }

        return _ingameMatrix.Value;
    }
}

All the vertices read from the vertex chunk in the WMO are transformed by this matrix.

[caytchen]

There is something that worries me, though. I didn't bother to implement MPQ reading code so I just pretty much extracted everything from each MPQ into a central directory. However, there are many duplicate files. Is there any specific order from which the MPQ files are searched? Or, put differently, which MPQs get priority?

[Bananenbrot]

That's something I was also wondering lately. namreeb said, that you have to read them in reverse alphabetical order.
That makes sense, the model editers are using patch-9.mpq (or something similar) for their "patches".
At least that's how I solved an issue with a northrend adt (in lichking.mpq), where a wmo was listed with 5 group files although there only were 4 in every mpq I scanned.

[namreeb]

Yes, when you are trying to open a file that exists in multiple MPQs you must open it from the MPQ that comes last when listed alphabetically.

[MaiN]

There is something that worries me, though. I didn't bother to implement MPQ reading code so I just pretty much extracted everything from each MPQ into a central directory. However, there are many duplicate files. Is there any specific order from which the MPQ files are searched? Or, put differently, which MPQs get priority?

I used to do this too for speed. Not a good idea. I began facing problems where meshes didn't fit terrain. Turned out the terrain had been updated in a patch. This was in Thunder Bluff when it was updated with zeppelins. I started checking doodad sets and my doodad handling before even thinking about it.

[caytchen]

I used to do this too for speed. Not a good idea. I began facing problems where meshes didn't fit terrain. Turned out the terrain had been updated in a patch. This was in Thunder Bluff when it was updated with zeppelins. I started checking doodad sets and my doodad handling before even thinking about it.

Maybe I shouldn't be so damn lazy and actually implement this.. might explain for some pathfinding hiccups I've seen - hiccups as in clearly wrong paths, where I could never tell the difference when comparing the actual WoW rendering with a Recast .obj dump.

[DrGonzo]

That wall issue/blocked cave entrances, could that be a problem with parsing and removing holes? Cave entrances specifically have holes in the terrain to expose the opening.

[Bananenbrot]

You should look at how you scale .m2's.
If I should guess, the 'wall issue' is because of the wooden... pier (<- replace with right word here), its scale is much too big.
Compare my pier with yours and take a look at the weird dangling cuboid in your picture.

[FenixTX2]

I 'think' i've solved my problem. Inside wowmappers adt_c.cpp class there is a method:

void Adt_c::GetDoodads(Meshes_t *meshes) {
   for (AdtDoodads_t::iterator doodad = doodads_.begin();
       doodad != doodads_.end();
       ++doodad) {
    const MddfChunk_s::DoodadInfo_s &info = *doodad->info;
    const M2_c *m2 = doodad->m2;

    // add new doodad
    meshes->push_back(Mesh_c());
    Mesh_c *mesh = &meshes->back();

    // if we have a skin we get the real mesh
    if(m2->skin.get() != NULL) {
      m2->GetMesh(*m2->skin, mesh);
    } else {
      m2->GetBVMesh(mesh);
    }

    // don't forget to readjust positions and rotations!
    static const float map_center = 17066.0f + (2.0f/3.0f);
    mesh->SetPositon(Vec3_t(info.pos.x-map_center, info.pos.y, info.pos.z-map_center));
    mesh->SetRotation(Vec3_t(-info.rot.x, info.rot.y-90, info.rot.z-90));
    mesh->SetScale(info.scale/1024.0f);
  }
}

That bottom line sets the scale for the loaded doodad. However the corresponding method in wowmappers mesh_c.cpp class was overriding the input float with 1.0f

void Mesh_c::SetScale(float scale) {
  scale_ = 1.0f;
}

I've changed the code to use the input float and now my maps look correct.

Is this the correct thing to do? I've had a look on wowdev but couldn't find any reference to doodad scaling.
Thanks