Locating point on a closed path to maximize sum of distances to a sample of weighted points (Game AI)

Question

I'm doing AI for a simple puzzled game and need to solve the following problem efficiently (less than 1 sec for the range specified since I need to do many iterations in a game).

A sample of N (1 to 100,000) monsters with strength from 1 to 10,000 are distributed on the sides of a square (0 to 200,000,000) at 1 unit interval starting from the upper left corner. Move hero to a point X on the square to maximize sum of the weighted distances to the monsters. A weighted distance to each monster is calculated by MonsterStrength*ShortestDistanceToX (by going clockwise or anticlockwise). X must also be on the 1 unit interval mark and the monsters and hero move on the sides of the square only

I have tried several approaches but none are fast or accurate enough.

The possibly complementary of this problem (minimizing the sum of distances to set of points at furthest distance from each corresponding monsters in the original set) seems to related to finding the geometric median, facility location problem, Weber problem etc.

Linear programming is also possible but might be too slow and overkilled.

Does anyone have any idea for a good approach?

---

Here is an illustration on a square of sides of length 3:

1-------2(M/3)-------3------4(M/1)
|                              |
12(M/2)                        5
|                              |
11(M/1)                        6
|                              |
10--------9---------8(X)-------7

if you put a monster of strength 3 at 2, one with strenth 1 at 4, one with strength 2 at 12 and one with strength 1 at 11 and the hero(X) at 8. the sum of weighted distane is: 3*6 + 1*4 + 1*3 + 2*4 = 33, which is also the maximum in this case

Answer 1

I will try to point out a strategy that you can follow to achieve the required 1 second response time. Of course, it must be implemented to ensure it fits this requirement.

The solution relies on the following fact:

Basically, given the sum of weighted distance WP for a position P, each monster will contribute to the sum of weighted distances of a P neighbor by adding or subtracting 1 time it strength to WP. The strength is added if the neighbor is nearer to the monster than P or subtracted if it is farther.

With this fact in mind, the solution resides in compute sum of weighted distance for some initial position on a initial step, and compute the sum of weighted distance for the other positions based on the value previously computed for its neighbor.

Besides compute the value for the initial position, we must define on the initial step:

• a direction (eg. clockwise) on which we will traverse the positions to compute the sum of weighted distances
• the sum of the strenght (SADD) of the monsters which we will get farther (to add) when traversing on the defined direction;
• the sum of the strenght (SSUB) of the monsters which we will get nearer (to subtract) when traversing on the defined direction;

Then, starting on the neighbor of the initial position, we traverse all position on the defined direction, and for each one, we update SADD and SSUB (when we traverse the circular path, some monster that were getting nearer starts to get farther and vice versa) and add (SADD - SSUB) to the value computed for the previous neighbor.

Thus, we can compute the sum of weighted distances for all positions without having to iterate over all monsters for each position.

I implemented an initial version of the solution in Java.

The following class represents a monster:

class Monster {
    private long strenght;
    private int position;
    // omitting getters and setters...        
}

And the following class represents the square side positions:

class SquareSidePositions {
    private List<Monster>[] positionWithMosters;
    private List<Monster> monstersOnSquareSides = new ArrayList<Monster>();

    @SuppressWarnings("unchecked")
    public SquareSidePositions(int numberOfPositions) {
        positionWithMosters = new LinkedList[numberOfPositions];
    }

    public void add(int position, Monster monster) {
        if (positionWithMosters[position] == null) {
            positionWithMosters[position] = new LinkedList<Monster>();
        }

        positionWithMosters[position].add(monster);
        monster.setPosition(position);
        monstersOnSquareSides.add(monster);
    }

    public int size() {
        return positionWithMosters.length;
    }

    public boolean hasMonsters(int position) {
        return positionWithMosters[position] != null;
    }

    public long getSumOfStrenghtsOfMonstersOnThePosition(int i) {
        long sum = 0;

        for (Monster monster : positionWithMosters[i]) {
            sum += monster.getStrenght();
        }

        return sum;
    }

    public List<Monster> getMonstersOnSquareSides() {
        return monstersOnSquareSides;
    }
}

And finally, the optimization is performed in the following method:

