Heap clarification needed

Hey, guys. I've been stumbling my way through trying to build a pathfinding script, and I finally get it working only to discover that it's hungry as hell. Googling around, I see a lot of references to heaps being much preferred to lists or arrays when dealing with searching through a large number of integers. Only problem is, I can't seem to find a really good explanation of how to implement a heap in Unity. All the examples I find are incomplete or convoluted. I thought maybe some brave soul on here might want to take a shot at dumbing it down for me. For example, let's say my script already has a list of integers. The size of the list doesn't change, but I need to be able to update the integers and search for the position of specific integers. What would be the most straightforward way to implement that in a heap? Thanks in advance.

 

There are several disconnects here which will inhibit useful responses.

Generally a "heap" refers to the primary memory pool that gets sliced up and handed out as part of malloc(3)

I'm not even sure what a heap of integers would mean in this context.

Also I am not sure why you are searching positions of integers for a pathfinding script, but anytime you are searching a collection, if you can keep the collection ordered, you can rapidly search it with a binary search.

 

I set it up so that I actually have 4 lists. A nodeList, gCostList, hCostList, and fCostlist. Position i gives me the associated node and position values for that node. It seemed like a good idea at the time.

Anyways, I'm obviously not asking the question very well. Here's a link to one of the examples I found. Also, Sebastian Lague uses one in his Pathfinding Tutorial, but there was so much going on in that one it was hard to separate the heap concepts from everything else. Any light you could shed on the subject would be appreciated.

 

Well, of course they meant the common heap datastructure and in most cases we talk about a binary heap. Heaps usually come in two different forms, either a min or max heap. The point is that the root element is automatically either the smallest or largest element. Since A* revolves around finding the smallest f cost at each step it's usually a good idea to implement the open list as a min heap.

C# essentially already has a min heap data structure which is the priorityqueue class.

You usually don't need seperate lists for the g/h/f cost. You generally need an open list and a closed list (though the closed list could also be implicit if each node has a closed flag). It's common to implement a node class or struct that holds all relevant information of a node (which includes the different costs as well as the parent node reference).

Though I'm not sure if you know what you're doing and why you may want to use a heap for the open list instead of a normal list. The min heap makes it easy to extract the smallest element and is always sorted. When adding an element to a min heap, the heap is immediately sorted. Since it is represented as a binary tree it usually takes about log2(n) steps to add an element or to remove the root element.

 

Interesting. Looks like I've got some reading to do. You're explanation of the binary heap really sheds some light. I guess I didn't appreciate that it was automatically moving the lowest value to the top. I assumed it was just an array structure that was somehow faster to search through.

At the time I was first writing this, my line of thinking was that I didn't want the movement costs attached to the nodes since I needed multiple enemies to be referencing the nodes at the same time. I had it set up where every enemy had pathfinding script attached and would find the player. Now I realize that's silly and I should have just one script and cycle through the enemies instead having them all query at the same time. Live and learn. Time for a re-write. Thanks again for the input.

 

I'm hoping you guys can help nudge me a bit further in the right direction. I'm definitely punching above my weight class with this project, so there are a lot of holes in my understanding. I feel I understand binary heaps a little better, but the examples I'm seeing for them tend to use a generic type T for input. I'd like to be able to feed in gameObjects so that I can have colliders attached for collision reference. Is that possible, or am I barking up the wrong tree? As way of example, I'll use Sebastian Lague's heap script below. I'd like to be able to feed in...

Code (CSharp):

1. Heap<GameObject> openNodes = new Heap<GameObject>(nodeList.Count);

into...

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System;
4.  
5. public class Heap<T> where T : IHeapItem<T> {
6.    
7.     T[] items;
8.     int currentItemCount;
9.    
10.     public Heap(int maxHeapSize) {
11.         items = new T[maxHeapSize];
12.     }
13.    
14.     public void Add(T item) {
15.         item.HeapIndex = currentItemCount;
16.         items[currentItemCount] = item;
17.         SortUp(item);
18.         currentItemCount++;
19.     }
20.  
21.     public T RemoveFirst() {
22.         T firstItem = items[0];
23.         currentItemCount--;
24.         items[0] = items[currentItemCount];
25.         items[0].HeapIndex = 0;
26.         SortDown(items[0]);
27.         return firstItem;
28.     }
29.  
30.     public void UpdateItem(T item) {
31.         SortUp(item);
32.     }
33.  
34.     public int Count {
35.         get {
36.             return currentItemCount;
37.         }
38.     }
39.  
40.     public bool Contains(T item) {
41.         return Equals(items[item.HeapIndex], item);
42.     }
43.  
44.     void SortDown(T item) {
45.         while (true) {
46.             int childIndexLeft = item.HeapIndex * 2 + 1;
47.             int childIndexRight = item.HeapIndex * 2 + 2;
48.             int swapIndex = 0;
49.  
50.             if (childIndexLeft < currentItemCount) {
51.                 swapIndex = childIndexLeft;
52.  
53.                 if (childIndexRight < currentItemCount) {
54.                     if (items[childIndexLeft].CompareTo(items[childIndexRight]) < 0) {
55.                         swapIndex = childIndexRight;
56.                     }
57.                 }
58.  
59.                 if (item.CompareTo(items[swapIndex]) < 0) {
60.                     Swap (item,items[swapIndex]);
61.                 }
62.                 else {
63.                     return;
64.                 }
65.  
66.             }
67.             else {
68.                 return;
69.             }
70.  
71.         }
72.     }
73.    
74.     void SortUp(T item) {
75.         int parentIndex = (item.HeapIndex-1)/2;
76.        
77.         while (true) {
78.             T parentItem = items[parentIndex];
79.             if (item.CompareTo(parentItem) > 0) {
80.                 Swap (item,parentItem);
81.             }
82.             else {
83.                 break;
84.             }
85.  
86.             parentIndex = (item.HeapIndex-1)/2;
87.         }
88.     }
89.    
90.     void Swap(T itemA, T itemB) {
91.         items[itemA.HeapIndex] = itemB;
92.         items[itemB.HeapIndex] = itemA;
93.         int itemAIndex = itemA.HeapIndex;
94.         itemA.HeapIndex = itemB.HeapIndex;
95.         itemB.HeapIndex = itemAIndex;
96.     }
97. }
98.  
99. public interface IHeapItem<T> : IComparable<T> {
100.     int HeapIndex {
101.         get;
102.         set;
103.     }
104. }

 

The GameObject class is the least useful class you can use when you want to store gameobjects in a collection. You can't store any additional data in a gameobject, only through additional components. However storing gameobjects means you have to use GetComponent everytime you want to access any actual useful information which is bad. You should always store one of your own component classes. Those can hold direct references to any other relevant component and store arbitrary additional information which is directly accessible.

Also, the point of using a min heap is to have the heap sorted based on the f cost of each node. When storing gameobjects you would sort them based on the default comparison which essentially sorts based on the reference / hashcode which is pretty useless. The class you posted requires each element to implement the "IHeapItem" interface. That in turns requires the implementation ot the IComparable interface. So you can provide a custom sort / compare condition. So you should create a MonoBehaviour class that you can attach to each "node" which will implement that interface. That forces this class to implement the CompareTo method which should take care of sorting based on the f cost of the node(s).