Help on improving code : Looting coins


#1

Hello,

I’m working on Zero Sums and other looting arena. I would like to have a feed back on the code below. You can copy paste the entire code in ZeroSums, and that would work.

I’ve been working with the console open, and I’ve been monitoring the computational time per frame, and I tried to improve it. I also tried to make it as clear as possible to understand.

Explainations :

The idea is to find a good path to your next coin. Your next coin has to :

Be nearby
Have a good value. Both of these are taken into account in // (1) (see code)
Be closer to me than to my opponent (because he’ll grab it first). This is // (2)
Prevent me to go to a “low gold” zone. This is both the // (3) and the // (0).

This last condition is expensive in computation, and only useful from time to time. It happened to me that I’ve been stuck in a path away from my own golden shower, going into a corner of the battlefield with very low income, and sometimes this is the difference between victory or death. Also I like the maths behind it, because I think it’s efficient mathematically.

The “no low gold zone” is achieved as explained in my other post here
I think the way I wrote it is fairly efficient. Maybe there are better ways, but I was somewhat happy with the if-condition // (3) because it filters out a lot of non necessary processing time. The computation of the goldBarycenter could also be computed upstream (and not every frame, as it doesn’t move a lot).

Feel free to give any feedback, and/or to use my code (or part of it) in your arenas to loot coins !

var pender=this.findNearest(this.findEnemies());

loop {
    var allCoins=this.findByType("coin");
    var nextCoin=findNextCoin(this);
    this.move(nextCoin.pos);
}

function findNextCoin(parThis){
    var leastCoinDistWeighted=100;
    var leastCoinDistWeighted2=100;
    var myPos={x:parThis.pos.x,y:parThis.pos.y};
    
    //Computing the barycenter of the coins, and a vector related // (0)
    var tempX=0; var tempY=0; var totalValue=0;
    for(var iCoin=0;iCoin<allCoins.length;iCoin++){
        var currCoin=allCoins[iCoin];
        var currValue=currCoin.value;
        tempX+=currCoin.pos.x*currValue;
        tempY+=currCoin.pos.y*currValue;
        totalValue+=currValue;
    }
    var goldBary={x:tempX/totalValue,y:tempY/totalValue}; 
    var v1={x:goldBary.x-myPos.x,y:goldBary.y-myPos.y};
    var v1Norm=Math.sqrt(v1.x*v1.x+v1.y*v1.y);
    
    // Deciding which coin to pick next
    for(iCoin=0;iCoin<allCoins.length;iCoin++){
        currCoin=allCoins[iCoin];
        var currCoinDist=parThis.distanceTo(currCoin);
        var currCoinDistWeighted=currCoinDist/currCoin.value;
        if (currCoinDistWeighted < leastCoinDistWeighted) {// (1)
            if(pender && currCoin.distanceTo(pender) > currCoinDist){ //(2)
                leastCoinDistWeighted=currCoinDistWeighted;
                if(leastCoinDistWeighted<15){// (3)
                    var v2={x:currCoin.pos.x-myPos.x,y:currCoin.pos.y-myPos.y};
                    var v2Norm=Math.sqrt(v2.x*v2.x+v2.y*v2.y);
                    var cosineV1V2=(v1.x*v2.x+v1.y*v2.y)/(v1Norm*v2Norm);
                    var coefTowardGoldBary=3+cosineV1V2;
                    var currCoinDistWeighted2=currCoinDistWeighted/coefTowardGoldBary;
                    if(currCoinDistWeighted2<leastCoinDistWeighted2){
                        leastCoinDistWeighted2=currCoinDistWeighted2;
                        nextCoin=currCoin;
                    }
                }else{
                    nextCoin=currCoin;
                } //(3) 
            } //(2)
        } //(1)
    } //(for iCoins)
    return nextCoin;
}

Is there a better way to make peasants target different coins?
Vectors, FacingTowards and looting Coins
#2

As a PS from my own post here is a fully functional code with no “facing the barycenter” stuff. This code is efficient and ready to copy-paste (if ever you’d be interested in a functional code and not the improvement discussion). This code runs a 16ms per frame average. The code above is 37ms per frame.

