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

i'm doing ai simple puzzled game , need solve following problem efficiently (less 1 sec range specified since need many iterations in game).

a sample of n (1 100,000) monsters strength 1 10,000 distributed on sides of square (0 200,000,000) @ 1 unit interval starting upper left corner. move hero point x on square maximize sum of weighted distances monsters. weighted distance each monster calculated monsterstrength*shortestdistancetox (by going clockwise or anticlockwise). x must on 1 unit interval mark , monsters , hero move on sides of square only

i have tried several approaches none fast or accurate enough.

the possibly complementary of problem (minimizing sum of distances set of points @ furthest distance each corresponding monsters in original set) seems related finding geometric median, facility location problem, weber problem etc.

linear programming possible might slow , overkilled.

does have idea approach?

---

here illustration on 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 put monster of strength 3 @ 2, 1 strenth 1 @ 4, 1 strength 2 @ 12 , 1 strength 1 @ 11 , hero(x) @ 8. sum of weighted distane is: 3*6 + 1*4 + 1*3 + 2*4 = 33, maximum in case

i try point out strategy can follow achieve required 1 second response time. of course, must implemented ensure fits requirement.

the solution relies on following fact:

basically, given sum of weighted distance wp position p, each monster contribute sum of weighted distances of p neighbor adding or subtracting 1 time strength wp. strength added if neighbor nearer monster p or subtracted if farther.

with fact in mind, solution resides in compute sum of weighted distance initial position on initial step, , compute sum of weighted distance other positions based on value computed neighbor.

besides compute value initial position, must define on initial step:

• a direction (eg. clockwise) on traverse positions compute sum of weighted distances
• the sum of strenght (sadd) of monsters farther (to add) when traversing on defined direction;
• the sum of strenght (ssub) of monsters nearer (to subtract) when traversing on defined direction;

then, starting on neighbor of initial position, traverse position on defined direction, , each one, update sadd , ssub (when traverse circular path, monster getting nearer starts farther , vice versa) , add (sadd - ssub) value computed previous neighbor.

thus, can compute sum of weighted distances positions without having iterate on monsters each position.

i implemented initial version of solution in java.

the following class represents monster:

class monster {     private long strenght;     private int position;     // omitting getters , setters...         } 

and following class represents 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;          (monster monster : positionwithmosters[i]) {             sum += monster.getstrenght();         }          return sum;     }      public list<monster> getmonstersonsquaresides() {         return monstersonsquaresides;     } } 

and finally, optimization performed in 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 initial position (0) skipped because @ distance 0      (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 other positions     (int = 1; < numberofpositions; ++i) {         strenghtsonpreviousposition = 0;         strenghtsonpositionstartinggetnearer = 0;         strenghtsoncurrentposition = 0;         positionstartgetnearer = (halfnumberofpositions + - 1);          if (positionstartgetnearer >= numberofpositions) {             positionstartgetnearer -= numberofpositions;         }          // monsters on previous position start affect current , next positions, starting farther         if (positions.hasmonsters(i-1)) {             strenghtsonpreviousposition = positions.getsumofstrenghtsofmonstersontheposition(i-1);               sumofgettingfarther += strenghtsonpreviousposition;         }          // monsters on current position not affect current position , stop nearer         if (positions.hasmonsters(i)) {             strenghtsoncurrentposition = positions.getsumofstrenghtsofmonstersontheposition(i);             currentsumofweight -= strenghtsoncurrentposition;             sumofgettingnearer -= strenghtsoncurrentposition;         }          // monsters on position next half circuit start nearer         if (positions.hasmonsters(positionstartgetnearer)) {             strenghtsonpositionstartinggetnearer = positions.getsumofstrenghtsofmonstersontheposition(positionstartgetnearer);             sumofgettingnearer += strenghtsonpositionstartinggetnearer;             sumofgettingfarther -= strenghtsonpositionstartinggetnearer;         }          currentsumofweight += sumofgettingfarther - sumofgettingnearer;          // if current better 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 sum of weighted distances: %d\n", currentbestposition, bestsumofweight);      return currentbestposition; } 

to setup input used example, 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 preliminary test, method took 771 ms execute, 100,000 monsters , 200,000,000 possible positions, on intel core i5-2400 running windows 7.

i employed following code generate input:

// used numberofmosters == 100000 , numberofpositions == 200000000 public  static squaresidepositions initializemonstersonpositions(int numberofmonsters, int numberofpositions) {     random rand = new random();     squaresidepositions positions = new squaresidepositions(numberofpositions);      (int = 0; < numberofmonsters; ++i) {         monster monster = new monster(rand.nextint(10000)+1);          positions.add(rand.nextint(numberofpositions), monster);     }      return positions; } 

i hope helps you!