Followers 0

Finding wall point

23 posts in this topic

The world in my game is represented with a two dimensional array: byte[stage_height][stage_width].

If the byte is 0, the pixel is solid space, if it is 1, its hollow.

So I have a game object called A, and is placed somewhere in my world. I want to iterate from A to an other point and see if there is solid space between these two points.

I already have a function that does this, but the performance of that method is awful. Is there anything faster around here? Super-precision is not required.

Here is my function if anyone is interested:

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
float dx = Math.abs(x1-x0);
float dy = Math.abs(y1-y0);
int sx = (x0 < x1) ? 1 : -1;
int sy = (y0 < y1) ? 1 : -1;
float err = dx-dy;
byte[][] b = Stage.STAGE.stageData;

while (true)
{
if (b[y0][x0] == SOLID)
return false;

if (x0 == x1 && y0 == y1)
return true;

float e2 = 2*err;
if (e2 > -dy)
{
err -= dy;
x0 += sx;
}
if (e2 < dx)
{
err += dx;
y0 += sy;
}
}
}
0

Share on other sites

[url="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm"]Bresenham's line algorithm[/url]?

EDIT: It's basically what you are doing. So no, I don't think there is something much faster you could do, other than minor optimizations.

Edited by Álvaro
0

Share on other sites

Would it be possible to jump more than one step each iteration(in the function posted above)?

0

Share on other sites

Your problem might be in that you seem to be using Java. Try implementing this in C and compare speeds.

0

Share on other sites

Also, why are you using float' at all? All your numbers are integers...

1

Share on other sites

Also, why are you using float' at all? All your numbers are integers...

The error from the line is still using floats .

Another approach  is considering floating point maths ( pseudo code)


float dx = x1-x0;
float dy = y1-y0;
float max_side = MAX(FABS(dx),FABS(dy)); // length of the longest side
if(max_side == 0)
{
if (b[y0][x0] == SOLID)
return false;
else
return true;
}

dx /= max_side;
dy /= max side;
// Normalised stepping
do
{
if (b[y0][x0] == SOLID)
return false;
if(max_side == 0)
return true;
max_side--;
y0 += dy;
x0 += dx;
}


?

?

?

?

?

?

?

Edited by seedy
0

Share on other sites

The error from the line is still using floats .

What operation in the original code produces something that is not an integer?
0

Share on other sites

seedy: I think that code works better.

How could I modify it, so it continues until it finds solid space? I tried by removing the "return false" checks but it did not work.

0

Share on other sites

Is "A" going to be moving very far each frame? You could limit the number of iterations to only as far as "A" can move at any given frame. Another way is to reduce the resolution of the SPACE/SOLID blocks (this will depend on what your game should look like).

By the way, can you give a screen shot so I can get an idea of what your game looks like?

0

Share on other sites

For large traces, dense matrix representations won't do it. You'll need a hierarchical approach involving a quadtree or at least a sparse structure.

I have no real idea what you're doing here, but the pixel step cannot just be +1 or -1: almost horizontal (or vertical) traces will have an increment close to 0 in the corresponding coordinate.

Using float is definitely required, but I'm inclined to believe you're not doing it correctly.

Also, define "the performance of that method is awful".

0

Share on other sites

Using float is definitely required

Line algorithms have been around for a long time, when floating-point operations were prohibitively expensive. Go ahead and read the link I posted to Bresenham's line algorithm.
0

Share on other sites

As many have already pointed out, Bresenham's line algorithm specifically avoids using floats. I'm no Java expert, but I believe floats are quite slow in Java.

I've commented things in your code that could be improved.

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
float dx = Math.abs(x1-x0);    // why make these floats? The two input arguments are integers, so the result can be an integer too
float dy = Math.abs(y1-y0);   // <-----
int sx = (x0 < x1) ? 1 : -1;
int sy = (y0 < y1) ? 1 : -1;
float err = dx-dy;                    // dx and dy should be integers, so err can also be an integer
byte[][] b = Stage.STAGE.stageData;   // This could be expensive, copying a two dimensional array from one place to another. Consider using the original array directly

while (true)
{
if (b[y0][x0] == SOLID)
return false;

if (x0 == x1 && y0 == y1)
return true;

float e2 = 2*err;
if (e2 > -dy)
{
err -= dy;
x0 += sx;
}
if (e2 < dx)
{
err += dx;
y0 += sy;
}
}
}

And here's how I'd write it.

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
int dx = Math.abs(x1-x0);
int dy = Math.abs(y1-y0);
int sx = (x0 < x1) ? 1 : -1;
int sy = (y0 < y1) ? 1 : -1;
int err = dx-dy;

while (true)
{
if (Stage.STAGE.stageData[y0][x0] == SOLID)
return false;

if (x0 == x1 && y0 == y1)
return true;

float e2 = 2*err;
if (e2 > -dy)
{
err -= dy;
x0 += sx;
}
if (e2 < dx)
{
err += dx;
y0 += sy;
}
}
}

How large is your array (stage_width and stage_height), and how many line checks are you performing every game loop? I have a feeling there may be some inefficiency in the way you're using the method as well.

Edited by TheComet
0

Share on other sites

Line algorithms have been around for a long time, when floating-point operations were prohibitively expensive. Go ahead and read the link I posted to Bresenham's line algorithm
I will state it again. I would use floats.
-2

Share on other sites

