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

Go Back   .:: Bots United ::. > Cyborg Factory > YaPB
YaPB Yet another POD-Bot flavor by Whistler and Jeefo Counter-Strike

Reply
 
Thread Tools
Question about PriorityQueue
Old
  (#1)
Immortal_BLG
Member
 
Status: Offline
Posts: 171
Join Date: Nov 2007
Location: Russian Federation
Question Question about PriorityQueue - 09-01-2010

I think so, that found a bug in the code: PriorityQueue class not correctly sorts the nodes by their priorities:
Code:
PriorityQueue testPriorityQueue;

testPriorityQueue.Insert (1, 100.0f);
testPriorityQueue.Insert (2, 100.0f);
testPriorityQueue.Insert (3, 100.0f);
testPriorityQueue.Insert (4, 10.0f);
testPriorityQueue.Insert (5, 9.0f);
testPriorityQueue.Insert (6, 11.0f);
testPriorityQueue.Insert (7, 1.0f);
Current log:
[17:05:10] Log: testPriorityQueue[0] == [7, 1.00].
[17:05:10] Log: testPriorityQueue[1] == [4, 10.00].
[17:05:10] Log: testPriorityQueue[2] == [5, 9.00].
[17:05:10] Log: testPriorityQueue[3] == [2, 100.00].
[17:05:10] Log: testPriorityQueue[4] == [1, 100.00].
[17:05:10] Log: testPriorityQueue[5] == [3, 100.00].
[17:05:10] Log: testPriorityQueue[6] == [6, 11.00].
Although to be so:
[17:05:10] Log: testPriorityQueue[0] == [7, 1.00].
[17:05:10] Log: testPriorityQueue[1] == [5, 9.00].
[17:05:10] Log: testPriorityQueue[2] == [4, 10.00].
[17:05:10] Log: testPriorityQueue[3] == [6, 11.00].
[17:05:10] Log: testPriorityQueue[4] == [1, 100.00].
[17:05:10] Log: testPriorityQueue[5] == [2, 100.00].
[17:05:10] Log: testPriorityQueue[6] == [3, 100.00].

I think that the functions
Code:
void PriorityQueue::Insert (int value, float priority)
and
Code:
int PriorityQueue::Remove (void)
should look like this:
Code:
void PriorityQueue::Insert (int value, float priority)
{	// insert value in priority order

   if (m_size >= m_heapSize)
   {
      m_heapSize += 100;
      m_heap = (HeapNode_t *)realloc (m_heap, sizeof (HeapNode_t) * m_heapSize);

      if (m_heap == null)
         TerminateOnMalloc ();
   }

	for (int index (0u); index < m_size; ++index)
		if (m_heap[index].priority > priority)
		{
			// Empty out hole.
			memmove (m_heap + (index + 1u), m_heap + index, (m_size - index) * sizeof (HeapNode_t));

			m_heap[index] = element;

			// Update current elements number....
			++m_size;

			return;
		}

	// Priority queue is empty or hasn't item with priority lower, that a new element, yet....
   m_heap[m_size].priority = priority;
   m_heap[m_size].id = value;

   ++m_size;
}
int PriorityQueue::Remove (void)
{
   int retID = m_heap[0].id;

	// Move elements down.
	memmove (m_elements, m_elements + 1u, (m_size - 1u) * sizeof (HeapNode_t));

	// Update heap length.
	m_itemCount -= count;

   return retID;
}
And functions HeapSiftDown() and HeapSiftUp() should be removed.

P.S. In HL2 SDK in the class CUtlPriorityQueue same "problem" - this idea of developers?
P.S.S. If I am wrong - please tell me.
  
Reply With Quote
Re: Question about PriorityQueue
Old
  (#2)
Whistler
Summoner
 
Whistler's Avatar
 
Status: Offline
Posts: 1,499
Join Date: Feb 2004
Location: Mist Village
Default Re: Question about PriorityQueue - 09-01-2010

IIRC I ripped that code from HL1 SDK, so thaty may be why it's similar as HL2 SDK.

Basically that code only ensures the data is stored as a heap, i.e. the one to be popped is the smallest. And doesn't sort everything.

Last edited by Whistler; 09-01-2010 at 13:50..
  
Reply With Quote
Re: Question about PriorityQueue
Old
  (#3)
Immortal_BLG
Member
 
Status: Offline
Posts: 171
Join Date: Nov 2007
Location: Russian Federation
Wink Re: Question about PriorityQueue - 09-01-2010

Quote:
Originally Posted by Whistler View Post
IIRC I ripped that code from HL1 SDK, so thaty may be why it's similar as HL2 SDK.
- I know it (HLSDK/dmc/nodes.h)

Hmm, strange, but what I have suggested that faster and more accurately for YaPB pathfinding, why not use it?
  
Reply With Quote
Re: Question about PriorityQueue
Old
  (#4)
Whistler
Summoner
 
Whistler's Avatar
 
Status: Offline
Posts: 1,499
Join Date: Feb 2004
Location: Mist Village
Default Re: Question about PriorityQueue - 10-01-2010

well as long as the pathfinder only uses the CQueuePriority::Remove() function rather than accessing the m_heap array directly (which is private btw) it isn't inaccurate at all.

And heaps usually cost less comparation and moving operations (i.e. faster) than insertion sort.
  
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 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com