How can I find the euclidean "zone" that a point on a 2D graph falls on?

Question

I'm trying to speed up my A* implementation (really bad lag just at 10x10 grid!) and the worst performance hit is likely coming from this function:

public Vector2 CoordsToIndex(Vector2 coords)
{
    for (int i = 0; i < mapCols; ++i)
    {
            for (int j = 0; j < mapRows; ++j)
            {
                if (coords.X >= i * map[0, 0].length &&
                    coords.X < i * map[0, 0].length + map[0, 0].length)
                {
                    indexi = i;
                }
                if (coords.Y >= j * map[0, 0].height &&
                    coords.Y < j * map[0, 0].height + map[0, 0].height)
                {
                    indexj = j;
                }
            }
    }
return new Vector2(indexi, indexj);
}

My original implementation of it isn't quite right, but if I can get this working instead it will speed things up a lot (I use this function constantly):

// The below math isn't quite right
indexi = (int)((coords.X - (map[0, 0].length / 2)) / map[0, 0].length) - 1;
indexj = (int)((coords.Y - (map[0, 0].height / 2)) / map[0, 0].height) - 1;

if (indexi < 0)
{
    indexi = 0;
}

if (indexj < 0)
{
    indexj = 0;
}

map[0, 0].length is the length of the tile, and map[0, 0].height is the height of the tile. All tiles are uniform.

It has to be possible to come up with a formula to calculate this but I'm not really certain as to what it would be. Any pointers/help/answers would be appreciated!

EDIT: Er...actually I think the problem might be subtracting the length or height divided by two. That's fine for tile nodes since I store their position as the center of the tile, but for this it would give the wrong tile back...maybe that's the problem...checking.

EDIT: Ah..it's that AND remove the -1. Man I get so confused, funny how I spent about two hours last night totally confused by this and then seconds after finally posting for help the answer comes to me in a flash.

SOLUTION:

public Vector2 CoordsToIndex(Vector2 coords)
{
    int indexi = (int)(coords.X / map[0, 0].length);
    int indexj = (int)(coords.Y / map[0, 0].height);

    return new Vector2(indexi, indexj);
}

That looks so much better.

Give some more info: Do you need to guess in which tile is the point? Are all the tiles the same size or not? Do all the columns have the same width or not? Do all the rows have the same size or not? Without this info it's hard to help you. — JotaBe, Mar 21 '12 at 18:50
@JotaBe based on the OP's original code it seems that all rows have the same size (and similarly for columns) — Attila, Mar 21 '12 at 18:52
Yes that's correct, the length can vary from the height but each tile has the exact same length or height as the rest of the tiles. The goal was to find the tile that contained the point coords. — Purebe, Mar 21 '12 at 18:55
If it's the same height and width for all tiles, remove it from each array item, and keep it in separate variables. If you really use it many times, it will somewhat improve performance, as you won't have to store it NxM times. It is also less confussing. — JotaBe, Mar 21 '12 at 18:57
That's a good point, I'm also trying to make the code easier to read so that's a double benefit. Thanks! — Purebe, Mar 21 '12 at 19:04

Sam DeHaan · Accepted Answer · 2012-03-21T18:59:40.850

3

Well, the short and simple answer:

indexi = (int)(coords.X/map[0,0].length)
indexj = (int)(coords.Y/map[0,0].height)

EDIT: Of course, OP edits post with almost this answer before I post this. /facepalm

edited Mar 21 '12 at 18:59

answered Mar 21 '12 at 18:51

Sam DeHaan

10,246
2
40
48

Sorry! I'm running on no sleep and a bit deprived of making sense right now. – Purebe Mar 21 '12 at 18:53
1

coords is a Vector2 which are two floats, and length and height are two floats. Casting to int (has to be explicit in C#) truncates (from my observations). So casting to double in theory would be a slow-down I think, although I'm interested in finding if the (int) cast actually truncates or if I'd be safer with a floor, good call! – Purebe Mar 21 '12 at 18:57
@Purebe Ah, if coords is a Vector of floats, then yeah, you should be fine. – Sam DeHaan Mar 21 '12 at 18:58
(http://stackoverflow.com/questions/8911440/strange-behavior-when-casting-a-float-to-int-in-c-sharp) - It appears C# does in fact truncate float and double values that are explicitly cast to int. Good to know! – Purebe Mar 21 '12 at 19:01

score 1 · Answer 2 · answered Mar 21 '12 at 18:48

How about this:

for (int i = 0; i < mapCols; ++i) 
{ 
   if (coords.X >= i * map[0, 0].length && 
       coords.X < i * map[0, 0].length + map[0, 0].length) 
   { 
     indexi = i;
     break; // no need to continue the loop
   } 
} 
for (int j = 0; j < mapRows; ++j) 
{ 
  if (coords.Y >= j * map[0, 0].height && 
      coords.Y < j * map[0, 0].height + map[0, 0].height) 
  { 
    indexj = j; 
    break; // no need to continue the loop
  } 
}

Note that in your original code you are looping through every single cell to find the row and the column, when you only need to loop through the rows to find the row index (and similarly for column). Thus instead of 100 comparisons, now you have 20 (at most).

EDIT: And of course your own solution of

int indexi = (int)(coords.X / map[0, 0].length); 
int indexj = (int)(coords.Y / map[0, 0].height);

is way more optimal :)

Yeah I'm happy with it right now (the performance is fine now) but that would have been a good boost too. — Purebe, Mar 21 '12 at 18:53

How can I find the euclidean "zone" that a point on a 2D graph falls on?

2 Answers2