1
\$\begingroup\$

I'm using Unity with Arongranberg's A* pathfinding project to move my characters. However, it appears that my characters are contending for a position on the terrain when they are told to move together to a same position.

For example, I have 5 characters being told to move to PositionA. They will move together based on their waypoints to PositionA. One of the characters, call it CharacterA, will reach PositionA before the rest. Now, the other 4 characters who arrived later will continue to keep walking and "sliding" around CharacterA. They seem to stop only when CharacterA moves away from PositionA so that they could reach their destination to break out of the loop. Even so, only one character can be in PositionA while the rest will continue to contend for the place.

So, how can I get the characters and objects to know that they have reached their destination and should stop beside the other characters instead of contending for the same place?

A naive method could be I get the characters to detect if they are blocked by something straight ahead of them. If they are, break out of the loop and stop the walking state. But at times when the character hasn't reached his destination yet and is blocked by an object, say another character, breaking out of the waypoint loop will stop him at the wrong destination. I can't recalculate for a new path from his current position either since the blocking object is another character, which the initial pathfinding grid scanning did not take into account. One way is I re-scan the whole terrain for a new grid of nodes with the characters in the scene taken into account. But this wouldn't be efficient and will lag a whole ton.

Improve this question
\$\endgroup\$
1
\$\begingroup\$

We had a small project with a similar problem.

How we got around this was each character in a group would do their path-finding and save it in a path list. Each node would have a "time" variable for when that character would occupy that node and when creating the next path, the character would make checks against other path lists and consider nodes blocked if the time values would be the same.

This was a bit costly as far as overhead so to counteract this we did not do full path finding just about 5-10 nodes at a time as well as not rebuilding the list until they were almost out of nodes in the path list.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/… \$\endgroup\$
    – Rakka Rage
    Mar 29 '13 at 1:28
  • \$\begingroup\$ Thanks, I think I could only get half of the idea. Could you elaborate a little more on your technique? \$\endgroup\$
    – xenon
    Mar 29 '13 at 13:53
  • \$\begingroup\$ Each character in a group of NPC's would have a list of nodes (tiles/spaces/etc) as (x,y) coordinates and, as the link rakkarage supplied, a time variable. When doing path-finding for new nodes, you'd want to search the lists of other NPC's in the group who you wish wouldn't want to collide, and treat those nodes as blocked if the time value in the other character's pathing list is equal to the pathing node time you are currently checking. \$\endgroup\$
    – UnderscoreZero
    Mar 29 '13 at 15:18
  • \$\begingroup\$ Sorry still waking up. Each step in A* you'll want to check for the current node in the other NPC's list, and then check to see if the time is the same. If so then that node is blocked. \$\endgroup\$
    – UnderscoreZero
    Mar 29 '13 at 15:29
0
\$\begingroup\$

You could try the following: Everytime a character moves, so while he is still walking to his destination, you check, if the destination position is walkable or if it's blocked by something. If it's walkable, everything is fine.

But if it's blocked you calculate the distance between the character and its destination. If it is lower than some certain value, which you can define as you wish, the character knows, that he actually reached his destination, but the position is blocked so he has to stand near the destination. If you define this distance variable well then your characters will just arrange around their shared destination.

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ This is a good solution when the characters are already very near their destination. In the case when the characters are blocked by non-static objects, like another character, which are not taken into account when scanning the terrain for the grid nodes for pathfinding, he may stop and stand beside a wrong thing. \$\endgroup\$
    – xenon
    Mar 28 '13 at 13:28
  • \$\begingroup\$ Actually this should not happen when you do it as I suggested. Because I wrote: "you check, if the destination position is walkable or if it's blocked by something". Maybe it is not totally clear, what I mean: You check if the destination position (and only the position itself) is blocked by something. And if this is the case, than you check if the character is even near enough to stand still. Or do you mean something else? Because I cannot see how another character blocking the path far away from the destination should be problematic. \$\endgroup\$
    – M0rgenstern
    Mar 28 '13 at 13:40
  • \$\begingroup\$ Suppose this scenario: CharA-----CharB----x. CharacterA's destination is x. He walks along the dotted line. He is blocked by CharacterB. Since all non-static characters are not considered during the pathfinding's grid scanning at compile time, the point where CharacterB is at is still considered "walkable". \$\endgroup\$
    – xenon
    Mar 28 '13 at 14:22
  • \$\begingroup\$ Now I see your problem. But why don't you mark the position where a char is as not walkable? Either it is walkable, then it has really to be walkable, or it is not walkable, but then the pathfinding algorithm hat to know, that each position of a character is not walkable. \$\endgroup\$
    – M0rgenstern
    Mar 28 '13 at 14:32
  • \$\begingroup\$ Exactly, the pathfinding algorithm has to know the positions of the characters. One way for it to know is to rescan the terrain for a new grid. But this is costly to do for every characters' movements. \$\endgroup\$
    – xenon
    Mar 29 '13 at 13:55

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.