.:: Bots United ::. - Navmesh Idea

.:: Bots United ::. (http://forums.bots-united.com/index.php)

- General Bot Coding (http://forums.bots-united.com/forumdisplay.php?f=24)

- - Navmesh Idea (http://forums.bots-united.com/showthread.php?t=3184)

sfx1999

12-12-2004 06:13

Navmesh Idea

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

12-12-2004 07:04

Re: Navmesh Idea

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

Pierre-Marie Baty

12-12-2004 15:43

Re: Navmesh Idea

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

12-12-2004 19:34

Re: Navmesh Idea

PMB how does it handle floor above floor?

Pierre-Marie Baty

12-12-2004 22:55

Re: Navmesh Idea

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

12-12-2004 23:23

Re: Navmesh Idea

i don't understand a shit of that :(

Pierre-Marie Baty

13-12-2004 02:57

Re: Navmesh Idea

it's easier to understand with the tutorial at hand ;)

Cheeseh

13-12-2004 16:09

Re: Navmesh Idea

like-a this...

player stands at x,y...

Code:

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

13-12-2004 17:07

Re: Navmesh Idea

yup, exactly :)

All times are GMT +2. The time now is 16:02.