3
\$\begingroup\$

I'm trying to implement Heap into my A* algorithm, However I'm having trouble with implementing one method. The Contains method. Which checks if the heap array has a specific node in it or not. I don't know how to implement that. If I just make a for loop and check every item in the heap that would be very very slow and defeat the purpose of a heap.

So my question is, How do you check if an item exist in a OpenSet of type Heap? What is the fastest way to do it?

This is my heap code:

namespace AI
{
public interface IHeapItem<T> : IComparable<T>
{
    int HeapIndex { get; set; }
}

class Heap<T> where T : IHeapItem<T>
{
    T[] Items;
    int count;
    public int Count { get { return count; } }

    public Heap(int MaxSize)
    {
        Items = new T[MaxSize];
    }

    public T this[int Index]
    {
        get
        {
            if (Index > count)
                Index = count - 1;

            return Items[Index];
        }

        set { Items[Index] = value; }
    }

    public void Push(T Item)
    {
        Item.HeapIndex = count;
        Items[count] = Item;
        SortUp(Item);
        count++;
    }

    public T Pop()
    {
        T FirstItem = Items[0];
        count--;
        Items[0] = Items[count];
        Items[0].HeapIndex = 0;
        SortDown(Items[0]);
        return FirstItem;
    }

    public bool Contains(T Item)
    {

    }

    void SortDown(T Item)
    {
        while (true)
        {
            int LeftChildIndex = Item.HeapIndex * 2 + 1;
            int RightChildIndex = Item.HeapIndex * 2 + 2;
            int swapIndex = 0;

            if (LeftChildIndex < count)
            {
                swapIndex = LeftChildIndex;

                if (RightChildIndex < count)
                    if (Items[LeftChildIndex].CompareTo(Items[RightChildIndex]) < 0)
                        swapIndex = RightChildIndex;

                if (Item.CompareTo(Items[swapIndex]) < 0)
                    Swap(Item, Items[swapIndex]);
                else
                    return;
            }
            else
                return;
        }
    }

    void SortUp(T Item)
    {
        int ParentIndex = (Item.HeapIndex - 1) / 2;

        while (true)
        {
            T ParentItem = Items[ParentIndex];
            if (Item.CompareTo(ParentItem) > 0)
                Swap(Item, ParentItem);
            else
                break;

            ParentIndex = (Item.HeapIndex - 1) / 2;
        }
    }

    void Swap(T ItemA, T ItemB)
    {
        Items[ItemA.HeapIndex] = ItemB;
        Items[ItemB.HeapIndex] = ItemA;
        int itemAIndex = ItemA.HeapIndex;
        ItemA.HeapIndex = ItemB.HeapIndex;
        ItemB.HeapIndex = itemAIndex;
    }
}
}
\$\endgroup\$
  • \$\begingroup\$ Note that you don't have to add [Solved] to the title. Instead, mark the answer that worked for you as "accepted". I noticed that you did this for your other question, you might want to do that there as well. \$\endgroup\$ – Pip Apr 8 '15 at 0:34
4
\$\begingroup\$

