I can do this manually of course, but I want to eventually do procedural levels (ala Age of Empires), not steal ones from StarCraft 2
Generate a Waypoint Graph from a Collision Map
January 20, 2011 01:34 AM
Is there an algorithm/technique I can use to generate waypoints based on a 2D collision map such as this? I'm thinking convex polygons with a minimum area, and I can use the midpoints of each shared face as the waypoints. I have a potential field to do local avoidance, I just need a sparse waypoint graph to avoid local optima between 'rooms'.
I can do this manually of course, but I want to eventually do procedural levels (ala Age of Empires), not steal ones from StarCraft 2
I can do this manually of course, but I want to eventually do procedural levels (ala Age of Empires), not steal ones from StarCraft 2
Anthony Umfer
208
January 20, 2011 01:43 AM
Is there an algorithm/technique I can use to generate waypoints based on a 2D collision map such as this? I'm thinking convex polygons with a minimum area, and I can use the midpoints of each shared face as the waypoints. I have a potential field to do local avoidance, I just need a sparse waypoint graph to avoid local optima between 'rooms'.
I can do this manually of course, but I want to eventually do procedural levels (ala Age of Empires), not steal ones from StarCraft 2
That is the "Xel'Naga Caverns" map from StarCraft2, right? Development studios typically put out papers on their games near the GDC after release, you may find something then.
January 20, 2011 01:52 AM
Blizzard uses automatically generated triangle-based navmeshes, with manually placed helper objects, I can tell that from the editor. I'm definitely excited to see what they have to present at GDC about their pathfinding or unit AI.
That said, I'm doing a 2D web-based game, and only using what level data I can scrape from the editor to test my AI with. I know there are resources out there for this. How can I divide a grid-based world into a minimum number of connected convex polygons?
That said, I'm doing a 2D web-based game, and only using what level data I can scrape from the editor to test my AI with. I know there are resources out there for this. How can I divide a grid-based world into a minimum number of connected convex polygons?
Anthony Umfer
101
January 20, 2011 02:04 AM
I'm thinking convex polygons with a minimum area, and I can use the midpoints of each shared face as the waypoints.
You may want to take a look at Recast Navigation.
January 20, 2011 02:44 PM
I'm definitely excited to see what they have to present at GDC about their pathfinding or unit AI.
Saw some of the advance stuff on that (because of my position... don't bother searching for it). Good stuff, Maynard!
To everyone else, he's referring to the the pathfinding session in the GDC AI Summit. The topic about that is pinned at the top of this forum.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
