Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Dark GDK / Perfection of a line algorithm...

Author
Message
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 24th Jun 2008 23:55 Edited at: 25th Jun 2008 03:20
Greetings,

I got this bit of code which works out the velocity shift which an object has to make if it moves between two points.

What i mean is that if i click somewhere it works out how quick it should go along the X and Y to go diagonally to the point where i clicked.

But the velocities aren’t perfect because it goes slightly higher or lower sometimes but I can't see how to fix it.

If anyone has any ideas how to get it working or do it better I would be happy to read them.

Cheers.

/Ludo

if ( dbMouseClick ( ) == 1 )
{
dbSprite ( 1, dbMouseX ( ), dbMouseY ( ), 1 ) ;

if ( dbSpriteX ( 1 ) > dbSpriteX ( 2 ) ) { One = dbSpriteX ( 1 ) - dbSpriteX ( 2 ) ; }
if ( dbSpriteX ( 1 ) < dbSpriteX ( 2 ) ) { One = dbSpriteX ( 2 ) - dbSpriteX ( 1 ) ; }

if ( dbSpriteY ( 1 ) > dbSpriteY ( 2 ) ) { Two = dbSpriteY ( 1 ) - dbSpriteY ( 2 ) ; }
if ( dbSpriteY ( 1 ) < dbSpriteY ( 2 ) ) { Two = dbSpriteY ( 2 ) - dbSpriteY ( 1 ) ; }

if ( ( One / 10 ) > ( Two / 10 ) ) { Three = ( One / 10 ) / ( Two / 10 ) ; Four = 10 / Three ; } else { Four = 10 ; }
if ( ( One / 10 ) < ( Two / 10 ) ) { Three = ( Two / 10 ) / ( One / 10 ) ; Five = 10 / Three ; } else { Five = 10 ; }
}

if ( dbSpriteX ( 1 ) > dbSpriteX ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 )+Five, dbSpriteY ( 2 ), 2 ) ; }
if ( dbSpriteX ( 1 ) < dbSpriteX ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 )-Five, dbSpriteY ( 2 ), 2 ) ; }

if ( dbSpriteY ( 1 ) > dbSpriteY ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 ), dbSpriteY ( 2 )+Four, 2 ) ; }
if ( dbSpriteY ( 1 ) < dbSpriteY ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 ), dbSpriteY ( 2 )-Four, 2 ) ; }

EDIT: Note to self: Spell Check Forum Posts!
Lilith
16
Years of Service
User Offline
Joined: 12th Feb 2008
Location: Dallas, TX
Posted: 25th Jun 2008 02:48
I'm not sure I understand the working of the code without staring at it for several hours, but keep in mind that you're working, it appears strictly with integer. You lose precision when you do this, especially if you divide one integer by another. You might try to work it out using floats.

Lilith, Night Butterfly
I'm not a programmer but I play one in the office
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 25th Jun 2008 03:12
I never specified the type of one, two, three, four or five and they are in fact, floats.

Basically its function makes the object move along the longer axis at 10 while, depending on the difference between the longer and short axis, moving along the short axis at a percentage of 10.

I.e. if the object has to go 100 along the X and up 50 on the Y then it moves at 10 on the X and 5 on the Y to generate a line between the starting position and the finish position.

The trouble is that there is a variant of 0 to 10 (although it's probably more like 0-9) in the ending position and the targeted position which I can't seem to move.

Additionally this code above seems to generate a minor curve in the movement moves the object faster on the diagonal than the horizontal or vertical.

I have since modded the code to this:

// Click Move Cursor Sprite Placement
if ( dbMouseClick ( ) == 1 )
{
dbSprite ( 1, dbMouseX ( ), dbMouseY ( ), 1 ) ;
}

if ( dbSpriteX ( 1 ) > dbSpriteX ( 2 ) ) { One = dbSpriteX ( 1 ) - dbSpriteX ( 2 ) ; }
if ( dbSpriteX ( 1 ) < dbSpriteX ( 2 ) ) { One = dbSpriteX ( 2 ) - dbSpriteX ( 1 ) ; }

if ( dbSpriteY ( 1 ) > dbSpriteY ( 2 ) ) { Two = dbSpriteY ( 1 ) - dbSpriteY ( 2 ) ; }
if ( dbSpriteY ( 1 ) < dbSpriteY ( 2 ) ) { Two = dbSpriteY ( 2 ) - dbSpriteY ( 1 ) ; }

if ( ( One / 10 ) > ( Two / 10 ) ) { Three = ( One / 10 ) / ( Two / 10 ) ; Four = 10 / Three ; } else { Four = 10 ; }
if ( ( One / 10 ) < ( Two / 10 ) ) { Three = ( Two / 10 ) / ( One / 10 ) ; Five = 10 / Three ; } else { Five = 10 ; }

if ( dbSpriteX ( 1 ) > dbSpriteX ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 )+Five, dbSpriteY ( 2 ), 2 ) ; }
if ( dbSpriteX ( 1 ) < dbSpriteX ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 )-Five, dbSpriteY ( 2 ), 2 ) ; }
if ( dbSpriteY ( 1 ) > dbSpriteY ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 ), dbSpriteY ( 2 )+Four, 2 ) ; }
if ( dbSpriteY ( 1 ) < dbSpriteY ( 2 ) ) { dbSprite ( 2, dbSpriteX ( 2 ), dbSpriteY ( 2 )-Four, 2 ) ; }

If you check the screen shot you can see the variant.

