Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Getting a grasp on Binary Heaps

Discussion in 'Scripting' started by DayyanSisson, Mar 3, 2013.

  1. DayyanSisson

    DayyanSisson

    Joined:
    Aug 4, 2011
    Posts:
    623
    So I've been reading this article on binary heaps and trying to incorporate it in my pathfinding code but have no luck. I was hoping to get some feedback on my attempt to see what went wrong:

    Code (csharp):
    1.     void SortedAdd (Node nextNode) {
    2.  
    3.         if(open.Count < 1){
    4.             open.Add(new Node());
    5.             return;
    6.         }
    7.  
    8.         open.Add(nextNode);
    9.  
    10.         int index = open.IndexOf(nextNode);
    11.         int parentIndex = Mathf.RoundToInt(index/2);
    12.         float fCost = nextNode.f;
    13.  
    14.         while(fCost > open[parentIndex].f){
    15.             if(fCost > open[parentIndex].f){
    16.                 Swap(nextNode, open[parentIndex]);
    17.                 int opIndex = parentIndex;
    18.                 parentIndex = Mathf.RoundToInt(opIndex/2);
    19.             }else{
    20.                 break;
    21.             }
    22.         }
    23.     }
    24.  
    25.     void Swap (Node n1, Node n2) {
    26.  
    27.         int n1ind = open.IndexOf(n1);
    28.         int n2ind = open.IndexOf(n2);
    29.         open[n1ind] = n2;
    30.         open[n2ind] = n1;
    31.     }
    When I checked the open list, the nodes were not in order therefore the path was all over the place. Any idea where I went wrong?
     
  2. scarpelius

    scarpelius

    Joined:
    Aug 19, 2007
    Posts:
    966
  3. DayyanSisson

    DayyanSisson

    Joined:
    Aug 4, 2011
    Posts:
    623
    Is there a library I'm supposed to be using? Because List<> doesn't contain OrderBy() or OrderByDescending().
     
  4. hpjohn

    hpjohn

    Joined:
    Aug 14, 2012
    Posts:
    2,190
    If you want to use binary heaps, you need "sink down", "bubble up", "and get-from-heap"(pop) style functions, so you can interact with it.
    and when using heaps, once you get something from the heap, it's no longer on the heap, so be sure it's what you need

    this is pretty clear
    http://eloquentjavascript.net/appendix2.html

    you dont need any special libraries, except collections.generic