Jump to content
Search In
  • More options...
Find results that contain...
Find results in...

Gustavo6046

Members
  • Content count

    968
  • Joined

  • Last visited

4 Followers

About Gustavo6046

  • Rank
    Forum Regular

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

Single Status Update

See all updates by Gustavo6046

  1. I did a quick pathfinder in ACS.

     

    #include "zcommon.acs"
    
    #define MAX_NODES 256
    #define MAX_LINKS 32
    
    int nodes[MAX_NODES];
    int numNodes = 0;
    int nodeLinks[MAX_NODES * MAX_LINKS];
    int numLinks[MAX_NODES];
    
    int currentPath[MAX_NODES];
    int pathLength = 0;
    int dCosts[MAX_NODES];
    int queue[MAX_NODES];
    int qCosts[MAX_NODES];
    int queueLength = 0;
    
    int nextNodes[MAX_NODES];
    int cameFrom[MAX_NODES * 2];
    
    function void recalculateLinks(void)
    {
    	for ( int i = 0; i < MAX_NODES; i++ )
    		numLinks[i] = 0;
    		
    	for ( int j = 0; j < MAX_NODES * MAX_LINKS; j++ )
    		nodeLinks[j] = 0;
    
    	for ( i = 0; i < numNodes - 1; i++ )
    		for ( j = 0; j < numNodes - 1; j++ )
    			if ( CheckSight(i, j, CSF_NOFAKEFLOORS) )
    			{
    				numLinks[i]++;
    				numLinks[j]++;
    				
    				nodeLinks[i * MAX_LINKS + numLinks[i]] = j;
    				nodeLinks[j * MAX_LINKS + numLinks[j]] = i;
    			}
    }
    
    function int addNode(int tid)
    {
    	nodes[numNodes] = tid;
    	numNodes++;
    	
    	recalculateLinks();
    			
    	return numNodes - 1;
    }
    
    function int distanceBetween(int source, int dest)
    {
    	int diffX = GetActorX(source) - GetActorX(dest);
    	int diffY = GetActorY(source) - GetActorY(dest);
    	
    	int sqDiff = FixedMul(diffX, diffX) + FixedMul(diffY, diffY);
    	
    	if ( sqDiff < 0 )
    		sqDiff = -sqDiff;
    
    	return FixedSqrt(sqDiff) >> 16;
    }
    
    function bool canTraverse(int old, int tid)
    {
    	for ( int i = 0; i < numNodes; i++ )
    		if ( cameFrom[i * 2] == tid )
    			return false;
    
    	return GetActorX(tid) - GetActorX(old) <= 24;
    }
    
    function int getCostFor(int old, int tid)
    {
    	dCosts[tid] = dCosts[old] + 1;
    
    	int distance = distanceBetween(old, tid);
    	int cost = GetActorPitch(tid) * distance + dCosts[tid];
    	
    	Log(i:distance, s:" -> ", i:cost);
    	
    	return cost;
    }
    
    function void visibleNodes(int tid)
    {
    	for ( int i = 0; i < MAX_NODES; i++ )
    		nextNodes[i] = 0;
    		
    	for ( i = tid * MAX_LINKS; i < tid * MAX_LINKS + numLinks[i]; i++ )
    		nextNodes[i - tid * MAX_LINKS] = nodeLinks[i];
    }
    
    function int nextFromQueue(void)
    {
    	if ( queueLength < 1 )
    		return 0;
    
    	int res = queue[--queueLength];
    	
    	for ( int i = 1; i < queueLength; i++ )
    		queue[i] = queue[i - 1];
    		
    	queue[i] = 0;
    	return res;
    }
    
    function int indexOfNode(int tid)
    {
    	for ( int i = 0; i < numNodes; i++ )
    		if ( nodes[i] == tid )
    			return i;
    			
    	return -1;
    }
    
    function void insertToQueue(int index, int node, int cost)
    {
    	for ( int i = queueLength - 1; i >= index; i++ )
    	{
    		queue[i + 1] = queue[i];
    		qCosts[i + 1] = qCosts[i];
    	}
    	
    	queue[index] = node;
    	qCosts[index] = cost;
    	
    	queueLength++;
    }
    
    function int getCameFrom(int tid)
    {
    	for ( int i = 0; i < numNodes * 2; i += 2 )
    		if ( cameFrom[i] == tid )
    			return cameFrom[i + 1];
    			
    	return -1;
    }
    
    function bool pathBetween(int sourceNode, int destNode)
    {
    	for ( int i = 0; i < MAX_NODES; i++ )
    	{
    		dCosts[i] = 0;
    		currentPath[i] = 0;
    	}
    		
    	int current = sourceNode;
    	int cfIndex = 0;
    		
    	while ( current != 0 && current != destNode )
    	{
    		visibleNodes(current);
    		
    		for ( i = 0; nextNodes[i] > 0; i++ )
    		{
    			if ( !canTraverse(current, nextNodes[i]) )
    		
    			int j = 0;
    			int cost = getCostFor(nodes[current], nextNodes[i]);
    			
    			while ( j < queueLength && qCosts[j] < cost )
    				j++;
    		
    			insertToQueue(j, nextNodes[i], cost);			
    			cameFrom[cfIndex * 2] = nextNodes[i];
    			cameFrom[cfIndex * 2 + 1] = current;
    		}
    		
    		current = nextFromQueue();
    	}
    
    	if ( current == 0 )
    		return false;
    		
    	pathLength = 0;
    	queueLength = 0;
    
    	for ( current = destNode; current != -1; current = getCameFrom(current) )
    	{
    		currentPath[pathLength] = current;
    		pathLength++;
    	}
    		
    	return true;
    }
    
    script 710 (void)
    {
    	int ntid = UniqueTID();
    	Thing_ChangeTID(0, ntid);
    	
    	addNode(ntid);
    }

    Still wondering how to use that.

×