Jump to content
  • Advertisement
Sign in to follow this  
Last Attacker

Find closest open spot

This topic is 4831 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

[EDITIED] Hi, does anyone know a fast algorithm that allows you to find the closest open spot in a matrix from a spicific point? If you don't know wht I mean, picture this: Remember Command & Conquer 95? The tiberium? You have a patch and every amount of time new teberium sprouts up to the closest available location attached to the patch. The center of the patch is for example the point and the new tiberium that sprouts up, should be part of the patch but to the closest available poisition. Get it? ;) So, anyone know of one? Thanks guys!

Share this post


Link to post
Share on other sites
Advertisement
How fast it has to be? Or, why does it need to be fast? How big the matrix is? How many times per second are you going to end up calling the routine? Thousand? Million? A hundred million?

My point is that it might not be wise to waste too much time trying to come up with an ultra-fast algorithm if a brute-force method might suffice instead. A profiler can tell you whether that is the case or not (of course, if you are already profiled and sure that you need ultra performance, my apologies :)

EDIT: One approach might be storing a set of pointers/references to the empty cells, sorted by the distance to the center. When you need to fill a cell, just pop the lowest element from the set, and when a full cell is emptied by someone, insert it into the list.

Share this post


Link to post
Share on other sites
No, I mean a sortof an optimized method. For our project, I have a 2D array of heights (width and height can vary). Now it can be populated by holes (little square sprites). When I copy and paste those holes, I want to paste them at the closest available location. My matrix won't help much its just, I'm using the distances and vector positions to obtain the holes.

Here's the very inefficient algo I'm using:


bool GlcTerrain::findClosestAvailableSpace(float &posX, float &posZ)
{
Vector3f pos(posX, 0.0f, posZ);

if(!mHoleManager->findNearestHole(pos, 3.0f))
{
return true;
}

register int i;

int prevSize = 0;
int size;


float temp1;
float temp2;

//Check for about 20 layers to find an
//open position.
for(size = 1; size < 21; ++size)
{
temp2 = size * mGrid->getCellY();

//Check at the upper & lower part of the current
//layer.
for(i = -size; i <= size; ++i)
{
temp1 = i * mGrid->getCellX();

pos.set(posX + temp1, 0.0f, posZ + temp2);

mGrid->snapToGrid(pos);

if(!mHoleManager->findNearestHole(pos, 3.0f))
{
posX += temp1;
posZ += temp2;

mGrid->snapToGrid(posX, posZ);

return true;
}

pos.set(posX + temp1, 0.0f, posZ - temp2);

mGrid->snapToGrid(pos);

if(!mHoleManager->findNearestHole(pos, 3.0f))
{
posX += temp1;
posZ -= temp2;

mGrid->snapToGrid(posX, posZ);

return true;
}
}

temp2 = size * mGrid->getCellX();

//Check the left & right part of the current
//layer.
for(i = -prevSize; i <= prevSize; ++i)
{
temp1 = i * mGrid->getCellY();

pos.set(posX - temp2, 0.0f, posZ + temp1);

mGrid->snapToGrid(pos);

if(!mHoleManager->findNearestHole(pos, 3.0f))
{
posX -= temp2;
posZ += temp1;

mGrid->snapToGrid(posX, posZ);

return true;
}

pos.set(posX + temp2, 0.0f, posZ + temp1);

mGrid->snapToGrid(pos);

if(!mHoleManager->findNearestHole(pos, 3.0f))
{
posX += temp2;
posZ += temp1;

mGrid->snapToGrid(posX, posZ);

return true;
}
}

prevSize = size;
}

return false;
}




'mGrid' is my grid to snap a position onto the grid specifications (like VB's)
'findNearestHole(pos, 3.0f)' returns a hole if its found within that distance and position.

What my algo does is this:
it takes the position, and scans the line above it like so:
XXX
_O

(X is matrix cell to be scanned)
(O is position to scan from)
(_ just an open line because the forum deletes the additional whitespaces)

Then it does the same with the left, right and bottom one.
Now by the 2nd, 3rd, 4th, etc. it scans like this:
Lets say the 3rd iteration:
XXXXXXX
_HHHHH
__HHH
___O

X
XH
XHHO
XH
X

etc.

(X is matrix cell to be scanned)
(H is cell already scanned from prev. iteration)
(O is position to scan from)
(_ just an open line because the forum deletes the additional whitespaces)

So I'm calling this method only when the user calls the paste method, so its not called 100,000,000 +/- a second ;p but out of curiosity, I would like to know what you guys whould have done to solve the problem a bit more efficiently.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!