public static int findBest(SquareSidePositions positions) {
    long tini = System.currentTimeMillis();
    long sumOfGettingNearer = 0;
    long sumOfGettingFarther = 0;
    int currentBestPosition;
    long bestSumOfWeight = 0;
    long currentSumOfWeight;
    final int numberOfPositions = positions.size();
    int halfNumberOfPositions = numberOfPositions/2;
    long strenghtsOnPreviousPosition = 0;
    long strenghtsOnCurrentPosition = 0;
    long strenghtsOnPositionStartingGetNearer = 0;
    int positionStartGetNearer;

    // initial step. Monsters from initial position (0) are skipped because they are at distance 0 
    for (Monster monster : positions.getMonstersOnSquareSides()) {
        // getting nearer
        if (monster.getPosition() < halfNumberOfPositions) {
            bestSumOfWeight += monster.getStrenght()*monster.getPosition();
            sumOfGettingNearer += monster.getStrenght();
        } else {
        // getting farther
            bestSumOfWeight += monster.getStrenght()*(numberOfPositions - monster.getPosition());
            sumOfGettingFarther += monster.getStrenght();
        }
    }

    currentBestPosition = 0;
    currentSumOfWeight = bestSumOfWeight;

    // computing sum of weighted distances for other positions
    for (int i = 1; i < numberOfPositions; ++i) {
        strenghtsOnPreviousPosition = 0;
        strenghtsOnPositionStartingGetNearer = 0;
        strenghtsOnCurrentPosition = 0;
        positionStartGetNearer = (halfNumberOfPositions + i - 1);

        if (positionStartGetNearer >= numberOfPositions) {
            positionStartGetNearer -= numberOfPositions;
        }

        // monsters on previous position start to affect current and next positions, starting to get farther
        if (positions.hasMonsters(i-1)) {
            strenghtsOnPreviousPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i-1);  
            sumOfGettingFarther += strenghtsOnPreviousPosition;
        }

        // monsters on current position will not affect current position and stop to get nearer
        if (positions.hasMonsters(i)) {
            strenghtsOnCurrentPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i);
            currentSumOfWeight -= strenghtsOnCurrentPosition;
            sumOfGettingNearer -= strenghtsOnCurrentPosition;
        }

        // monsters on position next to a half circuit start to get nearer
        if (positions.hasMonsters(positionStartGetNearer)) {
            strenghtsOnPositionStartingGetNearer = positions.getSumOfStrenghtsOfMonstersOnThePosition(positionStartGetNearer);
            sumOfGettingNearer += strenghtsOnPositionStartingGetNearer;
            sumOfGettingFarther -= strenghtsOnPositionStartingGetNearer;
        }

        currentSumOfWeight += sumOfGettingFarther - sumOfGettingNearer;

        // if current is better than previous best solution
        if (currentSumOfWeight > bestSumOfWeight) {
            bestSumOfWeight = currentSumOfWeight;
            currentBestPosition = i;
        }
    }

    final long executionTime = System.currentTimeMillis() - tini;

    System.out.println("Execution time: " + executionTime + " ms");
    System.out.printf("best position: %d with sum of weighted distances: %d\n", currentBestPosition, bestSumOfWeight);

    return currentBestPosition;
}

To setup the input you used as example, you can use:

SquareSidePositions positions = new SquareSidePositions(12);

positions.add(1, new Monster(3));
positions.add(3, new Monster(1));
positions.add(10, new Monster(1));
positions.add(11, new Monster(2));

On a preliminary test, this method took 771 ms to execute, for 100,000 monsters and 200,000,000 possible positions, on a Intel Core i5-2400 running Windows 7.

I employed the following code to generate this input:

// I used numberOfMosters == 100000 and numberOfPositions == 200000000
public  static SquareSidePositions initializeMonstersOnPositions(int numberOfMonsters, int numberOfPositions) {
    Random rand = new Random();
    SquareSidePositions positions = new SquareSidePositions(numberOfPositions);

    for (int i = 0; i < numberOfMonsters; ++i) {
        Monster monster = new Monster(rand.nextInt(10000)+1);

        positions.add(rand.nextInt(numberOfPositions), monster);
    }

    return positions;
}

I hope it helps you!

Answer 2

For anyone who is interested, here is my C/C++ code for unit testing of the algorithm which uses Crferreira's idea together with interval traversal. Input format: N L monster1_pos monster1_strength monster2_pos monster2_strength ....
Correctness is tested against a bruteforce algorithm on smaller cases
Large cases are generated randomly
Program run from 44 ms to 84 ms on Intel core i3 running Ubuntu Linux for largest test cases

