void DFS(Sprite* selectedSprite)
{
spriteList = g_pGame->GetSprites();
Sprite* firstSprite = selectedSprite;
RECT comparePos = firstSprite->GetPosition();
Search(comparePos, firstSprite);
// While all adjacent tiles haven't been deleted
while (matchedSprites.size() > 0)
{
matchedSprites.erase(matchedSprites.begin());
comparePos = matchedSprites.front()->GetPosition();
Search(comparePos, matchedSprites.front());
}
}
void Search(RECT compare, Sprite* firstSprite)
{
RECT oldRect = compare;
RECT tempRect = oldRect;
RECT newRect;
Sprite* theFirst = firstSprite;
vector<Sprite*> tempSprites;
//tempSprites.push_back(theFirst);
tempRect.left -= 25;
for (spriteIter = spriteList.begin(); spriteIter != spriteList.end(); ++spriteIter)
{
newRect = (*spriteIter)->GetPosition();
if ((newRect.left == tempRect.left) && (newRect.top == tempRect.top)
&& (*spriteIter)->GetBitmap() == firstSprite->GetBitmap())
{
tempSprites.push_back((*spriteIter));
}
}
tempRect = oldRect;
tempRect.top -= 25;
for (spriteIter = spriteList.begin(); spriteIter != spriteList.end(); ++spriteIter)
{
newRect = (*spriteIter)->GetPosition();
if ((newRect.left == tempRect.left) && (newRect.top == tempRect.top)
&& (*spriteIter)->GetBitmap() == firstSprite->GetBitmap())
{
tempSprites.push_back((*spriteIter));
}
}
//tempRect = oldRect;
//tempRect.right += 25;
//for (spriteIter = spriteList.begin(); spriteIter != spriteList.end(); ++spriteIter)
//{
// newRect = (*spriteIter)->GetPosition();
// if ((newRect.right == tempRect.right) && (newRect.top == tempRect.top)
// && (*spriteIter)->GetBitmap() == firstSprite->GetBitmap())
// {
// tempSprites.push_back((*spriteIter));
// }
//}
//tempRect = oldRect;
//tempRect.bottom += 25;
//for (spriteIter = spriteList.begin(); spriteIter != spriteList.end(); ++spriteIter)
//{
// newRect = (*spriteIter)->GetPosition();
// if ((newRect.right == tempRect.right) && (newRect.bottom == tempRect.bottom)
// && (*spriteIter)->GetBitmap() == firstSprite->GetBitmap())
// {
// tempSprites.push_back((*spriteIter));
// }
//}
matchedSprites.assign(tempSprites.begin(), tempSprites.end());
for (spriteIter = matchedSprites.begin(); spriteIter != matchedSprites.end(); ++spriteIter)
{
(*spriteIter)->SetHidden(TRUE);
}
tempSprites.clear();
InvalidateRect(g_pGame->GetWindow(), NULL, FALSE);
}
Problem With Depth-First Algorithm
Author
I'm working with a depth-first search but it crashes my game (puzzle-match style) when I try to search to the right and bottom (also when I try to add the first tile selected). I offset the original tiles RECT coordinates by 25 (the standard tile size) to check each time, and while it works for the left and top, it crashes with the right and bottom. I've commented out the parts that crash it.
Did you run this through a debugger already? What did it tell you?
// Bytheway, DFS is an awfully undescriptive function name... consider giving it a proper name to avoid confusion later - and now. What exactly is it supposed to do? Also, it looks like you're using quite a few global variabeles, and you're altering them in various parts of the program. This makes it harder to track down bugs, because it could be caused in any of these places. Consider only exposing variabeles to the code that really needs to know about it.
// Bytheway, DFS is an awfully undescriptive function name... consider giving it a proper name to avoid confusion later - and now. What exactly is it supposed to do? Also, it looks like you're using quite a few global variabeles, and you're altering them in various parts of the program. This makes it harder to track down bugs, because it could be caused in any of these places. Consider only exposing variabeles to the code that really needs to know about it.
We can go about the search much more simply. Just go through the list once. If the bitmap doesn't match, we can skip that one. Otherwise, check if its coordinates are any of the four valid sets. Also, you can consistently check just 'left' and 'top' members for that (I assume your sprites are all the same size, since they're presumably in a grid, since you're doing this kind of DFS).
Also, there is no point to 'clear'ing the tempSprites at the end of the function. Vectors clean up after themselves when they are destructed, which happens automatically when they fall out of scope. (If you .clear() matchedSprites in the destructor of whatever class it is you're in, or some global matchedSprites at the end of the game, that's useless too.)
Now, here's the problem: if you search to the left, and find something, you put it in the matchedSprites. The while-loop will eventually come up to that sprite, and it will, among other directions, search to the right. Thus it finds the original block. That block comes up again, and the process repeats - indefinitely.
What you need to do, conceptually, is keep the matches in two lists: those which you still need to process, and those which have already been processed. When you're about to process something, check if it's in the already-processed list, and skip it if so. However, you don't really need to search the already-processed list like that every time. Instead, keep a grid of "flags", the same size as the sprite grid, and use it to "mark" places you've already looked. But actually, it appears we already have a workable "flag": the 'hidden' status of the Sprite.
Also, this algorithm isn't DFS; it's flood-fill.
Also, a bunch more random cleanups. Please study the code carefully.
Also, there is no point to 'clear'ing the tempSprites at the end of the function. Vectors clean up after themselves when they are destructed, which happens automatically when they fall out of scope. (If you .clear() matchedSprites in the destructor of whatever class it is you're in, or some global matchedSprites at the end of the game, that's useless too.)
Now, here's the problem: if you search to the left, and find something, you put it in the matchedSprites. The while-loop will eventually come up to that sprite, and it will, among other directions, search to the right. Thus it finds the original block. That block comes up again, and the process repeats - indefinitely.
What you need to do, conceptually, is keep the matches in two lists: those which you still need to process, and those which have already been processed. When you're about to process something, check if it's in the already-processed list, and skip it if so. However, you don't really need to search the already-processed list like that every time. Instead, keep a grid of "flags", the same size as the sprite grid, and use it to "mark" places you've already looked. But actually, it appears we already have a workable "flag": the 'hidden' status of the Sprite.
Also, this algorithm isn't DFS; it's flood-fill.
Also, a bunch more random cleanups. Please study the code carefully.
bool Sprite::sameBitmap(Sprite* other) { // You might substitute the function calls here for direct member accesses. return GetBitmap() == other->GetBitmap();}bool Sprite::isAt(int left, int top) { return this->left == left && this->top == top;}// I make the Search a member function, so that instead of the 'current'// parameter we can use 'this', and instead of pulling out the rectangle// coordinates explicitly with getPosition(), we have direct access to them.// I'm assuming matchedSprites and spriteList live somewhere else, so I pass// them in.void Sprite::Search(vector<Sprite*>& matchedSprites, vector<Sprite*>& spriteList) { // Get left and top of the current sprite. int left = GetPosition().left; int top = GetPosition().top; // or just get the members, if possible // We want to append our matches to the matchedSprites, instead of replacing // them. There's no point in accumulating them in a temporary vector first. // But we only want to add sprites that weren't already hidden; the // already-hidden ones have been processed already. for (vector<Sprite*>::iterator it = spriteList.begin(); it != spriteList.end(); ++it) { Sprite* s = *it; if (!s->sameBitmap(current)) { continue; } // who cares where this one is; it doesn't match if (s->GetHidden()) { continue; } // we already looked at this one; don't put it back in the processing list if (s->isAt(left - 25, top) || s->isAt(left + 25, top) || s->isAt(left, top - 25) || s->isAt(left, top + 25)) { // is it adjacent? matchedSprites.push_back(s); // We can hide them as we add them. Notice that C++ has a real boolean // type; please use it for your own stuff whereever possible instead of // stupid TRUE and FALSE hacks. s->SetHidden(true); } }}// There should only be one InvalidateRect call for the entire flood-fill// process, if you're going to pass the screen rect for that...void floodFill(Sprite* start) { std::vector<Sprite*> matchedSprites; // why use a global? // Instead of handling the first sprite specially, just put it into the // container, and let the loop handle it. matchedSprites.push_back(start); // You can directly check a container for emptiness: while (!matchedSprites.empty()) { // It doesn't matter what order you process the matchedSprites in, so // take them from the end instead - it's faster for vectors (when you remove // from not-the-end, everything after the removed element has to be // "shifted" down. Sprite* s = matchedSprites.back(); matchedSprites.pop_back(); s->Search(matchedSprites, g_pGame->GetSprites()); }}
Author
Thanks! That definitely looks a lot better than my scrambled mess (maybe you could recommend a good book on OOP/OOD). Only problem I'm having is a compiler error:
Main.cpp In function `void floodFill(Sprite*)':
Main.cpp no matching function for call to `Sprite::Search(std::vector<Sprite*, std::allocator<Sprite*> >&, std::vector<Sprite*, std::allocator<Sprite*> >)'
note C:\...\Sprite.h:62 candidates are: void Sprite::Search(std::vector<Sprite*, std::allocator<Sprite*> >&, std::vector<Sprite*, std::allocator<Sprite*> >&)
Main.cpp In function `void floodFill(Sprite*)':
Main.cpp no matching function for call to `Sprite::Search(std::vector<Sprite*, std::allocator<Sprite*> >&, std::vector<Sprite*, std::allocator<Sprite*> >)'
note C:\...\Sprite.h:62 candidates are: void Sprite::Search(std::vector<Sprite*, std::allocator<Sprite*> >&, std::vector<Sprite*, std::allocator<Sprite*> >&)
Author
I've tried changing around some parameters, to pointers and references but still can't figure it out.
You've not posted the code for whatever you're passing into that function, but whatever it's returning is not of the type you need. Perhaps it returns a temporary and it doesn't want to take a reference to it, or vice versa. I'm not too good with that corner of the language, so just play around with it. Try reading the value into a temporary first perhaps.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
