LoginLogin

Algorithm for rectilinear spiral motion

Root / Programming Questions / [.]

MZ952Created:
Can't wrap my head around this one. I'm trying to get an algorithm to read/write from/on a set of data in a spiraling, rectilinear manner. Not complicated, really. Let me picture it for you:
'Consider a 3x3 gridspace:
'000
'000
'000

'Begin algorithm in center
'000
'010
'000

'Algorithm proceeds in spiral fashion
'010
'010
'000
'...
'011
'010
'000
'...
'011
'011
'000
'...
'011
'011
'001
'...
'011
'011
'011
'...
'011
'011
'111
'...
'etc.
Now, when the 3x3 gridspace becomes filled, the algorithm may be pressed to continue, building upon itself with layers. I'm trying to get something like this that can continue building for n-steps. What's the best way to do this? The algorithm isn't allowed to check gridspace for its position or the states of other elements surrounding it. It's basically a snail that wants to run around in circles for n-number of paces and not touch its trail, but it can't detect its trail and its blind. However, it can remember how many paces it traveled and has a basic grasp of mathematics and SB.

Does it matter where the start of each "circle" is?

Each "circle" starts one unit above where the last one ended, though, if it's any simpler starting somewhere else, it's not too big a deal

HALF = SIZE DIV 2
PRINT HALF, HALF
FOR J=1 TO HALF
 FOR I=-(J-1) TO J
  PRINT HALF+I,HALF-J
 NEXT
 FOR I=-(J-1) TO J
  PRINT HALF+J,HALF+I
 NEXT
 FOR I=J-1 TO -J STEP -1
  PRINT HALF+I,HALF+J
 NEXT
 FOR I=-J-1 TO -J STEP -1
  PRINT HALF-J,HALF+I
 NEXT
NEXT

I may not have described this well enough, so I drew a picture hopefully explaining this a little better than the text example from earlier. Each unit square represents a "step," and the algorithm is due to run only a given number of steps in the clockwise spiraling direction I tried to outline there^ Each move is counted as a step, including the start at the origin. It starts at the origin and moves up one step where it then continues to the right, down, left, up, turning clockwise about itself. When it can no longer turn about itself without reaching its starting position, it moves up one unit and proceeds. It proceeds for as many steps as it is given, ceasing anywhere it runs out of available steps.

Hi, I think that your problem can be modeled with a Finite State Machine. You may want to read up on them (https://en.wikipedia.org/wiki/Finite_state_machine). Finite State Machines are used frequently in game development. In fact I think that Unity has a finite state machine editor they are so common. They are often used for enemy AI. A super simple one might be something like a traffic light that transitions from green to yellow to red and back to green again. In this case it sounds like you have a state machine that travels around in a square of size 2n + 1 where n is an integer >= 0 and where n increases by one for every lap completed. In the example below I made a state machine that travels up then right then down then left (then up again). The tricky part is the up to right transition actually goes one step further than the rest and increases the "ring" size by one. Please give it a look and let me know if you have any questions about the code or concepts. I tried to leave you a ton of comments to help.
OPTION STRICT

'FINITE STATE MACHINE DEMONSTRATION
'FOLLOWING A RECTANGULAR SPIRAL PATH

'OUR MACHINE TRACES OUT A RECTANGULAR SPIRAL.
'EACH RING IS OF SIZE 2N + 1 BY 2N + 1
'WHER N IS A POSITVE INTEGER >= 0
'FOR EXAMPLE 1X1, 3X3, 5X5, ETC.
'
'OUR MACHINE HAS FOUR STATES
'* STATE NORTH
'* STATE EAST
'* STATE_SOUTH
'* STATE_WEST
'
'WE START OUT IN THE NORTH STATE.
'NORTH TRANSITIONS TO EAST. EAST TRANSITIONS 
'TO SOUTH, SOUTH TRANSITIONS TO WEST AND WEST
'TRANSITIONS BACK TO NORTH.
'STATES TRANSITION WHEN THEY REACH THE EDGE 
'OF THE RING THEY ARE ON IN THE DIRECTION OF
'TRAVEL. ALL THAT IS EXCEPT THE NORTH STATE 
'WHICH GOES ONE STEP FURTHER AND INCREASES
'THE RING SIZE WHEN TRANSITIONING.
'
'BESIDES THE STATE WE ARE IN, WE WANT EACH
'INSTANCE OF THE STATE MACHINE TO KEEP TRACK
'OF THE CENTER OF THE SPIRAL, CURRENT 
'POSITION, AND CURRENT RING. WE ALSO WANT TO 
'STOP AFTER A CERTAIN DISTANCE SO WE ALSO 
'HAVE A REMAINING DISTANCE COUNT DOWN 
'VARIABLE
'
'TO PROVE THE UNIQUENESS OF EACH INSTANCE,
'THE CODE SETS THEM UP A SPRITES WITH A CALL
'BACK THAT UPDATES EACH INDEPENDANTLY AND
'STORES STATE IN THE SPVAR VARIABLES. YOU CAN
'HAVE AS MANY INSTANCES AS YOU HAVE AVAILABLE
'SPRITES.

'SIZE OF THE SCREEN
VAR SCREEN_W = 400, SCREEN_H = 240

'MEDUSA FACING RIGHT
VAR SPRITE_ID = 1076

'HOW BIG TO DRAW THE RING, I WANT TO MATCH
'THE 16X16 SPRITE
VAR RING_SCALE = 16
VAR SPRITE_SPEED = 64 'HOW FAST DOES IT MOVE

'HOW LONG UNTIL WE MAKE A NEW SPRITE
VAR SPRITE_DELAY = 0
'HOW LONG TO WAIT BETWEEN GENERATING SPRITES
VAR DELAY_MAX = 1000

'SPRITE VARIABLE INDEXES
'(WE DON'T LIKE "MAGIC" NUMBERS)
VAR IDX_CENTER_X = 0
VAR IDX_CENTER_Y = 1
VAR IDX_STEPS_LEFT = 2
VAR IDX_STATE = 3
VAR IDX_RING = 4
VAR IDX_RING_COLOR = 5

