Good day everyone,
Im using c++ btw:
I've just finished and cleaned all the bugs out of a 3D graphics engine (vbo's and textures holy cow the bugs) and have a simple little function that loads models, textures, and unit information.
I won't bore you with details, but for the AI I have a "radius" of each unit. Basically, the unit will take up that much space, and there must be free space, if not the unit will either be pushed out of the way, or push others out of the way.
Now, the problem: for A* pathfinding, a 2D grid of open/closed values is necessary. what are your thoughts on making different grids per unit, because all units have different radii? Or should I make a different grid per 0.1 difference in radii? Like, a grid for 0.1,0.2,0.3...1.2,1.3, etc?
Thanks for any replies!
Applying A* pathfinding
A fairly standard solution is to use a navmesh and local steering instead of a pathing grid.
i'd recommend building a grid which is the average size of all your possible sizes, and then allow an path agent(or unit in your case), take up multiple nodes depending on their size. as well, if done correctly, you shouldn't have to "push objects" since no objects should overlap in a grid based pathing system.
use Recast http://code.google.com/p/recastnavigation/
it is MIT licensed. practically "do what you want' license
it is MIT licensed. practically "do what you want' license
Author
Ok, I may end up using recast to make navmeshes en masse, but for now I just need to implement the logistics of it.
I'm thinking that the navmesh will be of triangles, and I will run an A* algorithm based off the center of each triangle to get the basic path. However, I think it'd be most effective to add a lower level of navigation, but I don't know how. I don't want it to blindly walk to the center of each navmesh, because that's basically making it a waypoint graph. If the unit needs to get to a destination in the same nav triangle that's easy, but how do I get a unit to intelligently take the shortest path without burning all kinds of performance?
Example shown in image. Green and Red are start and destination, black lines form triangles (navmesh), beige lines represent shortest path.
I'm thinking that the navmesh will be of triangles, and I will run an A* algorithm based off the center of each triangle to get the basic path. However, I think it'd be most effective to add a lower level of navigation, but I don't know how. I don't want it to blindly walk to the center of each navmesh, because that's basically making it a waypoint graph. If the unit needs to get to a destination in the same nav triangle that's easy, but how do I get a unit to intelligently take the shortest path without burning all kinds of performance?
Example shown in image. Green and Red are start and destination, black lines form triangles (navmesh), beige lines represent shortest path.
You don't need to take the truly shortest path; a reasonably short path will suffice. The typical way to do this in combination with navmeshes is local steering systems, as I mentioned above. Some quick research on steering systems should get you started.
Author
Ok, that makes sense enough. Come to think about it, using local steering systems makes it easier to account for other mobile units!
Just a quick question, what do you think the best way to send this data to the individual agent is? Would you recommend a std::vector of navmesh pointers, or is there a better way?
Thanks!
Just a quick question, what do you think the best way to send this data to the individual agent is? Would you recommend a std::vector of navmesh pointers, or is there a better way?
Thanks!
Do the simplest thing that could possibly work. In your case, a vector of navmesh locations is probably fine. If and only if you find problems with that approach, you can look at alternatives, but generally unless you're talking thousands of units the cost of moving around a few small vectors will be negligible overall.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
