About pathfinding

[Auntie Mangos]

Hi,

I read this article about NPC pathfinding that someone already posted sometime ago:

http://www.ai-blog.net/archives/000152.html

I also read this post about making a navigation mesh out of WoW maps:

http://getmangos.eu/community/viewtopic.php?id=4371

I have a few questions:

If you compare the following two images:

In the first image, there is an extremely high amount of trianles involved to make the bridge

for a navigation mesh, why can't it be lowered to a few simple quads like on the second image?

It seems to me that it is difficult to make navigation meshes out of maps, since NPC's also

need coordinates to run into castles and buildings? (or are these included in maps?)

Also they need to run around obstacles...

My head question: Why aren't you creating navigation meshes yourself, instead of them being generated?

Thank you

[darkstalker]

could generate boundaries from the mesh triangle, and set virtual obstacles outside it, so you can move the unit using ground level (from vmaps i guess)

other alternative could be omit the navigation mesh completely and assume unknown terrain, the unit discovers it as long as it moves (update obstacles in visibility range). You do more processing but no need to have precalculated data

[smellbee2008]

as you can see

http://img6.imageshack.us/i/image2cne.png/

jolan did a great job and make the movemaps simple so you only need to know in which movezone(square where every point see every other point) the coord is and search way to another movezone where dest coord is. Then you just find path to that movezone and you are 100% sure you have IsInLOS dest point : )

[israweb1981]

Any news about movemaps?

[Derex]

Nobody wanted to manually create navmeshes out of all maps (or at least ralf didn't want), thats why we try to generate them. In the article you posted the navmesh is made by the designer that made the map.

If anybody would volunteer to make navmeshes manually for the whole world (maybe with some 3d software like 3dsmax, or with application that we can code especially for this task) and export it, and keep it up to date, it would be nice and will allow very optimized navigating around the world.

I tried to make a navmesh from the mmaps that ralf made and then apply some mesh optimization algorithm on it (the white lines are from this mesh), so that the end result looks like the navmesh in the blog post, but generated by a program, I tried several well known algorithms for mesh optimizations, but they didn't work very well, I needed to make some super custom algorithm.

So main answer:

My head question: Why aren't you creating navigation meshes yourself, instead of them being generated?

Because we are programmers, we like computers to do what we feel is too much of a repeating task for us to do manually and not go crazy.

[darkstalker]

what is the exact information contained on vmaps? if its the complete geometry then generating additional movemaps is redundant. Random sampling of ground position (probabilistic roadmap) would be enough to calculate approximate paths

[Derex]

The whole picture is vmaps + maps , so not everything is in vmaps.

[vladex]

this is a very intresting subject , but i think that doing pathfinding will require a team of at least 30 programmers to do it .

[Derex]

One developer is enough