# Finding wall point

This topic is 2075 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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

##### 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

##### 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?

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

##### 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?

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

• 21
• 13
• 9
• 17
• 13