On Programming

A discussion of programming strategies and results

Custom Binary Heap

| Comments

As a games programmer, one of the basic tasks that everyone accomplishes is implementing A* Path Finding. First, let me say that path finding is not basic in video games, but the underlying concepts like A* can be. One way to improved the speed of A* Path Finding is to store the open list in a binary heap. Lucky for us there is already one in the standard library called priority queue. Upon further inspection I noticed some limitations of the priority queue.

  1. There was no find() or contains() function to see if a node was already in the open list
  2. There was no way to re-sort the list after invalidating it by changing the parent node of a node already on the open list

To fix this I implemented my own binary heap with these options available. They should be used sparingly because they are not fast operations for binary heaps, but I feel like they should still be available. Below is my code for the binary heap. Please note that I use C++11 features in this code so you will need a modern compiler like Clang 3.1.

bheap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
  #pragma once
  #include <functional>
  #include <vector>

  template <class T>
  class bheap
  {
  public:
    /** 
     * Initialize the bheap with a function to compare the entries and an expected size to reduce allocations during insertion
     * 
     * @param _compare A function to compare the entries. If compare(a,b) returns true, A is located higher up in the queue to be popped off first
     * @param expected_size The amount of space to allocate for values
     */
    bheap(std::function< bool(T& a, T& b) > _compare = [](T& a, T& b) {return a < b;}, size_t expected_size = 100) :
      compare(_compare)
    {
      heap.reserve(expected_size);
    }
    /** 
     * Initialize the bheap with a list of initial values, a function to compare the entries and an expected size to reduce allocations during insertion
     * 
     * @param input An initializer list of values to be inserted into the heap
     * @param _compare A function to compare the entries. If compare(a,b) returns true, A is located higher up in the queue to be popped off first
     * @param expected_size The amount of space to allocate for values
     */
    bheap(const std::initializer_list<T> & input, std::function< bool(T& a, T& b) > _compare = [](T& a, T& b) {return a < b;}, size_t expected_size = 100) :
      compare(_compare)
    {
      heap.reserve((expected_size > input.size() ? expected_size : input.size()));
      for (const T& val : input)
        heap.push_back(val);
      sort();
    }
    ~bheap()
    {

    }

    /** 
     * Check to see if the heap has no values
     * 
     * 
     * @return true if it has no values, otherwise false
     */
    bool empty() const
    {
      return heap.empty();
    }

    /** 
     * Get the size of the heap
     * 
     * 
     * @return The size of the heap
     */
    size_t size() const
    {
      return heap.size();
    }

    /** 
     * Add a new value to the heap in the correct position
     * 
     * @param value The new value to add
     */
    void push(const T& value)
    {
      heap.push_back(value);
      percolate_up(heap.size()-1);
    }

    /** 
     * Get the lowest value in the heap
     * 
     * Gets the lowest value in the heap. This is determined by finding which value returns true compared against all other items when passed as the first parameter to the compare function. By defaul the compare function performs a simple operator<()
     * 
     * 
     * @return The lowest value in the heap
     */
    const T& top() const
    {
      return heap[0];
    }

    /** 
     * Remove the lowest value from the heap
     * 
     */
    void pop()
    {
      heap[0] = heap[heap.size()-1];
      heap.pop_back();
      percolate_down(0);
    }

    /** 
     * Fully sort the heap assuming nothing about the current state. This operation is expensive so only call it if necessary. The pop and push functions will keep the heap sorted on their own.
     * 
     */
    void sort()
    {
      if (empty())
        return;
      for (size_t i = (heap.size()-1)/2; i != -1; --i)
        percolate_down(i);
    }

    /** 
     * Find the first entry that matches value.
     * 
     * Find the first entry that matches value. If there are multiple entries with the same value there is no guarantee which one will be returned. Please note that if you change a value that affects the sorting then you must also make a call to sort()
       * 
       * @param value The value to look for
       * 
       * @return A pointer to the value in the heap matching the input value or nullptr if none is found
       */
    T* find(const T& value)
    {
      for (T& val : heap)
        if (val == value)
          return &val;
      return nullptr;
    }

    /** 
     * Remove a value from the heap.
     * 
     * Remove a value from the heap given a pointer to its location. This will call sort() automatically since the sorting of the heap will be destroyed. To remove by value, use find()
     * 
     * @param value A pointer to the value in the heap that needs to be removed.
     */
    void remove(const T* value)
    {
      bool found = false;
      for (auto it = heap.begin(); it != heap.end(); ++it)
        {
          if (&*it == value)
            {
              heap.erase(it);
              found = true;
              break;
            }
        }
      if (found)
        sort();
    }
  private:
    void percolate_down(size_t i)
    {
      while (2*i + 1 < heap.size())
        {
          size_t left_child = 2*i + 1;
          size_t right_child = 2*i + 2;
          size_t parent = (i-1)/2;
          size_t last_leaf = heap.size()-1;
          size_t child;
          if (right_child < heap.size() && compare(heap[right_child], heap[left_child]))
            child = right_child;
          else
            child = left_child;
          if (compare(heap[child], heap[i]))
            {
              //swap
              T tmp = heap[i];
              heap[i] = heap[child];
              heap[child] = tmp;
              i = child;
            } else {
            break;
          }
        }
    }

    void percolate_up(size_t i)
    {
      size_t parent = (i-1)/2;
      while (parent < i)
        {
          if (compare(heap[i], heap[parent]))
            {
              T tmp = heap[i];
              heap[i] = heap[parent];
              heap[parent] = tmp;
              i = parent;
              parent = (i-1)/2;
            } else {
            break;
          }
        }
    }

    std::function< bool(T& a, T& b) > compare;
    std::vector<T> heap;
  };

Comments