pathNode - a simple routing node script for unity

dabblet.css

/**
 * pathNode - a simple routing node script for unity
 */

background: #4bf;
min-height: 100%;

dabblet.html

<pre>
<code>
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class pathNode : MonoBehaviour
{

    /******************************************************************************
     * **************************************************************************
     * The pathNode
     * 
     * These nodes must be linked together into viable chains in the editor
     * 
     * Once linked the nodes will automatically initialise eachother and build
     * a navigation network where each node knows where to direct a requester
     * 
     * The network is built to find the shortest screen-space route.
     * It does not take into account number of nodes or anything else.
     * 
     * *************************************************************************
     *****************************************************************************/



    public pathNode[] linkedNodes;

    private Dictionary&ltpathNode, float&gt localNodes = new Dictionary&ltpathNode, float&gt();
    private Dictionary&ltpathNode, pathNode&gt nextRouteForAllNodes = new Dictionary&ltpathNode, pathNode&gt();
    private bool initialised = false;
    private Dictionary&ltpathNode, float&gt destinationsThatAlreadyHaveSolutions = new Dictionary&ltpathNode, float&gt();


    //this is just for debugging
    private static int passItOnCounter = 0;

    /******************************************************************************
     * **************************************************************************
     * This section is called from Start
     * It initialises the node
     * It searches down the node chain to build a list of all of the possibile
     * destination nodes, and which is the best localNode to go to to get there.
     * *************************************************************************
     *****************************************************************************/

    // Start is called before the first frame update
    void Start()
    {
        DoInitialise();
        //all the nodes have tried to initialise eachother, so they're ready.


        //now we need to get a list of all of the nodes in the linked network
        List&ltpathNode&gt allLinkedNodes = new List&ltpathNode&gt();
        AddAllNodesToList(ref allLinkedNodes);

        //now find the next step to each of these destinations
        foreach (pathNode aNode in allLinkedNodes)
        {
            //it's us!
            if (aNode == this)
            {
                nextRouteForAllNodes.Add(aNode, aNode);
            }
            else
            {
                //if it's one of our localNodes then just add it
                if (localNodes.ContainsKey(aNode))
                {
                    //the next step is just the destination
                    nextRouteForAllNodes.Add(aNode, aNode);
                }
                else
                {
                    //the destination isnt local, so now we have to get fancy
                    nextRouteForAllNodes.Add(aNode, FindPathToNode(aNode));
                }
            }

        }
    }

    /*******
     * Initialises this node by measurign the distance to all linked nodes
     * It also prompts all linked nodes to do the same.
     * This means that we know all nodes are ready once this method is complete,
     * regardless of the Start sequence order
     *******/
    public void DoInitialise()
    {
        if (!initialised)
        {
            //get the distance to all our local nodes
            foreach (pathNode aNode in linkedNodes)
            {
                localNodes.Add(aNode, (aNode.transform.position - transform.position).magnitude);
                destinationsThatAlreadyHaveSolutions.Add(aNode, (aNode.transform.position - transform.position).magnitude);
                initialised = true;
            }

            //now we're initialised tell the others to as well
            foreach (KeyValuePair&ltpathNode, float&gt otherNode in localNodes)
            {
                otherNode.Key.DoInitialise();
            }
        }
    }

    /******
     * fetches a complete list of all nodes that can be reached
     ******/
    void AddAllNodesToList(ref List&ltpathNode&gt allPathNodes)
    {
        foreach (KeyValuePair&ltpathNode, float&gt aNode in localNodes)
        {
            if (!allPathNodes.Contains(aNode.Key))
            {
                allPathNodes.Add(aNode.Key);
                aNode.Key.AddAllNodesToList(ref allPathNodes);
            }
        }
    }


    /******
     * Searches for the shortest route from self to the destination node
     * returns the next node in that route
     ******/
    private pathNode FindPathToNode(pathNode destinationNode)
    {

        /***
         * We only care about the Next Step in the node chain
         * so we don't actually need to pass the list of nodes down the line
         * So we go to the locals and then just pass a distance value from there
         ***/
        Tuple&ltpathNode, float&gt shortestRoute = new Tuple&ltpathNode, float&gt(null, -1);
        foreach (KeyValuePair&ltpathNode, float&gt aNode in localNodes)
        {
            float bestDistanceForThisLocal = aNode.Key.PassOnDownTheNodeChain(destinationNode, this, aNode.Value);

            //if its the first result
            if (shortestRoute.Item2 == -1)
            {
                shortestRoute = new Tuple&ltpathNode, float&gt(aNode.Key, bestDistanceForThisLocal);
            }
            else
            {
                //is this result shorter than those that came before?
                if (shortestRoute.Item2 &gt bestDistanceForThisLocal)
                {
                    shortestRoute = new Tuple&ltpathNode, float&gt(aNode.Key, bestDistanceForThisLocal);
                }
            }
        }

        //we've found the shortest route, but all we care about is which is the next node on that chain
        return shortestRoute.Item1;
    }

    /************
     * 
     * This method accepts the current path distance,
     * checks if it is linked to the end of the journey
     * if it is then it adds that step on and returns the value
     * if it's not then it adds on each local node distance and 
     * passes it on
     **********/
    private float PassOnDownTheNodeChain(pathNode destinationNode, pathNode previousNode, /*pathNode originNode, */float distanceSoFar)
    {
        //debugging//
        passItOnCounter++;
        Debug.Log("PassOnDownTheNodeChain: " + passItOnCounter + "    distanceSoFar: " + distanceSoFar);
        /////////////

        //first check to see if we already have an answer for this one:    
        float previousDistance;
        if(destinationsThatAlreadyHaveSolutions.TryGetValue(destinationNode, out previousDistance))
        {
            //it already exists in here, return it
            return previousDistance;            
        }

        //it's not here, keep going


        //first add it, but with an invalid distance
        destinationsThatAlreadyHaveSolutions.Add(destinationNode, -1);
        List&ltfloat&gt allRouteDistances = new List&ltfloat&gt();

        /******
         * we're assuming that the destinationsThatAlreadyHaveSolutions list
         * was initialised with the local nodes already, so if we've gotten
         * here then it wasn't one of the locals,  so Pass It On!
         ******/
        foreach (KeyValuePair&ltpathNode, float&gt aNode in localNodes)
        {
            float newDistance = aNode.Key.PassOnDownTheNodeChain(destinationNode, this, (distanceSoFar + aNode.Value));
            if (newDistance != -1)
            {
                //only add valid distances
                allRouteDistances.Add(newDistance + aNode.Value);
            }
        }
        

        /*** 
         * compare all of our returned distances
         * we just return the smallest since that's the quickest possible route from here
         * (we're trusting that the route finding process on each node found the same path)
         * @TODO a very obvious improvement is to store the next node here, rather than
         * checking after the returns.
         ***/

        //if the list is empty then we have no route
        if (!allRouteDistances.Any())
        {
            //remove the invalid entry so that other nodes can try to find the solution
            destinationsThatAlreadyHaveSolutions.Remove(destinationNode);
            return -1;
        }

        float smallestDistance = allRouteDistances.Min();
        destinationsThatAlreadyHaveSolutions[destinationNode] = smallestDistance;
        return smallestDistance;
    }





    /******************************************************************************
     * **************************************************************************
     * This section is called dynamically from gameplay
     * 
     * During gameplay another game element can query this node with a destination
     * and it returns the next step on the route
     * *************************************************************************
     *****************************************************************************/

    public pathNode GetNextStepToDestination(pathNode destination)
    {
        pathNode nextNode;
        nextRouteForAllNodes.TryGetValue(destination, out nextNode);

        return nextNode;
    }
}</code>
</pre>

dabblet.js

// alert('Hello world!');

settings.json

{"view":"split","fontsize":"100","seethrough":"","prefixfree":"1","page":"html"}