Finding direction to rotate

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|715\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Blitz -> Finding direction to rotate
Wed, 15 Aug 2007, 14:58
mike_g	I'm coding automated movement in my raycasting prog at the moment. It uses A* to find a path, then rotates to face the next tile to move to. I want to find out what direction to turn in will take the least rotation. So say I know the target facing I want to reach. I have 2 player directions dir_x and dir_y, which range between -1 and 1. How can I find which direction will take the least rotation? Heres an sketch. Ignore the blue writing its just random crap. The red dot represents the player. Theres an example target of dir_x = 0.5, dir_y = 0.5. Any facing in the green half of the grid would be rotated to the right, whereas anything in the turquoise half would be rotated to the left.
Wed, 15 Aug 2007, 15:05
JL235	I don't quite understand. Is the problem along the lines of if person X is facing a certain angle, say 90 degrees, he's going to turn to face say 180 degrees. You want to find out if he should turn left or right to get to face that angle in the shortest distance? i.e. in my example he should turn +90 degrees which is clockwise to go from 90 to 180, rather then -270 degrees anti-clockwise as it would take longer?
Wed, 15 Aug 2007, 15:28
mike_g	No basically the program doesent do anything interactive at the moment. Its just so I can get the pathfinding, and movement following paths sorted out. For each waypoint I get a sequence of tiles to move between to reach it. These are adjacent or diagonal from on another. The prog checks if a new tile is reached, then turns to face the next tile to move to before moving forward. At the moment I am always turning right, which looks kind of shit.
Wed, 15 Aug 2007, 19:36
power mousey	couldn't you use the standard rotation angles. like 0 to 359...positive or clockwise rotation. And 360 would be back to 0 degrees. Similar thing with counter clockwise rotation. 0 to -360. And -360.00 would bring the angle spin back to 0 degrees. then using 0.00 to 1.00 and 0.00 to -1.00 for the ranges of either clockwise or counterclockwise spin. um good luck have a nice Clockwork Orange, power mousey
Thu, 16 Aug 2007, 03:37
Jayenkai	;Should I Left ;or ;Should I Right ;Goto Example2 ;<---- Ooooooh! Mysterious second example!!! Graphics 800,600,32,2 SetBuffer BackBuffer() MyX=Rand(0,800):MyY=Rand(0,600):MyAng=Rand(0,360):HisX=Rand(0,800):HisY=Rand(0,600) SeedRnd MilliSecs() Repeat Cls Color 255,0,0 Oval MyX-16,MyY-16,32,32,0 Line MyX,MyY,MyX+Sin(MyAng)20,MyY-Cos(MyAng)20 HeIs=ATan2(HisX-MyX,MyY-HisY):If HeIs<0 Then HeIs=HeIs+360 Color 0,255,0 Oval HisX-16,HisY-16,32,32,0 Line MyX,MyY,MyX+Sin(HeIs)20,MyY-Cos(Heis)20 Way=WhereDoIGo(MyAng,HeIs) Color 0,180,255 Line MyX+Sin(MyAng)20,MyY-Cos(MyAng)20,MyX+Sin(MyAng+(Way20))20,MyY-Cos(MyAng+(Way20))20 If KeyHit(57) Then MyX=Rand(0,800):MyY=Rand(0,600):MyAng=Rand(0,360):HisX=Rand(0,800):HisY=Rand(0,600) Flip If KeyDown(1) Then endofgame=99 Until endofgame<>0 End .Example2 Graphics 800,600,32,2 SetBuffer BackBuffer() MyX=Rand(100,699) HisX=Rand(100,699) SeedRnd MilliSecs() Repeat Cls Text 1,20,"The blue line shows the best direction to go," Text 1,40,"if you assume the two white lines are the wraparound limits." Color 255,255,255 Line 100,80,100,440 Line 700,80,700,440 Color 255,0,0 Line MyX,80,MyX,440 Color 0,255,0 Line HisX,80,HisX,440 Way=WhereDoIGo(MyX,HisX,100,699) Color 0,180,255 Line MyX,300,MyX+(Way*24),300 If KeyHit(57) Then MyX=Rand(100,699):HisX=Rand(100,699) Flip If KeyDown(1) Then endofgame=99 Until endofgame<>0 End Function WhereDoIGo(ImAt,WanttoGo,BotLimit=0,TopLimit=359) ;ImAt - My current Angle. ;WanttoGo - The angle I want to face. ;BotLimit - The bottommost point ;TopLimit - The topmost point ;First check that the angles are between Top and Bottom. Repeat fin=1 If ImAt<BotLimit Then ImAt=ImAt+((TopLimit-BotLimit)+1):fin=0 If ImAt>TopLimit Then ImAt=ImAt-((TopLimit-BotLimit)+1):fin=0 Until fin=1 Repeat fin=1 If WanttoGo<BotLimit Then WanttoGo=WanttoGo+((TopLimit-BotLimit)+1):fin=0 If WanttoGo>TopLimit Then WanttoGo=WanttoGo-((TopLimit-BotLimit)+1):fin=0 Until fin=1 ;Find the difference Difference=(WantToGo-ImAt)+BotLimit ;Stick that between our limits Repeat fin=1 If Difference<BotLimit Then Difference=Difference+((TopLimit-BotLimit)+1):fin=0 If Difference>TopLimit Then Difference=Difference-((TopLimit-BotLimit)+1):fin=0 Until fin=1 ;Then decide if it's bigger or less than the mid-point.. out=1 If Difference>((TopLimit-BotLimit)/2)+BotLimit Then out=-1 ;Sorted... Return out End Function --v -=-=- ''Load, Next List!''
Thu, 16 Aug 2007, 08:08
mike_g	Cheers Jay. I have kind of given up on this code I was doing, as its become a bit of a mess. Hopefully I'll get back to it in a couple of days or so with a fresh head.
Thu, 16 Aug 2007, 08:55
Teasy	Looking at your pic, it seems you want something with simple range logic (no angles). The blue text makes it seem there's only 1 range for each color, but I think there's actually 2. Something like this: green x -0.5, +0.0, +0.5, +1.0, +0.5 y -0.5, -1.0, -0.5, +0.0, +0.5 range1 x >+0.5 <+1.0 range1 y >-0.5 <+0.5 range2 x >-0.5 <+0.5 range2 y >-1.0 <-0.5 blue (cyan) x -0.5, -1.0, -0.5, +0.0, +0.5 y -0.5, +0.0, +0.5, +1.0, +0.5 range1 x >-1.0 <-0.5 range1 y >-0.5 <+0.5 range2 x >-0.5 <+0.5 range2 y >+0.5 <+1.0 example code ; green ranges if ((x >= 0.5 and x < 1.0) and (y >= -0.5 and y < 0.5)) or ((x >= -0.5 and x < 0.5) and (y >= -1.0 and y < -0.5)) ; green! else ; blue (cyan)! endif --v I have no idea if this works, though Maybe with a vector comparison/translation, or even by applying some mathematical optimizations, the above can be substantially simplified. \|edit\| In most cases with angles and such I use Jay's approach, though \|edit\|
Thu, 16 Aug 2007, 10:16
mike_g	Yeah, apparently the solution has something to do with using the dot product of a vector at right angles to the way it is facing and the vector to the object you want to turn towards. I guess I got to learn more about the maths involving vectors. Something I'm pretty clueless about at the moment. \|edit\| I tried finding a solution using logic based on ranges, but I couldent find one. It dosent seem to be as easy as it looks. \|edit\|
Thu, 16 Aug 2007, 10:30
Afr0	Uhm, vector maths aren't that hard? o.O A vector is three coordinates, so to pull together a vector you go: x = x + newx y = y + newy z = z + newz To multiply, go: x = x * newx y = y * newy z = z * newz In Blitz, you should write functions to do it for you. In C# it becomes even easier as you can overload the standard math operators and just go: MyVec = MyVec + NewVec MyVec = MyVec * NewVec -=-=- Afr0 Games Project Dollhouse on Github - Please fork!
Thu, 16 Aug 2007, 10:38
JL235	It's a bad idea to overload operators. But wrapping it into a method or function, that's a very good idea.
Thu, 16 Aug 2007, 11:34
Nolan	It's a bad idea to overload operators. Why is it a bad idea? Operator overloading is there to be used; it'd be a shame to waste it. -=-=- nolandc.com
Thu, 16 Aug 2007, 11:52
JL235	Just because a feature is there doesn't mean you must use it. Overloading operators can confuse the reader because they don't expect it. It's even worse if the operator doesn't really reflect what it is doing. Ok there are some good occasions, for example with Strings and Arrays (Ruby uses << for adding something to an array which I love). But it is usually far better to not use operator overloading. When you start seeing 'a \|= b' it can start to get a little confusing. All I'm saying is to just err on the side of caution.
Thu, 16 Aug 2007, 12:16
Teasy	Btw, for the corners you seem to use -0.5 and +0.5 ('isometric') rather than for example -1.0 and +1.0 (square) or -0.7 and +0.7 (circular). If my previous posts made no sense to you (), then for a quick solution, try this: 1. Flip the X. 2. If both X and Y are <= 0, it's green 3. If both X and Y are >= 0, it's cyan. 4. Otherwise it's on the borderline. Local x#,y# Local dir Repeat dir = dir + 1 If dir > 8 dir = 1 EndIf Select dir Case 1 x = -1 y = -1 Case 2 x = 0 y = -1 Case 3 x = +1 y = -1 Case 4 x = +1 y = 0 Case 5 x = +1 y = 1 Case 6 x = 0 y = 1 Case 7 x = -1 y = 1 Case 8 x = -1 y = 0 End Select Cls Text 0,0 , "X:"+x+" Y:"+y Color 128,0,0 For dx = 0 To 1 For dy = 0 To 1 Rect 100-40+40dx,100-40+40dy , 40,40 , False Next Next Color 255,255,0 Line 100,100 , 100+x40,100+y40 Color 255,255,255 ; flip the borderline from topleft-bottomright to bottomleft-topright If -x <= 0 And y <= 0 Text 0,10 , "Green" ElseIf -x >= 0 And y >= 0 Text 0,10 , "Cyan" Else Text 0,10 , "Borderline" EndIf WaitKey Until KeyHit( 1 ) End --v This works for 'isometric', square and circular. It's very simple I know So maybe I misunderstood something completely
Fri, 17 Aug 2007, 07:29
mike_g	Btw, for the corners you seem to use -0.5 and +0.5 ('isometric') rather than for example -1.0 and +1.0 (square) or -0.7 and +0.7 (circular). Yeah that was something I noticed was wrong in my prog. I was checking on diagonals if the angles were >0.4 <0.6. then for a quick solution, try this: 1. Flip the X. 2. If both X and Y are <= 0, it's green 3. If both X and Y are >= 0, it's cyan. 4. Otherwise it's on the borderline. The target is variable tho. Maybe I'm missing something, but to me that does not seem as if it will work when the target is: x=1 y=0
Fri, 17 Aug 2007, 10:55
Teasy	When you flip the X, everything negative becomes green. If by x=1 and y=0 you mean right, then it works (in both algorithm and code) Have you tried my program above?
Sat, 18 Aug 2007, 11:26
mike_g	Yeah I had tried the code, and it works with varying player facing directions. I just cant see it working when the target direction is changed. Both are variables. I came up with something similar myself, that I initially thought worked, but later found out dident.
Mon, 20 Aug 2007, 09:20
Teasy	This is a very interesting puzzle To simplify the Sin/Cos approach, just divide the 360 degrees by 45 and use your own sine() function This probably sounds more complicated than it is! Basically what you have drawn, 45 degrees = 1 step, pre-defined in arrays/functions to look-up easily. ;------------------------------------------------------------------------------- ; keyboard scancodes Const Key_Esc = 1 Const Key_Up = 200 Const Key_Down = 208 Const Key_Left = 203 Const Key_Right = 205 ;------------------------------------------------------------------------------- ; directions Const dir_up = 0 Const dir_upright = 1 Const dir_right = 2 Const dir_downright = 3 Const dir_down = 4 Const dir_downleft = 5 Const dir_left = 6 Const dir_upleft = 7 Dim dirname$(7) dirname( dir_up ) = "Up " dirname( dir_upright ) = "Up Right" dirname( dir_right ) = " Right" dirname( dir_downright ) = "Down Right" dirname( dir_down ) = "Down " dirname( dir_downleft ) = "Down Left " dirname( dir_left ) = " Left " dirname( dir_upleft ) = "Up Left " ;------------------------------------------------------------------------------- ; convert direction to vector[1] Global vectorx[7],vectory[7] vectorx[ dir_up ] = 0 vectory[ dir_up ] = -1 vectorx[ dir_upright ] = +1 vectory[ dir_upright ] = -1 vectorx[ dir_right ] = +1 vectory[ dir_right ] = 0 vectorx[ dir_downright ] = +1 vectory[ dir_downright ] = +1 vectorx[ dir_down ] = 0 vectory[ dir_down ] = +1 vectorx[ dir_downleft ] = -1 vectory[ dir_downleft ] = +1 vectorx[ dir_left ] = -1 vectory[ dir_left ] = 0 vectorx[ dir_upleft ] = -1 vectory[ dir_upleft ] = -1 ;------------------------------------------------------------------------------- ; convert vector[1] to direction Dim vectordir(2,2) ; x,y:0=-1,1=0,2=+1 vectordir( 0+1,-1+1 ) = dir_up vectordir( +1+1,-1+1 ) = dir_upright vectordir( +1+1, 0+1 ) = dir_right vectordir( +1+1,+1+1 ) = dir_downright vectordir( 0+1,+1+1 ) = dir_down vectordir( -1+1,+1+1 ) = dir_downleft vectordir( -1+1, 0+1 ) = dir_left vectordir( -1+1,-1+1 ) = dir_upleft Function vector(vectorx,vectory) Return vectordir(Sgn(vectorx)+1,Sgn(vectory)+1) End Function ;------------------------------------------------------------------------------- ; rotate vector using direction Function rotatevector( playervector[1],rotation ) Local dir ; first get direction from vector dir = vector(playervector[0],playervector[1]) ; add rotation dir = dir + rotation ; - wrap around negative (single) If dir < 0 dir = dir + 8 ; - wrap around positive (single) ElseIf dir >= 8 dir = dir - 8 EndIf ; fill vector with rotated values playervector[0] = vectorx[dir] playervector[1] = vectory[dir] End Function ;------------------------------------------------------------------------------- ; determine green or cyan half: ; -1 = rotate left, 0 = on borderline, +1 = rotate right Function whichdir( playervector[1] ) If -playervector[0] <= 0 And playervector[1] <= 0 Return +1 ; green (right) ElseIf -playervector[0] >= 0 And playervector[1] >= 0 Return -1 ; cyan (left) Else Return 0 ; borderline EndIf End Function ;------------------------------------------------------------------------------- ; determine shortest rotation direction Function RotateDir%( CurrentAngle% , TargetAngle% ) ; over half of rotation difference (180 degrees) If TargetAngle - CurrentAngle >= 4 ; wrap to other side TargetAngle = TargetAngle - 8 EndIf ; same in other direction If CurrentAngle - TargetAngle >= 4 CurrentAngle = CurrentAngle - 8 EndIf ; determine on which side the difference is If TargetAngle - CurrentAngle < 0 Return -1 ElseIf TargetAngle - CurrentAngle > 0 Return +1 Else Return 0 EndIf End Function ;------------------------------------------------------------------------------- ; determine relative difference between angles Function AngleDifference%( CurrentAngle% , TargetAngle% ) ; over half of rotation difference (180 degrees) If TargetAngle - CurrentAngle >= 4 ; wrap to other side TargetAngle = TargetAngle - 8 EndIf ; same in other direction If CurrentAngle - TargetAngle >= 4 CurrentAngle = CurrentAngle - 8 EndIf ; return wrapped difference between angles Return TargetAngle - CurrentAngle End Function ;------------------------------------------------------------------------------- ; test 3 Function test3() Local playervector[1] ; 0=x,1=y Local targetvector[1] ; Local resultvector[1] ; Local sx,sy Local horipress,vertipress playervector[0] = 0 ; center playervector[1] = -1 ; up targetvector[0] = +1 ; right targetvector[1] = +1 ; down sx = 400 sy = 300 Graphics sx,sy , 0,3 SetBuffer BackBuffer() Repeat horipress = KeyHit( key_right ) - KeyHit( key_left ) vertipress = KeyHit( key_down ) - KeyHit( key_up ) If horipress rotatevector playervector , horipress EndIf If vertipress rotatevector targetvector , vertipress EndIf Cls ; grid Color 128,0,0 For dx = 0 To 1 For dy = 0 To 1 Rect sx/2-sx/4+(sx/4)dx,sy/2-sy/4+(sy/4)dy , sx/4,sy/4 , False Next Next ; lines on grid Color 0,255,0 Line sx/2-1,sy/2-1 , sx/2+playervector[0](sx/4)-1,sy/2+playervector[1](sy/4)-1 Color 255,255,0 Line sx/2+2,sy/2+2 , sx/2+targetvector[0](sx/4)+2,sy/2+targetvector[1](sy/4)+2 Color 255,255,255 Text 0, 0 , "Use Left/Right to change player vector" Text 0,10 , "Use Up /Down to change target vector" ; vectors Color 0,255,0 Text 0,30 , "Player vector X:"+playervector[0]+" Y:"+playervector[1]+" ("+dirname( vector(playervector[0],playervector[1]) )+")" Color 255,255,0 Text 0,40 , "Target vector X:"+targetvector[0]+" Y:"+targetvector[1]+" ("+dirname( vector(targetvector[0],targetvector[1]) )+")" ; algorithm Color 255,255,255 Text 0,60 , "RotateDir: "+rotatedir( vector(playervector[0],playervector[1]) , vector(targetvector[0],targetvector[1]) ) Text 0,70 , "Difference: "+angledifference( vector(playervector[0],playervector[1]) , vector(targetvector[0],targetvector[1]) ) Flip WaitKey Until KeyHit( key_esc ) End End Function ;------------------------------------------------------------------------------- test3 --v I've added 2 unused functions called rotatevector and whichdir which do the same as in my previous program further above, in case you want to do it that way (it is harder, though) The low-down on the new approach: - 2 vectors; playervector[] and targetvector[] - where playervector[0] means X and playervector[1] means Y - convert both of these to a universal direction using the vector() function (actually a limited and shifted array) which returns something between 0 (up) and 7 (up + left) - and finally detect either the angle difference using AngleDifference() which returns something between 0 and 4 (180 degrees) - or simply the shortest rotation direction using RotateDir() which returns -1 (left), 0 (same dir) or +1 (right) By running the program you'll see Btw, this technique is probably faster than Sin/Cos etc (even if precalculated) execution-wise, but this is not nearly as important as which technique you understand better ofcourse \|edit\| Btw, I think I understand now what you want (woohoo!), so this is probably what you were looking for \|edit\|
Mon, 20 Aug 2007, 13:51
mike_g	Cool, this looks more like it. I have gone off coding bots for my prog at the moment, but when I get back to it this should be handy! Cheers dude
Mon, 20 Aug 2007, 14:35
Afr0	Hm, so you're coding bots in Blitz? Don't you think it'd be cooler (not to mention tidier, as all you Blitz people seems to like having your entire program, no matter what the length of the entire source is, stuck into one single file) to phase it out to a scripting language so that people could make their own bots? Edit; About that tidy bit - It's possible that I am a bit biased towards being a neatfreak when it comes to separating code as much as possible, as I have seen C and C++ code before that have stuck up to 2000+ lines in the same file, and an average program or game in BlitzBasic usually doesn't grow much larger than that. I think my personal record for number of lines of code in the same file is around 500 - 600 lines. -=-=- Afr0 Games Project Dollhouse on Github - Please fork!
Mon, 20 Aug 2007, 15:02
mike_g	You dont have to have everything in one file using Blitz. I use Includes in my blitz progs all the time. And at the end of the day blitz is near enough a scripting language as it is. Allowing people to code their own bots for it would be cool. I hadent actually thought of that. I don't know how good I would be at setting up a system thats easy for other people to use tho. It seems OO languages are better suited for that kind of stuff.
Mon, 20 Aug 2007, 15:09
Afr0	I am perfectly aware that you don't have to have everything in one file in Blitz, I was merely pointing out that most people seems to like having it that way when coding in it. I've seen Blitz coders trying to phase out entire MMOs into one damn file, even! Sure, Blitz is a highlevel language, but seriously... there should be limits! Oh, and I know that I tried to build an MMO in Blitz too, but at least I phased it out into different files. And I still believe it's possible to do it in Blitz, just not any fun for me anymore, as I've come to love C# much more. -=-=- Afr0 Games Project Dollhouse on Github - Please fork!