In A* implementations, this method is commonly completely unneeded, as you maintain an "open list", which is the minheap (note minheap vs maxheap here). Instead of finding out if a node is contained in the frontier, you maintain a list called something like "costSoFar", which maintains a list of the smallest cost for any one node, and check for the node in this. Note that this could be handled inside of the node itself, in your case by adding a bool OnOpenList { get; set; }, a bool OnClosedList { get; set; }, as well as a float (or int) costSoFar { get; set; }. This would allow you to check if the node is contained in the minheap without actually checking. A sample loop would be as follows: (I use Vector2's to store positions here, but you could very well use two integers or floats.)

private static Foo FindPathReversed(Vector2 start, Vector2 end)
{
    var world = GetWorld();

    MinHeap<Foo> openList = new MinHeap<Foo>(); // The frontier
    Foo[,] nodeWorld = new Foo[(int)world.size.x, (int)world.size.y];
    Foo node;
    Vector2 temp;
    int cost;
    int diff;

    Foo current = new Foo(startPosition);
    current.cost = 0;

    Foo finish = new Foo(end);
    nodeWorld[(int)current.position.x, (int)current.position.y] = current;
    openList.Insert(current);

    while (openList.Count > 0)
    {
        //Find best item and switch it to the 'closedList'
        current = openList.RemoveRoot();
        current.onClosedList = true;

        //Find neighbours
        for (int i = 0; i < surrounding.Length; i++)
        {
            temp = new Vector2(current.position.x + surrounding[i].x, current.position.y + surrounding[i].y);
            if (world.TileIsPassable((int)temp.x, (int)temp.y)) // You must define this method
            {
                //Check if we've already examined a neighbour, if not create a new node for it.
                if (nodeWorld[(int)temp.x, (int)temp.y] == null)
                {
                    node = new Foo(temp);
                    nodeWorld[(int)temp.x, (int)temp.y] = node;
                }
                else
                {
                    node = brWorld[(int)temp.x, (int)temp.y];
                }

                //If the node is not on the 'closedList' check it's new score, keep the best
                if (!node.onClosedList)
                {
                    diff = 0;
                    if (current.position.x != node.position.x)
                    {
                        diff += 1;
                    }
                    if (current.position.y != node.position.y)
                    {
                        diff += 1;
                    }

                    // These functions are not part of the standard library but probably have equivalents.
                    int distance = (int)Mathf.Pow(Mathf.Max(Mathf.Abs(end.x - node.position.x), Mathf.Abs(end.y - node.position.y)), 2);
                    //int distance1 = (int)Mathf.Pow(Vector2.Distance(new Vector2(node.position.x, node.position.y), new Vector2(end.x, end.y)), 2);
                    cost = current.cost + diff + distance;
                    //cost = current.cost + diff + (int)Mathf.Pow(Vector2.Distance(node.position, end), 2);


                    if (cost < node.cost)
                    {
                        node.cost = cost;
                        node.next = current;
                    }

                    //If the node wasn't on the openList yet, Insert it 
                    if (!node.onOpenList)
                    {
                        //Check to see if we're done
                        if (node.Equals(finish))
                        {
                            node.next = current;
                            return node;
                        }
                        node.onOpenList = true;
                        openList.Insert(node);
                    }
                }
            }
        }
    }
    return null; //no path found
}

Note that this code should be taken at face value: as a sample. I have written this code from memory, so it may very well be not completely accurate. I also have more infrastructure surrounding this; if you have some basic implementation or structure questions don't be scared to leave a comment.

\$\endgroup\$
  • \$\begingroup\$ ooh wow. I did not think of that. That would work perfectly. Now I understnad. Thank you ^_^ \$\endgroup\$ – David Apr 8 '15 at 0:31
  • \$\begingroup\$ @Fantasy no problem. If this works for you, don't forget to mark the answer as "accepted" by clicking the checkmark next to the top of the post, and leave an upvote on any answers that you like. \$\endgroup\$ – Pip Apr 8 '15 at 0:32
2
\$\begingroup\$

Pip's answer is the right answer but I wanted to add that if you really did need to know set membership quickly and efficiently, you could have added a flag to each node to specify which list it was in. That gives you the extra burden of maintaining that flag's correctness as you move nodes between lists, but the benefit is that you get a super quick answer to your question about whether its in the open list or not.

\$\endgroup\$
  • \$\begingroup\$ That is exactly what I did. I set two boolean variables in the Node class called InOpenList and InClosedList to indicated where is this node currently is. It worked perfectly ^_^ \$\endgroup\$ – David Apr 9 '15 at 3:51
  • \$\begingroup\$ Note that this was part of my answer already, but the code sample there was an alternative to that that I prefer :) Also, I actually do use an onClosedList boolean there, even if I used that minheap to improve performance. \$\endgroup\$ – Pip Apr 14 '15 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.