Search icon CANCEL
Arrow left icon
Explore Products
Best Sellers
New Releases
Books
Videos
Audiobooks
Learning Hub
Conferences
Free Learning
Arrow right icon
Arrow up icon
GO TO TOP
Lua Game Development Cookbook

You're reading from   Lua Game Development Cookbook Over 70 recipes that will help you master the elements and best practices required to build a modern game engine using Lua

Arrow left icon
Product type Paperback
Published in Jul 2015
Publisher
ISBN-13 9781849515504
Length 360 pages
Edition 1st Edition
Languages
Tools
Arrow right icon
Author (1):
Arrow left icon
Mário Kašuba Mário Kašuba
Author Profile Icon Mário Kašuba
Mário Kašuba
Arrow right icon
View More author details
Toc

Table of Contents (11) Chapters Close

Preface 1. Basics of the Game Engine 2. Events FREE CHAPTER 3. Graphics – Common Methods 4. Graphics – Legacy Method with OpenGL 1.x–2.1 5. Graphics – Modern Method with OpenGL 3.0+ 6. The User Interface 7. Physics and Game Mechanics 8. Artificial Intelligence 9. Sounds and Networking Index

Making a prioritized queue

A prioritized queue or simple priority queue extends basic queue with the entry sorting feature. Upon entry insertion, you can set what will be the priority of the entry. This data structure is often used in job queuing where the most important (highest priority) jobs must be processed before the jobs with lower priority. Priority queues are often used in artificial intelligence as well.

This version of the prioritized queue allows you to obtain entries with minimal or maximal priority at constant time. Element priority can be updated. However, priority queue insertion, update, and removal might use linear time complexity in worst case scenarios.

There are two rules that should be noted:

  • Each entry of this queue should be unique
  • The order of retrieving elements with the same priority is not defined

Getting ready

This recipe will use the following shortcuts:

local ti = table.insert
local tr = table.remove

-- removes element from table by its value
local tr2 = function(t, v)
  for i=1,#t do
    if t[i]==v then
      tr(t, i)
      break
    end
  end
end

It's recommended to put it all together in one Lua module file.

How to do it…

The priority queue can be defined as in the following code:

return function pqueue()
  -- interface table
  local t = {}

  -- a set of elements
  local set = {}
  -- a set of priority bags with a elements
  local r_set = {}
  -- sorted list of priorities
  local keys = {}

  -- add element into storage, set its priority and sort keys
  --  k - element
  --  v - priority
  local function addKV(k, v)
    set[k] = v
    -- create a new list for this priority
    if not r_set[v] then
      ti(keys, v)
      table.sort(keys)
      local k0 = {k}
      r_set[v] = k0
      setmetatable(k0, {
        __mode = 'v'
      })
    -- add element into list for this priority
    else
      ti(r_set[v], k)
    end
  end

  -- remove element from storage and sort keys
  local remove = function(k)
    local v = set[k]
    local prioritySet = r_set[v]
    tr2(prioritySet, k)
    if #prioritySet < 1 then
      tr2(keys, v)
      r_set[v] = nil
      table.sort(keys)
      set[k] = nil
    end
  end; t.remove = remove

  -- returns an element with the lowest priority
  t.min = function()
    local priority = keys[1]
    if priority then
      return r_set[priority][1] or {}
    else
      return {}
    end
  end

  -- returns an element with the highest priority
  t.max = function()
    local priority = keys[#keys]
    if priority then
      return r_set[priority][1] or {}
    else
      return {}
    end
  end

  -- is this queue empty?
  t.empty = function()
    return #keys < 1
  end
  -- simple element iterator, retrieves elements with
  -- the highest priority first
  t.iterate = function()
    return function()
      if not t.empty() then
        local element = t.max()
        t.remove(element)
        return element
      end
    end
  end
  -- setup pqueue behavior
  setmetatable(t, {
    __index = set,
    __newindex = function(t, k, v)
      if not set[k] then
        -- new item
        addKV(k, v)
      else
        -- existing item
        remove(k)
        addKV(k, v)
      end
    end,
  })
  return t
end

How it works…

This priority queue algorithm uses three tables: set, r_set, and keys. These tables help to organize elements into so-called priority bags. The first one, set contains elements paired with their priorities. It's also used when you try to obtain element priority from the queue. The second one, r_set contains priority bags. Each bag represents a priority level. The last one keys contains a sorted list of priorities, which is used in the extraction of elements from a minimal or maximal priority bag.

Each element can be inserted in a way similar to the Lua table with the exception that the inserted element is used as a key and priority is stored as a value:

priority_queue[element] = priority

This form of access can be used to update element priority. Elements with minimal or maximal priority can be extracted using the min or max function respectively;

local min_element = priority_queue.min()
local max_element = priority_queue.max()

Note that elements remain in the priority queue until you delete them with the remove function;

priority_queue.remove(element)

Priority queue can be queried with the empty function that returns true if there's no element in the queue;

priority_queue.empty()

You can use the iterator function in for loop to process all queue elements sorted by their priority:

for element in priority_queue.iterator() do
  -- do something with this element
end
lock icon The rest of the chapter is locked
Register for a free Packt account to unlock a world of extra content!
A free Packt account unlocks extra newsletters, articles, discounted offers, and much more. Start advancing your knowledge today.
Unlock this book and the full library FREE for 7 days
Get unlimited access to 7000+ expert-authored eBooks and videos courses covering every tech area you can think of
Renews at $19.99/month. Cancel anytime