# Help on improving code : 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.

1 Like
#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

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 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.

3 Likes
#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!

#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).

1 Like
#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.

1 Like
#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.

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.

``````    for (var i = 0; i < nCoins; i++){
coin = coins[i];

// First Elimination
if (self.distanceTo(coin) <= coin.distanceTo(pender)) {
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;
}
}
}
}
``````
#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
``````
3 Likes
#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…

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)) {
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,
• 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.

#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

#22

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