Got questions on navmesh manipulation. < Some background on questions: > I'm trying to align my rectangular nodes of navmesh so that my paths are created w/ better quality. By aligning I mean configuring nodes so that nodes don't zigzag to produce small edges which doesn't really give much info on how much room i have while moving through that portal. (And aesthetically it would produce better paths.) I use string pulling as post process to smoothen my path and thought it might help to have em nodes aligned. The approach I took is likely to produce more nodes of smaller size cuz in order to get rid of zigzagged nodes I need to some how sort them and the left overs will end up being smaller nodes. (Which got me thinking again that this will also result in many portals w/ little info on how much space i can guarantee while passing thru it.) While I was considering my algorithm to align nodes, I remembered reading something about merging & splitting nodes to produce better paths. Seemed to me that aligning would rather produce the due result but would also have some problems cuz it's not so complicated to handle all exceptions. To match the very need to produce better paths, manual manipulations(merge & split) seems inevitable to me. < Real question: > So, the basic need is to produce better path especially when path can be achieved in a straight line(no obstacles in between) which is likely to have some problems w/ zigzagged nodes. (maybe i'm assuming wrong but it seems like a good optimization.) 1. Any suggestion or direction you can offer me on the idea of aligning itself or the method of which it's done. 2. Is it needless to do aligning when split and merge is supported? (if u know any resource on split & merge(Algorithm) plz share it w/ me. it would help a lot.) 3. Am I going off on the wrong path here? To use these methods to produce better results? Looking forward to your replies. Thanks for reading.

OK I'll share my failure w/ u all since I've never shared anything here.

//------------------------------------------------------

Underlying system:

rectangular navmesh from 2d grid.

A* Pathfinder & String pulling.

//------------------------------------------------------

My initial approach to optimize my rectangular node based navmesh was by reducing small edges(portal) which is made by zigzagged rectangular nodes.

I would luv to post a visual assistnace to what I just said above but I'm not used to HTML and so I'll try my best in words.

-----
////|/////| OK, maybe not in words lol. Now u know what I mean by zigzagged!
---- /////
|///|/////|
|///|-----
----

So I wanted to get rid of that cuz it wasn't so good to have a poral w/ size 0.5f for example.

It would cause zigzagged path for my pathfinder and even when I do my string pulling scheme, due to the length of the portal It won't be straightened out.

I wanted to do something about it.

So I thought of having my nodes in aligned fashion.

----------
|///|////| There! I wanted to arrange my nodes so that it would look something
|///|////| like that.
---- ----

The challenges that I faced are as follows:

1. If I expand(looped expansion to left/right/top/bottom) trying to form the largest rectangular node possible, small edges are very likely to be produced.
(I do have max area limit for nodes so it's not absurdly large.)

Expanding without limitation meant that it wouldn't care for it's arrangement w/ surrounding nodes. Here I felt the need to have a limit of sort to force alignment.


2. I instantly realized that if I forced alignment, it would cause many smaller nodes to be produced cuz whatever is left from aligning would produce small fragments.

I knew this would happen but figured that I'll deal w/ it when I see how my graph appears.

3. I needed a rule to enforce alignment. I was confused here cuz I have to define them for my own needs.

Here I choose to use squares to limit expansion.

ex)

GenerateNavGraph(int MaxSize, int MinSize)
{
for(MaxSize to MinSize)
{
Fill Square(Current Size x Current Size) & produce node;
if(Failed to fill current Size of square) == something inside was blocked
{
newSize = current Size /2 ;
Try Filling failed area w/ newSize using same method as above;
}
}
}

I hope this makes sense.

Above is what I did to enforce alignment.


It came out to have aligned nodes but as expected, with many more smaller nodes especially around blocked grids.

I also did merging between suquare nodes within the same bounding Square which again produced zigzagged nodes.. so this was really depressing.

I wanted a way to down-size the number of nodes but failed to do it with this approach cuz it kept producing zigzagged nodes if any sort of merge occured.
(not always but couldn't predict..)

Cuz merging breaks my alignment rule with surrounding nodes.

I realized that this approach had too many problems for just getting rid of small portals.

I took a different approach to down size number of nodes and produce better path result by sorting them(low level grid) in the order of largest area that can be achieved.

I'd pop the largest and fill that and next.

I had to check every attempt, if any of the previously filled node overlapped my current attempt.


I failed here AGAIN!! cuz the process of locating largest area meant loooong search time. Horrible it was when I tried map size of 1024 x1024 or even 512..

Currently I've setteled for what I had in the first place..(Ouch) and am thinking about merging and splitting manually instead of an algorithm.

I don't know if this wil be any help to you but I hope someone reads with interest.

I am worn out from this.. attempts though I must say it was fun.

Anyways thats all I got to share for now.

Many thnx for viewing my thread. Take care.

I have been trying to find any information on Navmesh creation, and can't find any!!!! =( Do you have any links I can look at for the steps of creating and using one? What did you look at to learn enuf to get this far? Its like a secret =( Everyone talks about how navigation in wide open areas has a solution through navmesh and there is no longer an excuse for implementing poor path finding in large areas, however there is practically nothing on the net indicating how a person would create, implement, and use it =\

Quote: Original post by HumanoidTyphoon
I have been trying to find any information on Navmesh creation, and can't find any!!!! =( Do you have any links I can look at for the steps of creating and using one? What did you look at to learn enuf to get this far? Its like a secret =( Everyone talks about how navigation in wide open areas has a solution through navmesh and there is no longer an excuse for implementing poor path finding in large areas, however there is practically nothing on the net indicating how a person would create, implement, and use it =\

I noticed this as well; I get the impression everyone does it slightly differently. Fret not however, there is hope!
A good navmesh approach I came across some time ago is TRA*; a technique that decomposes your map into triangles and uses the result as a graph structure to pathfind on. You can read that paper here.

Paul Tozour also very helpfully posted a bunch of such resources in a (somewhat) recent article on pathfinding which you can read here (look right at the bottom, before the comments).

I use string pulling, plus skip ahead.

As my NPC is moving along, I spherecast to nodes up ahead in the path. If its clear to them, I just walk towards them rather than towards the nearest node.

This effectively eliminates zig-zagging.

Quote: Original post by HumanoidTyphoon
I have been trying to find any information on Navmesh creation, and can't find any!!!! =( Do you have any links I can look at for the steps of creating and using one? What did you look at to learn enuf to get this far? Its like a secret =( Everyone talks about how navigation in wide open areas has a solution through navmesh and there is no longer an excuse for implementing poor path finding in large areas, however there is practically nothing on the net indicating how a person would create, implement, and use it =\

Check out AI Game Programming Wisdom 2 and 3. Several good articles in there. Then do a search for the articles they cite and articles that cite them.

I first approached navmesh w/ game programming gems 1.(book)

It had many articles on it regarding pathfinding and navmesh.

I don't know much on actually generating low level data for building navmesh cuz most of the time it was given in the form which I can extend to building navmesh.

ex) 2d suqare grid map or map data consisting of triangles(primitive) made from 3dmax.

So all I had to do was find some sort of a rule to make nodes out of em and store linkage(neighboring means can travel to) those nodes which finally would give me the navmesh.

I know this is not much of an explanation but I'm sure u would find it easier to read through the books suggested.

I think there are some ref pages on this site that gives good info on the whole pathfinding and navmesh. (Resource page, I suggest u check that out as well.)

Hope it helped!

Ok thanks guys. Will check out the resources ^_^