5
\$\begingroup\$

The AI I'm making is really simple, however it might be a bit too inefficient for what it is doing. The chart below shows speed differences between various arithmetic and math operations. sin, cos and especially atan are really inefficient. It's tested in C++ but should still hold true to JavaScript.

Is it possible to achieve the same result with more efficient math?

Math efficiency Chart Source

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

let targetX = 50;
let targetY = 50;

let obstacleX = 150;
let obstacleY = 50;

let aiX = 250;
let aiY = 51;

function loop() {
    // Distance between the vector points
    let disTargetX = targetX - aiX;
    let disTargetY = targetY - aiY;
    
    let disObstacleX = obstacleX - aiX;
    let disObstacleY = obstacleY - aiY;

    // Moves to target by default
    const angleTarget = Math.atan2(disTargetY, disTargetX);
    let moveAngle = angleTarget;

    // If near obstacle, adjust course and try to avoid it
    if (Math.sqrt(disObstacleX * disObstacleX + disObstacleY * disObstacleY) < 60) {
        const angleObstacle = Math.atan2(disObstacleY, disObstacleX);
        moveAngle += angleTarget - angleObstacle;
    }

    // Move the vector to desired location
    aiX += Math.cos(moveAngle);
    aiY += Math.sin(moveAngle);

    //Drawing
    ctx.clearRect(0, 0, 600, 200);

    ctx.beginPath();
    ctx.fillStyle = "teal";
    ctx.arc(aiX, aiY, 10, 0, Math.PI * 2, true);
    ctx.fill();

    ctx.beginPath();
    ctx.fillStyle = "purple";
    ctx.arc(obstacleX, obstacleY, 10, 0, Math.PI * 2, true);
    ctx.fill();
    
    ctx.rect(targetX - 20, targetY - 20,40,40);
    ctx.stroke();

    requestAnimationFrame(loop);
}

requestAnimationFrame(loop);
<canvas id="canvas" width="600" height="200"></canvas>

\$\endgroup\$
  • 2
    \$\begingroup\$ If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared. \$\endgroup\$ – superlaks Nov 6 '18 at 7:40
  • 1
    \$\begingroup\$ @superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers. \$\endgroup\$ – 200_success Nov 6 '18 at 15:31
  • \$\begingroup\$ @superlaks can I use cartesian for movement too? \$\endgroup\$ – Will Pierce Nov 9 '18 at 2:17
2
\$\begingroup\$

You are probably aware of this but representing floating point numbers in JavaScript is difficult to do without rounding errors

Are you sure you the math is correct in the calculations? Specifically, when subtracting angleObstacle from moveAngle, should angleTarget really be added? I attempted to change it such that angleTarget does not get added when that happens. It appears to allow the green circle to avoid colliding with the obstacle circle. I am not sure why the speed changes... perhaps because of the exponential change with the arc tan or other sin functions.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

const targetX = 50;
const targetY = 50;

const obstacleX = 150;
const obstacleY = 50;

let aiX = 250;
let aiY = 51;

function loop() {
    // Distance between the vector points
    const disTargetX = targetX - aiX;
    const disTargetY = targetY - aiY;
    
    const disObstacleX = obstacleX - aiX;
    const disObstacleY = obstacleY - aiY;

    // Moves to target by default
    const angleTarget = Math.atan2(disTargetY, disTargetX);
    let moveAngle = angleTarget;

    // If near obstacle, adjust course and try to avoid it
    if (Math.sqrt(disObstacleX * disObstacleX + disObstacleY * disObstacleY) < 60) {
        const angleObstacle = Math.atan2(disObstacleY, disObstacleX);
        moveAngle += /*angleTarget -*/angleObstacle;
    }

    // Move the vector to desired location
    aiX += Math.cos(moveAngle);
    aiY += Math.sin(moveAngle);

    //Drawing
    ctx.clearRect(0, 0, 600, 200);

    ctx.beginPath();
    ctx.fillStyle = "teal";
    ctx.arc(aiX, aiY, 10, 0, Math.PI * 2, true);
    ctx.fill();

    ctx.beginPath();
    ctx.fillStyle = "purple";
    ctx.arc(obstacleX, obstacleY, 10, 0, Math.PI * 2, true);
    ctx.fill();
    
    ctx.rect(targetX - 20, targetY - 20,40,40);
    ctx.stroke();
    
    if (aiX > 50) {
        requestAnimationFrame(loop);
    }
}

requestAnimationFrame(loop);
<canvas id="canvas" width="600" height="200"></canvas>

Other review points

In the code snippet above, you will notice that let has been replaced with const for many of the declarations of variables that are not re-assigned within the function - e.g. targetX, targetY, obstacleX, obstacleY, disTargetX, disTargetY . This avoids any unintentional re-assignment.

Also, the original code loops forever. I added a condition in the snippet above - i.e. aiX > 50 which needs to be true in order for the function to be called again (via requestAnimationFrame). This avoids unnecessary processing.

\$\endgroup\$
  • \$\begingroup\$ Appreciate the answer and the corrections you mentioned. I'm pretty sure my math is correct but the code is very inefficient when I applied the same AI to more bots. I did do what superlaks suggested in a comment and used distance squared instead of the square root operation. That only helped a little bit so I believe that the atan2 operations are the performance hogs in my AI logic. \$\endgroup\$ – Will Pierce Jan 17 at 17:36
1
\$\begingroup\$

AFAIK, trigonometric functions are pretty much unavoidable in (non-graph-based) dynamic movement. Depending on what you're trying to accomplish, grid- or graph-based movement might be an option, though graph traversal and pathfinding can be its own can of worms.

A simpler solution might be to just precalculate the sine/cosine/arctangent of a few hundred values and store them in a TypedArray where you can look them up directly. Since you're not doing scientific calculations, this might very well be enough. You'll probably want to run some benchmarks to compare the two solutions, though.

\$\endgroup\$
  • \$\begingroup\$ I tried what you mentioned and an approximation of sin, cos and atan2... problems became apparent when AI went off course. It apparently needs a high precision to navigate properly. The other guy in this thread showed me how to do it with hypotenuse but AI's movement is lowered. Do you happen to know how this can be implemented without the fancy 2D library? stackoverflow.com/a/36134706/1426486 \$\endgroup\$ – Will Pierce Nov 10 '18 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.