Slither.io-bot: New food clustering algorithm is laggy

Created on 10 May 2016 · 26Comments · Source: ErmiyaEskandary/Slither.io-bot

I do not understand why it was necessary to change the previous algorithm, if he has never been the cause of lags. Collision detection algorithm is main reason of lags.

Now this algorithm introduce new lag, when foods.length > 300 (e.g. dead big snake). Also food selection code become more complicated and unclear.

The reason of total rewriting is not clear for me.

Source

ksofiyuk

👍1

Most helpful comment

And even more.
Lets try to see averaged time:

global vars:

    window.ksofiyuk_sum_time = 0;
    window.chancity_sum_time = 0;
    window.iters = 0;

thinkAboutGoals:

                    window.ksofiyuk_sum_time += time_ksofiyuk;
                    window.chancity_sum_time += time_chancity;
                    window.iters += 1;

                    console.log(window.iters, window.ksofiyuk_sum_time / window.iters,
                        window.chancity_sum_time / window.iters);

Output:
num_iters ksofiyuk_avg_time chancity_avg_time
1 3 10
2 2 7.5
3 2 5.333333333333333
4 1.75 4.25
5 1.8 6.6
6 1.6666666666666667 5.666666666666667
7 1.5714285714285714 5.142857142857143
8 1.625 4.875
9 1.5555555555555556 4.444444444444445
10 1.6 4.7
...

166 4.481927710843373 11.55421686746988
167 4.485029940119761 11.55688622754491
168 4.482142857142857 11.505952380952381
169 4.491124260355029 11.455621301775148
170 4.4941176470588236 11.423529411764706
171 4.485380116959064 11.380116959064328
172 4.476744186046512 11.331395348837209
173 4.497109826589595 11.364161849710984
174 4.488505747126437 11.316091954022989

@chancity implemented algorithm that is more than two times slower in average than my algorithm.
Is it optimization? :)

114

ksofiyuk on 10 May 2016

👍2

All 26 comments

I am eager to test :+1:
Very please create code ;)

Seple on 10 May 2016

I agree with you ksofiyuk

llennac on 10 May 2016

@Seple Implement algorithm switching for comparision. #124

ksofiyuk on 10 May 2016

👍1

thank you :)

Seple on 10 May 2016

What's with the title then if the lag is due to enemy avoidance ?

ErmiyaEskandary on 10 May 2016

What's with the title then if the lag is due to enemy avoidance ?

Algorithm lag when foods.length > 300, e.g. big dead snake

ksofiyuk on 10 May 2016

I made a fair comparison:

                var start1 = new Date().getTime();
                bot.computeFoodGoal();
                var end1 = new Date().getTime();
                var time_ksofiyuk = end1 - start1;

                var start2 = new Date().getTime();
                var foodClusters = bot.getFood().map(bot.foodClusters);
                window.sortedFood = foodClusters.sort(bot.sortFoodClusters);
                var end2 = new Date().getTime();
                var time_chancity = end2 - start2;

                console.log(foods.length, time_ksofiyuk, time_chancity);

Output:
food.length time_ksofiyuk time_chancity
78 18 41
89 29 16
92 4 32
93 24 3
93 6 22
93 26 4
93 31 2
102 4 26
102 28 3
102 21 2
102 5 14
102 4 4
102 20 21
102 6 37
102 25 2
102 4 44
102 4 4
102 3 3
102 5 5
102 2 3
102 5 3
102 5 5
102 5 3
102 2 2
102 3 2
102 5 13
102 25 3
102 3 2
102 3 8
102 5 5
102 5 3
102 5 11
102 5 26
102 4 14
102 4 2
102 4 3
102 3 5
102 4 14
102 2 4
102 6 5
102 3 4
102 5 21
102 4 7
102 3 6
102 7 13
102 3 7
104 5 8
106 7 5
110 4 6
2110 3 3
128 7 17
128 6 4
128 7 6
128 4 5
128 5 4
134 4 14
135 5 11
138 3 11
138 7 4
138 8 7
138 8 3
138 3 5
138 5 15
139 7 7
139 9 8
139 4 7
139 8 6
139 3 5
139 3 17
139 7 15
139 3 8
139 6 11
139 5 4
139 3 3
139 6 5
139 3 3
139 5 17
139 7 18
139 5 19

ksofiyuk on 10 May 2016

👍2

And even more.
Lets try to see averaged time:

global vars:

    window.ksofiyuk_sum_time = 0;
    window.chancity_sum_time = 0;
    window.iters = 0;

