Advanced Question Using recursion to determine if vessel is docked

[Zatnikitelman]

I have an interesting situation with an addon I'm developing. Basically, I need to determine if a particular vessel is in a docked superstructure in order to send messages to it. Originally, I had planned to make a list of vessels in the superstructure at simulation start, and then update that during docking events during runtime. However, that won't work unless one of my vessels is the one being docked to. If I have:

MyVessel---othervessel-><-othervessel---MyVessel

Neither of my vessels would locate each other, as their clbkDockEvents would not be called if the two "othervessels" docked. So now my solution is to just recurse through the "tree" and find the vessel when needed. The problem isn't the recursion itself, the problem is how do I terminate the recursion. My basic recursive function is like this:

//this line is how I start it
map<char,bool> visited;
foreach dock in this
   docksearch(GetDockStatus(dock),visited)


docksearch(OBJHANDLE, map<char*,bool> &v)
   if(!v[ves->GetName()]) //if I haven't visited the vessel before
      v[ves->GetName()] = true;
      if(!_strnicmp(ves->GetName(),searchstring))
         ves->clbkGeneric(themessage); //need to terminate after this
   foreach dock in ves
      docksearch(GetDockStatus(dock),v)

This would work, but if it found the target vessel in short order, it would end up recursing unnecessarily through the entire rest of the superstructure, and if possible, I'd like to terminate it after a successful find. However, even if I changed the function to return a bool or something, it would still only work once, and I would still end up going through multiple other "iterations."
Given that this would probably be run pretty infrequently now, I guess I can tolerate the wasted cycles, but with a large number of docked ships, I imagine it would be pretty slow going through them all.
Does anyone have any suggestions on how to terminate a recursive function like this?
Thanks,
Matt

 

[Hielor]

Make docksearch return a value--in the simplest case, true/false. If it finds something return true, if not return false.

Then:

...
      if(!_strnicmp(ves->GetName(),searchstring))
         ves->clbkGeneric(themessage); //need to terminate after this
else
   foreach dock in ves
{
if (docksearch(GetDockStatus(dock),v))
return true;
}
...

Look up "base case" with respect to recursive programming.

 

[jedidia]

In the following example I assume that you are looking for a vessel in the stack with the name == searchstring, which is what I took out of your partly pseudocode example:

bool docksearch(OBJHANDLE, map<char*,bool> &v)
   if(!v[ves->GetName()]) //if I haven't visited the vessel before   
      v[ves->GetName()] = true;
      if(!_strnicmp(ves->GetName(),searchstring))
     {
         ves->clbkGeneric(themessage); //need to terminate after this
        return true;
     }

   foreach dock in ves
     if (docksearch(GetDockStatus(dock),v)) return true;

This way, if you call docksearch, it will return true if the vessel with the name searchstring is anywhere in the stack, and it will stop recursing as soon as it found it.

 

[Zatnikitelman]

Thanks Hielor and jedidia, your methodologies should work. I haven't been able to test it just yet, but the logic is sound. I'm used to doing recursive functions where on return it is part of an expression so it changes constantly as it moves back up the stack, but not one like this.

 

[Enjo]

For larger problems you have to resort to a while loop, popping std::stack, or risk stack overflow.