Sign in to follow this  

Applying A* pathfinding

This topic is 2056 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

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!

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

This topic is 2056 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this