var pender=this.findNearest(this.findEnemies());
loop {
    var allCoins=this.findByType("coin");
    var nextCoin=findNextCoin(this);
    this.move(nextCoin.pos);
}

function findNextCoin(parThis){
    var leastCoinDistWeighted=100;
    // Deciding which coin to pick next
    for(iCoin=0;iCoin<allCoins.length;iCoin++){
        currCoin=allCoins[iCoin];
        var currCoinDist=parThis.distanceTo(currCoin);
        var currCoinDistWeighted=currCoinDist/currCoin.value;
        if (currCoinDistWeighted < leastCoinDistWeighted) {// (1)
            if(pender && currCoin.distanceTo(pender) > currCoinDist){ //(2)
                leastCoinDistWeighted=currCoinDistWeighted;
                nextCoin=currCoin;

            } //(2)
        } //(1)
    } //(for iCoins)
    return nextCoin;
}

#3

What kind of improvements are you looking for? Performance? Load? Fewer instructions? Or is this still trying to address the Hard Execution Limit?


#4

The idea is that you only run computations when a coin is added or removed. Simply cache the number. Depending on the level (and current state) this can save a ton of computations. This can even help for friend and enemy processing, especially in cases where a whole ton of objects are created simply to make some decision.

**Outdated Example - (still useful in other circumstances)**
loop {
// New placeholder variable
    var numCoins;  
    var allCoins = this.findByType("coin");
// Wrap processing in a condition that runs when only changed
    if (numCoins !== allCoins.length) {
    // Has changed: Record the new value
        numCoins = allCoins.length;
        nextCoin = findNextCoin(this);
    }
// Continue moving because nothing has changed.
    this.move(nextCoin.pos);
}

Personal Note: Your code is very hard to read. Improving the code style would really help. Add spaces between variables and operators. Some white space would help too.


#5

As a self taught guy in Basic, I’m looking for any tip from anyone better than me now that I’m working in JavaScript.

For example, I don’t know if I’m handling position object correctly. It seems objects { x: , y: } are nice, but I can’t find a way to make simple operation with them. Every time I’m writing a new position, I feel I have to extract infos out of the object to remake a whole new object. Is this stupid / inefficient ? (see example below) Isn’t there a better way to do the same more elegantly ?

    var tempX=0; var tempY=0; var totalValue=0;
    for(var iCoin=0;iCoin<allCoins.length;iCoin++){
        var currCoin=allCoins[iCoin];
        var currValue=currCoin.value;
        tempX+=currCoin.pos.x*currValue;
        tempY+=currCoin.pos.y*currValue;
        totalValue+=currValue;
    }
    var goldBary={x:tempX/totalValue,y:tempY/totalValue}; 

Another question is : Is it better / worse / same to have

if(condition1){
    if(condition2){
        somecode1
    }else{
        somecode2     
    }
}

and

if(condition1&&condition2){
    somecode1
}
if(condition1&&!condition2){
    somecode2
}

Does this code seem correctly written ? Redundancy in the call of conditions ? Unecessary variables ? Weird syntax ? Standard way to name variables (mine tend to be rather long) ? I’d like to learn how to write efficient code and get good habits doing so.

In the end for the tournament ZeroSum and the HardExecutionLimit, I think I’ll drop the whole “let’s find the goldBarycenter” piece, as it’s not battle-efficient enough to spend this much computation doing this little. But I tried to write non-obvious piece of code and tried my best to make it well written so that people could jugde how good/bad it feels / is.


#7

Thanks, this is exactly what I’m looking for. I’ve been programing for too long on my own, I’m sure I have bad habits and wrong ways to make many things. It’s good to share, only few of my friends are in computers… It’s hard to improve on my own :smile:

One question, when you mean “cache”, you mean “set the value of something in a variable ?”. I think I don’t understand exactly the meaning of this precise word : “cache”. (embarassing…)

(I’ll go to bed now, I help moving my brother’s appartement tomorrow early in the morning. I’ll read and appreciate your help by Sunday. Thanks again for your time)


#8

Yup, “store/save it somewhere” is what he means.

I think cache has fallen out of favor as a general word. People hide their money in/under their mattress :slight_smile: instead of caching it there…


#9

