Pathfinding Is A* good when entities should collide with eachother?

Recommended Posts

Kylotan    10002

A* is about finding paths, or more abstractly, about finding the cheapest route through a graph, that's all. It has no opinion on entities or collision between them.

You can recalculate a new A* path when the current one ends up being blocked, and that is often good enough. There are also things you can do with A* to try and reduce collisions, such as change the weight of nodes when you know other entities will be occupying them. You can use steering behaviours or crowd/flocking algorithms when navigating along the A* path to give entities some degree of freedom to avoid each other while following paths. You could share paths among friendly entities so that they can form an orderly line when passing along the same path instead of competing for chokepoints.

There are also more advanced algorithms that attempt to acknowledge the fact that the environment can change, and that a path that was previously found may not always continue to be the best one when other entities become involved. These algorithms are generally based on A*, so you can start with a good A* implementation and adapt it to one of these algorithms later if you need.

Share this post

Link to post
Share on other sites
ddengster    882

With this problem I recommend using steering(obstacle avoidance) for entities every frame, it's pretty good for short-range maneuvering. Couple it with A* for longer range navigation which you can run sparingly.

Share this post

Link to post
Share on other sites
ApochPiQ    23061

Have a look at steering as well as avoidance algorithms such as ORCA, Reciprocal Velocity Obstacles, etc. A* is for strategy, avoidance is for tactics. A* will tell you what route to take, steering and other avoidance mechanisms will give you the details of how to follow that route, including moment-to-moment accelerations for obstacle avoidance.

Share this post

Link to post
Share on other sites
IADaveMark    3740

That said, if you are working on a low rez game such as a turn-based game where pieces are on a grid board, there are ways you can incorporate the locations of objects into your A*. For example, there are articles that talk about not only blocking the location of pieces currently, but blocking locations where they will be on future turns. The problem is you have to keep phantom copies of the "board" for those times in the future and iterate through them as you do your pathfinding search. e.g. for step 1, I can use the current locations, for step 2, I use where people are going to be 1 step into the future, step 3, 2 steps into the future, etc. Get's kind of intractable after a bit.

Share this post

Link to post
Share on other sites
Crayz92    173

My grid agents will flag the node they are standing on/moving to as Occupied and I've implemented an option into my A* that basically says Occupied nodes are unwalkable and skips them during the search much like it would a node marked as unwalkable/wall/etc.  It makes for somewhat boxy movement much like Warcraft 3 or the original Starcraft I suppose.

Since paths are calculated on a single frame I can't determine what nodes might have changed and become occupied after an agent has already calculated a path, so if a node along the agent's path becomes occupied after the fact he will walk right through it.  To counter this, in my update loop (if the agent is currently moving) I determine what node the agent will be standing in next, and if it's occupied the agent will stop, stall for a brief moment, then calculate another path.

I recorded a quick video to show what this looks like:


Share this post

Link to post
Share on other sites

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

  • Similar Content

    • By Crayz92
      Here are the two main files:
      Path: https://pastebin.com/ZkrbJ78t
      AStar: https://pastebin.com/EVGazFtU
      A few things I've done to optimize the search:
      1. Rather than a dictionary to keep track of scores and parents, I use a 2d array of objects that are mapped to the grid i.e. [x,y] represents grid point (x,y).  Objects have F,G,H and Parent fields, these fields are reset to default values during each search.
      2. Cheap weighted heuristic
      3. Orthogonal neighbors (searching 4 neighbors rather than 8)
      Paths don't have to be beautiful because the point reduction smooths them out quite nice. 
      In Path.cs you can see the two functions to reduce points, Incremental and Stretch.  Stretch is much faster because it has the potential to reduce points all the way to the end right off the bat or early on thus reducing calls to the LineOfSight function, but it isn't so reliable around small areas/corners.  The incremental function is reliable but it calls to the LineOfSight function for each and every point along the path, this causes the path reduction to be just about as slow as calculating the path itself. 
      Line of Sight is determined by getting all points between 2 points and checking that they are all flagged as Walkable.
      My grid is dynamic and roughly 250x250.  I tried out Theta* and JPS, both were slower than my current A*.  I'm trying to avoid using a navmesh or worker thread, I suppose mostly just looking for ideas to tighten up my code
    • By lucky6969b
      When my program was generating navigation meshes for my geometry, and the extent is 5000x5000 (m), with a cell size of 5.0 meters, it has to generate 250,000 cells, which makes my computer halt, the target object is a truck, which has a radius of about 20 meters, should I give the cell size a value of 20, because I don't really want to use this navigation mesh on one type of vehicle only. I want to use it for vehicles like cars, which has only about 5 meters in radius... the generation speed is a problem while the memory consumption is another.
      Any ideas how to improve this?
    • By ApochPiQ
      I've just posted a pre-release edition of Curvature, my utility-theory AI design tool. Curvature provides a complete end-to-end solution for designing utility-based AI agents; you can specify the knowledge representation for the world, filter the knowledge into "considerations" which affect how an agent will make decisions and choose behaviors, and then plop a few agents into a dummy world and watch them run around and interact with things.
      Preview 1 (Core) contains the base functionality of the tool but leaves a lot of areas unpolished. My goal with this preview is to get feedback on how well the tool works as a general concept, and start refining the actual UI into something more attractive and fluid. The preview kit contains a data file with a very rudimentary "scenario" set up for you, so you can see how things work without cutting through a bunch of clutter.
      Give it a test drive, let me know here or via the Issue Tracker on GitHub what you like and don't like, and have fun!
    • By Marc Klein
      I'm using BMfont to create a Bitmap font for my text Rendering. I noticed some strange behaviour when I use the option "force Offsets to Zero".
      If I use this option my rendering resultions looks ok, but without it, there is some missing space between some characters.
      I attached the BMFont configuration files and font that I used.
      In the rendering result with variable Offset you can see that there is missing space right next to the "r" letter.
      To get the source and destination of my render rectangles I basically to following:
      void getBakedQuad(const fontchar_t* f, int* x_cursor, int * y_cursor, SDL_Rect* src, SDL_Rect* dest) {
      dest->x = *x_cursor + f->xoffset;
      dest->y = *y_cursor + f->yoffset;
      dest->w = f->width;
      dest->h = f->height;
      src->x = f->x;
      src->y = f->y;
      src->w = f->width;
      src->h = f->height;
      *x_cursor += f->xadvance;
      Has somebody noticed a similar behaviour?
      SIL Open Font License.txt


    • By Jesse "Chime" Collins
      3D Rigger Mixamo Is Making Some Changes
      Originally founded in 2008, Mixamo has been a go-to source for 3D animation and rigging for nearly a decade. On August 28th, 2013, Mixamo launched a platform called Face Plus. It was designed to allow developers or animators turn facial expressions recorded with even a webcam into top-notch 3D animation. This is not unlike what Holotech Studios’ “FaceRig” does for streamers and video creators as well.
      Back this past May 2017, Adobe (publishers of the Mixamo platform since 2015) announced the end of an era. Mixamo’s Face Plus will be removed on August 22nd, 2017, as well as several other free features.
      According to the Adobe post on the Mixamo website, they lay out what is changing and what is staying the same.

      Set out as bullet points in the post, they seem to be cleaning house on the “free” features. But, they are keeping a small handful of their main key points, such as:
      Select and use characters from Mixamo’s Character Collection
      Upload 3D characters to get them ready to animate using the Auto-Rigger
      Apply animations to characters
      Download as an .fbx or .dae
      Noticeably, the list that’s getting 86’ed includes major tools and the ability to save assets from their site:
      The ability to save and retrieve assets in “My Assets”.
      The Face Plus facial animation plugin
      The Decimator polygon reduction tool
      The ability to download Control-rig scripts
      Download types for .bvh and .biped that streamline integration with 3rd party applications
      Mixamo forums will close and all help articles will be moved to Adobe’s HelpX
      Don't Worry! There's still time!

      They’re allowing people to still download the tools and plug-ins until August 22nd, as well as utilizing their easy-to-download features of saving Assets directly. Those that use Mixamo, utilize Face Plus, or even just do animation are highly encouraged to take advantage and download the tools for the next week.
      To download, sign into your (free) Adobe account at the Mixamo website and start downloading. Developers have only one week left to grab as much as they can. For a complete FAQ and how-to for the Mixamo massacre, check out the Adobe post from their Customer Care Team.
      UPDATE (8/15/17): Adobe would like to stress that Mixamo, itself, is not going anywhere, just the Face Plus features, the tools mentioned above, and a couple other features to make the platform more "streamlined and a little modernized". Once the dust is cleared next week from the changes, I'll reach out to Adobe from a more guided tour of the new set-up. Additionally, I have changed the title of this article to reflect the clarification. Apologies for the inconvenience to those that have already read the article. 

  • Popular Now