Archived

This topic is now archived and is closed to further replies.

Looking for a nearest free point in a 2D table

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
- 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

Share this post


Link to post
Share on other sites
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?"

Share this post


Link to post
Share on other sites