Hm... I don't see why e2 has to be a float. err is an integer, and surely err * 2 will still be an integer.

You can try to mark all your constants and remove some redundant operations, sometimes it helps a bit (after all, it isn't something the JVM can't do on its own). You'll have to test it though.

public static boolean solidSpace ( int x0, int y0, final int x1, final int y1) // Some parameters are constant.
{
final int dx = Math.abs(x1-x0); // Constant
final int minusDy = -Math.abs(y1-y0); // Looks to me from what you're doing that you need -dy
// stored instead of just dy and negating it all the time.

final int sx = (x0 < x1) ? 1 : -1; // Constant
final int sy = (y0 < y1) ? 1 : -1; // Constant
int err = dx+minusDy; // Changed the op from -dy to +minusDy.

final byte[][] stageData = Stage.STAGE.stageData; // Constant reference to stageData.

while ( x0 != x1 || y0 != y1 ) // Boolean algebra! Yay!
{
if ( stageData[y0][x0] == SOLID ) // I'd put the braces anyway. Code style thing.
return false; // I don't get why "solidSpace()" returns false if it is solid
// but it's your code so it returns false. :D

final int e2 = 2*err; // Constant for the scope of the loop iteration. If err is integer, 2 * err will be integer.

if ( e2 > minusDy ) // Removed the -dy for minusDy.
{
x0 += sx;
}

if ( e2 < dx )
{
err += dx;
y0 += sy;
}
}
return true; // The 'true' return is here now.

}

BTW TheComet, final byte[][] stageData = Stage.STAGE.stageData isn't copying the array. Java works with references for everything that isn't a primitive type (that means arrays are references too).

Holding the constant reference in the method's scope *might* help the JVM if it's making any null check, it will do nothing otherwise.

Edited by TheChubu
0

Share on other sites

BTW TheComet, final byte[][] stageData = Stage.STAGE.stageData isn't copying the array. Java works with references for everything that isn't a primitive type (that means arrays are references too).

Ah, that's cool, I didn't know that.

0

Share on other sites

seedy: I think that code works better.

How could I modify it, so it continues until it finds solid space? I tried by removing the "return false" checks but it did not work.

	if(max_side == 0)
return true;
max_side--;



The do loop is controlled by the length of the line. You could check to see if the line went outside of your array x0 < 0 or x0 >= map_width ( C++ programmer another languages might start at 1 to map_width) and also the same for y0. Else you might want to check Z units past the end of the line - just add Z to max_side before starting the loop

0

Share on other sites

The error from the line is still using floats .

What operation in the original code produces something that is not an integer?

If you read the code which was originally posted you would have see the use of floats and not have asked.

-2

Share on other sites

The error from the line is still using floats .

What operation in the original code produces something that is not an integer?

If you read the code which was originally posted you would have see the use of floats and not have asked.

I am rather confused. Are you saying that the code mutated? The code in the first post (which doesn't seem to have been altered) uses the type float' but none of the operations can possibly result in a value that doesn't represent an integer. If you disagree with this, please explain what operation produces something that is not an integer.
0

Share on other sites

I the original code correct?

Should it be dx / dy instead of dx - dy?

0

Share on other sites

Look at the Wikipedia link http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

OP seems to have taken it almost verbatim from the last one in there (under the "Simplification" title). Which also explains the "while (true)" block, since that Wiki pseudocode doesn't has conditionals in the loop either.

0

Share on other sites

Hmm ok then, they are all integers then. So get rid of the floats.

It also says there are 8 cases to consider as well.

However, as mentioned above this is only for the first octant. This means there are eight possible cases to consider. The simplest way to extend the same algorithm, if implemented in hardware, is to flip the co-ordinate system on the input and output of the single-octant drawer.

0

Share on other sites

The error from the line is still using floats .

What operation in the original code produces something that is not an integer?

If you read the code which was originally posted you would have see the use of floats and not have asked.

I am rather confused. Are you saying that the code mutated? The code in the first post (which doesn't seem to have been altered) uses the type float' but none of the operations can possibly result in a value that doesn't represent an integer. If you disagree with this, please explain what operation produces something that is not an integer.

public static boolean solidSpace (int x0, int y0, int x1, int y1)
{
float dx = Math.abs(x1-x0);
float dy = Math.abs(y1-y0);

float err = dx-dy;

while (true)
{

float e2 = 2*err;
if (e2 > -dy)
{
err -= dy;

}
if (e2 < dx)
{
err += dx;
}
}
}


The code above is from the original post with only the parts relating to floating point numbers left.  Subtracting 2 integers does result in an integer but the result is then placed into a floating point number which will get converted into a floating point number.

Rereading what you have said, you asked what in the original code does not use floats and I have shown which parts of the code does use floating points. I think what you meant that floating points are not needed as all the maths involved can be represented with integer maths.

Edited by seedy
0

Share on other sites

Also, why are you using `float' at all? All your numbers are integers...

This is the comment that started the whole argument between us. I stand by that comment. If you don't know what "integer" means (it's a notion in Math, not programming), you might have misunderstood.
0

Share on other sites

Using all integers works fine, no floats required. But it did not increase the speed of the function at all. Mather fact, the function is actually fast, taking about 10000-15000 ns to complete.

I thought it was lagging but the issue was not in that function. Thanks for all the help anyway!

0

Create an account

Register a new account