[SOLVED] Drawing a vector line pixel by pixel

[MiteWiseacreLives!]

I am working on a concept for a game and I want to potentially move objects from one x,y coordinate to any other in 360degrees. My question is what is the math to move one pixel at a time procedurally towards a target? Would rounding work to set position, or is more involved to make a nice pixel line?

[Gurok]

If you just want to move an object from one place to another, in a straight line, the syntax is:

Code: ags

oBall.Move(x, y, speed);

I'm not trying to scare you off calculating the position yourself, but is there any need to? The maths is pretty simple, but it can get quite involved because a pixel line is a tricky thing.

The maths is:

y = mx + c

And this is generally true for lines with a gradient of magnitude < 1. For lines that are more vertical than horizontal, you'll want to change things a bit. More about this in a second.

Let's say you have a line going from (100, 100) to (200, 150). The gradient (m) is 1/2 (rise over run => 50 / 100 => 1 / 2). The constant (c) is the starting y value. In this case, 100.

So in this case, a line drawing function might look like:

Code: ags

function MyDrawLine(DrawingSurface *surface, int x1, int y1, int x2, int y2)
{
    int swap;

    if(x1 > x2) // Swap the x values if they're in the wrong order
    {
        swap = x2;
        x2 = x1;
        x1 = swap;
    }
    if(y1 > y2) // Swap the y values if they're in the wrong order
    {
        swap = y2;
        y2 = y1;
        y1 = swap;
    }
    float m = IntToFloat(y2 - y1) / IntToFloat(x2 - x1);

    while(x1 < x2)
    {
        surface.DrawPixel(x1, FloatToInt(m * IntToFloat(x1)) + y1);
        x1++;
    }
}

If you picture the line, a gradient of 1/2 goes along the x axis at a mild slope. For every x value, you need exactly one y value to make the line look smooth. This isn't the case with a line that's more vertical than horizontal. If your gradient's 3/2, you'll want 1-2 pixels going down for every x value. Otherwise your line will look sparse. To solve this, we can draw the line with respect to x instead of y, i.e.

x = my + c

and here's a function that takes it into account:

Code: ags

function MyDrawLine2(DrawingSurface *surface, int x1, int y1, int x2, int y2)
{
    int swap;

    if(x1 > x2) // Swap the x values if they're in the wrong order
    {
        swap = x2;
        x2 = x1;
        x1 = swap;
    }
    if(y1 > y2) // Swap the y values if they're in the wrong order
    {
        swap = y2;
        y2 = y1;
        y1 = swap;
    }
    if(y2 - y1 < x2 - x1) // Is this a shallow slope (best handled by y = mx + c)?
    {
        float m = IntToFloat(y2 - y1) / IntToFloat(x2 - x1);
        while(x1 < x2)
        {
            surface.DrawPixel(x1, FloatToInt(m * IntToFloat(x1)) + y1);
            x1++;
        }
    }
    else // Or a deep slope (x = my + c)?
    {
        float m = IntToFloat(x2 - x1) / IntToFloat(y2 - y1);
        while(y1 < y2)
        {
            surface.DrawPixel(FloatToInt(m * IntToFloat(y1)) + x1, y1);
            y1++;
        }
    }
}

Finally, it's probably best to have a case to handle things like y = c (straight horizontal line) and x = c (straight vertical line).

Put this all together and you'll have a mighty line drawing function that emulates the built-in one (DrawingSurface::DrawLine) pretty well.

But the question is, how do you want to use it?

You could put a call to your own function in there instead of surface.DrawPixel. That would let you move an object to that point and Wait(1) instead of putting a pixel there.

But I'm guessing you want to do this with some extra calculations on the values (otherwise you might just as well use the Move function). If that's the case, you might be better off with a generator style function. Something you can call with a particular x or y value to get the next corresponding pixel in the line. The trouble is, a line function has a lot of setup involved and it'd be pretty wasteful to write things that way. If you want to do something like that, I think your best bet might be to have a function that creates an array of integers that represents the final positions along the line. Obviously you'd still want to treat shallow and deep gradients separately.

To answer your rounding question, FloatToInt will round values, so yes there's rounding involved.

Also a disclaimer, I haven't checked these code examples with a compiler, so there may be some issues. They're not supposed to be verbatim anyway, just some illustrative examples to show you the maths.

[MiteWiseacreLives!]

Thanks Gurok!
It was as scary as I feared
I was looking at a simple setposition(x + Dx/length, y + Dy/length)  with float to int thrown in... Too simplistic I see...

The reason I needed to move towards the goal a pixel at a time was to check for collisions (a bullet flying).
Thanks again I'll test it out when I get home.
P.S. what is the symbol ^ ?

[Gurok]

