AI to avoid obstacle
up vote
3
down vote
favorite
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?
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>
javascript performance animation computational-geometry pathfinding
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.
add a comment |
up vote
3
down vote
favorite
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?
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>
javascript performance animation computational-geometry pathfinding
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
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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?
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>
javascript performance animation computational-geometry pathfinding
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?
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
javascript performance animation computational-geometry pathfinding
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
add a comment |
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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