It's not that complicated really, it's just a bit of code for moving an object at a set speed to a position defined by clicking at a point on the screen.

Attachments

Login to view attachments
Lilith
16
Years of Service
User Offline
Joined: 12th Feb 2008
Location: Dallas, TX
Posted: 25th Jun 2008 08:06
I may have a solution for you but it will have to wait until morning. I had unexpected company that didn't leave until now.

Lilith, Night Butterfly
I'm not a programmer but I play one in the office
Mahoney
16
Years of Service
User Offline
Joined: 14th Apr 2008
Location: The Interwebs
Posted: 25th Jun 2008 08:09
Wondered where you've been.
Lilith
16
Years of Service
User Offline
Joined: 12th Feb 2008
Location: Dallas, TX
Posted: 25th Jun 2008 17:30 Edited at: 25th Jun 2008 19:23
This is pretty raw but....


From point p1(x1, y1) to point p2(x2, y2)



The problem with the code you're using may predicate the next step based on the current coordinates which must be integral by nature and can cause you to lose precision in making subsequent steps. This method bases every step on the initial position and uses floats to calculate the offset for each of the coordinates.

And obviously the loop may need to be changed to something a bit more open to allow other activities or allow a sync() operation.

Lilith, Night Butterfly
I'm not a programmer but I play one in the office
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 25th Jun 2008 20:10
Hmm, I can see what you mean in that plotting from the origin point and simply moving it towards the destination along a line would be a lot more precise than working out the movement direction based on a constantly adjusting origin but I can't say I've fully understood your code yet. I’m used to working in IF statements that apply and brake depending on logical conditions.

I'm going to do some work on it now and I'll post again when I've thought about your suggestion.

Cheers Lil.

/Ludo
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 25th Jun 2008 23:21
Ok first question; how does Max() work because I've copied some examples for the includes (see URL below) and you have it your code but I cannot get it to work.

We are here and it is now.
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 25th Jun 2008 23:27
This would be a lot easier if I could edit new posts...

I found out what Max() does and can put that into a function:

template <class T> const T& max ( const T& a, const T& b ) {
return (b<a)?a:b; // or: return comp(b,a)?a:b; for the comp version
}

Also here is the URL I forgot to add before posting the last message which seems a rather good place for C++ referencing:

http://www.cplusplus.com/reference/algorithm/max.html

We are here and it is now.
Lilith
16
Years of Service
User Offline
Joined: 12th Feb 2008
Location: Dallas, TX
Posted: 26th Jun 2008 00:14
It's rather hard to explain without having the ability to draw pictures at the same time. At least from the line drawing point of view.

Look at it this way. If you have an X and Y distance you need to traverse in 7 steps, you can break it down into the separate components. So the first step you need to go (X/7)*1 units in the x direction from your initial x position and (Y/7)*1 units in the y direction from your initial y coordinate. On the second step you go (X/7)*2 units from your initial x position and (Y/7)*2 units in the y direction from your initial y coordinate. Keep doing that until you've taken your 7 steps.

In retrospect I probably made a mistake in starting out from my line drawing algorithm because it ended up in some extra, unnecessary calculation. On further thought, you can, if you want, store the coordinates as floats and just add the X/7 and Y/2 to the coordinates each step. It saves the multiplication. But when you plot the position always cast it to an integer value for display purposes.

Lilith, Night Butterfly
I'm not a programmer but I play one in the office
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 26th Jun 2008 00:49 Edited at: 26th Jun 2008 01:01
Oh I see, your building up from a point.

Go 1 from X, Y to X, Y
Go 2 from X, Y to X, Y
Go 2 from X, Y to X, Y
etc

So each time the actual calculation is done from the same origin but the resulting value gets bigger and, more impotently, evenly on the X and Y. Yes that is a good idea because it would be very precise.

N, as you have labeled, is the characters movement speed (I think), which in my game will be something which develops with use and will therefore be in flux (i.e. the more running the character does, the faster and longer they can actually run).

In your last for loop, N is the characters speed and step is how many irritations of the characters speed is required to traverse the distance, right?

X1/Y1 is the origin point, step is the distance traversed measured in character speed and the slope indicates the direction(?).

...I'm just trying to work out how the for loop plugs into the coordinate redefinition of the character.

The Slope values multiplied by 10 and then put though:



Results in the same inaccurate method as before so I am guessing the accuracy of your algorithm comes from the for loop.

If you could explain how it's resultant values could be added to or moved from the sprites actual position so I can define it that would be helpful.

If it helps, here is my entire code so far is nothing but a load of functions in a prototype program that will later be compressed into classes and what have you. I must remember to post this stuff in the code base and that if I can get it working because doubtless people could use it in other games; the click movement function is present in most RTS games after all.



The code you provided (the Min/Max) did help to compress the code I already have too, so thanks for that by the way because I didn't know about them.

EDIT: One other thing, if you use if statements instead of for loops with counters which increase each time they run and then stop when the counters full they allow operations like sync to occur while performing the same functions as for loops. Just something you may want to think about.

We are here and it is now.
Ludo
16
Years of Service
User Offline
Joined: 23rd Jun 2008
Location: UK, Oxfordshire
Posted: 26th Jun 2008 01:28
I'm gonna pack this in for the night but me thinks you are missing a fundamental part of my objective; I am looking to traverse 1567 in 156.7 moves of 10 each, not 1567 in 10 moves of 156.7.

We are here and it is now.

Login to post a reply

Server time is: 2024-11-20 15:20:00
Your offset time is: 2024-11-20 15:20:00