OK. There’s a lot here to improve upon. Keep in mind that this is not a primer for how to write good code, but some answers for your stated desires based on this piece of code. Some could be more efficient, some could be more readable, and some will just be “smarter” computing. Much here is better explored and explained with other resources and should not go any further into depth than this, here. It may even be beyond the scope of this site’s goals (I’m sure we’ll find out). This is a long post, so be prepared.

Style Improvements

Multiple var statements

Avoid this type of declaring, unless there’s a reason that they should be this way (for clearer understanding). JavaScript allows you to declare and initialize multiple variables with one statement.

var tempX = 0,
    tempY = 0,
    totalValue = 0;

This helps readability and if necessary allows you to comment specific variables according to whichever style you prefer.

Vars in loops and conditions

Avoid declaring vars in any loop and most conditions. This is misleading and some interpreters actually mishandle this into odd bugs. The only var in a for loop that is acceptable and universally handled correctly in the parens. Example:

var currCoin,
    currValue;
for (var iCoin = 0; iCoin < allCoins.length; iCoin++) {
    currCoin = allCoins[iCoin];
    currValue = currCoin.value;
    ...
    ...
}

Variable Names

A variable name should be exactly as long as it needs to be to describe exactly what it is. It’s that simple. If you have two iterators being used at the same time, then differentiate between them. If not, i is standard and clear and can be reused later. Long variable names are just a hazard of the job.

What is caching?

Caching is when you get some data and store it for one of two reasons:

  • For faster, or easier later access (not manipulation)
  • To reduce load or processing.

This can be in a simple file format, a variable or even to local storage. The idea is that, by storing this information, it is instantly available until it changes or we don’t need it anymore. In the particular case that I gave, the length property which normally requires a full array is stored so that we can compare against a potentially new later array. If it changes, then we update it and do our thing. But if not, our previous information is still valid. It should be noted that while it is pretty reliable, it is not foolproof. If for some reason, a coin is added at the exact same frame that one is removed, then it is possible it won’t register the change. However, those cases are extremely rare and I have never encountered it in this game (so far).

Efficiency

There are lots of micro-optimizations that one can do that are just as readable… however, mileage varies widely between interpreters. So, these won’t be addressed. However, here are a few things which are good to know based on both a) your questions and b) smart conventions.

Single Objects vs. Multiple Primitives (ints, floats, strings, etc)

Objects are handy… super handy. In general, we create objects when properties and/or methods are related to a single concept. There are a few exceptions, however:

  • When the properties will never be referenced beyond the first time
    AND
  • If they aren’t going to be returned together

So, some of your objects could definitely be multiple vars. But, some should probably stay as objects.

For loops and Objects/Arrays

In general, using objects in the setup for a for loop is actually bad. In some cases, it is more readable, but it is ALWAYS slower to the point that many even discourage such use.

    for (var iCoin = 0; iCoin < allCoins.length; iCoin++) {
        ...
    }

The above checks allCoins.length everytime the loop iterates. This means that even though you type it once, it is access length number of times. This is generally (not always better).

var nCoins = allCoins.length;
for (var iCoin = 0; iCoin < nCoins; iCoin++) {
    ...
}

Still quite readable, and a lot of performance gains. If order is not important, a reverse can be beneficial and limit the need of another variable. Some find it confusing because of misunderstanding of difference between ++var and var++. I use this often, but never would I recommend it. I only add it for completeness.

for (var iCoin = allCoins.length; --iCoin >= 0; ) {
   ...
}

This saves a variable and is generally readable. If novices are expected to be using your code, or you could confuse yourself, don’t use this.

Redundancy of Call Conditions

This depends on need but Generally, if you can, only check a condition once per opportunity for it to change. If it is possible for it to change, but the condition is still needed, definitely check it again. If its value or state is not changed between the checks, it should only be checked the once.

// This form can also save computations, especially if in a loop.
if (condition1) {
    if (condition2) {
        // some code
    }
    else {
        // some code
   }
}

An additional note is that your most common result should generally be at the top. This not only improves performance in the majority of interpreters, but also signifies to you and other coders that this is the most expected result. Of course, there are always exceptions, but this is a standard that one should adhere to more often than not.

