2021-03-07【Math】BucketQueue
2021-03-09 本文已影响0人
持刀的要迟到了
https://www.redblobgames.com/pathfinding/a-star/implementation.html#algorithm
桶队列
原理:把Queue放到List中 放入的位置,是根据优先级放置的,如优先级1,放在List[1],优先级5,放List[5]
中间没有的放null
这样列表直接就具有优先级属性了。
private readonly List<Queue<T>> m_Buckets = new List<Queue<T>>();
private int m_Bucket = 0;
public void Add(T value, int cost)
{
m_Bucket = Math.Min(m_Bucket, cost);
// 根据cost的最大值及历史最大值,决定 m_Buckets 的数量。
// 而 m_Bucket 的位置,是最小的有值的地方。
// Grow the bucket array if needed.
int distance = cost + 1 - m_Buckets.Count;
while (distance > 0)
{
m_Buckets.Add(null);
distance--;
}
// 往这个相同优先级的队列中加入 value
// Find the bucket, or create it if needed.
var bucket = m_Buckets[cost];
if (bucket == null)
{
bucket = new Queue<T>();
m_Buckets[cost] = bucket;
}
bucket.Enqueue(value);
}
Add:
RemoveNext:
/// Removes the best item from the queue or returns `null` if the queue is
/// empty.
public T RemoveNext()
{
// Advance past any empty buckets.
// 满足两点才会加:1.m_BucketMin比总长度小 2.m_BucketMin位置是空的,那么加
while (m_BucketMin < m_Buckets.Count &&
(m_Buckets[m_BucketMin] == null || m_Buckets[m_BucketMin].Count == 0))
{
m_BucketMin++;
}
// If we ran out of buckets, the queue is empty.
// 过了,直接返回
if (m_BucketMin >= m_Buckets.Count) return default(T);
// 在m_BucketMin的地方获取一个元素。
return m_Buckets[m_BucketMin].Dequeue();
}