Shortest Path Algorithm

Go To Last Post
6 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Suppose I have something like an analogue clock with just a single hand driven by a 12-position stepper motor. Let's also suppose that at any instance I know where the hand is.

What I want is an algorithm that I call with the current position (0-11), the new position (0-11) and a flag. What I want it to return is the number of steps to move and the direction (indicated by the sign, +ve = CW, -ve = CCW) based on taking either the shortest or longest route (determined by the flag parameter) from the current to the new position.

int8_t steps_to_take(uint8_t old, uint8_t new, uint8_t shortest)

I have some code to do this but it relies on multiple if-then-else statements nested 3 deep to determine all the various outcomes.

It feels like there ought to be a really elegant solution to this but after many hours I'm not seeing it.

Anyone up for the challenge?

#1 This forum helps those that help themselves

#2 All grounds are not created equal

#3 How have you proved that your chip is running at xxMHz?

#4 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand." - Heater's ex-boss

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I just did a little sketch on paper. I replaced your "0" with "12" in fact as it looks more natural.

If you start with the midnight case then clearly 1-5 are counter-clock-wise and 7-11 are clock-wise. There's then the question of 6. Which way do you go? Let's say it is clock-wise too. Similarly then for 3 it would be the case that 4-8 are CCW and 9-12 and 1-2 are CW.

In general it appears that you go CCW when N+1 to N+5 and CW when N-6 to N-1 with all being done % 12.

As an example put 5 into that. 5+1 is 6 and 5+5 is 10. So you go CCW for 6 to 10. Now N-6 is -1. That's tricky, it's negative. So add 12 to it. That gets you 11. N-1 is 5-1 which is 4. So from 11 round to 4 you go CCW.

How about trying 8. 8+1 is 9 and 8+5 is 13. Again it's tricky - it's more than 12 so subtract 12. That gives you 1. So from 9 round to 1 you go CCW. N-1 is 7 abd N-6 is 2. So form 2 to 7 you go CW.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you add the absolute values of the longest and shortes path, it sums to 12... once you know the shortest path, the 'longest' , which has the opposite sign , is easy to know.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Wow. I made one of these in the early 80s. Only we had 8 "bins" not 12.

I just put a table that looked like:

0b00000001
0b00000011
0b00000111
0b00001111
0b00011111
0b00111111
0b01111111
0b11111111

And did a simple lookup. "I'm at position 4 and want to go to position 7, so the 7th bit of the 4th byte is 0."

This replaced pages and pages of tangled 8080 Assembler code that took weeks to get right with an 8 byte table and about 10 lines of code.

You'll need words, not bytes, and 12 of them, not 8.

The largest known prime number: 282589933-1

It's easy to stop breaking the 10th commandment! Break the 8th instead. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
dist = dest - source;
if (dist > 6) // if more than half a turn CW
{
   dist = dist - 12; // reverse direction
}
else if (dist < -6) // if more than half a turn CCW
{
   dist = dist + 12; // reverse direction
}
// we now have shortest
if (!shortest) // if we want longest, reverse the direction
{
   if (dist > 0)
   {
      dist = dist - 12;
   }
   else
   {
      dist = dist + 12;
   }
}

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A needle that doesnt drive thru zero is what I call 'speedometer mode': If the demand is greater than the position, step cw. A 'compass card' that can rotate continuously might want to go from 11 oclock to 1 oclock thru 12oclock.... 'shortest distance' mode, which Kartman has given the algo and example code for.

Imagecraft compiler user