Unnecessary Variables

A variable is only unnecessary when it adds no value to the code or removes from the readability. While there are many reasons to use (and avoid) them, most fall within these 3 core reasons:

  • The result of a computation is needed for later
  • The result of a computation (data, operation or function) is used more than twice.
  • A concept should be illustrated by name (hence, more easily understood by sight)

In other words, no one can tell you if you need a variable. Something to keep in mind, however, especially with function calls:

var d = this.distanceTo(object);
var result = d * d;

// ... is much, much more efficient than ...

var result = this.distanceTo(object) * this.distanceTo(object);

Although the above is demonstrated with a function, it is also true for objects. Many devs will actually create vars for object properties that they are accessing more than a couple of times. This is especially true for nested object properties.

Consider:

var obj = {
    pos: {
        x: value1,
        y: value2
    }
};

You can easily access the properties via obj.pos.x. But if you are doing this more than once, it is actually faster and more readable to do the following:

var pos1 = obj.pos;

pos.x;

While in many cases, you can save more by sometimes doing:

var tmpPos = obj.pos;
var xPos = tmpPos.x;

… this will sometimes detract from both readability and performance. It all depends on how often you are accessing pos and x. If you use x a lot, but ignore pos, then this might be preferrable: var xPos = obj.pos.x; The second you access more than two properties from an object, that object should be a variable, if performance is the concern. Now there is an exception, because of how JavaScript works. Any variable that is discarded immediately, could probably be simply changed. This is because JavaScript is not hard-typed. Here’s an example from your own code.

                if(leastCoinDistWeighted<15){// (3)
                    var v2={x:currCoin.pos.x-myPos.x,y:currCoin.pos.y-myPos.y};
                    var v2Norm=Math.sqrt(v2.x*v2.x+v2.y*v2.y);
                    var cosineV1V2=(v1.x*v2.x+v1.y*v2.y)/(v1Norm*v2Norm);
                    var coefTowardGoldBary=3+cosineV1V2;
                    var currCoinDistWeighted2=currCoinDistWeighted/coefTowardGoldBary;
                    if(currCoinDistWeighted2<leastCoinDistWeighted2){
                        leastCoinDistWeighted2=currCoinDistWeighted2;
                        nextCoin=currCoin;
                    }
                }else{
                    nextCoin=currCoin;
                } //(3) 

The cosineV1V2 could be unnecessary. It is never referenced again. You could simply do the following:

                if(leastCoinDistWeighted<15){// (3)
                    var v2={x:currCoin.pos.x-myPos.x,y:currCoin.pos.y-myPos.y};
                    var v2Norm=Math.sqrt(v2.x*v2.x+v2.y*v2.y);
              // Here is the change!
                    var coefTowardGoldBary =(v1.x*v2.x+v1.y*v2.y)/(v1Norm*v2Norm);
                    coefTowardGoldBary += 3;
                    var currCoinDistWeighted2=currCoinDistWeighted/coefTowardGoldBary;
                    if(currCoinDistWeighted2<leastCoinDistWeighted2){
                        leastCoinDistWeighted2=currCoinDistWeighted2;
                        nextCoin=currCoin;
                    }
                }else{
                    nextCoin=currCoin;
                } //(3) 

The Hard Execution Limit

This is a tough subject because many thing will contribute to HEL that could be otherwise inlined directly by the interpreter. What I mean is, the interpreter optimizes much of your code as it is run. But CodeCombat doesn’t necessarily work this way since it uses a transpiler and code magic to achieve its ends. This means that some inline statements could indeed increment the execution count multiple times (in fact, I have found this to be a possibility with several things). The best way to avoid HEL is to keep your code simple and not count on in-lining. This generally means all of the above that I already mentioned. It actually helps in most circumstances.

The Golden Rule

All of the above are suggestions based on your requested answers. The truth is, it is your code and it always depends on your needs. If you need to share code with a community or get feedback, then style guidelines are probably important. If not, you can ignore them freely.


#10

