Databases
StackOverflow2013
Postsdbo
POExtension to Pathfinding - Path of fewest turns
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POExtension to Pathfinding - Path of fewest turns
    primarykey
    data
    text
    <p>First I want to thank anyone for taking the time to look at this. Many of us are familiar with Dijkstra's algorithm, and thus A*. I have used A* in many applications, but for this particular case I am having a very tough time coming up with an algorithm. This case involves finding the path with the fewest number of turns. Indeed, I don't even care about the "shortest" path, only the one with the least turns!I am working with an up-down-left-right grid, no diagonals, which means there are many possible solutions for shortest path. For instance, in a 5x5 grid with the starter on the bottom left and ender on the top right, we could do a stair case or go the whole way to the right then all the way up (better for me!). </p> <p>With A* you use Cost = DistanceFromStart + Heuristic(Manhattan), and I have tried to extend it by adding a numTurns cost. This works perfectly until I get to a case such as the following:</p> <p>| 0 0 0 0 0 * 0 0</p> <p>| 0 0 1' 2' + 0 0 E</p> <p>| 0 0 S 1 2 * 0 0</p> <p>| 0 0 0 0 0 * 0 0</p> <p>| 0 0 0 0 0 * 0 0</p> <p>Please forgive the poor formatting, I hope you can see what I intended.</p> <p>*'s are walls, 0's are empty, S is start and E is end. You will find that the path S->1->2->+ will give the same cost as s->1'->2'->+. They both have one turn so far, same distance from S, and same manhattan. However from the +, if we took the prime (') route, we dont have to turn. But if we took the 1 2 route, we have to turn right (+1 cost). Thus, even though we may arrive there first with 1 2, it is not the path of least turns. </p> <p>I have tried adjustments such as letting multiple of the same square be in the priority queue at once such that they both get a chance (if their values are minimal in the heap). I have tried additional other "hacky" solutions, but I keep getting cases that arent covered. Does anyone know of an intuitive way to do this? Again, I'll pose the question the best I can:</p> <p>Given a grid with up-down-left-right movement and obstacles, how may I find the path of least turns from A to B. I do not need the guarantee of shortest distance. The application is a bot program for a game which connects tiles and the tiles can only be eliminated if they are less than 3 turns apart. Thanks again for anyone who can help!</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USuser2045279
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POExtension to Pathfinding - Path of fewest turns
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POExtension to Pathfinding - Path of fewest turns
      1. This table or related slice is empty.
      1. VTUpMod
    1. CODid you manage to find a solution? I'm facing the same problem and haven't find a proper solution yet.
      singulars
      1. POExtension to Pathfinding - Path of fewest turns
      1. USdimayak
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload