Jump to content
  • Advertisement
Sign in to follow this  
Myth000

How-To Create an AI map from trinagle coordinates?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!