.:: Bots United ::.  
filebase forums irc server wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps waypoints yapb

Go Back   .:: Bots United ::. > Cyborg Factory > United Bot
United Bot The ultimate beast is being given birth right here! Half-Life 2

Reply
 
Thread Tools
_src.tar.bz2
Old
  (#1)
[NvT]_KaszpiR_
Member
 
[NvT]_KaszpiR_'s Avatar
 
Status: Offline
Posts: 322
Join Date: Apr 2004
Default _src.tar.bz2 - 26-10-2004

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
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#2)
Rashid Rana
Guest
 
Status:
Posts: n/a
Default Re: _src.tar.bz2 - 27-10-2004

For: jozef wagner
Password for branch and bounds program?
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#3)
Whistler
Whistler
 
Whistler's Avatar
 
Status: Offline
Posts: 1,478
Join Date: Feb 2004
Location: Beijing, P. R. China
Default Re: _src.tar.bz2 - 28-10-2004

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".
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#4)
koraX
Member
 
koraX's Avatar
 
Status: Offline
Posts: 145
Join Date: Jan 2004
Location: Slovak Republic
Default Re: _src.tar.bz2 - 28-10-2004

I'm browsing this forum and now I see my name here. o_O

*screams

*dies


kXBot
koraX's utils
- see my homepage for other projects (OpenGL CSG Editor, FAT16 Sim, NNetwork Sim, ...)
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#5)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 4643'60N 043'0W 0.187A
Default Re: _src.tar.bz2 - 28-10-2004

What is there so confidential ? it's written on your website... ???



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#6)
Whistler
Whistler
 
Whistler's Avatar
 
Status: Offline
Posts: 1,478
Join Date: Feb 2004
Location: Beijing, P. R. China
Default Re: _src.tar.bz2 - 12-11-2004

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]

Last edited by Whistler; 12-11-2004 at 13:55..
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#7)
botman
Super Moderator
 
Status: Offline
Posts: 280
Join Date: Jan 2004
Location: Plano, TX
Default Re: _src.tar.bz2 - 12-11-2004

If I remember correctly, Half-Life used a depth first search for its pathfinding.

botman
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#8)
Whistler
Whistler
 
Whistler's Avatar
 
Status: Offline
Posts: 1,478
Join Date: Feb 2004
Location: Beijing, P. R. China
Default Re: _src.tar.bz2 - 13-11-2004

"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.

Last edited by Whistler; 13-11-2004 at 10:33..
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#9)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 4643'60N 043'0W 0.187A
Default Re: _src.tar.bz2 - 13-11-2004

I think botman meant Breadth first search.



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
   
Reply With Quote
Re: _src.tar.bz2
Old
  (#10)
botman
Super Moderator
 
Status: Offline
Posts: 280
Join Date: Jan 2004
Location: Plano, TX
Default Re: _src.tar.bz2 - 13-11-2004

Yes, Breadth, Depth, whatever, either way it's not A*

botman
   
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com