•      Sign In
• Create Account

## Finding wall point

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

23 replies to this topic

### #1P0jahn  Members

305
Like
0Likes
Like

Posted 05 November 2013 - 02:33 PM

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;
}
}
}

### #2Álvaro  Members

20235
Like
0Likes
Like

Posted 05 November 2013 - 02:39 PM

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, 05 November 2013 - 02:41 PM.

### #3P0jahn  Members

305
Like
0Likes
Like

Posted 05 November 2013 - 02:45 PM

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

### #4Álvaro  Members

20235
Like
0Likes
Like

Posted 05 November 2013 - 02:46 PM

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

### #5Álvaro  Members

20235
Like
1Likes
Like

Posted 05 November 2013 - 02:47 PM

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

### #6seedy  Members

122
Like
0Likes
Like

Posted 05 November 2013 - 03:45 PM

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, 05 November 2013 - 03:48 PM.

### #7Álvaro  Members

20235
Like
0Likes
Like

Posted 06 November 2013 - 01:51 AM

The error from the line is still using floats .

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

### #8P0jahn  Members

305
Like
0Likes
Like

Posted 06 November 2013 - 08:37 AM

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.

### #9Hawkblood  Members

950
Like
0Likes
Like

Posted 06 November 2013 - 05:34 PM

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?

### #10MaxDZ8  Members

4976
Like
0Likes
Like

Posted 07 November 2013 - 01:02 AM

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".

Previously "Krohm"

### #11Álvaro  Members

20235
Like
0Likes
Like

Posted 07 November 2013 - 03:42 AM

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.

### #12TheComet  Members

2671
Like
0Likes
Like

Posted 07 November 2013 - 04:07 AM

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, 07 November 2013 - 04:09 AM.

"I would try to find halo source code by bungie best fps engine ever created, u see why call of duty loses speed due to its detail." -- GettingNifty

### #13MaxDZ8  Members

4976
Like
-2Likes
Like

Posted 07 November 2013 - 07:25 AM

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.

Previously "Krohm"

### #14TheChubu  Members

8945
Like
0Likes
Like

Posted 07 November 2013 - 08:20 AM

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.
{
err += minusDy; // Adding minusDy instead of substracting dy.
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, 07 November 2013 - 08:34 AM.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

My journals: dustArtemis ECS framework and Making a Terrain Generator

### #15TheComet  Members

2671
Like
0Likes
Like

Posted 07 November 2013 - 08:59 AM

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.

"I would try to find halo source code by bungie best fps engine ever created, u see why call of duty loses speed due to its detail." -- GettingNifty

### #16seedy  Members

122
Like
0Likes
Like

Posted 07 November 2013 - 04:17 PM

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

### #17seedy  Members

122
Like
-2Likes
Like

Posted 07 November 2013 - 04:20 PM

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.

### #18Álvaro  Members

20235
Like
0Likes
Like

Posted 07 November 2013 - 09:16 PM

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.

### #19Paradigm Shifter  Members

5832
Like
0Likes
Like

Posted 07 November 2013 - 09:28 PM

I the original code correct?

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

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #20TheChubu  Members

8945
Like
0Likes
Like

Posted 08 November 2013 - 05:06 AM

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.

"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

My journals: dustArtemis ECS framework and Making a Terrain Generator

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.