4 replies to this topic

[LarryKing]

Okay, so I have a working implementation of Navigation-Mesh path finding in my game - using A*
It works great!
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.

Now this is where the problem arises:
I have to somehow determine which polygon in the mesh contains the player and each-and-every AI entity.
( So I can find the path from the entity to the player )

Regarding my "Meshes"
- All of the navigation-mesh's polygons are convex, containing up to 15 vertices
- A "polygon" is nothing more that a collection of the vertices, and in turn triangles, that make it up, and "pointers" to its neighbors.

I don't know if I should do some sort of ray-cast, compare distances, or some other approach.

Ray-Cast:
- Can be accurately done (my polygons follow a winding order)
- Could be very expensive
- Has to be done for each and every triangle and entity

Distance:
- Cheaper
- Not nearly as accurate
- How would I even get this to return tangible results?

So, I'm stuck as to which approach to choose, a hybrid solution, or a completely different method...
-or simply put, "How is this usually done, efficiently?"
Any ideas or suggestions would be greatly appreciated

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)
http://ruinedgame.blogspot.com/

-Thanks Again

P.S. I'm using XNA, so I have a slight performance overhead...

[jefferytitan]

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).

[LarryKing]

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).

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:

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
}

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

[web383]

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.

[LarryKing]

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.

Yep, that's what I've done

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 most 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!