1
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ (A link to) an image could really help you explain the problem. \$\endgroup\$
    – House
    Aug 7, 2013 at 13:30
  • \$\begingroup\$ I have added in an illustration, hope that helps clarify \$\endgroup\$
    – neiht
    Aug 7, 2013 at 13:47
  • \$\begingroup\$ Just to clarify after your example, is the hero also placed on the edges or can it be inside the square? If the hero is also on the edges, does the shape matter at all or could it be just any ring? \$\endgroup\$
    – msell
    Aug 8, 2013 at 5:39
  • \$\begingroup\$ Hi msell, the hero is only placed on the edge and the shape could be any ring. Similar problems in 2D plane are well-known and would significantly increase complexity of an accurate solution. I actually has 2D plane for higher levels but simply employ a approximate greedy function to simulate "repulsion" behavior \$\endgroup\$
    – neiht
    Aug 8, 2013 at 10:09

1 Answer 1

1
\$\begingroup\$

I have found a pretty good solution for this. For anyone who is interested, here is my C/C++ code for unit testing of the algorithm. 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;
}

Here is a brief explanation for the code above:

  • We have a sequence of monsters' positions: e.g. 2 4 11 12

  • Function oppSeg() generates a sorted sequence of positions opposite to that of the monsters in O(N) time by going through the monsters clockwise starting with monsters in the second half of the shape (start with boundaryMonster found in input loop)
    e.g. we obtained the sequence: 5 6 8 10

Here are the main algorithm after the oppSeq() function in main():

  • Put the hero at intial position 1 and calculate the initial sum of weighted distance
  • Calculate delta which is the change in the sum as the hero move 1 step clockwise
  • It can be seen that delta only changes when the current position of the hero or his opposite position contains monsters.
  • Going through the relevant positions (with monsters or monsters at opposite position) by using a procedure similar to the merging phase of merge sort on the monsters positions sequence and the opposite positions sequence
  • update delta, cur_sum, best sum so far accordingly
  • delta = 2*monster_strength__at_current_pos - 2*monster_strength_opposite_at_pos
    *start moving away from monsters at current position and towards monsters at opposite position in the next step
  • cur_sum = (current_position - previous_position)*delta

The main part also takes O(N) time and the program uses O(N) space overall

\$\endgroup\$
2
  • \$\begingroup\$ Explaining your chosen algorithm in words would be best. \$\endgroup\$
    – House
    Aug 8, 2013 at 13:15
  • \$\begingroup\$ Hi Byte56, thanks for asking. I have added in a brief explanation. Hope that helps \$\endgroup\$
    – neiht
    Aug 8, 2013 at 15:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .