Classic Algorithms - Danger! Minefield (Movement Problems)


#1

Hello,

First, I was not sure if I put this topic on Bugs, so I put here by default. Excuse me.

Second, I want to congratulate the whole team and community CodeCombat.com this project is improving, and it’s magnificent.

Right now I’m with classical algorithms, and in one of the levels: Danger! Minefield, I managed to remove composites mines, but when I tell the character to move to the position of each coin … takes a few steps, and never reaches the coins.

This is the original code:

/////////////////// 2. Collect Gold //////////////////////////////
// After all the composite mines are gone, the prime ones become duds,
// and Mace can just walk around and collect the coins.
this.say("Woohoo, safe! Lootin' time!");  // (do not remove)

this.move(coins[0].pos);

This is my code:

/////////////////// 2. Collect Gold //////////////////////////////
// After all the composite mines are gone, the prime ones become duds,
// and Mace can just walk around and collect the coins.
this.say("Woohoo, safe! Lootin' time!");
// (do not remove)

coins = this.getItems();

for (var c = 0; c < coins.length; c++){
        item = coins[c];
        this.move(item.pos);
}




Solution (short)

//..... code in JavaScript
this.say("Woohoo, safe! Lootin' time!");

coins = this.getItems();
numCoins = coins.length;

for (var c = numCoins; c > 0; c--) {
    item = coins[c-1];
    while (coins.length == c){
        this.move(item.pos);
        coins = this.getItems();
    }
}

Solution (long…probably due to the effects of Christmas)

I found an approximate solution for my knight to collect all the coins (after being only unexploded mines prime number). At first I wanted to edit the code level, but did not want to modify the existing code by a bug in a simple function “move ()”

Which one have you been my problems?

  1. With move(x, y), where (x, y) a distant position. The knight did
    not reach the position, just took a few steps and stopped.

  2. If the position (x, y) was far from the initial position of the
    knight, this could move to (x, y) using iteratively “move (x, y)”.
    But if the knight arrives at (x, y), and you use "move (x, y)"
    once again, the knight enters an infinite loop not stop walking
    (without moving)


To solve the first problem, I used a for-loop for the position of each coin. Then I calculated the distance (approximate) there from the initial position of the knight to the next position, and when they reached the target position, end position stored how the initial position for the next iteration.

The precise distance would be:

distance = [ ( x2 - x1 )^2 + ( y2 - y1 )^2 ] ^ ( 1/2 )

But because I did not have the “sqrt” function Math javascript library, had to do some approximation without the square root. For this I used: “Bakhshali approximation”, which allows an approach from the nearest square root of my problem (source: http://bit.ly/1JWCWt1). To my “aproxSqrt()” function, I put the variables the same name as the source.

But knowing the distance, I do not know how many steps have to give my knight. So happens that I come to consider another approach:

Whereas the knight begins at the starting position (18,20) and the first currency that has to catch this in the final position (40,50), the distance is 37.20. If we test several iterations until the final position, we can see that the gentleman made 12 necessary steps. So approx. would be:

37.20 / 12 ~= “3 steps / 1 distance

So, that to calculate the number of iterations (or steps) that our knight has to do, has to be the result of “aproxSqrt ()” function divided by 3.

But that does not solve the second problem, because when horizontal distances are realized, the knight always makes an extra step that causes the problem described in section 2. How are the steps he need to perform horizontally are always ten, fortunately, the solution simpler in this case is that when you have to make 10 just steps, subtract 1 step.

CODE

Here is the code:

function aproxSqrt (S){
	N = 0;
	while ((N*N) < S){
		N = N + 1;
	}
	d = S-N*N;
	P = d/(2*N);
	A = N + P;
	result = A - (P*P)/(2*A);
	return result;
}


// Here you would code for the mines that are not prime numbers.


this.say("Woohoo, safe! Lootin' time!");
x0 = 18;
y0 = 20;
coins = this.getItems();


for (var c = 0; c < coins.length; c++) {
    item = coins[c];
    if (item.pos.x > x0){
        x1 = (item.pos.x - x0);
    } else {
        x1 = (x0 - item.pos.x);
    }
    if (item.pos.y > y0){
        y1 = (item.pos.y - y0);
    } else {
        y1 = (y0 - item.pos.y);
    }
  
    
    total = (x1*x1)+ (y1*y1);
    
    total = aproxSqrt(total)/3;
    //this.say(total + " step");
    
    if (total == 10){
        total = 9;
    }
    
    for (var mult=0; mult <= total; mult++ ){
        this.move (item.pos);
    }
 
    x0 = item.pos.x;
    y0 = item.pos.y;
}

#2

Try moveXY instead of move (youll need to equip different boots). Move is very very buggy


#3

But the boots could only be equipped in Normal Campaign?

Currently the functions my character are: move (), getItems () and say ().

And when I start the level, don’t give me the option to choose the equipment of my character.

Thanks for replying


#4

Ohhhhh it’s one of the older levels. i see. in that case sorry, I’m not sure. =\


#5

Ah, I think I know what’s going on there. Try making your movement loop so that you call move to coins[0] until you get there, and then remove it from the coins list. move is now only going a little bit at a time when planning.


#6

Hi nick,

I was just testing a solution that has served me, but I think it is a bit long (I have written above) … I will try what you told me.

Thank You


#7

Wow, that’s a very detailed workaround for our unfortunate movement bug! (The difficult part of the level is supposed to be the prime sieve, not the coin pickup, but we changed the way move works for the new hero levels and it is messing up a couple of the older challenge levels.)


#8

I prefer to think of a problem (with appropriate methods) with a possible solution, becomes a challenge.

Another thing is that the solution is the optimal (how is not my case -.-). I just try what you told me and it works (now I feel idiot xD)