Question about PriorityQueue

[Immortal_BLG]

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

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

void PriorityQueue::Insert (int value, float priority)

and

int PriorityQueue::Remove (void)

should look like this:

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.

[Whistler]

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.

[Immortal_BLG]

Originally Posted by Whistler

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?

[Whistler]

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.