#include <stdio.h>
#include <stdlib.h>

#define MAXH 100000

int num_monster, side;
int half, total;
int monster[MAXH][2]; //col0: monster pos, col1: strength
int opp[MAXH][3]; //col0: opp pos, col1: num people in opp monster, col2: index of opp monster
int boundaryMonster = -1;

int min (int a, int b) {
    return a<b?a:b;
}

int getOpp(int pos) {
    return (pos==half)?total:(pos+half)%total;
}

int getDist(int from, int to) {
    return min(abs(to-from), total-abs(to-from));
}

int totalsum(int pos) {
    int result = 0;
    for (int i = 0; i < num_monster; i++) {
        result += getDist(pos, monster[i][0])*monster[i][1];
    }
    return result;
}

//find sorted sequence of pos where monster exists at opposite pos
void oppSeq() {
    int count = 0;
    for (int i = boundaryMonster; i < num_monster; i++) {
        opp[count][0] = getOpp(monster[i][0]);
        opp[count][1] = monster[i][1];
        opp[count][2] = i;
        count++;
    }
    for (int i = 0; i < boundaryMonster; i++) {
        opp[count][0] = getOpp(monster[i][0]);
        opp[count][1] = monster[i][1];
        opp[count][2] = i;
        count++;
    }
}

int main() {
    FILE *input, *output;

    input = fopen("monster.in", "r");
    output = fopen("monster.out", "w");

    fscanf(input, "%d %d", &num_monster, &side);
    for (int i = 0; i < num_monster; i++) {
        fscanf(input, "%d %d", &monster[i][0], &monster[i][1]);
        if (boundaryMonster == -1 && monster[i][0] >= (1+2*side))
            boundaryMonster = i;
    }

    fclose(input);

    if (num_monster == 0) { 
        fprintf(output, "%d", 0); 
        fclose(output);
        return 0; 
    }

    half = 2*side;
    total = 4*side;

    oppSeq();

    int cur_sum = totalsum(1);
    int cur_monster = 0, cur_opp = 0;
    int prev_pos = 1;

    int delta = 0;
    for (int i = 0; i < num_monster; i++) {
        int mid = 1+half;
        if (monster[i][0] > 1 && monster[i][0] <= mid) 
            delta -= monster[i][1];
        else delta += monster[i][1];
    }

    if (monster[0][0] == 1) cur_monster = 1;
    if (opp[0][0] == 1) cur_opp = 1;

    int best = cur_sum;
    while (cur_monster < num_monster || cur_opp < num_monster) {
        if (cur_monster < num_monster && cur_opp < num_monster) {
            //going clockwise with both `monster` and `opp` *similar to merge sort merge phase
            if (monster[cur_monster][0] < opp[cur_opp][0]) {
                //update sum going from prev to cur_monster
                cur_sum += delta*(monster[cur_monster][0]-prev_pos);
                //start moving away from cur_monster->update delta
                delta += 2*monster[cur_monster][1];
                prev_pos = monster[cur_monster][0];
                cur_monster++;
            } else if (opp[cur_opp][0] < monster[cur_monster][0]) {
                cur_sum += delta*(opp[cur_opp][0]-prev_pos);
                //starting moving towards opposite monster
                delta -= 2*monster[ opp[cur_opp][2] ][1];
                prev_pos = opp[cur_opp][0];
                cur_opp++; 
            } else if (opp[cur_opp][0] == monster[cur_monster][0]) {
                cur_sum += delta*(monster[cur_monster][0]-prev_pos);
                //starting towards opp monster and away from current monster;
                delta += 2*(monster[cur_monster][1] - monster[ opp[cur_opp][2] ][1]);
                prev_pos = monster[cur_monster][0];
                cur_opp++; cur_monster++;
            }
        } else if (cur_monster < num_monster) {
            cur_sum += delta*(monster[cur_monster][0]-prev_pos);
            delta += 2*monster[cur_monster][1];
            prev_pos = monster[cur_monster][0];
            cur_monster++;
        } else {
            cur_sum += delta*(opp[cur_opp][0]-prev_pos);
            delta -= 2*monster[ opp[cur_opp][2] ][1];
            prev_pos = opp[cur_opp][0];
            cur_opp++; 
        }
        if (cur_sum > best) best = cur_sum;
    }

    fprintf(output, "%d", best);
    fclose(output);

    return 0;
}