1
\$\begingroup\$

I am trying to implement a path-finding routine involving the following:

  • Multiple agents
  • Multiple Goals
  • Obstacles
  • Both agents move in sync, i.e. they both move in the same direction unless one is stopped by an Obstacle. See explanation below in the edit section.

See the following image for illustration: Path finding Problem

A1 and A2 represent the starting position of two agents. The dark squares marked with "X" represent obstacles. "G1" and "G2" represent the final goal.

I played around with A* path finding algorithm, and it works great with 1 actor with one goal. However, I couldn't get it to work with more than one actor and goal.

Any suggestions and pointers about how to go about it would be very helpful.

Edit: Synchronized movement explained

If for instance, A1 is stopped by the obstacle but A2 can move, it is a valid option. A1 would stay in place but A2 will move.

Example:

  1. Move Right: A1 moves to (2,1) and A2 moves to (2,7)
  2. Move Right: A1 stays in place but A2 moves to (3,7)
  3. Move Up: A1 moves to (2,0) and A2 moves to (3,6)
  4. Move Up: A1 stays at (2,0) and A2 moves to (3,5)
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Can you be more specific on "move in sync"? How would a correct path look for provided example? In case one is stopped by an obstacle, what happen to the other? \$\endgroup\$ – wondra Jan 28 '17 at 11:59
  • \$\begingroup\$ Sorry for the lack of clarity. If for instance, A1 is stopped by the obstacle but A2 can move, it is a valid option. A1 would stay in place but A2 will move. I will add the info to the question. \$\endgroup\$ – Puneet Jan 28 '17 at 12:16
  • \$\begingroup\$ What's the big picture here? Are you creating this AI to validate that a level can be finished and/or count the minimum amount of required moves? \$\endgroup\$ – Vaillancourt♦ Jan 28 '17 at 12:48
  • \$\begingroup\$ Its as you said. I am creating this for three fold use: 1) In-game hint, 2) Validate that level can be completed, and 3) Minimum moves needed to complete the game to provide feedback at the end of the level. \$\endgroup\$ – Puneet Jan 28 '17 at 12:54
2
\$\begingroup\$

This problem can be easily solved by A* without any modifications. The implementation, however, is not trivial. You want your A* run not in the actual world, but rather in C-space of your world (or even state space given you have extra constraint).
Most interesting for you is the paragraph mentioning that while for 1 particle in 3D the C-space has 3 dimentions, for n particles the space has 3 n dimensions.
Applied to you problem, you want to construct a 4D graph where obstacles in each 2D slice(the first two dimensions) are generated by overlaying current obstacles translated by the actor displacement vector(the second two dimensions), with connection between 2D slices made only near obstacles, e.g. as you identified in your example, at [(2,0),(0,6)] you can move to the [(2,0),(0,5)] slice of world.
For example (=one slice), finding path for two points in scene on left is equivalent to finding path for one point in scene on the right (light gray obstacle is due to the world boundary). enter image description here
As you can see, if you build you A* graph as described above, A* will no longer have any problems with second actor and as expected, will find the correct path given one exists.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Thank you for trying to explain it in a relatively simple manner along with an illustration. I am not a math/physics major so anything beyond 2D/3D takes me a bit of time to grasp/visualize. Based on your answer, it is more a problem of redefining the graph. However, if I translate the obstacles by actor displacement vector, it would take care of both A1 and A2 reaching either G1 or G2 together. Instead, I need A1 and A2 to reach G1 and G2 respectively at the same time.(The bottom Goal was supposed to be G2. Apologies for the mistake.) \$\endgroup\$ – Puneet Jan 28 '17 at 16:06
  • 1
    \$\begingroup\$ @Puneet It is important to understand you are looking for specific position and displacement vector(=slice) giving you 4D target for A*. In your example you want to navigate A1 to (8,1) coordinate and (0,4) slice (producing 4D coordine of 8,1,0,4). In other words, if A1 is at (8,1), the G1 node and the displacement of A2 is (0,4), then A2 must be at (8,5), the G2 node. \$\endgroup\$ – wondra Jan 28 '17 at 16:22
  • 1
    \$\begingroup\$ @Puneet also note, you dont have to create the graph as preprocessing step when pathfinding on grid, you can just "try every move" and check if that move was valid (=any of objects is colliding for first 2 dimension, and if the objects has obstacle on correct side when moving in other two dimensions, displacement), if the edge exists. This could be implemented by bunch of else-ifs, still not easy task however. \$\endgroup\$ – wondra Jan 28 '17 at 16:44
  • \$\begingroup\$ Thanks for the explanation. Let me wrap my head around it. This is much more complex than implementing a simple A* in 2d space. \$\endgroup\$ – Puneet Jan 28 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.