4
\$\begingroup\$

I just started learning about pathfinding algorithms.
Assume we have this scenario:
Scenario
Blue and Green can move only on those tiles. They can also talk to each other.
Blue wants to go through the tunnel and green wants to go too, however both need to pass each other somehow. In case of a "basic" A* pathfinding algorithm they will both get stuck in the tunnel.

To prevent this issue i had some Ideas:
- Blue can tell green that he should move back first (give blue priority) when they both step next to each other (problems arise when there are more than 2)
- A better algorithm, that calculates this like an automatic traffic regulator (one will wait till the other frees the path) --> seems complicated

Now I am wondering if there are more efficient methods, how its done in general, if you have better ideas, if you can point me to some algorithms or some papers that adress this issue.

\$\endgroup\$
1
\$\begingroup\$

This is definitely a classic problem that can be seen if you play Red Alert or something.

What you might do is count squares that are in these congested areas as being impassible if a unit is moving across them in the near future (within x squares); and have your algorithm tell the other units to stop on squares just outside of "temporarily impassible" areas.

This would also naturally assist with the "piling up" of confused units all going the same direction, as who ever said they were going first would just go, block the path, and then another would follow in its wake.

To make sure you guard against an edge case, I think you should detect when a square "opens up" by seeing how many passable adjacent squares there are, allowing this solution to be effective no matter how long the "bridge" is.

NOTE: I would only block squares "in front" of a unit moving across the "bridge", which allows the next unit in line behind it to cross the bridge. This means you "unblock" bridge squares as it crosses them and the next unit simply queue's up the new "block" on it.

This solution is O(n) (might be considered O(1)) because each unit only uses as much calculation as it was going to to determine that the bridge is "blocked", where as units talking to eachother would be O(n^2) or worse. This is to say that it is highly efficient among the various solutions to may get.

For units that are "blocked" or "waiting", give them a new "moving" state that says as much, where they move to the nearest allowed square until they get priority; "remembering" but not acting on the rest of their move.

Lastly, as to who gets priority you'll probably want to keep it simply with "first come first serve" of who gets to cross first; after all this is a convenience to the player who didn't micro-manage his units (because they could basically do this by stationing the first group on one side and prioritizing the one that they care about.)


As a second solution, you could consider that units are allowed to temporarily occupy the same spot, giving you (essentially) two lanes. You see this a lot with infantry in old RTS, where they can pile up in a single spot for a moment but they eventually sort themselves into their positions.

\$\endgroup\$
  • \$\begingroup\$ I like the idea of marking grid elements as paths that are already taken. I could also add them to the A* algorithm and make some prioritzed path based on that. I will have a deeper look at that and its possible issues. Thanks so far \$\endgroup\$ – RIJIK Apr 11 '18 at 10:35
  • \$\begingroup\$ This seems a nice idea, there's a point though: given two paths on the same plane, if they cross each other it doesn't mean the two instances will eventually bump into each other. This happens if the two objects move at different speeds: one may arrive way earlier than the other, and at least there'll be a global minimum distance between them over time. \$\endgroup\$ – liggiorgio Apr 11 '18 at 13:15
  • \$\begingroup\$ @liggiorgio I think this is best handled by saying "What is the next grid pos I'll occupy" and if it's "blocked" then you set yourself to "wait" mode. If it's not blocked, you check if it's a "bridge" by looking to see if it has X-amount of open nearby squares. You keep checking squares until you find one that satisfies this and then these all become "blocked." This means the unit who arrives at the bridge first (not who was told to move across it first) will get priority, as it'll "block" the bridge. if they arrive "at the same time" it'll be the unit who is iterated over first \$\endgroup\$ – blurry Apr 11 '18 at 20:01
  • \$\begingroup\$ @RIJIK A side note: Units that block a path should remember to clear that path if they are destroyed. You may want to track a unit's "blocked" squares so it is easy to clear them. You could also (instead) have the position track who blocked it, then see if the reference to the unit still exists when someone finds the blocked square. It ceasing to exist could indicate it's been destroyed and that the "block" is invalid. These types of bugs will definitely come up if not considered early. \$\endgroup\$ – blurry Apr 11 '18 at 20:04

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.