Graal Forums - Pathfinder

Graal Forums (https://forums.graalonline.com/forums/index.php)

- NPC Scripting (https://forums.graalonline.com/forums/forumdisplay.php?f=8)

- - Pathfinder (https://forums.graalonline.com/forums/showthread.php?t=77822)

Edges are of equal value.

PHP Code:


		
			
/**
  * Finds the path from one object to another through the nodes variable.
  *
  * Node is an object which has nodes variable containing a list of connected node.
  * Nodes are single directions. In order to make it two-directions, you have to define
  *   them separately.
**/

function findPath( startNode, endNode )
{
  temp.nodeList.add( {startNode, new[0]} );
  temp.nodeIndex = 0;
  while ( temp.nodeList.size() > temp.nodeIndex )
  {
    temp.node = temp.nodeList[ temp.nodeIndex ][0];
    temp.nodePath = temp.nodeList[ temp.nodeIndex ][1];
    temp.nodePath.add( temp.node );
    if ( temp.node == endNode )
      return temp.nodePath;

    for ( temp.subnode: node.nodes )
    {
      if ( temp.subnode in temp.nodeList )
        continue;

      temp.nodeList.add( { temp.subnode, temp.nodePath } );
    }
    temp.nodeIndex ++;
  }

  return null;
}

Example of Usage:

PHP Code:


		
			
function onCreated()
{
  node1 = new TStaticVar("Node-1");
  node2 = new TStaticVar("Node-2");
  node3 = new TStaticVar("Node-3");
  node4 = new TStaticVar("Node-4");

  node1.nodes = { node2, node3 };
  node2.nodes = { node1, node3 };
  node3.nodes = { node4 };
  node4.nodes = { node1 };
  
  path = findPath( node1, node4 );
  for ( node: path )
    echo( node.name );
}

I see you found a way to transfer it into Gscript :p

PHP Code:


		
			
/**
 * Nodes Interface for PathFinder
 *
 * (+) void connect( Node node );
 * (+) void disconnect( Node nodes );
 * (+) Node[] getNodes();
 **/
 
/**
  * This connects a node to the node-list.
  *
  * @param node Node, any object that could be treated as a Node.
  *                If used to connect afterwards, add Node interface!
  **/
public function connect( node )
{
  if ( node == null )
    return;
  if ( node in this.nodes )
    return;
  
  this.nodes.add( node );
}

/**
  * This removes a node to the node-list.
  *
  * @param node Node, any object that could be treated as a Node.
  **/

public function disconnect( node )
{
  this.nodes.remove( node );
}

/**
  * This obtains the nodes that are currently connected to the object.
  *
  * @return Node[] List of nodes attached to object
  **/

public function getNodes()
{
  return this.nodes;
}

/**
  * This calculates the shortest distance to a particular node.
  *
  * @return Node[] An ordered list of the nodes that need to be traveled
  *                    to reach given destination.
  **/
function findPath( endNode )
{
  temp.nodeList.add( {this, new[0]} );
  temp.nodeIndex = 0;
  while ( temp.nodeList.size() > temp.nodeIndex )
  {
    temp.node = temp.nodeList[ temp.nodeIndex ][0];
    temp.nodePath = temp.nodeList[ temp.nodeIndex ][1];
    temp.nodePath.add( temp.node );
    if ( temp.node == endNode )
      return temp.nodePath;

    for ( temp.subnode: node.getNodes() )
    {
      if ( temp.subnode in temp.nodeList )
          continue;

      temp.nodeList.add( { temp.subnode, temp.nodePath } );
    }
    temp.nodeIndex ++;
  }

  return null;
}

For Stan... And anyone else... It elaborates onto the original code and encapsulates it. You could use node.findPath( endNode ); instead... As a shortcut. Just don't mix-and-match the findPath and Node... ( they'd conflict on the function declaration. )