AI to avoid obstacle











up vote
3
down vote

favorite
1












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>












share|improve this question
















bumped to the homepage by Community 13 mins ago


This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.











  • 1




    If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared.
    – superlaks
    Nov 6 at 7:40










  • @superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers.
    – 200_success
    Nov 6 at 15:31










  • @superlaks can I use cartesian for movement too?
    – Will Pierce
    Nov 9 at 2:17















up vote
3
down vote

favorite
1












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>












share|improve this question
















bumped to the homepage by Community 13 mins ago


This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.











  • 1




    If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared.
    – superlaks
    Nov 6 at 7:40










  • @superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers.
    – 200_success
    Nov 6 at 15:31










  • @superlaks can I use cartesian for movement too?
    – Will Pierce
    Nov 9 at 2:17













up vote
3
down vote

favorite
1









up vote
3
down vote

favorite
1






1





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>












share|improve this question















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>








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>





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>






javascript performance animation computational-geometry pathfinding






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 6 at 15:30









200_success

127k15149412




127k15149412










asked Nov 6 at 7:32









Will Pierce

363




363





bumped to the homepage by Community 13 mins ago


This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.







bumped to the homepage by Community 13 mins ago


This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.










  • 1




    If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared.
    – superlaks
    Nov 6 at 7:40










  • @superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers.
    – 200_success
    Nov 6 at 15:31










  • @superlaks can I use cartesian for movement too?
    – Will Pierce
    Nov 9 at 2:17














  • 1




    If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared.
    – superlaks
    Nov 6 at 7:40










  • @superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers.
    – 200_success
    Nov 6 at 15:31










  • @superlaks can I use cartesian for movement too?
    – Will Pierce
    Nov 9 at 2:17








1




1




If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared.
– superlaks
Nov 6 at 7:40




If you don't need the actual Euclidean distance, you can leave the Math.sqrt out and just do distance squared.
– superlaks
Nov 6 at 7:40












@superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers.
– 200_success
Nov 6 at 15:31




@superlaks Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements, even simple ones, in answers.
– 200_success
Nov 6 at 15:31












@superlaks can I use cartesian for movement too?
– Will Pierce
Nov 9 at 2:17




@superlaks can I use cartesian for movement too?
– Will Pierce
Nov 9 at 2:17










1 Answer
1






active

oldest

votes

















up vote
0
down vote













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.






share|improve this answer





















  • 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
    – Will Pierce
    Nov 10 at 7:24











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207037%2fai-to-avoid-obstacle%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
0
down vote













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.






share|improve this answer





















  • 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
    – Will Pierce
    Nov 10 at 7:24















up vote
0
down vote













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.






share|improve this answer





















  • 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
    – Will Pierce
    Nov 10 at 7:24













up vote
0
down vote










up vote
0
down vote









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.






share|improve this answer












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.







share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 8 at 10:48









Máté Safranka

49618




49618












  • 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
    – Will Pierce
    Nov 10 at 7:24


















  • 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
    – Will Pierce
    Nov 10 at 7:24
















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
– Will Pierce
Nov 10 at 7:24




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
– Will Pierce
Nov 10 at 7:24


















draft saved

draft discarded




















































Thanks for contributing an answer to Code Review Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207037%2fai-to-avoid-obstacle%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Costa Masnaga

Fotorealismo

Sidney Franklin