I have a 2D grid with a number of cells. I need to find a path from one cell to another. There are no obstacles or opponents, and all cells are identical. What is a SUPER SIMPLE routine to calculate the shortest path? I have read about A* and other routines, but they are waaaaaaaay overkill in my case at this point. (Maybe I will need them later, in the future.) Thanks!
\$\begingroup\$
\$\endgroup\$
6
-
2\$\begingroup\$ If there's no obstacles or enemies to avoid, then wouldn't the shortest path simply be the straight line from you to your destination? Do you need help navigating along this line, or is there another complication that demands a different shape of path? \$\endgroup\$– DMGregory ♦Commented Aug 21, 2017 at 21:39
-
1\$\begingroup\$ The simplest algorithm is probably to calculate the vector between start and finish, then determine which of your valid directions it's closest to pointing towards. Then repeat until you're there. \$\endgroup\$– BlueRaja - Danny PflughoeftCommented Aug 21, 2017 at 22:02
-
2\$\begingroup\$ If you are locked to a grid, any path is going to touch the same number of cells, assuming you do not go in the opposite direction (if the destination is right of the start, never go left). Just going from corner to corner in a 3x3 grid would give 6 equally short paths. \$\endgroup\$– tyjkennCommented Aug 21, 2017 at 22:18
-
\$\begingroup\$ Those are all good suggestions. Are there examples of actual code somewhere? \$\endgroup\$– posfan12Commented Aug 22, 2017 at 0:21
-
\$\begingroup\$ Can your path include diagonals or only cardinal directions? \$\endgroup\$– DMGregory ♦Commented Aug 22, 2017 at 2:15
|
Show 1 more comment
1 Answer
\$\begingroup\$
\$\endgroup\$
If you are locked to a grid and can only move in the four cardinal directions with no obstacles, then this becomes similar to the lattice path problem on Project Euler. If we call the dimensions on this lattice x and y, then subtract the destination's x from the start's x to get the number of steps right that need to be taken (left if negative). Do the same with y to get the number of steps up or down. The steps can be taken in any order (left then up, up then left, etc.) Each order will give you a different path, but get you to the same place. The number of paths when the change in x is the same as the change in y corresponds to the middle column of Pascal's Triangle. In other words, a 2x2 grid has 2 paths, a 3x3 grid has 6 paths, a 4x4 grid has 20 paths, and so forth. All these paths have the same length.
This means pathfinding doesn't work like normal. Usually, you would expect a straight line to be shorter, but if you approximate a straight line by zigzagging, you don't save any time.
_| |
_| is just as long as |
_| _ _ _|
The easiest to implement would be the latter example. However, if you want the zigzag that approximates the line, you can find x/y. This is how many to move right for every cell you move up. For example, if x / y = 2, then move like this: right, right, up, right, right, up, .... If it is less than one, take the reciprocal, and move that much on y for every movement on x.
