• Advertisement

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

Recommended Posts

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

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

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

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

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


  • Advertisement
  • Advertisement
  • Advertisement
  • Similar Content

    • By lucky6969b

      Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
      thanks
      Jack
    • By GreenGodDiary

      Solved: didn't think clearly and realized I can't just compare the cross-product with 0,0,0.  
      Fixed by doing this:
      float3 originVector = float3(0.0, 0.0, 0.0) - v1.xyz; if (dot(cross(e1, e2).xyz, originVector) > 0.0) { //... } I'm trying to write a geometry shader that does backface culling. (Dont ask me why)
      What I'm doing is checking the cross-product of two edges of the triangle (in NDC space) and checking if it's facing 0,0,0 .
      The problem is when I compile I get this error:
      this is i guess because if it isn't facing us, I dont append any verts to the stream. I always assumed maxvertexcount implied I can emit as few verts as I like, but I suppose not.
      How do I get around this?

      Shader below:
      struct GS_IN_OUT { float4 Pos : SV_POSITION; float4 PosW : POSITION; float4 NorW : NORMAL; float2 UV : TEXCOORD; }; [maxvertexcount(3)] void GS_main( triangle GS_IN_OUT input[3], inout TriangleStream< GS_IN_OUT > output ) { //Check for backface float4 v1, v2, v3; v1 = input[0].Pos; v2 = input[1].Pos; v3 = input[2].Pos; float4 e1, e2; e1 = v1 - v2; e2 = v1 - v3; if (dot(cross(e1, e2).xyz, float3(0.0, 0.0, 0.0)) > 0.0) { //face is facing us, let triangle through for (uint i = 0; i < 3; i++) { GS_IN_OUT element; element = input[i]; output.Append(element); } } }  
    • By Viir
      This screenshot shows a game with the new bot and map.
      Screenshot from the DRTS Devlog at 
       
       
    • By ferreiradaselva
      There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
      Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (`uastar.c` and `uastar.h`) library: https://github.com/ferreiradaselva/uastar
      No memory dynamic allocation. Straight to the point (the README.md explains how to use).
      It's nothing biggie, but certainly useful.
      Path finder at work:

      I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).
    • By lucky6969b
      I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
      Any ideas?
      Jack
  • Advertisement
  • Popular Now

  • Advertisement