This topic is 4480 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
All day and no thoughts above and beyond the ideas that I mentioned?

##### Share on other sites
I think that the axis-aligned constraints on your current method are the biggest problem. I think it would be worth your time to examine different ways to convert to a non-aligned mesh. Your bot would be able to handle more radical level design much more easily that way.

Let's take your rectangular room with rounded corners for example. Using a common pattern from your pictures, it looks like there will often be thin strips along the walls because of the rounded corners. If you raycast each vertex of the AABB sectors against the vertices of the other sectors and throw away rays that cross the existing edges of the AABBs, you would generate extra edges that could be used to merge the AABBs into a single octagonal mesh. Same thing would happen on ramps and stairs - you would generate a sloped feature.

##### Share on other sites
The preference for keeping it AA is for simplicity, and because small zones like that won't really ever be used anyways so I could probably just delete them if I really wanted. The AA constraint doesn't really apply to the vertical axis, as a later step will drop the sectors to the floor, forming a contour on ramps and stuff. That's the idea at least. I'm not adamantly against a convex mesh approach, I'm just not yet convinced it's that much better. I welcome thoughts and ideas on that approach as well though. Given that the CS:S bots are able to navigate pretty well with a AA nav mesh I figured it would be good to try my own version of that first off. Going to an arbitrary mesh or convex meshes it a whole other problem. I thought about using the AABB grid after the first step as triangles for a tri-mesh, and then run it through a processor to optimize the dense mesh into convex shapes. Anyone know of an algorithm that does this?

##### Share on other sites
Personally, I found creating navigation meshes out of arbitrary planar polygons with a shared vertex list to be the simplest and cleanest option for most scenarios. In one effort I worked on, I also tagged edges with different kinds of information; whether the polygon borders on a solid and vertical wall, for instance (situation; a monster that can scrabble partially up a wall when running and taking a hallway corner at speed), whether or not the adjoining polygon is a climbable wall (situation; ladders, vines), and a bit more.

Axis-aligned areas are well and good, but I find it harder to get information about the adjacent areas; arbitrary polygonal meshes are a simpler matter, since they always meet at edges. I also found mesh-based navigation to give a cleaner solution to the rounded-corner problem.

But that's just my ¢2.

##### Share on other sites
Mind sharing how you ended up generating your mesh for it? I'm looking for ideas for mesh generation in the situation where you don't have access to the map geometry. The flood fill seems like the best solution for step 1, whether the target is an arbitrary mesh or an AABB based mesh. I can dial down the grid size more to get finer detail but the part I'm unsure how to handle best is how to turn the resulting flood filled grid into the actual mesh. Any ideas? Or if you have ideas that don't involve the initial flood fill I'd love to hear those too. With the restriction of not having direct access to the map geometry the flood fill is the best I've come up with so far for building a nice map of my own.

Assuming my flood cells end up as quads on a smooth mesh what sort of algorithms are used to smooth it and turn a room for example from a many triangle cell into a convex room.

I'm interested in building an actual mesh instead of the AABB mesh if I can figure out some of these questions. I'm not locked into the AABB method.

I considered building the mesh by extruding the edge of each flood fill node as it floods the map, in theory ending with a continuous mesh which could then be optimized into large convex sectors, but I'm not familiar with good algorithms to do the merging and optimization part.

##### Share on other sites
Anyone with nav mesh experience please see this thread and share any info you may have.

1. 1
Rutin
45
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633407
• Total Posts
3011700
• ### Who's Online (See full list)

There are no registered users currently online

×