Avoid u-turns in A* algorithm
I have defined nodes and edges for a graph, which I want to use to resolve pathfinding using the A* algorithm. I have an A* algorithm that seems to work but I now need to prevent u-turns. These aren't 2 or more lanes roads, these are single direction only, although two nodes form two edges (one in either direction).
So, for example, if I want to calculate the route from 1114-1105, the algorithm gives me 1114-1112-1105. This is invalid as it involves a u-turn from 1112 to 1105. The result I want to achieve would be more like 1114-1110-1111-1113-1112-1105.
I naively thought I could calculate the angle between the previous, current and next nodes, which in this case would be 0 and then add a large number to the 'f' value. But this doesn't seem to do anything.
Any suggestions for how to implement this? Thanks
path-finding a-star
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
add a comment |
I have defined nodes and edges for a graph, which I want to use to resolve pathfinding using the A* algorithm. I have an A* algorithm that seems to work but I now need to prevent u-turns. These aren't 2 or more lanes roads, these are single direction only, although two nodes form two edges (one in either direction).
So, for example, if I want to calculate the route from 1114-1105, the algorithm gives me 1114-1112-1105. This is invalid as it involves a u-turn from 1112 to 1105. The result I want to achieve would be more like 1114-1110-1111-1113-1112-1105.
I naively thought I could calculate the angle between the previous, current and next nodes, which in this case would be 0 and then add a large number to the 'f' value. But this doesn't seem to do anything.
Any suggestions for how to implement this? Thanks
path-finding a-star
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
add a comment |
I have defined nodes and edges for a graph, which I want to use to resolve pathfinding using the A* algorithm. I have an A* algorithm that seems to work but I now need to prevent u-turns. These aren't 2 or more lanes roads, these are single direction only, although two nodes form two edges (one in either direction).
So, for example, if I want to calculate the route from 1114-1105, the algorithm gives me 1114-1112-1105. This is invalid as it involves a u-turn from 1112 to 1105. The result I want to achieve would be more like 1114-1110-1111-1113-1112-1105.
I naively thought I could calculate the angle between the previous, current and next nodes, which in this case would be 0 and then add a large number to the 'f' value. But this doesn't seem to do anything.
Any suggestions for how to implement this? Thanks
path-finding a-star
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
I have defined nodes and edges for a graph, which I want to use to resolve pathfinding using the A* algorithm. I have an A* algorithm that seems to work but I now need to prevent u-turns. These aren't 2 or more lanes roads, these are single direction only, although two nodes form two edges (one in either direction).
So, for example, if I want to calculate the route from 1114-1105, the algorithm gives me 1114-1112-1105. This is invalid as it involves a u-turn from 1112 to 1105. The result I want to achieve would be more like 1114-1110-1111-1113-1112-1105.
I naively thought I could calculate the angle between the previous, current and next nodes, which in this case would be 0 and then add a large number to the 'f' value. But this doesn't seem to do anything.
Any suggestions for how to implement this? Thanks
path-finding a-star
path-finding a-star
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
asked Nov 14 '18 at 19:19
Mike StoddartMike Stoddart
13412
13412
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Your "state" in the graph depends on two things:
- The node you're in
- The node you came from
To model this, we can create a new (directed) graph where each "state" is its own node. In other words, you create a new graph by splitting each node in your old graph in N nodes in the new graph (where N is the number of incoming edges to that old-node). The new-node will then have fewer outgoing edges.
This may split your start/end nodes into multiple nodes. To fix this, you can create new single start/end nodes, and connect them to the old start/end nodes with 0-cost edges.
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
add a comment |
Your Answer
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: "1"
};
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
});
}
});
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%2fstackoverflow.com%2fquestions%2f53307361%2favoid-u-turns-in-a-algorithm%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
Your "state" in the graph depends on two things:
- The node you're in
- The node you came from
To model this, we can create a new (directed) graph where each "state" is its own node. In other words, you create a new graph by splitting each node in your old graph in N nodes in the new graph (where N is the number of incoming edges to that old-node). The new-node will then have fewer outgoing edges.
This may split your start/end nodes into multiple nodes. To fix this, you can create new single start/end nodes, and connect them to the old start/end nodes with 0-cost edges.
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
add a comment |
Your "state" in the graph depends on two things:
- The node you're in
- The node you came from
To model this, we can create a new (directed) graph where each "state" is its own node. In other words, you create a new graph by splitting each node in your old graph in N nodes in the new graph (where N is the number of incoming edges to that old-node). The new-node will then have fewer outgoing edges.
This may split your start/end nodes into multiple nodes. To fix this, you can create new single start/end nodes, and connect them to the old start/end nodes with 0-cost edges.
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
add a comment |
Your "state" in the graph depends on two things:
- The node you're in
- The node you came from
To model this, we can create a new (directed) graph where each "state" is its own node. In other words, you create a new graph by splitting each node in your old graph in N nodes in the new graph (where N is the number of incoming edges to that old-node). The new-node will then have fewer outgoing edges.
This may split your start/end nodes into multiple nodes. To fix this, you can create new single start/end nodes, and connect them to the old start/end nodes with 0-cost edges.
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
Your "state" in the graph depends on two things:
- The node you're in
- The node you came from
To model this, we can create a new (directed) graph where each "state" is its own node. In other words, you create a new graph by splitting each node in your old graph in N nodes in the new graph (where N is the number of incoming edges to that old-node). The new-node will then have fewer outgoing edges.
This may split your start/end nodes into multiple nodes. To fix this, you can create new single start/end nodes, and connect them to the old start/end nodes with 0-cost edges.
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
edited Nov 14 '18 at 20:55
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
answered Nov 14 '18 at 19:26
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
58.4k21153241
58.4k21153241
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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%2fstackoverflow.com%2fquestions%2f53307361%2favoid-u-turns-in-a-algorithm%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
