Help on improving code : Looting coins

According to a (I believe it is) better measurement of efficiency, your mean statement rate per frame should be : 250k / (60 * 8) = 520 statements per frame (520 SPF)

I found a bit of time to experiment around optimization. Not perfect, not bad : here is my new Algo that works at 310 SPF on my random seed when doing nothing else than looting coins. Of course you’ll see a lot of your work in mine. The tweaks I’ve brought are explained below.

Let’s keep in mind the HEL is 3125 SPF (see link above for explaination). For the record, the very first Algorithm originally posted in this post was (tried it just now) : 1750 SPF. I’m so far more than 5 times more efficient than my original code. It means 10 times lower than HEL. Maybe I should start working on actually fighting Pender now ! Thanks guys. A lot.

Algorithm : 3 parts

**Code : Main Loop**
``````// INIT: Constants and Configuration
var PENDER = this.findNearest(this.findEnemies());
var kFrame=-1;

// Used to unthrottle the computation of barycenter
var thenBary = -10, unthrottleBary = false;

// Stores the position of the next Coin
var toCoin = this;
var nCoins=0;
var xSelf=0,ySelf=0;

var baryPos={x: 1 , y: 0 , norm: 1};

// MAIN: begin loop
loop {

// Initializing the frame
kFrame+=1;
xSelf = this.pos.x,
ySelf = this.pos.y;
coins=this.findItems();

// Processing Coin stuff
if(nCoins!=coins.length||this.distanceTo(toCoin)<1){
nCoins=coins.length;
unthrottleBary = kFrame - thenBary >= 15;
if (unthrottleBary) { // Only compute bary at most every 15 frames
thenBary = kFrame ;
baryPos=vectBaryToMe(this,coins,nCoins,xSelf,ySelf);
}
toCoin = findNextItem(this, coins,nCoins,baryPos,xSelf,ySelf);
} // if Processing Coin stuff

if (toCoin) {
this.move(toCoin.pos);
} // if toCoin

} // End main loop
``````
**Function : Computing Barycenter**
``````// External computation of the barycenter of coins
function vectBaryToMe(self,items,nItems,xSelf,ySelf){
// Barycenter Variables
var xSum = 0,
ySum = 0,
valSum = 0;

// Loop variables
var item, iVal;

// Return values
var xRes, yRes ;

for (i = 0; i < nItems; i++) {
item = items[i];
// Get Barycentric Sums
iVal = item.value;
xSum += item.pos.x * iVal;
ySum += item.pos.y * iVal;
valSum += iVal;
}

xRes = xSum / valSum - xSelf ;
yRes = ySum / valSum - ySelf ;

return {
x : xRes ,
y : yRes ,
norm : Math.sqrt(xRes * xRes + yRes * yRes)
};
}
``````
**Function : findNextItem**
``````// Function deciding which coin to go to next.
function findNextItem(self, items,nItems,baryVect,xSelf,ySelf) {

var distWeighted,
distWeighted2,
leastDistWeighted = 2147483647,
leastDistWeighted2 = 2147483647;

// For looping
var i,
item,
iVal;

// Vectorization
var coeffBary,
xV1, yV1, normV1,
xV2, yV2, normV2;

// Return Values
var nextItem = null,
nextItem2 = null;

// Deciding which coin to pick next

for (i = 0; i < nItems; i++) {
item = items[i];

if (self.distanceTo(item) >= item.distanceTo(PENDER)) {
// First Elimination: Closer to me than enemy?
continue;
}

distWeighted = self.distanceTo(item) / item.value;
if (distWeighted < leastDistWeighted) {
leastDistWeighted = distWeighted;
nextItem=item;
if (leastDistWeighted < 25) {
xV1 = baryVect.x;
yV1 = baryVect.y;
normV1 = baryVect.norm;
xV2 = item.pos.x - xSelf;
yV2 = item.pos.y - ySelf;
normV2 = Math.sqrt(xV2 * xV2 + yV2 * yV2);
coeffBary = 5 + (xV1 * xV2 + yV1 * yV2) / (normV1 * normV2);
distWeighted2 = distWeighted / coeffBary;
if (distWeighted2 < leastDistWeighted2){
leastDistWeighted2 = distWeighted2;
nextItem2 = item;
}
}
}
}

// We return the best Coin, according to this algo.
// This if ensure the function returns a coin, if at least one is present
if (nextItem2){
return nextItem2;
}else if(nextItem){
return nextItem;
}else{
return self.findNearest(items);
}
} // end function findNextItem
``````

Throttling

First of all, minor change : I removed the unthrottling part to limit the computation once a frame. I love the idea and the structure you use. However, as I made sure my hero had a target every frame, it didn’t change anything in the StatementPerFrame (SPF) measurement (the move command already ensures nothing is done until next frame). Maybe the unthrottle will be back in a later algo (when actually fighting), but it felt redundant to me, so I removed it for now.

###Barycenter
Second, I extracted the computation of barycenter out of the actual findNextCoin function. Two reasons : I wanted to prevent unecessary computation with a computation once every N=15 frames. The actual position of bary isn’t moving fast, even on a 2sec duration. This alone decreased the SPF by 130.

Also, I think the position of the barycenter should be computed over all coins and not only the ones on my side. The whole idea of checking where the barycenter is, is to tend to prevent being enclosed into a low gold area. And I think with the computation of the barycenter you gave above, if enemy Pender is in center of the map and you are in a corner, there is no way you’d ever consider a coin past the corner you’re stucked within.

###findNextItem()

The function findNextItem has also been tweaked to ensure a return of a coin. I’ve created two possible returning values : nextItem2 and nextItem :
The more refined coin to go to is nextItem2, as it checks the “no-low-gold-zone” criteria. So preferentially, I’ll return nextItem2. But sometimes I can’t return nextItem2 (when I’ve looted every single close coin : no coin matches the condition leastDistWeighted < 25). So when this happen, I return the best coin my algorithm was able to provide me : I return nextCoin. But even this might not happen : when pender is closer to every coin than I am (this happens when I’m in a corner, and Pender is close to me, but closer to the center than me). So in this case : I return the first coin I find (nearestCoin).
I think having two return values in a double conditions algorithm is a good way to structure it. I like the presence of nextItem2 in order to not overwrite nextItem.

Alos, you’ll see that tweaked the “consider only coins that are closer to me than to pender” part to be :

``````if (self.distanceTo(item) >= item.distanceTo(PENDER)) {
// First Elimination: Closer to me than enemy?
continue;
}
``````

###Coin computing

The idea you gave :

**Idea**
``````loop {
coins = this.findByType("coin");
if (nCoins != coins.length) {
nCoins = coins.length;
nextCoin = findNextCoin(this);
}
this.move(nextCoin.pos);
}
``````

is very nice. Love it. Reduced SPF a lot. However, sometimes my hero would be stuck whenever a coin would be looted during the same frame another one popped out. I added a distance check but I’m not totally satisfied with it.

``````if(nCoins!=coins.length || this.distanceTo(toCoin)<1)
``````

I’ve tried many things to prevent this minor problem at low cost but to no avail. The distance checks adds a 100 SPF (50% increase ) to prevent some minor pauses here and there. I’ve played around with indexes and arrays of items (as findItems() returns an array that is PUSHED when a coin pops out and is SPLICED when a coin is looted, whereas findByType(“coin”) is not reliable to search through with indexes). But I couldn’t find a more efficient way to solve this problem.

Hope this is constructive and someone find this big block of text useful. Have a good night all.

4 Likes