@VincentMaths: How are you getting the ms per frame measurements? I’d like to use some available tools as well. I think that many players would. Sometimes it seems to me that CodeCombat isn’t so much about learning to code as it is about dominating the game. This is not directed at you, but if the premise in CC is for everyone to devise their own clever strategy for each level, then I’m not sure that that is the most efficient way to learn. (It’s kind of like the inventor of some technology taking the attitude “I figured it out. Now you figure it out!”)
[Stepping down off my soapbox]

Thank you for sharing your code! I appreciate it! :thumbsup:


#11

If he is relying on “this.say(this.now())”, just know that those are approx. timings.
Your mileage may vary, but when I did

(.say this (.now this))  ;; said: 0
(.say this (.now this))  ;; said: 0.897
(.say this (.now this))  ;; said: 1.75   (added: 0.853)

yet, say should “Takes: 1s.”

The timings are approximate (could be for all sorts of reasons, most of which would be legitimate).


#12

AMAZING ! Reading later. Thanks very much guys. Really appreciated. Got to go !


#13

That is, in fact, the most efficient way to learn programming: Give the aspiring programmer something that they want to program. Historically, it applies to any creative science. Sorry you feel that way.


#14

So, I’ve taken the code into my own Zero Sum to experiment with it. Not surprisingly, only checking coins when coins are added or removed helps a lot and I haven’t reached the HEL once. Of course, the AI dies after 1 min, but considering you were having problems at 30sec, this is a good indicator.

Regarding your second condition:

Looking at your code and conditions, this appears to be the most important consideration, but doesn’t actually save your code any work. As it stands, the code runs through all coins twice. If you were to check for your second condition in the first loop, you can save yourself a lot of processing.

Here’s what I have tweaked to:

**Tweak: Main Loop (throttling by length)**
loop {
    coins = this.findByType("coin");
    if (nCoins != coins.length) {
        nCoins = coins.length;
        nextCoin = findNextCoin(this);
    }
    this.move(nextCoin.pos);
}

In discriminating algorithms, it is generally best to eliminate early whenever possible. With this code, virtually 1/2 of the field is eliminated before we even start moving. As position updates, the number of options for comparison increase and decrease naturally. In tense situations (opposing pender controlling more field), this makes things much faster. In relaxed situations, there is better chance to pick the best value.

**Tweak: findNext - 1st Loop (move condition 2)**
    myCloser = [];
    nCoins = coins.length;
    for (var i = 0; i < nCoins; i++){
        coin = coins[i];
    
    // Get Barycentric Sums
        var currValue = coin.value;
        tempX += coin.pos.x * currValue;
        tempY += coin.pos.y * currValue;
        totalValue += currValue;
        
    // First Elimination (Second Condition)
    // Is it closer to me or her?
        if (self.distanceTo(coin) <= coin.distanceTo(pender)) {
            myCloser.push(coin);
        }
    }
**Tweak: findNext - 2nd Loop (use new array)**
    nCoins = myCloser.length;
    for (i = 0; i < nCoins; i++) {
         currCoin = myCloser[i];
         ...
         // Rest of Barycenter code
         ...
    }

I haven’t tweaked the rest of the code, but this seems to help a lot without worrying about micro-optimizations (which should be discouraged until absolutely needed).

Udpate: After running the original vs these changes

This actually grabs coins faster for the same level seed. Your code was winning against AI @ 1:05 with 502 gold. These changes win against AI @ 1:05 with 558 gold.

Update 2: With the next change

I got to thinking that perhaps the barycenter should also change according to the second condition. In other words, the vector will change according to the most value that your hero can access. After running tests, win is at 1:08 with 615 gold.

First Loop: Adjusted Barycenter
    for (var i = 0; i < nCoins; i++){
        coin = coins[i];
        
    // First Elimination
        if (self.distanceTo(coin) <= coin.distanceTo(pender)) {
        // Add to new array
            myCloser.push(coin);
        // Get Barycentric Sums
            var currValue = coin.value;
            tempX += coin.pos.x * currValue;
            tempY += coin.pos.y * currValue;
            totalValue += currValue;
        }
    }

Final Update: Serious Flaw

While the code works, the algorithm as you coded it has a serious flaw and fails to accomplish what you wished it to. This is dues to your last condition:

