Hello, I want to create an AI map so I can use my pathfindig algoritm to go through it. This map should look like, for example: ------------ ---XXX------ ---XXX------ ---XXX------ ------------ ------------ Where X is an obstacle, like for example a very steep hill or a building. So if the diffrence in height is too big an X will be placed. I have to create a map like this from a list of coordinates. Alot of coordinates... The coordinates are like this: triangle[0].Vertex[0].X triangle[0].Vertex.Y etc... You know, just 3x3 vertices for each triangle. How could I create such a map of that? Loading them all and then going trough all for each triangle and see if some vertex on the same position (or near it) has an height diffrence of some thing? Little height diffrences or non-steep hills aren't obstacles. I would like some advice here. Also when it scanns a building with a roof the roof should't be soon as obstacle... EDIT: The size of the AI map doesn't matter it can be very big. Thanks for your help, - Myth

I am doing the same thing as you describe right now in my game.

Sounds like you want to automate the process, like I am doing, rather than have designers place waypoints manually.

First you have to decide if you are doing cells or points. I am using points.

Next, you have to scan your 3d world in some way to find all traversable units at some density.

I use a 1x1 meter probe of the level, looking for areas that could be walked on. I create a navigation node for each of these.

Then once all are created, for each valid 1x1 meter area, I look at its 8 neighbors and see if I could walk to them, and if so, I mark that as a valid path, and store the cost.

If you only have a 2d path to travel on, you can store the nodes in a 2d array.

If not, you must use a hashtable, map, set, or some other sparse structure.

What you can do, once you have your top view of what's an obstacle and what's not, is create an outline for each obstacles (merging those who overlap), then run a triangulation process to actually build a mesh of everything inside these outlines (outline the borders of your world). That's what we used for our game and it works perfectly. We then merge triangles that can form convex polygons to lower the amount of nodes.

We use a modified version of the Delaunay triangulation process

Hope this helps

Eric

Thank you guys for the advice. I think I'll be able to create an AI map.

Quote:

We then merge triangles that can form convex polygons to lower the amount of nodes.

I love how such a non-trivial problem gets a small throw away line! ;) Out of interests sake, how did you choose the merge ordering for triangles?

Cheers,

Timkin