thinkAboutGoals:

                    window.ksofiyuk_sum_time += time_ksofiyuk;
                    window.chancity_sum_time += time_chancity;
                    window.iters += 1;

                    console.log(window.iters, window.ksofiyuk_sum_time / window.iters,
                        window.chancity_sum_time / window.iters);

@chancity implemented algorithm that is more than two times slower in average than my algorithm.
Is it optimization? :)

114

ksofiyuk on 10 May 2016

👍2

I'm getting different results, what browser are you using? When i switch between your algorithm and mine there is noticeable lag while using yours.

I've modified my code alittle after it was merged.

foodClusters: function(food) {
            if (!food.clustered) {
                food.clusterScore = 0;
                food.clusterxx = food.xx;
                food.clusteryy = food.yy;

                var clusterSumX = 0;
                var clusterSumY = 0;

                for (var i = window.foods.length;0 < i;i--) {
                    nearFood = window.foods[i];
                    if (nearFood == null) continue;
                    if (nearFood.id !== food.id && !nearFood.clustered) {
                        foodDistance = canvas.getDistance(food.xx, food.yy, nearFood.xx, nearFood.yy);

                        if (foodDistance <= window.getSnakeWidth() * 5) {
                            food.clusterScore += nearFood.sz;
                            clusterSumX += nearFood.xx * nearFood.sz;
                            clusterSumY += nearFood.yy * nearFood.sz;
                            nearFood.clusterxx = nearFood.xx;
                            nearFood.clusteryy = nearFood.yy;
                            nearFood.clusterScore = nearFood.sz;
                            nearFood.clustered = true;
                        }
                    }
                }

                if (clusterSumX > 0) {
                    food.clusterxx = clusterSumX / food.clusterScore;
                    food.clusteryy = clusterSumY / food.clusterScore;
                }
            }

            food.clustered = true;
            return food;
        },

chancity on 11 May 2016

Output:
num_iters ksofiyuk_avg_time chancity_avg_time
1 11 1
2 17 6.5
3 18.333333333333332 6.666666666666667
4 19 5.5
5 21 4.6
6 21 4
7 21 3.5714285714285716
8 21.125 3.25
9 23 3
10 24.7 2.9
11 26.181818181818183 2.8181818181818183
12 27.916666666666668 2.75
13 28.846153846153847 3.230769230769231
14 30.428571428571427 3.2142857142857144
15 31 3.066666666666667
16 31.5 3
17 32.705882352941174 2.9411764705882355
18 33.166666666666664 2.8333333333333335
19 32.63157894736842 2.789473684210526
20 33.3 2.75
21 33.61904761904762 2.761904761904762
22 34.22727272727273 2.727272727272727
23 33.56521739130435 2.652173913043478
24 33 2.5833333333333335
25 32.44 2.52
26 31.884615384615383 2.4615384615384617
27 31.11111111111111 2.4074074074074074
28 30.5 2.357142857142857
29 29.93103448275862 2.310344827586207
30 29.4 2.2666666666666666
31 28.93548387096774 2.225806451612903
32 28.71875 2.1875
33 28.484848484848484 2.1515151515151514
34 28.794117647058822 2.1470588235294117
35 29.085714285714285 2.1142857142857143
36 29.055555555555557 2.0833333333333335
37 29 2.054054054054054
38 28.973684210526315 2.026315789473684
39 28.897435897435898 2.0256410256410255
40 29.1 2.025
41 29.29268292682927 2.024390243902439
42 30.142857142857142 2.0476190476190474
43 33.86046511627907 2.116279069767442
44 37.27272727272727 2.1818181818181817
45 40.733333333333334 2.2444444444444445
46 43.34782608695652 2.347826086956522
47 45.93617021276596 2.4468085106382977
48 48.25 2.5208333333333335
49 50.51020408163265 2.5918367346938775
50 53.14 2.64
51 56.333333333333336 2.6862745098039214
52 59.59615384615385 2.75
53 62.81132075471698 2.7735849056603774
54 64.81481481481481 2.7962962962962963
55 66.61818181818182 2.8181818181818183
56 68.53571428571429 2.857142857142857
57 71.29824561403508 2.9298245614035086
58 72.37931034482759 2.9482758620689653
59 73.27118644067797 2.9661016949152543
60 74.3 2.966666666666667
61 75.04918032786885 3.19672131147541
62 75.46774193548387 3.193548387096774
63 75.6984126984127 3.1904761904761907
64 76.171875 3.203125
65 76.58461538461539 3.2
66 77.6969696969697 3.212121212121212
67 78.38805970149254 3.2238805970149254
68 78.8970588235294 3.2205882352941178
69 79.42028985507247 3.217391304347826
70 79.5 3.2142857142857144
71 79.56338028169014 3.211267605633803
72 79.36111111111111 3.2083333333333335
73 79.31506849315069 3.2054794520547945
74 79.10810810810811 3.189189189189189
75 78.85333333333334 3.1733333333333333
76 78.59210526315789 3.1578947368421053

