? Algorithm for rectilinear spiral motion (Page 1) ● SmileBASIC Source Forums

Sign In

Register
*Usernames are case-sensitive
Forgot my password

Algorithm for rectilinear spiral motion

  • #1 ✎ 193 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies 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. Posted Edited by MZ952
  • #2 ✎ 1614 12Me21 Head Admin Second Year My account is over 2 years old Website Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself Does it matter where the start of each "circle" is? Posted
  • #3 ✎ 193 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies 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 Posted
  • #4 ✎ 1614 12Me21 Head Admin Second Year My account is over 2 years old Website Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself 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 Posted
  • #5 ✎ 193 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies 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. Posted Edited by MZ952
  • #6 ✎ 83 seggiepants 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 Posted
  • #7 ✎ 1614 12Me21 Head Admin Second Year My account is over 2 years old Website Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself 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) 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 Posted Edited by 12Me21
  • #8 ✎ 83 seggiepants I like the mathematical simplicity and compactness of your code, the graph is very nice as well. Posted
  • #9 ✎ 193 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies
    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.
    Posted
  • #10 ✎ 193 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies
    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
    Posted
  • #11 ✎ 193 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies https://codegolf.stackexchange.com/q/173869/81375 Posted
  • #12 ✎ 1 FantaSanta What's the best way to do this? Posted
  • #13 ✎ 83 seggiepants 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. Posted