Oh, that was a different way to swap variables. I've updated the examples now with something a little more verbose.

EDIT: If you're doing collision detection, you could still use the Move method of an object. Try moving your bullet with eNoBlock:

Code: ags

oBullet.Move(x, y, 1, eNoBlock);

And then use a check in repeatedly_execute_always() to determine whether it's colliding:

Code: ags

function repeatedly_execute_always()
{
    if(oBullet.x >= left_boundary && oBullet.x <= right_boundary && oBullet.y >= top_boundary && oBullet.y <= bottom_boundary)
        // Do something here
}

Unless you absolutely *need* to precalculate collisions before the bullet moves, this should suffice.

[MiteWiseacreLives!]

I've found before on the last game using move and repeatedly execute always was very messy. I am looking at doing several checks each frame and some other calculations on impact (rebounds). Just one shot at a time, make the bullet a character and the function global.

[MiteWiseacreLives!]

Ok so after doing this on paper for way too long I think I finally get how to use this

(Xa,Ya) -starting coordinates
(Xb,Yb) -target coordinates

X2 = Xb - Xa
Y2 = Yb - Ya
Grad = Y2 / X2


Y1 = Grad * X1
Next Coord (X1 + Xa , Y1 + Ya)
>Run some checks...
If (Xa < Xb)
X1 ++
Else
X1 --

For sharper angles move along y-axis:
If (Grad > 1)
X1 = Grad * Y1
Next Coord (X1 + Xa , Y1 + Ya)
>Run some checks...
If (Ya < Yb)
  Y1 ++
Else
  Y1 --

Works good unless a vertical line because Grad = null
So check for that and move straight up/down

This was probably exactly what you told me but I had to figure it out on paper to understand.
Only tested in theory, but hopefully useful to some other AGS'r
(If someone would like to check my math please do)

[Gurok]

EDIT: It looks about right. For completeness, here's a tested algorithm:

Code: ags

function MyDrawLine(DrawingSurface *surface, int x1, int y1, int x2, int y2)
{
	float m;
	int dx;
	int dy;
	int swap;
	int i;
	int flipX;
	int flipY;
	int base;

	if(x1 > x2)
	{
		swap = x2;
		x2 = x1;
		x1 = swap;
		flipX = -1;
	}
	else
		flipX = 1;
	if(y1 > y2)
	{
		swap = y2;
		y2 = y1;
		y1 = swap;
		flipY = -1;
	}
	else
		flipY = 1;
	dx = x2 - x1;
	dy = y2 - y1;

	if(dx == 0)
		while(y1 < y2)
		{
			surface.DrawPixel(x1, y1);
			y1++;
		}
	else
		if(dy == 0)
			while(x1 < x2)
			{
				surface.DrawPixel(x1, y1);
				x1++;
			}
		else
			if(dy < dx)
			{
				m = IntToFloat(dy) / IntToFloat(flipY * dx);
				i = x1;
				if(flipY == 1)
				{
					if(flipX == -1)
					{
						base = y2;
						m = -1.0 * m;
					}
					else
						base = y1;
				}
				else
				{
					if(flipX == -1)
					{
						base = y1;
						m = -1.0 * m;
					}
					else
						base = y2;
				}
        while(i < x2)
        {
					surface.DrawPixel(i, FloatToInt(m * IntToFloat(i - x1)) + base);
					i++;
        }
			}
			else
			{
				m = IntToFloat(dx) / IntToFloat(flipY * dy);
				i = y1;
				if(flipY == 1)
				{
					if(flipX == -1)
					{
						base = x2;
						m = -1.0 * m;
					}
					else
						base = x1;
				}
				else
				{
					if(flipX == -1)
					{
						base = x1;
						m = -1.0 * m;
					}
					else
						base = x2;
				}
        while(i < y2)
        {
					surface.DrawPixel(FloatToInt(m * IntToFloat(i - y1)) + base, i);
					i++;
        }
			}

	return;
}

[MiteWiseacreLives!]

Thanks 

[Monsieur OUXX]

Sorry to step in, but I'm highly suspicious of a solution that would involve the need of calculating yourself the position at each game cycle. One of the many solutions: If the object needs to be moved at constant speed (the concept of "one pixel at each game cycle" is a bit blurry, e.g. if the object moves diagonally), you could use the Tweens module. Or you could make the moving objects invisible characters and use the "WalkTo" command and let the engine do all the work, then get their X and Y.

[MiteWiseacreLives!]

Sorry Monsieur, but walk to stinks. Unless you want to have to character zig zagging all over the screen each segment. This can be adjusted to 3 pixel/frame for example, and don't get me wrong it's not the way to move every object or character but I want to check for intersection between solid objects, walkable areas or check properties. Even if not the method used in the end, now the answer to the question  and the code is available on the forum.