Second Loop:

    for (i = 0; i < nCoins; i++) {
        ...
        if (currCoinDistWeighted < leastCoinDistWeighted) {
            if (pender && currCoin.distanceTo(pender) > currCoinDist) {
                ...
                if (leastCoinDistWeighted < 15) {
                    ...
                } 
                else {
                    nextCoin = currCoin;
                }
            }
        }
    }

When this executes, anytime any coin doesn’t meet the weighted distance, it overwrites any previously found optimal coin. So, this means that if the last coin is not optimal, it becomes the chosen coin. It additionally means that each optimal coin is often compared against coins that are already not optimal (rather than compared against other potentially optimal coins). I fixed this with the following:

**Code: Fixed Loop**
    for (i = 0; i < nCoins; i++) {
        ...
        if (currCoinDistWeighted < leastCoinDistWeighted) {
            if (pender && currCoin.distanceTo(pender) > currCoinDist) {
                ...
                if (leastCoinDistWeighted < 15) {
                    ...
                } 
            // If we already have an optimal coin, don't overwrite it
                else if (!nextCoin) {  
                    nextCoin = currCoin;
                }
            }
        }
    }

Console & Optimization [Advanced]
#15

If you want to time how long things are taking, don’t put this.say() into your code; just open up the JS console and look at the log statement it outputs for how long it took to simulate the match. Of course it’s counting time, not statements, and it’ll only be relevant against the same opponent with the same computer with the same general outcome of the match, but it does do that much timing for you.

|Ra's Krieger| And it was so: (27.932ms per frame, 923 frames)
Simulation   : 25781ms 
Serialization: 683ms
Delivery     : 241ms

You can also see how many statements you used by typing this into the JS console:

currentView.tome.spellView.spellThang.castAether.metrics.statementsExecuted
// 905156

Console & Optimization [Advanced]
#16

That is very awesome information to have.


#17

OK, at first I thought he was going to use Vector stuff and not do it by hand, but it looks like there are no “new Vector”, no .add, .subtract, .multiply, .normalize, …

Then I thought maybe he was going to use them somehow as position objects, nope.

So I am wondering if there is a reason to make an object {x:,y:} out of the x and y coords, instead of simply making them variables “goldBaryX, goldBaryY, v1x, v1y, v2x, & v2y”. Is it faster? Is it just because objects are so cool… :wink:

For example, v2 is created and used solely in the following three consecutive lines:

var v2={x:currCoin.pos.x-myPos.x,y:currCoin.pos.y-myPos.y};
var v2Norm=Math.sqrt(v2.x*v2.x+v2.y*v2.y);
var cosineV1V2=(v1.x*v2.x+v1.y*v2.y)/(v1Norm*v2Norm);

Thanks


#18

He was originally using objects and functions, if you were available to read the original thread. The reason he backed away from them was based on hitting the HEL way too early. Temporary objects are expensive, especially if they have a prototype, so variables are definitely the way to go. Working version with explanation below.


#19

A Working Version

After hearing that you were ready to give up on this fine algorithm, I figured modifying it to working condition might be more helpful to show not only what can help within CodeCombat, but some generally good practices when working with JavaScript. Keep in mind, this is not the best version it could be. There is always much to learn, but maybe this will give you a better starting point. Is this the best algorithm? Who knows? But it is definitely worthy of getting to work.

Main Loop

The most significant differences here are the throttling and the summoning. Most actions are execution blocking, which means that the more your hero does, the more room you will have from the HEL. unthrottle is provided as a variable because there might be other places you wish to use it.

**Code:Main Loop**
// INIT: Constants and Configuration
    var FRAME_CLAMP = 0.125,
        PENDER = this.findNearest(this.findEnemies());
    
// Used for Timing and Processor Throttling
    var now = 0, then = 0, unthrottle = false;

// Stores the position of the next Coin
    var toCoin = null;

