PDA

View Full Version : Pathfinder


Novo
12-05-2007, 06:22 AM
Edges are of equal value.


/**
* 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:

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 );
}

Kyranki
12-05-2007, 06:29 AM
I see you found a way to transfer it into Gscript :p

Novo
12-06-2007, 01:21 AM
/**
* 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. )