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();
        }
上一篇下一篇

猜你喜欢

热点阅读