chancity on 11 May 2016

So from my results the computeFood algorithm is 26x slower than foodClusters. I'm using Chrome.

chancity on 11 May 2016

👍1

It's very strange. Can someone else test it?
I'm using Chrome 50.0.2661.94 (64-bit) with Xubuntu 15.04 x64.

ksofiyuk on 11 May 2016

I measured the iteration time inside block if (bot.tickCounter > 15) { ... }
And above if (bot.foodClusteringMode == 1) {

If you measure time after if (bot.foodClusteringMode == 1) { than it is not correct.

        thinkAboutGoals: function() {
            // If no enemies or obstacles, go after what you are going after
            var speedingMultiplier = (window.snake.sp > 10) ? 1.5 : 1.0;
            var headCircle = canvas.collisionScreenToCanvas({
                x: window.getX(),
                y: window.getY(),
                radius: window.getSnakeWidth() * (window.collisionRadiusMultiplier * speedingMultiplier)
            });

            bot.collisionPoints = bot.getCollisionPoints();
            // If no enemies or obstacles, go after what you are going after
            if (!bot.checkCollision(headCircle)) {

                // Save CPU by only calculating every Nth frame

                bot.tickCounter++;
                if (bot.tickCounter > 15) {
                    bot.tickCounter = 0;

                    var start1 = new Date().getTime();
                    bot.computeFoodGoal();
                    var end1 = new Date().getTime();
                    var time_ksofiyuk = end1 - start1;

                    var start2 = new Date().getTime();
                    var foodClusters = bot.getFood().map(bot.foodClusters);
                    window.sortedFood = foodClusters.sort(bot.sortFoodClusters);
                    var end2 = new Date().getTime();
                    var time_chancity = end2 - start2;

                    window.ksofiyuk_sum_time += time_ksofiyuk;
                    window.chancity_sum_time += time_chancity;
                    window.iters += 1;

                    console.log(window.iters, window.ksofiyuk_sum_time / window.iters,
                        window.chancity_sum_time / window.iters);

                    var accelerationClusterSize = 120;
                    if (bot.foodClusteringMode == 1) {
                        bot.computeFoodGoal();
                        accelerationClusterSize = 120;
                    } else {
                        var foodClusters = bot.getFood().map(bot.foodClusters);
                        window.sortedFood = foodClusters.sort(bot.sortFoodClusters);
                        window.currentFood = window.sortedFood[0];
                        window.currentFoodX = window.currentFood.clusterxx;
                        window.currentFoodY = window.currentFood.clusteryy;
                        window.currentFoodScore = window.currentFood.clusterScore;
                        accelerationClusterSize = 70;
                    }


                    var coordinatesOfClosestFood = canvas.mapToMouse(window.currentFoodX, window.currentFoodY);
                    window.goalCoordinates = coordinatesOfClosestFood;
                    // Sprint
                    //use speed to go to larger clusters
                    setAcceleration((window.currentFoodScore >= accelerationClusterSize) ? 1 : 0);

                    // Check for preys, enough "length", dont go after prey if current cluster is large
                    if (window.preys.length > 0 && window.huntPrey && window.currentFoodScore < 100) {
                        // Sort preys based on their distance relative to player's snake
                        window.sortedPrey = bot.getSortedPrey();
                        // Current prey
                        window.currentPrey = window.sortedPrey[0];
                        // Convert coordinates of the closest prey using mapToMouse
                        var coordinatesOfClosestPrey = canvas.mapToMouse(window.currentPrey.xx, window.currentPrey.yy);
                        // Check for the distance
                        if (window.currentPrey.distance <= Math.pow(window.getSnakeLength(), 2) / 2) {
                            // Set the mouse coordinates to the coordinates of the closest prey
                            window.goalCoordinates = coordinatesOfClosestPrey;
                            // "Sprint" enabled
                            window.setAcceleration(1);
                        }
                    }
                    window.kd_l = false;
                    window.kd_r = false;
                    canvas.setMouseCoordinates(window.goalCoordinates[0], window.goalCoordinates[1]);
                }
            }
        }

ksofiyuk on 11 May 2016

I don't remember where I placed it, I'll check again in the morning. My fps decreased when I switched to computeFoodGoals I know that for sure.

chancity on 11 May 2016

my results with the code you posted...I'm using Windows 10, Chrome Version 50.0.2661.94 m.

1 17 21
2 16.5 14
3 20.333333333333332 10
4 19.5 7.75
5 20.2 6.4
6 21.833333333333332 5.666666666666667
7 21.428571428571427 6
8 21.625 5.375
9 22 5.111111111111111
10 22.4 5.9
11 22.181818181818183 5.818181818181818
12 22.333333333333332 5.416666666666667
13 22.692307692307693 5.615384615384615
14 23.714285714285715 5.285714285714286
15 24.4 5.066666666666666
16 25 4.875
17 25.470588235294116 4.647058823529412
18 24.444444444444443 4.833333333333333
19 23.526315789473685 4.631578947368421
20 22.7 4.4
21 22.571428571428573 4.238095238095238
22 21.818181818181817 4.090909090909091
23 21.347826086956523 4.217391304347826
24 20.916666666666668 4.083333333333333
25 20.52 3.96
26 20.115384615384617 3.8461538461538463
27 19.74074074074074 3.740740740740741
28 19.714285714285715 3.7142857142857144
29 19.655172413793103 3.6551724137931036
30 19.633333333333333 3.566666666666667
31 20 3.4838709677419355
32 19.75 3.40625
33 19.515151515151516 3.3333333333333335
34 19.470588235294116 3.2941176470588234
35 19.457142857142856 3.2285714285714286
36 19.36111111111111 3.1666666666666665
37 19.10810810810811 3.108108108108108
38 18.86842105263158 3.026315789473684
39 18.641025641025642 3.076923076923077
40 18.425 3.025
41 18.195121951219512 2.975609756097561
42 17.976190476190474 2.9285714285714284
43 17.790697674418606 2.86046511627907
44 17.727272727272727 2.840909090909091
45 17.8 2.8
46 17.869565217391305 2.760869565217391
47 17.97872340425532 2.723404255319149
48 18.020833333333332 2.6875
49 18.06122448979592 2.673469387755102
50 18.12 2.64
51 18.15686274509804 2.627450980392157
52 18.28846153846154 2.6153846153846154
53 18.358490566037737 2.6037735849056602
54 18.425925925925927 2.5925925925925926
55 18.472727272727273 2.5636363636363635
56 18.5 2.5357142857142856
57 18.56140350877193 2.526315789473684
58 18.603448275862068 2.5172413793103448
59 18.661016949152543 2.5084745762711864
60 18.716666666666665 2.4833333333333334
61 18.80327868852459 2.459016393442623
62 18.822580645161292 2.4516129032258065
63 18.841269841269842 2.4285714285714284
64 18.875 2.421875
65 18.923076923076923 2.4
66 18.939393939393938 2.393939393939394
67 18.955223880597014 2.388059701492537
68 18.985294117647058 2.3970588235294117
69 19 2.3768115942028984

chancity on 11 May 2016

So which algorithm is better ?

ErmiyaEskandary on 12 May 2016

So which algorithm is better ?

The results are contradictory.

ksofiyuk on 12 May 2016

So we need someone else (me?) To check and confirm or ... ?

ErmiyaEskandary on 12 May 2016

small snake better code - chancity
vs.
a large snake better code - ksofiyuk
...a difficult choice :(
@ErmiyaEskandary - check on your own or wait

Seple on 12 May 2016

combine the two!

chancity on 12 May 2016

Fixed by pull #143?

Or does that simply use one of these two options?

ChadSki on 13 May 2016

simply use one of these two options

Think it's that...

ErmiyaEskandary on 13 May 2016

combine the two!

maybe test how big the snake is then make
small snake use chancity code and large snake uses ksofiyuk code?

ghost on 15 May 2016

@ksofiyuk is your algorithm currently being used ? If no, please make a new PR with your algorithm so we can test.

ErmiyaEskandary on 15 May 2016

Yeah it's being used.

On Sunday, May 15, 2016, Ermiya Eskandary [email protected] wrote:

@ksofiyuk https://github.com/ksofiyuk is your algorithm currently being
used ? If no, please make a new PR with your algorithm so we can test.

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
https://github.com/ErmiyaEskandary/Slither.io-bot/issues/122#issuecomment-219308939