Navmesh Idea

[sfx1999]

I was looking at PMB's navmesh tutorial and noticed that it recommends ising quadtrees. I was wondering, what if you generated a BSP tree instead? There could be some more complicated navmeshes, and it is relatively easy to find where you are (using planes/lines). When you know where you are, you can traverse the BSP tree and find out what EXACTLY is next to it.

Also, a potentially reachable set could work.

[Whistler]

BSP tree is what's used in Quake3 official bot. However it will just go more complicated.

[Pierre-Marie Baty]

My system isn't a quadtree, it's a hashtable. The only difference with a "normal" hashtable is that the buckets in this hashtable are organized spatially along 2 axises, x and y (which I refer as "parallels" and "meridians" of the world).

Since these buckets are relatively small, they contain each a limited number of walkfaces, hence the cost of the search for neighbours remains low.

It's not the most elegant solution, but it's the simplest and the most effective in regard to its complication IMO.

[sfx1999]

PMB how does it handle floor above floor?

[Pierre-Marie Baty]

simple.... the walkfaces are "stockpiled" in the same bucket in the hashtable. When the bot code needs to determine the walkface supporting a point, it traces down until it finds the ground. Then, the hit point is determined to belong to a particular walkface by summing the angles between the walkface corners. If we have 360, then the supporting walkface is found.

[stefanhendriks]

i don't understand a shit of that

[Pierre-Marie Baty]

it's easier to understand with the tutorial at hand

[Cheeseh]

like-a this...

player stands at x,y...

list of faces = navmeshthing[x][y];

while ( (current_face = next face in list of faces) != NULL )
{
     
    if ( standing_on_face (current_face,player_stand_point) ) 
    // all angles in face from all vertices from stand point add up to 360 degrees
    {
        face_player_is_standing_on = current_face;
    }
}

I think .. from looking at it a while back

[Pierre-Marie Baty]

yup, exactly