Looking for a nearest free point in a 2D table
Author
Hi!
I have a table filled with TRUE-s and FALSE-s and I need to find
a nearest FALSE for some point in the table. How do I do it?
Example:
Table:
0 1 0 0
1 1 1 1
0 1 1 1
1 1 1 1
Coordinates for the starting point 3, 3 (x, y) == 1 (TRUE)
How do I find the nearest FALSE for this coordinate in the table?
Thanks for any useful responses!
Tarmo
You can start by defining ''nearest''
What are the rules?
Magmai Kai Holmlor
- The disgruntled & disillusioned
What are the rules?
Magmai Kai Holmlor
- The disgruntled & disillusioned
I think he means distance-wise. He wants to find the nearest, as in a linear search algo that gets the nearest false. So if he has the table:
X012345
Y
0 111000
1 110110
2 111101
3 001101
4 111001
5 000001
And he''s at (0,0), he wants to know how to find the nearest, which would be (2,1). I think that''s what he means...
X012345
Y
0 111000
1 110110
2 111101
3 001101
4 111001
5 000001
And he''s at (0,0), he wants to know how to find the nearest, which would be (2,1). I think that''s what he means...
- In absolute terms you''d make a list of all the FALSE co-ordinates(at the beginning of the level or map) and then loop through them doing a Pythagorean test
dist = (falsex-startx)^2 + (falsey-starty)^2
and record the minimum (no need to do the root)
- A short-cut would be to chop up the array into sub-arrays that yield whether there is a FALSE. You''d check the sub-array you''re in and the sub-arrays around you. Or Quad-trees
- Create a search algorithm: Check the co-orinates 1 away from the startx, statty. Then 2 away, etc.
3333333
3222223
3211123
3210123
3211123
3222223
3333333
- it also really depends on the density of the FALSEs and whether they have to checked every frame, whether they are changing all the time or are static.
You might need to do a combination of some of the above.
ZoomBoy
Developing a iso-tile 2D RPG with skills, weapons, and adventure. See my old Hex-Tile RPG GAME, character editor, diary, 3D Art resources at Check out my web-site
dist = (falsex-startx)^2 + (falsey-starty)^2
and record the minimum (no need to do the root)
- A short-cut would be to chop up the array into sub-arrays that yield whether there is a FALSE. You''d check the sub-array you''re in and the sub-arrays around you. Or Quad-trees
- Create a search algorithm: Check the co-orinates 1 away from the startx, statty. Then 2 away, etc.
3333333
3222223
3211123
3210123
3211123
3222223
3333333
- it also really depends on the density of the FALSEs and whether they have to checked every frame, whether they are changing all the time or are static.
You might need to do a combination of some of the above.
ZoomBoy
Developing a iso-tile 2D RPG with skills, weapons, and adventure. See my old Hex-Tile RPG GAME, character editor, diary, 3D Art resources at Check out my web-site
If its a distance dependant, u can do the following:
bool found;
int dist;
while(!found)
{
for(int c1=startx-1;c1<=startx+1;c1++)
for(int c2=starty-1;c2<=starty+1;c2++)
if(c1!=startx && c2!=starty)
{
if(array[c1][c2]==true)
{
//do ur stuff, e.g.:
dist=sqrt((c1-startx)^2+(c2-starty)^2);
found=true;
}
}
}
}
cout<
Pseudocode:
For example, u want to find closest true:
u search all surrounding nodes, e.g.:
0 0 0
0 s 0
1 0 0
so, with use of above algorithm it will start at top left corner and search all surrounding "nodes" until it founds the true, or bottom left "node".
Of course, my algorithm does only one circle of search around start position, but u can easily upgrade it to required one..
Good luck!
"Do we need us?"
bool found;
int dist;
while(!found)
{
for(int c1=startx-1;c1<=startx+1;c1++)
for(int c2=starty-1;c2<=starty+1;c2++)
if(c1!=startx && c2!=starty)
{
if(array[c1][c2]==true)
{
//do ur stuff, e.g.:
dist=sqrt((c1-startx)^2+(c2-starty)^2);
found=true;
}
}
}
}
cout<
Pseudocode:
For example, u want to find closest true:
u search all surrounding nodes, e.g.:
0 0 0
0 s 0
1 0 0
so, with use of above algorithm it will start at top left corner and search all surrounding "nodes" until it founds the true, or bottom left "node".
Of course, my algorithm does only one circle of search around start position, but u can easily upgrade it to required one..
Good luck!
"Do we need us?"
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
