- Home /
Find Next Node - recursive algorithm
Hi,
I am trying to make player being able to move on next available point. For Example Below photo.
Player Position is the blue one.
Red Nodes are corners and player can not move there , but must pass from corners position to reach grey nodes
Player can go to next available grey node
Each node has a list which contains Neightbor_Corners [RED] and NeightBoor_Targets[Grey]
I don't care about distance of each road the only think I need is to now if its reachable from player
I think solution is to run recursive method from start node and save on a list available next nodes, as long as waypoints.
Any idea? I am bit stacked and not so clever to solve this recursive problem :)
Update Ok let me try to explain with a new picture.
Have in mind that every node (grey or red) have 2 different list one for Grey and one for Red Neightboor nodes. Square are positions that player can go.
Player can go to next position only if ;
its connected directly with its current position (example 0 ->[1])
Its not connected directly but only through red spherer/corners. (example 0->6->7->8>[5])
Player can not reach position if ;
It has first to pass from grey node in order to reach target (example 0->6->7->[4] x->[9])
In this example player is on blue spot and available positions are 2,3,5,4,1.
I hope it helps a little bit. Please feel free to ask me a question
Update Here is the function that finds available positions.Currently, I am trying to find how to save path using below recursive method
public void FindTargets(List<GameObject> targets, bool firstTry)
{
Debug.Log("***************************");
//firstTry bool in order not to terminate first check on player's position node
if (!isItCorner && !firstTry)
{
targets.Add(gameObject);
GetComponent<MeshRenderer>().material.color = Color.yellow;
Debug.Log("exit function");
return;
}
else
{
//Bool in order not to check again already checked corners
if(isItCorner)
{
Havepassed = true;
}
Debug.Log("Non - exit function");
if (CornerLists.Count==0 && TargetLists.Count == 0)
{
Debug.Log("1 function,Does nothing");
return;
}
else if(CornerLists.Count > 0 && TargetLists.Count == 0)
{
foreach (GameObject corner in CornerLists)
{
if (!corner.GetComponent<Beacon>().Havepassed)
{
corner.GetComponent<Beacon>().FindTargets(targets, false);
}
}
Debug.Log("2 function");
}
else if (CornerLists.Count > 0 && TargetLists.Count > 0)
{
foreach (GameObject target in TargetLists)
{
if (!targets.Contains(target))
{
targets.Add(target);
target.GetComponent<MeshRenderer>().material.color = Color.yellow;
}
}
foreach (GameObject corner in CornerLists)
{
if(!corner.GetComponent<Beacon>().Havepassed)
{
corner.GetComponent<Beacon>().FindTargets(targets, false);
}
}
Debug.Log("3 function");
}
else if (CornerLists.Count == 0 && TargetLists.Count > 0)
{
Debug.Log("4 function,Does nothing");
foreach (GameObject target in TargetLists)
{
if (!targets.Contains(target))
{
targets.Add(target);
target.GetComponent<MeshRenderer>().material.color = Color.yellow;
}
}
}
}
}
Ok let me try to explain with a new picture.
Have in $$anonymous$$d that every node (grey or red) have 2 different list one for Grey and one for Red Neightboor nodes. Square are positions that player can go.
Player can go to next position only if ;
its connected directly with its current position (example 0 ->[1])
Its not connected directly but only through red spherer/corners. (example 0->6->7->8>[5])
Player can not reach position if ;
It has first to pass from grey node in order to reach target (example 0->6->7->[4] x->[9])
In this example player is on blue spot and available positions are 2,3,5,4,1. I hope it helps a little bit. Please feel free to ask me a question
Updated post with method to find next available. Any idea on how to save the path. I am thinking about having a dictionary with Gameobject Node, List Path. Any idead on how to save that on the above method?
Answer by elkawee · Nov 22, 2021 at 06:10 PM
If i understand your rule set correctly, use a "Depth First Search" algorithm to determine the set of all reachable red nodes.
Set of reachable grey nodes is ( pseudo code ) :
s = Set( playerNode.greyNeighbors )
foreach ( r in reachable_red_nodes ) {
s = s.Union( r.greyNeighbors )
}