// MAIN: begin loop
    loop {
    // Check whether to process... 
        now = this.now();
        unthrottle = now - then >= FRAME_CLAMP;
        if (unthrottle) {
            then = now;

        // Pass coins by reference
            toCoin = findNextCoin(this, this.findByType("coin"));

        // This slows things down a bit :)
            if (this.gold > 20) 
                this.summon("soldier");
        }

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

Function: findNextCoin()

This will look fairly similar, but I use more local variables and store object properties where appropriate. This makes a huge difference. The largest impact comes from creating a smaller array excluding coins that are close to the opponent. Though it is two loops, the second has much fewer items.

These differences have enough of an impact that you could easily consider being more functional. If you go with objects, follow the same rules as here. Store properties that are accessed multiple times. Really, you should only build an object when you are passing one or returning one. Deconstruct it when you are using its parts. Set the properties when you are done modifying the values.

**Code:findNextCoin**
    function findNextCoin(self, items) {
    // The hero's coordinates
        var xSelf = self.pos.x,
            ySelf = self.pos.y;

    // Use actual maxes: May allow multiplicative solutions in the future.
        var currCoinDistWeighted,
            currCoinDistWeighted2,
            leastCoinDistWeighted = 2147483647,
            leastCoinDistWeighted2 = 2147483647;
    
        var coin, iVal,              // item iteration
            i, nCoins, myCoins;  // For looping

    // Barycenter Variables
        var xSum = 0,
            ySum = 0,
            valSum = 0;

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

    // Return Value
        var nextCoin;
    
    // Compute Barycenter
        myCoins = [];
        nCoins = items.length;
        for (i = 0; i < nCoins; i++) {
            coin = items[i];
    
        // First Elimination: Closer to me?
            if (self.distanceTo(coin) <= coin.distanceTo(PENDER)) {
            // Add to new array
                myCoins.push(coin);
            // Get Barycentric Sums
                iVal = coin.value;
                xSum += coin.pos.x * iVal;
                ySum += coin.pos.y * iVal;
                valSum += iVal;
            }
        }

        xV1 = xSum / valSum - xSelf;
        yV1 = ySum / valSum - ySelf;
        normV1 = Math.sqrt(xV1 * xV1 + yV1 * yV1);
    
    // Deciding which coin to pick next
        nCoins = myCoins.length;
        for (i = 0; i < nCoins; i++) {
            coin = myCoins[i];

            currCoinDistWeighted = self.distanceTo(coin) / coin.value;
            if (currCoinDistWeighted < leastCoinDistWeighted) {
                leastCoinDistWeighted = currCoinDistWeighted;
                if (leastCoinDistWeighted < 15) {
                    xV2 = coin.pos.x - xSelf;
                    yV2 = coin.pos.y - ySelf;
                    normV2 = Math.sqrt(xV2 * xV2 + yV2 * yV2);
                    coeffBary = 4 + (xV1 * xV2 + yV1 * yV2) / (normV1 * normV2);
                    currCoinDistWeighted2 = currCoinDistWeighted / coeffBary;
                    if (currCoinDistWeighted2 < leastCoinDistWeighted2){
                        leastCoinDistWeighted2 = currCoinDistWeighted2;
                        nextCoin = coin;
                    }
                }
            }
        }
    
    // We return the Position because that is what we really want.
    // Also, this might be useful for other movement affecting factors
        if (nextCoin)
            return nextCoin.pos;
    }

Final Results

This current code executes 516k statements with a verdict at 1:25. This is way below the original Hard Execution Limit.

**Other Possible Improvements**
  • With the expanded HEL of 3000000, this gives plenty of room for:
    • ally coordination,
    • advanced targeting
    • and other possibilities.
      *range tweaking is pretty cheap. +5k (< 1%) statements @ 25

If you want to further improve, you might consider tweaking how you weight distances. It will go out of its way to get a gem, when it may not be more efficient. 5 coins in a cluster is generally better than a single gem. (Remember, coins only repop when they are picked up). That said, there aren’t a lot of situations where that will be a problem.

Hope this answers some of the questions in the big bag of yours. :smile:


#20

I just wanted to say thank you to everybody in this thread (especially FuzzicalLogic) for taking the time to answer my questions. I finally had time to read all the posts (crazy extended Easter week-end), and this discussion was very helpful to me. Thanks. Again.


#21

Thanks for your algo. I’ve tweaked it quite a bit myself and found a great balance of coin gathering vs. CPU. Finally finished with a 30% gold gain and 75% drop (250k instructions @ 1:00 min). Of course, I spent so much time on it, I didn’t do anything with the tourney. LOL