.:: Bots United ::.

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   United Bot (http://forums.bots-united.com/forumdisplay.php?f=46)
-   -   _src.tar.bz2 (http://forums.bots-united.com/showthread.php?t=2859)

[NvT]_KaszpiR_ 26-10-2004 11:53

_src.tar.bz2
 
I added link to my sourcepack to filebase
please verify if it does not break any rules, (then remove)
http://filebase.bots-united.com/inde...on=file&id=218

Rashid Rana 27-10-2004 23:51

Re: _src.tar.bz2
 
For: jozef wagner
Password for branch and bounds program?

Whistler 28-10-2004 12:30

Re: _src.tar.bz2
 
Quote:

Originally Posted by Rashid Rana
For: jozef wagner
Password for branch and bounds program?

I think this is wrong forum for asking this...
PM or e-mail him instead. His nickname is "KoraX".

koraX 28-10-2004 20:32

Re: _src.tar.bz2
 
I'm browsing this forum and now I see my name here. o_O

*screams

*dies

Pierre-Marie Baty 28-10-2004 23:45

Re: _src.tar.bz2
 
What is there so confidential ? it's written on your website... ???:(

Whistler 12-11-2004 13:01

Re: _src.tar.bz2
 
I just found the Branch & Bound source code in the HLSDK: (I'm not quite sure though, wonder if this is Dynamic Plan or Branch & Bound)
PHP Code:

//=========================================================
// CGraph - FindShortestPath 
//
// accepts a capability mask (afCapMask), and will only 
// find a path usable by a monster with those capabilities
// returns the number of nodes copied into supplied array
//=========================================================
int CGraph :: FindShortestPath int *piPathint iStartint iDestint iHullint afCapMask)
{
    
int        iVisitNode;
    
int        iCurrentNode;
    
int        iNumPathNodes;
    
int        iHullMask;

    if ( !
m_fGraphPresent || !m_fGraphPointersSet )
    {
// protect us in the case that the node graph isn't available or built
        
ALERT at_aiconsole"Graph not ready!\n" );
        return 
FALSE;
    }
    
    if ( 
iStart || iStart m_cNodes )
    {
// The start node is bad?
        
ALERT at_aiconsole"Can't build a path, iStart is %d!\n"iStart );
        return 
FALSE;
    }

    if (
iStart == iDest)
    {
        
piPath[0] = iStart;
        
piPath[1] = iDest;
        return 
2;
    }

    
// Is routing information present.
    //
    
if (m_fRoutingComplete)
    {
        
int iCap CapIndexafCapMask );

        
iNumPathNodes 0;
        
piPath[iNumPathNodes++] = iStart;
        
iCurrentNode iStart;
        
int iNext;

        
//ALERT(at_aiconsole, "GOAL: %d to %d\n", iStart, iDest);

        // Until we arrive at the destination
        //
        
while (iCurrentNode != iDest)
        {
            
iNext NextNodeInRouteiCurrentNodeiDestiHulliCap );
            if (
iCurrentNode == iNext)
            {
                
//ALERT(at_aiconsole, "SVD: Can't get there from here..\n");
                
return 0;
                break;
            }
            if (
iNumPathNodes >= MAX_PATH_SIZE
            {
                
//ALERT(at_aiconsole, "SVD: Don't return the entire path.\n");
                
break;
            }
            
piPath[iNumPathNodes++] = iNext;
            
iCurrentNode iNext;
        }
        
//ALERT( at_aiconsole, "SVD: Path with %d nodes.\n", iNumPathNodes);
    
}
    else
    {
        
CQueuePriority    queue;

        switch( 
iHull )
        {
        case 
NODE_SMALL_HULL:
            
iHullMask bits_LINK_SMALL_HULL;
            break;
        case 
NODE_HUMAN_HULL:
            
iHullMask bits_LINK_HUMAN_HULL;
            break;
        case 
NODE_LARGE_HULL:
            
iHullMask bits_LINK_LARGE_HULL;
            break;
        case 
NODE_FLY_HULL:
            
iHullMask bits_LINK_FLY_HULL;
            break;
        }

        
// Mark all the nodes as unvisited.
        //
        
for ( int i 0m_cNodesi++)
        {
            
m_pNodes].m_flClosestSoFar = -1.0;
        }

        
m_pNodesiStart ].m_flClosestSoFar 0.0;
        
m_pNodesiStart ].m_iPreviousNode iStart;// tag this as the origin node
        
queue.InsertiStart0.0 );// insert start node 
        
        
while ( !queue.Empty() )
        {
            
// now pull a node out of the queue
            
float flCurrentDistance;
            
iCurrentNode queue.Remove(flCurrentDistance);

            
// For straight-line weights, the following Shortcut works. For arbitrary weights,
            // it doesn't.
            //
            
if (iCurrentNode == iDest) break;

            
CNode *pCurrentNode = &m_pNodesiCurrentNode ];
            
            for ( 
pCurrentNode->m_cNumLinks i++ )
            {
// run through all of this node's neighbors
                
                
iVisitNode INodeLink iCurrentNode);
                if ( ( 
m_pLinkPool[  m_pNodesiCurrentNode ].m_iFirstLink ].m_afLinkInfo iHullMask ) != iHullMask )
                {
// monster is too large to walk this connection
                    //ALERT ( at_aiconsole, "fat ass %d/%d\n",m_pLinkPool[ m_pNodes[ iCurrentNode ].m_iFirstLink + i ].m_afLinkInfo, iMonsterHull );
                    
continue;
                }
                
