Sign in to follow this  
lastlinkx

Navigation Mesh - "Which Polygon?"

Recommended Posts

lastlinkx    484
[color=#4A4A4A]Okay, so I have a working implementation of Navigation-Mesh path finding in my game - using A*[/color][color=#4A4A4A]
It works great![/color][color=#4A4A4A]
I've gotten to the stage where I want to start making some AI actually use the navigation mesh to find the player - always I good point to be at.[/color]
[color=#4A4A4A]
Now this is where the problem arises:[/color][color=#4A4A4A]
I have to somehow determine [b]which polygon[/b] in the mesh contains the player and each-and-every AI entity.[/color][color=#4A4A4A]
( So I can find the path from the entity to the player )[/color]
[color=#4A4A4A]
Regarding my "Meshes"[/color][color=#4A4A4A]
- All of the navigation-mesh's polygons are convex, containing up to 15 vertices[/color][color=#4A4A4A]
- A "polygon" is nothing more that a collection of the vertices, and in turn triangles, that make it up, and "pointers" to its neighbors.[/color]
[color=#4A4A4A]
I don't know if I should do some sort of ray-cast, compare distances, or some other approach.[/color]
[color=#4A4A4A]
Ray-Cast:[/color][color=#4A4A4A]
- Can be accurately done (my polygons follow a winding order)[/color][color=#4A4A4A]
- Could be very expensive[/color][color=#4A4A4A]
- Has to be done for each and every triangle and entity[/color]
[color=#4A4A4A]
Distance:[/color][color=#4A4A4A]
- Cheaper[/color][color=#4A4A4A]
- Not nearly as accurate[/color][color=#4A4A4A]
- How would I even get this to return tangible results?[/color]
[color=#4A4A4A]
So, I'm stuck as to which approach to choose, a hybrid solution, or a completely different method...[/color][color=#4A4A4A]
-or simply put, "How is this usually done, efficiently?"[/color][color=#4A4A4A]
Any ideas or suggestions would be greatly appreciated :)[/color]
[color=#4A4A4A]
You can see more and get a better idea - PICTURES - of what I'm doing on my blog (the last few posts have been about navigation meshes)[/color][color=#4A4A4A]
[url="http://ruinedgame.blogspot.com/"]http://ruinedgame.blogspot.com/[/url][/color]
[color=#4A4A4A]
-Thanks Again[/color]
[color=#4A4A4A]
P.S. I'm using XNA, so I have a [s]slight[/s] performance overhead...[/color]

Share this post


Link to post
Share on other sites
jefferytitan    2523
Hmm, not an expert on implementing this, but my first thoughts would be:
- Each agent keeps a record of polygon it is on.
OR
- Maintain a quadtree/hashtable/whatever of polygons by the x and z coordinates. This will give you a short list so you can check point-in-polygon (flattening to ignore y).

Share this post


Link to post
Share on other sites
lastlinkx    484
[quote name='jefferytitan' timestamp='1337146637' post='4940593']
Hmm, not an expert on implementing this, but my first thoughts would be:
- Each agent keeps a record of polygon it is on.
OR
- Maintain a quadtree/hashtable/whatever of polygons by the x and z coordinates. This will give you a short list so you can check point-in-polygon (flattening to ignore y).
[/quote]

Hmm... that first idea might work,
but I'd still have to check to make sure each entity hasn't been pushed aside / out of the polygon each frame.

So I'm seeing a process of steps like this for each entity:

[CODE]
if (we are NOT still above the same (stored) polygon)
{
foreach of the stored polygons neighbors
{
if (we are above one of these polygons)
{
storedPolygon = neighbor-x
return
}
}

foreach of the Mesh-s Polygons
{
if (we are above one of these polygons)
{
storedPolygon = polygon-x
return
}
}

}
else
{
Move along the path, towards its destination
}
[/CODE]

Does this make sense, or am I still missing something?

Note: my meshes shouldn't have a TON of polygons, each "room" of a level has it's own Navigation Mesh

Share this post


Link to post
Share on other sites
web383    804
Every time an agent is moved or bumped, it should do a vertical ray cast into the navmesh to find the intersection. This will keep your agent's vertical position correctly aligned to the navmesh. The agent can then store it's current polygon. I believe this is how Recast/Detour handles things.

Honestly, I would just start with this approach and profile your results before deciding to optimize further.

Share this post


Link to post
Share on other sites
lastlinkx    484
[quote name='web383' timestamp='1337206184' post='4940781']
Every time an agent is moved or bumped, it should do a vertical ray cast into the navmesh to find the intersection. This will keep your agent's vertical position correctly aligned to the navmesh. The agent can then store it's current polygon. I believe this is how Recast/Detour handles things.

Honestly, I would just start with this approach and profile your results before deciding to optimize further.
[/quote]

Yep, that's what I've done :P

So far it seems to work fine, to speed up the ray-tests I first check the neighbors of the last polygon the entity was on.
-This makes sense seeing how [u]most[/u] monsters don't fly randomly across the map in the blink of an eye

Thanks for the suggestions!

... now all I have to do is figure out a way to prevent enemies from converging along the same path!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this