'STATE CONSTANTS
'THE NUMBERS DON'T MATTER THEY JUST NEED TO
'BE UNIQUE. IN OTHER LANGUAGES YOU WOULD
'USE AN ENUMERATION
VAR STATE_E = 0
VAR STATE_S = 1
VAR STATE_W = 2
VAR STATE_N = 3

'TIME BASED MOVEMENT
VAR T1, T2, DT#

'GENERAL GAME LOOP FLAGS AND VARIABLES
VAR GAME_OVER = FALSE, B
VAR SPID

'SETUP THE SCREEN
ACLS
LOCATE 0, 0
COLOR #TWHITE, #TBLUE
PRINT "PRESS [B] TO EXIT";
COLOR #TWHITE, 0 'TRANSPARENT BACKGROUND

'PRIME THE TIMER
T2 = MILLISEC - 8

'GAME LOOP
WHILE GAME_OVER == FALSE
 'CALCULATE ELAPSED TIME IN MILLISECONDS
 T1 = T2
 T2 = MILLISEC
 'KEEP IT BETWEEN 16 AND 250 MILLISECONDS
 DT# = MAX(16, MIN(150, T2 - T1))
 
 'SPAWN A NEW SPRITE IF IT IS TIME
 IF SPRITE_DELAY <= 0 THEN
  SPID = NEW_SPIRAL_SPRITE(RND(SCREEN_W), RND(SCREEN_H), 100 + RND(1000), RGB(RND(256), RND(256), RND(256)))
  SPRITE_DELAY = DELAY_MAX
 ELSE
  SPRITE_DELAY = SPRITE_DELAY - DT#
 ENDIF
 
 'UPDATE ALL SPRITES WITH A CALLBACK
 CALL SPRITE
 
 'CHECK IF WE SHOULD EXIT THE GAME
 B = BUTTON()
 IF (B AND #B) != 0 THEN 
  GAME_OVER = TRUE
 ENDIF
 
 'SCREEN REFESH WAIT
 VSYNC
WEND

'CREATE A NEW SPRITE / STATE MACHINE INSTANCE
'PARAMETERS:
'* CENTER_X - CENTER OF SPIRAL X COORDINATE
'* CENTER_Y - CENTER OF SPIRAL Y COORDINATE
'* STEPS_LEFT - HOW MANY STEPS/PIXELS TO 
'              TRAVEL BEFORE SHUTTING DOWN
'* TRAIL_COLOR - WHAT COLOR TO DRAW THE 
'                SLIME TRAIL
'RETURNS:
'* -1 ON FAILURE, GENERATED SPRITE ID ON
'  SUCCESS
'
DEF NEW_SPIRAL_SPRITE(CENTER_X, CENTER_Y, STEPS_LEFT, TRAIL_COLOR)
 VAR SP_ID
 
 SPSET SPRITE_ID OUT SPID
 'SPSET RETURNS -1 IF OUT OF SPRITES
 IF SPID != -1 THEN
  SPVAR SPID, IDX_CENTER_X, CENTER_X
  SPVAR SPID, IDX_CENTER_Y, CENTER_Y
  SPVAR SPID, IDX_STEPS_LEFT, STEPS_LEFT
  SPVAR SPID, IDX_STATE, STATE_N
  SPVAR SPID, IDX_RING, 0 'RING
  SPVAR SPID, IDX_RING_COLOR, TRAIL_COLOR
  SPFUNC SPID, "SPIRAL_SPRITE_UPDATE"
  SPOFS SPID, CENTER_X, CENTER_Y
 ENDIF
 RETURN SPID
END

'STATE MACHINE CALLBACK.
'NO PARAMETERS ARE PASSED IN. THE SPRITE TO
'OPERATE ON IS IN THE SYSTEM VARIABLE CALLIDX
'
'PARAMETERS:
' NONE, CALLIDX IMPLIED
'RETURNS:
' NONE
DEF SPIRAL_SPRITE_UPDATE
 VAR X, Y, CENTER_X, CENTER_Y
 VAR STEPS_LEFT, STATE, RING, RING_COLOR
 VAR NEW_X, NEW_Y, NEW_STATE, RADIUS
 VAR MOVEMENT
 
 'GET X, Y COORDINATE
 SPOFS CALLIDX OUT X, Y
 'READ MORE STATE FROM SPVAR
 CENTER_X = SPVAR(CALLIDX, IDX_CENTER_X)
 CENTER_Y = SPVAR(CALLIDX, IDX_CENTER_Y)
 STEPS_LEFT = SPVAR(CALLIDX, IDX_STEPS_LEFT)
 STATE = SPVAR(CALLIDX, IDX_STATE)
 RING = SPVAR(CALLIDX, IDX_RING)
 RING_COLOR = SPVAR(CALLIDX, IDX_RING_COLOR)
 
 'HOW FAR SHOULD WE TRAVEL SINCE LAST UPDATE
 MOVEMENT = MAX(((DT# * SPRITE_SPEED)/1000), 1)
 'BY DEFAULT KEEP THE CURRENT STATE
 'I AM SAVING THE NEXT STATE IN ANOTHER
 'VARIABLE SO WE DON'T PROCESS MORE THAN
 'ONE STATE ON A STATE TRANSITION.
 NEW_STATE = STATE
 
 'USEFULL TO CALCULATE THE RADIUS OF THE
 'CURRENT RING.
 RADIUS = RING * RING_SCALE
 
 'UPDATE ACCORDING TO THE CURRENT STATE
 'JUST AN IF ELSEIF SETUP. COULD BE FUNCTION
 'CALLS IF YOU WANT TOO. OTHER LANGUAGES MAY 
 'USE A SWITCH STATEMENT.
 IF STATE == STATE_N THEN
  '-RADIUS, RADIUS -> -RADIUS, -RADIUS + 1
  NEW_X = CENTER_X - RADIUS
  NEW_Y = Y - MOVEMENT
  'NORTH GOES ONE STEP FURTHER THAN THE REST
  'AND INCREASES RING SIZE ON STATE
  'TRANSITION
  IF NEW_Y <= CENTER_Y - RADIUS - RING_SCALE THEN
   NEW_Y = CENTER_Y - RADIUS - RING_SCALE
   NEW_STATE = STATE_E
   RING = RING + 1
  ENDIF
  
  GFILL NEW_X, NEW_Y, X + RING_SCALE, Y + RING_SCALE, RING_COLOR
 ELSEIF STATE == STATE_E THEN
  '-RADIUS, -RADIUS -> RADIUS, -RADIUS
  NEW_Y = CENTER_Y - RADIUS
  NEW_X = X + MOVEMENT
  IF NEW_X >= CENTER_X + RADIUS THEN
   NEW_X = CENTER_X + RADIUS
   NEW_STATE = STATE_S
  ENDIF
  
  GFILL X, Y, NEW_X + RING_SCALE, NEW_Y + RING_SCALE, RING_COLOR
 ELSEIF STATE == STATE_S THEN
  'RADIUS, -RADIUS -> RADIUS, RADIUS
  NEW_X = CENTER_X + RADIUS
  NEW_Y = Y + MOVEMENT
  IF NEW_Y >= CENTER_Y + RADIUS THEN
   NEW_Y = CENTER_Y + RADIUS
   NEW_STATE = STATE_W
  ENDIF
  
  GFILL X, Y, NEW_X + RING_SCALE, NEW_Y + RING_SCALE, RING_COLOR

 ELSEIF STATE == STATE_W THEN
  'RADIUS,RADIUS -> -RADIUS,RADIUS
  NEW_Y = CENTER_Y + RADIUS
  NEW_X = X - MOVEMENT

  IF NEW_X <= CENTER_X - RADIUS THEN
   NEW_X = CENTER_X - RADIUS
   NEW_STATE = STATE_N
  ENDIF
  GFILL NEW_X, NEW_Y, X + RING_SCALE, Y + RING_SCALE, RING_COLOR

 ENDIF
 
 'MOVE TO THE NEW X, Y LOCATION
 SPOFS CALLIDX, NEW_X, NEW_Y
 'DECREASE REMAINING STEPS BY DISTANCE 
 'TRAVELED
 STEPS_LEFT = STEPS_LEFT - MOVEMENT
 IF STEPS_LEFT <= 0 THEN
  'OUT OF STEPS, CLEAR THE SPRITE
  SPCLR CALLIDX
 ELSE
  'SAVE CURRENT STATE CHANGES
  'SPOFS UPDATED THE X,Y COORDINATE ALEADY
  SPVAR CALLIDX, IDX_STEPS_LEFT, STEPS_LEFT
  SPVAR CALLIDX, IDX_STATE, NEW_STATE
  SPVAR CALLIDX, IDX_RING, RING
 ENDIF
END

You can calculate the next position directly from the current position as long as you know where the center is: (Here I'm assuming it to be x=0, y=0)
IF -X>ABS(Y)-0.5 THEN 'up
 DEC Y
ELSEIF X>ABS(Y+0.5) THEN 'down
 INC Y
ELSEIF Y>ABS(X-0.5) THEN 'left
 DEC X
ELSE 'right
 INC X
ENDIF
'(The last 5 lines can be simplified to ELSE : DEC X,SGN(Y) : ENDIF)
old
IF X==Y && X<=0 THEN 'move to next layer
 DEC Y
ELSEIF -Y>=ABS(X+0.5) THEN 'right
 INC X
ELSEIF X>=ABS(Y+0.5) THEN 'down
 INC Y
ELSEIF Y>=ABS(X-0.5) THEN 'left
 DEC X
ELSE 'up
 DEC Y
ENDIF

I like the mathematical simplicity and compactness of your code, the graph is very nice as well.

[quote/]Please give it a look and let me know if you have any questions about the code or concepts. I tried to leave you a ton of comments to help. ...I think I'll have to get in touch with my good friend Petit Modem first haha Thanks for your effort. After I give the code a whirl I'll have more thoughts to share I'm sure.

You can calculate the next position directly from the current position as long as you know where the center is: (Here I'm assuming it to be x=0, y=0)
IF -X>ABS(Y)-0.5 THEN 'up
 DEC Y
ELSEIF X>ABS(Y+0.5) THEN 'down
 INC Y
ELSEIF Y>ABS(X-0.5) THEN 'left
 DEC X
ELSE 'right
 INC X
ENDIF
'(The last 5 lines can be simplified to ELSE : DEC X,SGN(Y) : ENDIF)
This is so shockingly simple and easy to follow


What's the best way to do this?

If you want to code golf it, I would go with 12Me21's solution as code golf places a premium on smallest possible code size. My approach is decidedly verbose. If you want a general purpose tool that you can refer to over and over again for a multitude of problems, well I would suggest the Finite State Machine approach. I haven't tried, but either way, it should be fairly simple to start at the top left corner and run either one backwards. Just stop when you get to 0, 0.