koobas.hobune.stream
Recursive function that allows me to do stuff in the meantime
Hello,
I need the player to be able to use an hint if he wants to solve some puzzle game and then I figured out that to explore the possibilities he have and to find a solution if it exist I have to do that trough a recursive function like this one:
bool MyRecursiveFunction()
{
// some tests and adds to a List of possibilities
if(MyRecursiveFunction())
//do stuff
else
//other stuff
}
I did that already to found a solution of my puzzles when I need to test them but now I need that to be available for players I wonder how the same thing can occurs without freezing the engine. Then I could put some animation while it is searching and put a cancel button. I thought I could use some coroutine to do that but since my function needs to return a bool i have no clue of what I should do.
Any help please?
Since I thought it was not possible to use yield in a recursive form I managed after some thinking to do my exploration of possibilities without recursivity like this:
IEnumerator HintCoroutine()
{
remainingSquares = new List<int>();
idListCopy = new List<int>();
possibleMovesForHints = new List<List<int>>();
foreach(int sq in idList)
{
idListCopy.Add(sq);
}
nbMovesForHints=squaresButtonsID.Count-idListCopy.Count;
for(int i=0; i<=nbMovesForHints; i++)
{
possibleMovesForHints.Add(new List<int>());
}
bool loop = true;
int it=0;
List<int>iterators = new List<int>();
for(int i=0; i<=nbMovesForHints;i++)
{
iterators.Add(0);
}
while(loop)
{
GetPossibleMovesForHints(it);
if(possibleMovesForHints[it].Count==0)
{
if(idListCopy.Count==squaresButtonsID.Count)
{
loop=false;
StartCoroutine(BlinkSquare(possibleMovesForHints[0][iterators[0]]));
}
else
{
if(idListCopy.Count==idList.Count)
{
loop = false;
NoSolution();
}
else
{
for(int i=1; i<=it+1; i++)
{
if(it-i<0)
{
NoSolution();
loop = false;
break;
}
else if(iterators[it-i]!=possibleMovesForHints[it-i].Count-1)
{
iterators[it-i]++;
it=it-i;
for(int j=1; j<=i; j++)
{
idListCopy.RemoveAt(idListCopy.Count-1);
}
break;
}
}
if(iterators[0]==possibleMovesForHints[0].Count-1 && it==0)
{
NoSolution();
loop = false;
}
}
}
}
else if(iterators[it]<possibleMovesForHints[it].Count)
{
idListCopy.Add(possibleMovesForHints[it][iterators[it]]);
it++;
iterators[it]=0;
}
yield return null;
}
}
One possibility would be to run it on a separate thread (pretty nice tutorial here ), and have that trigger a callback on the main thread when done. That would probably be the best if you don't rely heavily on some aspects of the UnityEngine namespace like physics, but this can be a bit tricky, and if it does need access to things like raycasting, then it's not an option.
An alternative would be coroutines like you said:
//kind of hacky, but since we can't pass in 'out' or 'ref' variables into a coroutine, oh well
//another possibility would be using callbacks/delegates, but I didn't feel like getting into that
public bool recursiveResult;
public void StartSearch ()
{
//start the waiting animation loop
//animation.Play();
StartCoroutine(RecursiveFunctionWait());
}
public void FinishSearch ()
{
//stop the waiting animation loop
//animation.Stop();
if(recursiveResult)
{
//full recursion returned true, probably found the solution or whatever
}
else
{
//no solution, or whatever returning false meant before
}
}
private IEnumerator RecursiveFunctionWait ()
{
//basically the same as using yield return StartCoroutine(), but I get the feeling that it's more performance friendly (my coworkers always use this way)
var routine = MyRecursiveFunction();
//basically yields whenever the one of the recursion levels does until it's done and would have returned a value if called normally
while (routine.MoveNext())
yield return null;
FinishSearch();
}
private IEnumerator MyRecursiveFunction ()
{
// some tests and adds to a List of possibilities
//starts the next recursion level
var routine = MyRecursiveFunction();
while (routine.MoveNext())
yield return null;
//somewhere in these you'll want to add the "yield return null;" lines
//probably after about 10 milliseconds have passed since the last yield (around there gives good trade off between responsiveness and speed)
//System.DateTime is usually what I use for this, ex: if(System.DateTime.Now.TimeOfDay.TotalMilliseconds > lastYield + delay)...
if (recursiveResult)
{
//do stuff
}
else
{
//other stuff
}
}
It would kind of nice to see the actually recursive function for reference though. Anyways, I hope this helps, and good luck!
That seems nice althought it's made with plenty things I don't know yet (shame on me) Anyway I did manage to do it in my while loop without recursivity but the next time I need something like that I'll definitely go back to what you said. Thanks!
Not sure why a recursive is needed. Nevertheless you can use Update or a Coroutine. There's not much difference to the user.
void Update()
{
if (MyRecursiveFunction()) {
// do stuff
}
}
IEnumerator MyCoroutine()
{
if (MyRecursiveFunction()) {
// do stuff
}
yield return new WaitForEndOfFrame();
}
I'm trying to use some coroutine right now even if I can't figure out how to use a non recursive function to succeed. In your example here is the problem
IEnumerator $$anonymous$$yCoroutine()
{
if ($$anonymous$$yRecursiveFunction()) {
// do stuff
// problem is the recursive function will call itself after here (that's why it is recursive :P) and will never reach the yield before it ends with a result
}
yield return new WaitForEndOfFrame();
}
Now I need a function that explore all possibilities from a point and then explore all possibilities from all the previous possibilities etc until it reach either to I found it or it can't be done. The recursive form was simple enough to uses but now i'm trying to do it in a single while loop (contained inside the coroutine) I didn't found yet how to make the same process...
Here is what I have so far:
IEnumerator HintCoroutine()
{
//setting some new lists
idListCopy = new List<int>();
possible$$anonymous$$ovesForHints = new List<int>();
//copying the current position of the puzzle
foreach(int sq in idList)
{
idListCopy.Add(sq);
}
bool loop = true;
while(loop)
{
GetPossible$$anonymous$$ovesForHints(); //get the list of possible moves from here
//if no moves can be done
if(possible$$anonymous$$ovesForHints.Count==0)
{
//if the puzzle is solved
if(idListCopy.Count==squaresButtonsID.Count)
{
print ("win");
loop=false;
}
else
{
//if we can't go back anymore and we explored all the possibilities without finding a solution
if(idListCopy.Count==idList.Count)
{
print ("lost");
loop = false;
}
else
{
//here I will need to remove the last entry and pick another one because 0 moves can be done
idListCopy.RemoveAt(idListCopy.Count-1);
}
}
}
else
{
//here I will need to add some move in the idListCopy from the list of possibilities from all the new positions and I still have no clue of how I'll do that not using recursive function
}
if(!loop)
break;
yield return null;
}
}
I'll show you what I'm using for the solver (wich does freeze the engine until it find a solution but I don't care because I'm the only one as programmer to use it)
public void Solve()
{
float startTime = Time.realtimeSinceStartup;
float timeToSolve=0;
solver$$anonymous$$oves = new List<int>();
possible$$anonymous$$ovesForSolver = new List<int>();
remainingSquares = new List<int>();
for(int i=0; i<squaresButtonsID.Count; i++)
{
if(solved && !mustSolveAll)
break;
solver$$anonymous$$oves.Add(squaresButtonsID[i]);
//now begins the recursive function
if(SolverRec())
{
// those lines don't really matter because it will never find it in 1 move
print ("win");
solver$$anonymous$$oves.RemoveAt(solver$$anonymous$$oves.Count-1);
}
else
{
solver$$anonymous$$oves.RemoveAt(solver$$anonymous$$oves.Count-1);
}
}
if(solved)
{
print (possibilities + " way(s) to solve this on " + nbPos + " possibilities - ratio: " + possibilities/nbPos);
}
else
print ("No way to solve this");
timeToSolve = Time.realtimeSinceStartup-startTime;
print ("Solved in: " + timeToSolve + " - " + nb$$anonymous$$oves + " moves analysed");
alreadySolved=true;
}
//the recursive function
bool SolverRec()
{
if(solved && !mustSolveAll)
return false;
nb$$anonymous$$oves++;
//each of the recursive functions will have his own list of possibilities
GetPossible$$anonymous$$ovesForSolver();
List<int> possible$$anonymous$$ovesForSolverRec = new List<int>();
foreach(int p in possible$$anonymous$$ovesForSolver)
{
possible$$anonymous$$ovesForSolverRec.Add(p);
}
if(possible$$anonymous$$ovesForSolverRec.Count==0)
{
if(solver$$anonymous$$oves.Count==squaresButtonsID.Count)
{
nbPos++;
return true;
}
else
{
nbPos++;
return false;
}
}
for(int i=0; i<possible$$anonymous$$ovesForSolverRec.Count; i++)
{
if(solved && !mustSolveAll)
break;
//if some algorithm to accelerate the calculation are used and their results
if((!checkDoubleIsolated && !checkIslands )|| (checkDoubleIsolated && !DoubleIsolated() && !checkIslands) || (!checkDoubleIsolated && checkIslands && !$$anonymous$$anyIslands()) || (checkDoubleIsolated && !DoubleIsolated() && checkIslands && !$$anonymous$$anyIslands()))
{
//we add a move so we can go on and call back the function again
solver$$anonymous$$oves.Add(possible$$anonymous$$ovesForSolverRec[i]);
//here
if(SolverRec())
{
solved=true;
possibilities++;
//then we remove the last move and go to the next one
solver$$anonymous$$oves.RemoveAt(solver$$anonymous$$oves.Count-1);
if(mustSolveAll)
break;
}
else
{
//same here
solver$$anonymous$$oves.RemoveAt(solver$$anonymous$$oves.Count-1);
}
}
}
return false;
}
To say it simply the recursive form allowed me to do lists of possibilities from every possibility recursively. From those list I can then explore all the possibilities with a simple for loop and everytime it can moves further create more lists of possibilites which are used in their own functions. Very easy to use.
But that doesn't allow some yield function.
And I can't see how to do a similar exploration mechanic of possibilities without using a recursive form.
Help!!