// check the connection from the current node to the node we're about to mark visited and push into the queue                
                
if ( m_pLinkPoolm_pNodesiCurrentNode ].m_iFirstLink ].m_pLinkEnt != NULL )
                {
// there's a brush ent in the way! Don't mark this node or put it into the queue unless the monster can negotiate it
                    
                    
if ( !HandleLinkEnt iCurrentNodem_pLinkPoolm_pNodesiCurrentNode ].m_iFirstLink ].m_pLinkEntafCapMaskNODEGRAPH_STATIC ) )
                    {
// monster should not try to go this way.
                        
continue;
                    }
                }
                
float flOurDistance flCurrentDistance m_pLinkPoolm_pNodesiCurrentNode ].m_iFirstLink i].m_flWeight;
                if (  
m_pNodesiVisitNode ].m_flClosestSoFar < -0.5
                   
|| flOurDistance m_pNodesiVisitNode ].m_flClosestSoFar 0.001 )
                {
                    
m_pNodes[iVisitNode].m_flClosestSoFar flOurDistance;
                    
m_pNodes[iVisitNode].m_iPreviousNode iCurrentNode;

                    
queue.Insert iVisitNodeflOurDistance );
                }
            }
        }
        if ( 
m_pNodes[iDest].m_flClosestSoFar < -0.5 )
        {
// Destination is unreachable, no path found.
            
return 0;
        }

    
// the queue is not empty
        
        // now we must walk backwards through the m_iPreviousNode field, and count how many connections there are in the path
        
iCurrentNode iDest;
        
iNumPathNodes 1;// count the dest
        
        
while ( iCurrentNode != iStart )
        {
            
iNumPathNodes++;
            
iCurrentNode m_pNodesiCurrentNode ].m_iPreviousNode;
        }

        
iCurrentNode iDest;
        for ( 
iNumPathNodes >= i-- )
        {
            
piPath] = iCurrentNode;
            
iCurrentNode m_pNodes iCurrentNode ].m_iPreviousNode;
        }
    }

#if 0

    
if (m_fRoutingComplete)
    {
        
// This will draw the entire path that was generated for the monster.

        
for ( int i iNumPathNodes i++ )
        {
            
MESSAGE_BEGINMSG_BROADCASTSVC_TEMPENTITY );
                
WRITE_BYTETE_SHOWLINE);
                
                
WRITE_COORDm_pNodespiPath] ].m_vecOrigin.);
                
WRITE_COORDm_pNodespiPath] ].m_vecOrigin.);
                
WRITE_COORDm_pNodespiPath] ].m_vecOrigin.NODE_HEIGHT );

                
WRITE_COORDm_pNodespiPath] ].m_vecOrigin.);
                
WRITE_COORDm_pNodespiPath] ].m_vecOrigin.);
                
WRITE_COORDm_pNodespiPath] ].m_vecOrigin.NODE_HEIGHT );
            
MESSAGE_END();
        }
    }

#endif
#if 0 // MAZE map
    
MESSAGE_BEGINMSG_BROADCASTSVC_TEMPENTITY );
        
WRITE_BYTETE_SHOWLINE);
        
        
WRITE_COORDm_pNodes].m_vecOrigin.);
        
WRITE_COORDm_pNodes].m_vecOrigin.);
        
WRITE_COORDm_pNodes].m_vecOrigin.NODE_HEIGHT );

        
WRITE_COORDm_pNodes].m_vecOrigin.);
        
WRITE_COORDm_pNodes].m_vecOrigin.);
        
WRITE_COORDm_pNodes].m_vecOrigin.NODE_HEIGHT );
    
MESSAGE_END();
#endif

    
return iNumPathNodes;


(note that you can't rip this code to your program as it's owned by valve unless it's a HL bot or so, this is NOT "open source"; but you can learn ideas from it)

[edit]
well this isn't BB because of this one...
PHP Code:


                float flOurDistance 
flCurrentDistance m_pLinkPoolm_pNodesiCurrentNode ].m_iFirstLink i].m_flWeight;
                if (  
m_pNodesiVisitNode ].m_flClosestSoFar < -0.5
                   
|| flOurDistance m_pNodesiVisitNode ].m_flClosestSoFar 0.001 

but remove these lines it will be BB:
PHP Code:


                float flOurDistance 
flCurrentDistance m_pLinkPoolm_pNodesiCurrentNode ].m_iFirstLink i].m_flWeight
                if (  
m_pNodesiVisitNode ].m_flClosestSoFar < -0.5 
                   
|| flOurDistance m_pNodesiVisitNode ].m_flClosestSoFar 0.001 
                { 
                    
m_pNodes[iVisitNode].m_flClosestSoFar flOurDistance

[/edit]

botman 12-11-2004 16:11

Re: _src.tar.bz2
 
If I remember correctly, Half-Life used a depth first search for its pathfinding.

botman

Whistler 13-11-2004 11:23

Re: _src.tar.bz2
 
"If I remember correctly, Half-Life used a depth first search for its pathfinding."
I don't think so, as the "queue" is actually a priority queue (it's a CQueuePriority class, which is a heap).

also DFS uses a stack and not a queue. Breadth-first search uses queue.

Pierre-Marie Baty 13-11-2004 15:50

Re: _src.tar.bz2
 
I think botman meant Breadth first search.

botman 13-11-2004 16:16

Re: _src.tar.bz2
 
Yes, Breadth, Depth, whatever, either way it's not A*

botman


All times are GMT +2. The time now is 01:01.

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.