Choreography Algorithm.

Def'n: Manhattan distance: the distance between two points, (x1,y1) and (x2,y2), on a grid. Basically abs(x2-x1)+abs(y2-y1).

Assign Goals

The first order of business is to assign each dancer to an end position. I found that an effective way to assign end positions is select a mapping that minimizes the average Manhattan distance that each dancer has to go.


Preferred Directions

Once goals are assigned, and assuming that no dancer is initially standing on his or her goal square, each dancer will have either one or two preferred directions. A preferred direction is any direction which if taken the dancer will advance towards his or her goal. That is, moving in a preferred direction makes the dancer's Manhattan distance to goal smaller. If the dancer takes a step that makes his or her Manhattan distance to goal bigger, then he or she is moving in an unpreferred direction.

Preferred ordering of directions:

  1. 1st preferred direction (if one exists).
  2. 2nd preferred direction (if one exists).
  3. Don't move. Stay put.
  4. 1st unpreferred direction.
  5. 2nd unpreferred direction.
  6. 3rd unpreferred direction (if one exists).
  7. 4th unpreferred direction (if one exists).


The Loop

Priorities are assigned to each dancer at the top of each iteration of the algorithm. A dancer's priority is his or her Manhattan distance to goal, plus the number of times he or she has moved in an unpreferred direction.

The next step is to ask each dancer to state their desired locations. That is, each dancer decides the square he or she would like to occupy next. Usually this is to move into an adjacent square in one of his or her preferred directions, but if the dancer has already reached his or her goal then the dancer would simply prefer to stay put.

Often multiple dancers will want to occupy the same square. These conflicts need to be resolved.

To do this we sort the dancers by their priorities. Higher priorities are better; dancers who are far away from their goals (or made lots of unproductive moves) get to move before dancers who are close to their goals. Once sorted, iterate through the sorted dancer list.

For each dancer who has not been resolved already:

If the dancer's desired square has not been claimed by another dancer already, that square becomes claimed by the current dancer. If the square has already been claimed choose the next direction from the dancer's preferred ordering (above). Once an unclaimed square is found, claim it, and then repeat this process for the dancer who is currently occupying the claimed square. If no square can be claimed, backtrack to the last dancer who has another direction which can be tried.

In psuedo-python syntax:

def resolve( dancer ):
        if dancer == nobody:
                return True
        resolved = False
        directions = dancer.get_preferred_directions()
        for d in directions:
                sq = dancer.get_square_in_direction( d )
                if sq.is_unclaimed():
                        sq.set_claimed_by( dancer )
                        occupant = sq.get_current_occupant()
                        if occupant == dancer:
                                resolved = True
                                break
                        resolved = resolve( occupant )
                        if not resolved:
                                sq.set_claimed_by( nobody )
                        else:
                                break
        dancer.set_resolved( resolved )
        return resolved

Once all the dancers have been resolved they all move into their claimed squares, and we go to the top of the loop. The algorithm terminates when all dancers reach their goal positions.

Of course, you will also need to make sure that two dancers don't collide with each other. That is an easy extension to this algorithm.