Vectors, FacingTowards and looting Coins

1

It seems I found out a solution, even though there is still something bugging me about it. Writing this post helped me clear my head and my syntax to explain my problem. No more help requiered about this specific instance. Sorry I wrote this “dead” post. I didn’t find the need to delete it, if the idea of double weighting could help someone. If it did, I would love to hear a thank you in my inbox :smile:

For any curious coder, the solution of the problem below is : “don’t compute vectorial stuff when the coin is too far away to matter”. I added a condition. Instead of

var facingValue = 3 + cosinusOf( Vector( this.pos , currentCoin.pos) , Vector( this.pos , goldBarycenter.pos);

I wrote :

if(currCoinDist<15){
  var cosine= cosinusOf( Vector( this.pos , currentCoin.pos) , Vector( this.pos , goldBarycenter.pos);
}else{
  cosine=0;
}
var facingValue=3+cosine;

Original post

Hello there,

I’m having a bit of trouble finding out why my code is bringing me a HardExecutionLimit, and I think I’ve narrowed it down to my vectorial functions.

In order to find the best coin to go to, I check the value of the distance/goldValue of the coin and I make a loop throught all the coins to find the minimum.
As I refined this idea, I wanted to add another weight : facingValue, so that the variable to minimize would be

var leastDistance = distance / ( goldValue * facingValue )

if the coin makes you go towards the bulk of the gold on the ground -> good ( facingValue = 4); if it makes you walk away from most of the gold -> bad. (facingValue = 2). It means that a coin that’s making go away from goldBarycenter will appear twice less appealing that a similar coin helping you go toward goldBarycenter.

So it comes down to a simple formula (wikipedia dotProduct) :

var facingValue = 3 + cosinusOf( Vector( this.pos , currentCoin.pos) , Vector( this.pos , goldBarycenter.pos);

with the vectorial functions being :

function Vector(head,tail){
  return {x:(head.x-tail.x),y:(head.y-tail.y)};   
}

function cosinusOf(vect1,vect2){
  var res=dotProd(vect1,vect2)/Math.sqrt(dotProd(vect1,vect1)*dotProd(vect2,vect2));
  res;
}

function dotProd(vect1,vect2){
  return vect1.x*vect2.x+vect1.y*vect2.y;   
}

In order to debug my code :

  1. Everything runs smoothly if I skip the computation of facingValue, and I set its value to 1
  2. I get a HardExecutionLimit reach around 30sec in combat when I compute facingValue.
  3. The problem doesn’t come from the computation of the goldBarycenter, because even if I set it to a fixed position (ex : center of the battlefield ; no computation requiered), I still reach a HardExecutionLimit around 30sec in combat.

I don’t get it. What’s wrong with my dotProd() & cosinusOf() functions ? Few “+” and “x” are really this expensive to compute ? Any tip is very welcomed.

PS : interesting library I’d like to be able to fully understand.

1 Like
2

I have run into hard execution limits many times. Do not let this confuse you… Unless you can find it, your code is not necessarily slow or running large loops.

Despite much conjecture on this, I’ve found that using loop { breaks; } over whiles and fors (even if they run the same calculations) helps whenever you can do it. Chances are there is nothing wrong with your code, but putting limits on execution can help. In my experience, they help considerably.

Limit 1

Cache as many values as possible by storing them in a local variable. This even includes property lookups. One thing that I cache that others may not is friends and enemies. Then I only do recalcs when the field has changed. This allows for a lot of leeway.

Limit 2

Check a given condition as few times as possible per loop iteration. Combined with caching, this also helps considerably.

Limit 3

Use assertive code. I.E. Force the conditions to meet your desires as much as possible.

Limit 4

Avoid Functions. On every level I have used a function, the hard execution limit occurs faster than if it is just run inline. As much as I love functions, until this is fixed, I have sworn them off.

Limit 5

Integers as much as possible. Don’t know why, but it’s demonstrated itself over and over again. When I replace a float with an integral counterpart, fewer hard limits are reached.

Final Note

It is important that your hero always perform an action (even a wait()). Normally a move() is sufficient.

While I can’t say why it happens (only the devs can do that), These tips have helped me considerably. They do require inventive coding, however, which sometimes becomes a bit convoluted. These posts may also help:

2 Likes
3

Thanks a lot for those tips ! I’m somewhat new to CodeCombat (my account was created last Wednesday). Thus I guess I’m lacking (a lot of) experience as I didn’t bash my head long enough on the limitations. Thanks a lot for the insight on how to (try to) prevent HardExecutionLimit.

4

Not a problem. I’ve been doing this a long time, so I have a code style and like to meet my own needs as much as possible. The Hard Execution Limit was put in to help new coders. Novices frequently accidentally create infinite loops and this detects them. The issue with this is that it is unable to determine accurately when the code is still performing as expected, so the limit is never reset unless the level is restarted.

This means that even smart (and fast) calculations can cause you to hit the limit, even if your code is working as expected. Be especially wary of long levels. The longer the level (in time), the more simple your code has to be in order to avoid the limit. For instance, my Zero Sum submission originally did some cool enemy prioritization and minion proportioning. However, I would lose because at 1m40s, my code would stop due to hard limit execution. In order to compensate, I had to remove one of those capabilities and add an action that reduced the effectiveness of the code so that it would at least last the match.

It can be frustrating, but keep your head up. Find new ways to calculate and save execution steps and you’ll be golden.

P.S. I’ve only been on codecombat about 2 weeks, so don’t measure your limits based on time played.

5

Great tips. I’ve been in code combat since last wednesday. If I have more time today, I’d like to write a more complete post asking you about all your limits above. I’m a math teacher, and learnt coding / programming all by myself with no training what so ever, so sometimes your tips aren’t so clear to me.

I think I’ll go with “here an example, is this what you meant ? Or is there another way to do it better ?”

No more time now. Maybe during the day. Later !

6

Gladly! I welcome your post. There is also a private message ability for anything that shouldn’t be public discussion.

Awesome. I am actually self taught, since 1995. Truth is, once you learn two languages, you pretty much know them all. Programming isn’t about the language. The language is simply a tool for expressing logical processes, which is what programming is really about: finding new logical processes and combining them to solve a problem.

Understood. It is hard to recognize what a new coder knows or doesn’t. That is mostly because we all express our processes with different kinds of logic, based on varying backgrounds. For instance, the average math teacher will code in a manner that is similar to other math teachers, but different from many physics teachers. Even though both use similar logical tools, their awareness of priority changes the way that they code. It’s completely fascinating.

I would be glad to provide examples. Is there a way to do it better, however, will never give you the answer you want. Better is always subjective, unless you provide specific details about what you want and need. Most new coders don’t know these details yet. So, I would stick to asking for examples or clarifications on terms until you get more experience. Also, be aware, that for people like us to help you, we may require additional information from you. Provide as much as you can when you post, but be ready to add more if needed.

7

I also developed a complex algorithm to help me decide which coin to take, unfortunately I still can’t execute it due to the 1 million hard execution limit. I see that in your code, you limited your hero to a range of 15 units of distance, which in the game is pretty low. In my code I wrote a mathematical function inversely proportional between the distance and the centroid weight. By Centroid Weight I mean the sum of the coins in a given centroid. The further a centroid is from me, the more expensive it is to go there, which means that I’ll only walk a lot to change the “region” in which I’m collecting coins if and only if the weight of the centroid divided by the distance is greater than the current region plus a threshold.

8

You can also update your coin targeting once every 4 frames or if the coin has been collected or take other shortcuts like this–you’ll get almost 4 times as many statements to play with and little loss of efficiency, since the battlefield barely changes in each frame (0.125 seconds).

1 Like
9

Not exactly. I have a “low computation requiered” algorithm which points at good coins. Only when the coin is “good enough” (distance / value < 25), I use my heavy computation part where I check if this good coin isn’t making me going an overall wrong path. If it does, I rule this coin out.

I invite you to check the full code there, the line I’m refering too is marked with a // (3) in my code. That helped in pushing back the hard execution limit. However, my algorith is still far from being light.