Pathfinding using Rank-Pairing Heaps

Rank pairing heaps

Introduction

This is a header-only implementation of rank-pairing heaps (rp-heap) written in C++11. The idea of rp-heap is based on lazy binomial queue with the rank restriction to ensure the balance of half trees. Heap has wide applications like heapsort, k-smallest elements, Prim's algorithm and notably well-known Dijkstra's shortest-path algorithm. We are implementing this data structure because:

• std::priority_queue does not support decrease-key
• Fibonacci heap is theoretically fast but not good in practice
• we are looking for an efficient 'decrease key' operation in pathfinding algorithm which is better than practical d-ary heap and pairing heap

In game development, A* algorithm is a standard shortest path algorithm. The main file provides a demo of A* pathfinding using rp-heap.

Usage

The implementation mimics STL containers and provides STL-like member functions.
To use it, simply include the header file
rp_heap.h

Basic member functions

cpp
// make heap
rp_heap(const _Pr& _Pred = _Pr());
// capacity
bool empty() const;
size_type size() const;
// find-min
const_reference top() const;
// insert, returns an iterator holding the internal pointer of node for the parameter of decrease key
const_iterator push(const value_type& _Val);
const_iterator push(value_type&& x);
// delete-min
void pop();
void pop(value_type& _Val);
// delete-all
void clear();
// decrease-key
void decrease(const_iterator _It, const value_type& _Val);
// for type 1 rank reduction (default type 2)
#define TYPE1_RANK_REDUCTION

Test program

cpp
#include <iostream>
#include <algorithm> // std::random_shuffle
#include "rp_heap.h"
#include <vector>
int main()
{
    std::vector<int> v;
    int size = 1000;
    for (int i = 0; i < size; i++)
        v.push_back(i + 1); // v = {1, 2,... 1000}
    std::random_shuffle(v.begin(), v.end()); // shuffle v
    
    rp_heap<int> heap;
    std::vector<rp_heap<int>::const_iterator> its; // save the iterators returned from push
    for (int i = 0; i < size; i++)
        its.push_back(heap.push(v[i]));
        
    heap.decrease(its[0], 0); // a number decreases to 0
    heap.pop(); // pop that number
    
    for (int i = 1; i < size; i++)
        heap.decrease(its[i], *its[i] - 1); // each element in heap is decreasd by 1
    while (!heap.empty())
    {
        int x;
        heap.pop(x);
        std::cout << x << '\n'; // will print the number from {1, 2,...999} but missing the one in the first pop
    }
    return 0;
}

Performance

• For detailed analysis of rp-heap, see [1]

A* algorithm using rp-heap

A sample map taking from MMORPG Strugarden NEO

Transformed 2D grid Map

Shortest path by BFS (unweighted, 4-direction movement)

Shortest path by A* (weighted, 8-direction movement)

References

[1] B. Haeupler, S. Sen, and R. E. Tarjan. Rank-pairing heaps. SIAM J. Comput., 40:1463–1485, 2011.

[2] Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996), "Shortest paths algorithms: theory and experimental evaluation", Mathematical Programming, Series A 73 (2): 129–174, doi:10.1016/0025-5610(95)00021-6, MR 1392160

[3] Introduction to A*