-- This code is derived from the SOM benchmarks, see AUTHORS.md file. -- -- Copyright (c) 2016 Francois Perrad -- -- Permission is hereby granted, free of charge, to any person obtaining a copy -- of this software and associated documentation files (the 'Software'), to deal -- in the Software without restriction, including without limitation the rights -- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -- copies of the Software, and to permit persons to whom the Software is -- furnished to do so, subject to the following conditions: -- -- The above copyright notice and this permission notice shall be included in -- all copies or substantial portions of the Software. -- -- THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN -- THE SOFTWARE. --[[ The module 'bit' is available with: * LuaJIT * LuaBitOp extension which is available for: * Lua 5.1 * Lua 5.2 The module 'bit32' is available with: * Lua 5.2 * Lua 5.3 when compiled with LUA_COMPAT_5_2 The bitwise operators are added to Lua 5.3 as new lexemes (there causes lexical error in older version) --]] local band, bxor, rshift if _VERSION < 'Lua 5.3' then local bit = bit32 or require'bit' band = bit.band bxor = bit.bxor rshift = bit.rshift else band = assert(load'--[[band]] return function (a, b) return a & b end')() bxor = assert(load'--[[bxor]] return function (a, b) return a ~ b end')() rshift = assert(load'--[[rshift]] return function (a, b) return a >> b end')() end local alloc_array local ok, table_new = pcall(require, 'table.new') -- LuaJIT 2.1 extension if ok then alloc_array = function (n) local t = table_new(n, 1) t.n = n return t end else alloc_array = function (n) local t = {} t.n = n return t end end local Vector = {_CLASS = 'Vector'} do local floor = math.floor function Vector.new (size) local obj = { storage = alloc_array(size or 50), first_idx = 1, last_idx = 1, } return setmetatable(obj, {__index = Vector}) end function Vector.with (elem) local v = Vector.new(1) v:append(elem) return v end function Vector:at (idx) if idx > self.storage.n then return nil end return self.storage[idx] end function Vector:at_put (idx, val) if idx > self.storage.n then local new_n = self.storage.n while idx > new_n do new_n = new_n * 2 end local new_storage = alloc_array(new_n) for i = 1, self.storage.n do new_storage[i] = self.storage[i] end self.storage = new_storage end self.storage[idx] = val if self.last_idx < idx + 1 then self.last_idx = idx + 1 end end function Vector:append (elem) if self.last_idx > self.storage.n then -- Need to expand capacity first local new_storage = alloc_array(2 * self.storage.n) for i = 1, self.storage.n do new_storage[i] = self.storage[i] end self.storage = new_storage end self.storage[self.last_idx] = elem self.last_idx = self.last_idx + 1 end function Vector:is_empty () return self.last_idx == self.first_idx end function Vector:each (fn) for i = self.first_idx, self.last_idx - 1 do fn(self.storage[i]) end end function Vector:has_some (fn) for i = self.first_idx, self.last_idx - 1 do if fn(self.storage[i]) then return true end end return false end function Vector:get_one (fn) for i = self.first_idx, self.last_idx - 1 do local e = self.storage[i] if fn(e) then return e end end return nil end function Vector:remove_first () if self:is_empty() then return nil end self.first_idx = self.first_idx + 1 return self.storage[self.first_idx - 1] end function Vector:remove (obj) local new_array = alloc_array(self:capacity()) local new_last = 1 local found = false self:each(function (it) if it == obj then found = true else new_array[new_last] = it new_last = new_last + 1 end end) self.storage = new_array self.last_idx = new_last self.first_idx = 1 return found end function Vector:remove_all () self.first_idx = 1 self.last_idx = 1 self.storage = alloc_array(self:capacity()) end function Vector:size () return self.last_idx - self.first_idx end function Vector:capacity () return self.storage.n end function Vector:sort (fn) -- Make the argument, block, be the criterion for ordering elements of -- the receiver. -- Sort blocks with side effects may not work right. if self:size() > 0 then self:sort_range(self.first_idx, self.last_idx - 1, fn) end end function Vector:sort_range (i, j, fn) assert(fn) -- The prefix d means the data at that index. local n = j + 1 - i if n <= 1 then -- Nothing to sort return end local storage = self.storage -- Sort di, dj local di = storage[i] local dj = storage[j] -- i.e., should di precede dj? if not fn(di, dj) then local tmp = storage[i] storage[i] = storage[j] storage[j] = tmp local tt = di di = dj dj = tt end -- NOTE: For DeltaBlue, this is never reached. if n > 2 then -- More than two elements. local ij = floor((i + j) / 2) -- ij is the midpoint of i and j. local dij = storage[ij] -- Sort di,dij,dj. Make dij be their median. if fn(di, dij) then -- i.e. should di precede dij? if not fn(dij, dj) then -- i.e., should dij precede dj? local tmp = storage[j] storage[j] = storage[ij] storage[ij] = tmp dij = dj end else -- i.e. di should come after dij local tmp = storage[i] storage[i] = storage[ij] storage[ij] = tmp dij = di end if n > 3 then -- More than three elements. -- Find k>i and l l then break end local tmp = storage[k] storage[k] = storage[l] storage[l] = tmp end -- Now l < k (either 1 or 2 less), and di through dl are all -- less than or equal to dk through dj. Sort those two segments. self:sort_range(i, l, fn) self:sort_range(k, j, fn) end end end end -- class Vector local Set = {_CLASS = 'Set'} do local INITIAL_SIZE = 10 function Set.new (size) local obj = { items = Vector.new(size or INITIAL_SIZE) } return setmetatable(obj, {__index = Set}) end function Set:size () return self.items:size() end function Set:each (fn) self.items:each(fn) end function Set:has_some (fn) return self.items:has_some(fn) end function Set:get_one (fn) return self.items:get_one(fn) end function Set:add (obj) if not self:contains(obj) then self.items:append(obj) end end function Set:remove_all () self.items:remove_all() end function Set:collect (fn) local coll = Vector.new() self:each(function (it) coll:append(fn(it)) end) return coll end function Set:contains (obj) return self:has_some(function (it) return it == obj end) end end -- class Set local IdentitySet = {_CLASS = 'IdentitySet'} do setmetatable(IdentitySet, {__index = Set}) function IdentitySet.new (size) local obj = Set.new(size) return setmetatable(obj, {__index = IdentitySet}) end function IdentitySet:contains (obj) return self:has_some(function (it) return it == obj end) end end -- class IdentitySet local Entry = {_CLASS = 'Entry'} do function Entry.new (hash, key, value, next) local obj = { hash = hash, key = key, value = value, next = next, } return setmetatable(obj, {__index = Entry}) end function Entry:match (hash, key) return self.hash == hash and self.key == key end end -- class Entry local Dictionary = {_CLASS = 'Dictionary'} do local INITIAL_CAPACITY = 16 function Dictionary.new (size) local obj = { buckets = alloc_array(size or INITIAL_CAPACITY), size = 0, } return setmetatable(obj, {__index = Dictionary}) end function Dictionary:hash (key) if not key then return 0 end local hash = key:custom_hash() return bxor(hash, rshift(hash, 16)) end function Dictionary:is_empty () return self.size == 0 end function Dictionary:get_bucket_idx (hash) return band(self.buckets.n - 1, hash) + 1 end function Dictionary:get_bucket (hash) return self.buckets[self:get_bucket_idx(hash)] end function Dictionary:at (key) local hash = self:hash(key) local e = self:get_bucket(hash) while e do if e:match(hash, key) then return e.value end e = e.next end return nil end function Dictionary:contains_key (key) local hash = self:hash(key) local e = self:get_bucket(hash) while e do if e.match(hash, key) then return true end e = e.next end return false end function Dictionary:at_put (key, value) local hash = self:hash(key) local i = self:get_bucket_idx(hash) local current = self.buckets[i] if not current then self.buckets[i] = self:new_entry(key, value, hash) self.size = self.size + 1 else self:insert_bucket_entry(key, value, hash, current) end if self.size > self.buckets.n then self:resize() end end function Dictionary:new_entry (key, value, hash) return Entry.new(hash, key, value, nil) end function Dictionary:insert_bucket_entry (key, value, hash, head) local current = head while true do if current:match(hash, key) then current.value = value return end if not current.next then self.size = self.size + 1 current.next = self:new_entry(key, value, hash) return end current = current.next end end function Dictionary:resize () local old_storage = self.buckets self.buckets = alloc_array(old_storage.n * 2) self:transfer_entries(old_storage) end function Dictionary:transfer_entries (old_storage) local buckets = self.buckets for i = 1, old_storage.n do local current = old_storage[i] if current then old_storage[i] = nil if not current.next then local hash = band(current.hash, buckets.n - 1) + 1 buckets[hash] = current else self:split_bucket(old_storage, i, current) end end end end function Dictionary:split_bucket (old_storage, i, head) local lo_head, lo_tail = nil, nil local hi_head, hi_tail = nil, nil local current = head while current do if band(current.hash, old_storage.n) == 0 then if not lo_tail then lo_head = current else lo_tail.next = current end lo_tail = current else if not hi_tail then hi_head = current else hi_tail.next = current end hi_tail = current end current = current.next end if lo_tail then lo_tail.next = nil self.buckets[i] = lo_head end if hi_tail then hi_tail.next = nil self.buckets[i + old_storage.n] = hi_head end end function Dictionary:remove_all () self.buckets = alloc_array(self.buckets.n) self.size = 0 end function Dictionary:keys () local keys = Vector.new(self.size) local buckets = self.buckets for i = 1, buckets.n do local current = buckets[i] while current do keys:append(current.key) current = current.next end end return keys end function Dictionary:values () local vals = Vector.new(self.size) local buckets = self.buckets for i = 1, buckets.n do local current = buckets[i] while current do vals:append(current.value) current = current.next end end return vals end end -- class Dictionary local IdEntry = {_CLASS = 'IdEntry'} do setmetatable(IdEntry, {__index = Entry}) function IdEntry.new (hash, key, value, next) local obj = Entry.new (hash, key, value, next) return setmetatable(obj, {__index = IdEntry}) end function IdEntry:match (hash, key) return self.hash == hash and self.key == key end end -- class IdEntry local IdentityDictionary = {_CLASS = 'IdentityDictionary'} do setmetatable(IdentityDictionary, {__index = Dictionary}) function IdentityDictionary.new (size) local obj = Dictionary.new (size) return setmetatable(obj, {__index = Dictionary}) end function IdentityDictionary:new_entry (key, value, hash) return IdEntry.new(hash, key, value, nil) end end -- class IdentityDictionary local Random = {_CLASS = 'Random'} do function Random.new () local obj = {seed = 74755} return setmetatable(obj, {__index = Random}) end function Random:next () self.seed = band(((self.seed * 1309) + 13849), 65535); return self.seed; end end -- class Random --------------------------------- local benchmark = {} do function benchmark:inner_benchmark_loop (inner_iterations) for _ = 1, inner_iterations do if not self:verify_result(self:benchmark()) then return false end end return true end function benchmark:benchmark () error 'subclass_responsibility' end function benchmark:verify_result () error 'subclass_responsibility' end end --------------------------------- local MIN_X = 0.0 local MIN_Y = 0.0 local MAX_X = 1000.0 local MAX_Y = 1000.0 local MIN_Z = 0.0 local MAX_Z = 10.0 local PROXIMITY_RADIUS = 1.0 local GOOD_VOXEL_SIZE = PROXIMITY_RADIUS * 2.0 local Vector2D = {_CLASS = 'Vector2D'} do function Vector2D.new (x, y) local obj = {x = x, y = y} return setmetatable(obj, {__index = Vector2D}) end function Vector2D:plus (other) return Vector2D.new(self.x + other.x, self.y + other.y) end function Vector2D:minus (other) return Vector2D.new(self.x - other.x, self.y - other.y) end local function compare_numbers (a, b) if a == b then return 0 elseif a < b then return -1 elseif a > b then return 1 -- We say that NaN is smaller than non-NaN. elseif a == a then return 1 else return -1 end end function Vector2D:compare_to (other) local result = compare_numbers(self.x, other.x) if result ~= 0 then return result else return compare_numbers(self.y, other.y) end end end -- class Vector2D local Vector3D = {_CLASS = 'Vector3D'} do local sqrt = math.sqrt function Vector3D.new (x, y, z) local obj = {x = x, y = y, z = z} return setmetatable(obj, {__index = Vector3D}) end function Vector3D:plus (other) return Vector3D.new(self.x + other.x, self.y + other.y, self.z + other.z) end function Vector3D:minus (other) return Vector3D.new(self.x - other.x, self.y - other.y, self.z - other.z) end function Vector3D:dot (other) return self.x * other.x + self.y * other.y + self.z * other.z end function Vector3D:squared_magnitude () return self:dot(self) end function Vector3D:magnitude () return sqrt(self:squared_magnitude()) end function Vector3D:times (amount) return Vector3D.new(self.x * amount, self.y * amount, self.z * amount) end end -- class Vector3D local function tree_minimum (x) local current = x while current.left do current = current.left end return current end local Node = {_CLASS = 'Node'} do function Node.new (key, value) local obj = { key = key, value = value, left = nil, right = nil, parent = nil, color = 'red', } return setmetatable(obj, {__index = Node}) end function Node:successor () local x = self if x.right then return tree_minimum(x.right) end local y = x.parent while y and x == y.right do x = y y = y.parent end return y end end -- class Node local RbtEntry = {_CLASS = 'RbtEntry'} do function RbtEntry.new(key, value) local obj = { key = key, value = value } return setmetatable(obj, {__index = RbtEntry}) end end -- class RbtEntry local InsertResult = {_CLASS = 'InsertResult'} do function InsertResult.new(is_new_entry, new_node, old_value) local obj = { is_new_entry = is_new_entry, new_node = new_node, old_value = old_value, } return setmetatable(obj, {__index = InsertResult}) end end -- class InsertResult local RedBlackTree = {_CLASS = 'RedBlackTree'} do function RedBlackTree.new () local obj = {root = nil} return setmetatable(obj, {__index = RedBlackTree}) end function RedBlackTree:put (key, value) local insertion_result = self:tree_insert(key, value) if not insertion_result.is_new_entry then return insertion_result.old_value end local x = insertion_result.new_node while x ~= self.root and x.parent.color == 'red' do if x.parent == x.parent.parent.left then local y = x.parent.parent.right if y and y.color == 'red' then -- Case 1 x.parent.color = 'black' y.color = 'black' x.parent.parent.color = 'red' x = x.parent.parent else if x == x.parent.right then -- Case 2 x = x.parent self:left_rotate(x) end -- Case 3 x.parent.color = 'black' x.parent.parent.color = 'red' self:right_rotate(x.parent.parent) end else -- Same as "then" clause with "right" and "left" exchanged. local y = x.parent.parent.left if y and y.color == 'red' then -- Case 1 x.parent.color = 'black' y.color = 'black' x.parent.parent.color = 'red' x = x.parent.parent else if x == x.parent.left then -- Case 2 x = x.parent self:right_rotate(x) end -- Case 3 x.parent.color = 'black' x.parent.parent.color = 'red' self:left_rotate(x.parent.parent) end end end self.root.color = 'black' return nil end function RedBlackTree:remove (key) local z = self:find_node(key) if not z then return nil end -- Y is the node to be unlinked from the tree. local y if not z.left or not z.right then y = z else y = z:successor() end -- Y is guaranteed to be non-null at this point. local x if y.left then x = y.left else x = y.right end -- X is the child of y which might potentially replace y -- in the tree. X might be null at this point. local x_parent if x then x.parent = y.parent x_parent = x.parent else x_parent = y.parent end if not y.parent then self.root = x else if y == y.parent.left then y.parent.left = x else y.parent.right = x end end if y ~= z then if y.color == 'black' then self:remove_fixup(x, x_parent) end y.parent = z.parent y.color = z.color y.left = z.left y.right = z.right if z.left then z.left.parent = y end if z.right then z.right.parent = y end if z.parent then if z.parent.left == z then z.parent.left = y else z.parent.right = y end else self.root = y end elseif y.color == 'black' then self:remove_fixup(x, x_parent) end return z.value end function RedBlackTree:get (key) local node = self:find_node(key) if node then return node.value end return nil end function RedBlackTree:for_each (fn) if not self.root then return end local current = tree_minimum(self.root) while current do fn(RbtEntry.new(current.key, current.value)) current = current:successor() end end function RedBlackTree:find_node (key) local current = self.root while current do local comparison_result = key:compare_to(current.key) if comparison_result == 0 then return current elseif comparison_result < 0 then current = current.left else current = current.right end end return nil end function RedBlackTree:tree_insert (key, value) local y = nil local x = self.root while x do y = x local comparison_result = key:compare_to(x.key) if comparison_result < 0 then x = x.left elseif comparison_result > 0 then x = x.right else local old_value = x.value x.value = value return InsertResult.new(false, nil, old_value) end end local z = Node.new(key, value) z.parent = y if not y then self.root = z else if key:compare_to(y.key) < 0 then y.left = z else y.right = z end end return InsertResult.new(true, z, nil) end function RedBlackTree:left_rotate (x) local y = x.right -- Turn y's left subtree into x's right subtree. x.right = y.left if y.left then y.left.parent = x end -- Link x's parent to y. y.parent = x.parent if not x.parent then self.root = y else if x == x.parent.left then x.parent.left = y else x.parent.right = y end end -- Put x on y's left. y.left = x x.parent = y return y end function RedBlackTree:right_rotate (y) local x = y.left -- Turn x's right subtree into y's left subtree. y.left = x.right if x.right then x.right.parent = y end -- Link y's parent to x. x.parent = y.parent if not y.parent then self.root = x else if y == y.parent.left then y.parent.left = x else y.parent.right = x end end x.right = y y.parent = x return x end function RedBlackTree:remove_fixup (x, x_parent) while x ~= self.root and (not x or x.color == 'black') do if x == x_parent.left then -- Note: the text points out that w cannot be null. -- The reason is not obvious from simply looking at the code; -- it comes about from the properties of the red-black tree. local w = x_parent.right if w.color == 'red' then -- Case 1 w.color = 'black' x_parent.color = 'red' self:left_rotate(x_parent) w = x_parent.right end if (not w.left or w.left.color == 'black') and (not w.right or w.right.color == 'black') then -- Case 2 w.color = 'red' x = x_parent x_parent = x.parent else if not w.right or w.right.color == 'black' then -- Case 3 w.left.color = 'black' w.color = 'red' self:right_rotate(w) w = x_parent.right end -- Case 4 w.color = x_parent.color x_parent.color = 'black' if w.right then w.right.color = 'black' end self:left_rotate(x_parent) x = self.root x_parent = x.parent end else -- Same as "then" clause with "right" and "left" exchanged. local w = x_parent.left if w.color == 'red' then -- Case 1 w.color = 'black' x_parent.color = 'red' self:right_rotate(x_parent) w = x_parent.left end if (not w.right or w.right.color == 'black') and (not w.left or w.left.color == 'black') then -- Case 2 w.color = 'red' x = x_parent x_parent = x.parent else if not w.left or w.left.color == 'black' then -- Case 3 w.right.color = 'black' w.color = 'red' self:left_rotate(w) w = x_parent.left end -- Case 4 w.color = x_parent.color x_parent.color = 'black' if w.left then w.left.color = 'black' end self:right_rotate(x_parent) x = self.root x_parent = x.parent end end end if x then x.color = 'black' end end end -- class RedBlackTree local CallSign = {_CLASS = 'CallSign'} do function CallSign.new (value) local obj = {value = value} return setmetatable(obj, {__index = CallSign}) end function CallSign:compare_to (other) return (self.value == other.value) and 0 or ((self.value < other.value) and -1 or 1) end end -- class CallSign local Collision = {_CLASS = 'Collision'} do function Collision.new (aircraft_a, aircraft_b, position) local obj = { aircraft_a = aircraft_a, aircraft_b = aircraft_b, position = position } return setmetatable(obj, {__index = Collision}) end end -- class Collision local Motion = {_CLASS = 'Motion'} do local sqrt = math.sqrt function Motion.new (callsign, pos_one, pos_two) local obj = { callsign = callsign, pos_one = pos_one, pos_two = pos_two, } return setmetatable(obj, {__index = Motion}) end function Motion:delta () return self.pos_two:minus(self.pos_one) end function Motion:find_intersection (other) local init1 = self.pos_one local init2 = other.pos_one local vec1 = self:delta() local vec2 = other:delta() local radius = PROXIMITY_RADIUS -- this test is not geometrical 3-d intersection test, -- it takes the fact that the aircraft move -- into account; so it is more like a 4d test -- (it assumes that both of the aircraft have a constant speed -- over the tested interval) -- we thus have two points, -- each of them moving on its line segment at constant speed; -- we are looking for times when the distance between -- these two points is smaller than r -- vec1 is vector of aircraft 1 -- vec2 is vector of aircraft 2 -- a = (V2 - V1)^T * (V2 - V1) local a = vec2:minus(vec1):squared_magnitude() if a ~= 0.0 then -- we are first looking for instances -- of time when the planes are exactly r from each other -- at least one plane is moving; -- if the planes are moving in parallel, they do not have constant speed -- if the planes are moving in parallel, then -- if the faster starts behind the slower, -- we can have 2, 1, or 0 solutions -- if the faster plane starts in front of the slower, -- we can have 0 or 1 solutions -- if the planes are not moving in parallel, then -- point P1 = I1 + vV1 -- point P2 = I2 + vV2 -- - looking for v, such that dist(P1,P2) = || P1 - P2 || = r -- it follows that || P1 - P2 || = sqrt( < P1-P2, P1-P2 > ) -- 0 = -r^2 + < P1 - P2, P1 - P2 > -- from properties of dot product -- 0 = -r^2 + + v * 2 + v^2 * -- so we calculate a, b, c - and solve the quadratic equation -- 0 = c + bv + av^2 -- b = 2 * local b = 2.0 * init1:minus(init2):dot(vec1:minus(vec2)) -- c = -r^2 + (I2 - I1)^T * (I2 - I1) local c = -radius * radius + init2:minus(init1):squared_magnitude() local discr = b * b - 4.0 * a * c if discr < 0.0 then return nil end local v1 = (-b - sqrt(discr)) / (2.0 * a) local v2 = (-b + sqrt(discr)) / (2.0 * a) if v1 <= v2 and ((v1 <= 1.0 and 1.0 <= v2) or (v1 <= 0.0 and 0.0 <= v2) or (0.0 <= v1 and v2 <= 1.0)) then -- Pick a good "time" at which to report the collision. local v if v1 <= 0.0 then -- The collision started before this frame. -- Report it at the start of the frame. v = 0.0 else -- The collision started during this frame. Report it at that moment. v = v1 end local result1 = init1:plus(vec1:times(v)) local result2 = init2:plus(vec2:times(v)) local result = result1:plus(result2):times(0.5) if result.x >= MIN_X and result.x <= MAX_X and result.y >= MIN_Y and result.y <= MAX_Y and result.z >= MIN_Z and result.z <= MAX_Z then return result end end return nil end -- the planes have the same speeds and are moving in parallel -- (or they are not moving at all) -- they thus have the same distance all the time; -- we calculate it from the initial point -- dist = || i2 - i1 || = sqrt( ( i2 - i1 )^T * ( i2 - i1 ) ) local dist = init2:minus(init1):magnitude() if dist <= radius then return init1:plus(init2):times(0.5) end return nil end end -- class Motion local CollisionDetector = {_CLASS = 'CollisionDetector'} do local floor = math.floor local HORIZONTAL = Vector2D.new(GOOD_VOXEL_SIZE, 0.0) local VERTICAL = Vector2D.new(0.0, GOOD_VOXEL_SIZE) function CollisionDetector.new () local obj = {state = RedBlackTree.new()} return setmetatable(obj, {__index = CollisionDetector}) end function CollisionDetector:handle_new_frame (frame) local motions = Vector.new() local seen = RedBlackTree.new() frame:each(function (aircraft) local old_position = self.state:put(aircraft.callsign, aircraft.position) local new_position = aircraft.position seen:put(aircraft.callsign, true) if not old_position then -- Treat newly introduced aircraft as if they were stationary. old_position = new_position end motions:append(Motion.new(aircraft.callsign, old_position, new_position)) end) -- Remove aircraft that are no longer present. local to_remove = Vector.new() self.state:for_each(function (e) if not seen:get(e.key) then to_remove:append(e.key) end end) to_remove:each(function (e) self.state:remove(e) end) local all_reduced = self:reduce_collision_set(motions) local collisions = Vector.new() all_reduced:each(function (reduced) for i = 1, reduced:size() do local motion1 = reduced:at(i) for j = i + 1, reduced:size() do local motion2 = reduced:at(j) local collision = motion1:find_intersection(motion2) if collision then collisions:append(Collision.new(motion1.callsign, motion2.callsign, collision)) end end end end) return collisions end function CollisionDetector:is_in_voxel (voxel, motion) if voxel.x > MAX_X or voxel.x < MIN_X or voxel.y > MAX_Y or voxel.y < MIN_Y then return false end local init = motion.pos_one local fin = motion.pos_two local v_s = GOOD_VOXEL_SIZE local r = PROXIMITY_RADIUS / 2.0 local v_x = voxel.x local x0 = init.x local xv = fin.x - init.x local v_y = voxel.y local y0 = init.y local yv = fin.y - init.y local low_x = (v_x - r - x0) / xv local high_x = (v_x + v_s + r - x0) / xv if xv < 0.0 then local tmp = low_x low_x = high_x high_x = tmp end local low_y = (v_y - r - y0) / yv local high_y = (v_y + v_s + r - y0) / yv if yv < 0.0 then local tmp = low_y low_y = high_y high_y = tmp end return (((xv == 0.0 and v_x <= x0 + r and x0 - r <= v_x + v_s) or -- no motion in x (low_x <= 1.0 and 1.0 <= high_x) or (low_x <= 0.0 and 0.0 <= high_x) or (0.0 <= low_x and high_x <= 1.0)) and ((yv == 0.0 and v_y <= y0 + r and y0 - r <= v_y + v_s) or -- no motion in y ((low_y <= 1.0 and 1.0 <= high_y) or (low_y <= 0.0 and 0.0 <= high_y) or (0.0 <= low_y and high_y <= 1.0))) and (xv == 0.0 or yv == 0.0 or -- no motion in x or y or both (low_y <= high_x and high_x <= high_y) or (low_y <= low_x and low_x <= high_y) or (low_x <= low_y and high_y <= high_x))) end function CollisionDetector:put_into_map (voxel_map, voxel, motion) local array = voxel_map:get(voxel) if not array then array = Vector.new() voxel_map:put(voxel, array) end array:append(motion) end function CollisionDetector:recurse (voxel_map, seen, next_voxel, motion) if not self:is_in_voxel(next_voxel, motion) then return end if seen:put(next_voxel, true) then return end self:put_into_map(voxel_map, next_voxel, motion) self:recurse(voxel_map, seen, next_voxel:minus(HORIZONTAL), motion) self:recurse(voxel_map, seen, next_voxel:plus(HORIZONTAL), motion) self:recurse(voxel_map, seen, next_voxel:minus(VERTICAL), motion) self:recurse(voxel_map, seen, next_voxel:plus(VERTICAL), motion) self:recurse(voxel_map, seen, next_voxel:minus(HORIZONTAL):minus(VERTICAL), motion) self:recurse(voxel_map, seen, next_voxel:minus(HORIZONTAL):plus(VERTICAL), motion) self:recurse(voxel_map, seen, next_voxel:plus(HORIZONTAL):minus(VERTICAL), motion) self:recurse(voxel_map, seen, next_voxel:plus(HORIZONTAL):plus(VERTICAL), motion) end function CollisionDetector:reduce_collision_set (motions) local voxel_map = RedBlackTree.new() motions:each(function (motion) self:draw_motion_on_voxel_map(voxel_map, motion) end) local result = Vector.new() voxel_map:for_each(function (e) if e.value:size() > 1 then result:append(e.value) end end) return result end function CollisionDetector:voxel_hash (position) local x_div = floor(position.x / GOOD_VOXEL_SIZE) local y_div = floor(position.y / GOOD_VOXEL_SIZE) local x = GOOD_VOXEL_SIZE * x_div local y = GOOD_VOXEL_SIZE * y_div if position.x < 0 then x = x - GOOD_VOXEL_SIZE end if position.y < 0 then y = y - GOOD_VOXEL_SIZE end return Vector2D.new(x, y) end function CollisionDetector:draw_motion_on_voxel_map (voxel_map, motion) local seen = RedBlackTree.new() return self:recurse(voxel_map, seen, self:voxel_hash(motion.pos_one), motion) end end -- class CollisionDetector local Aircraft = {_CLASS = 'Aircraft'} do function Aircraft.new (callsign, position) local obj = { callsign = callsign, position = position } return setmetatable(obj, {__index = Aircraft}) end end -- class Collision local Simulator = {_CLASS = 'Simulator'} do local cos = math.cos local sin = math.sin function Simulator.new (num_aircrafts) local aircraft = Vector.new() for i = 1, num_aircrafts do aircraft:append(CallSign.new(i)) end local obj = {aircraft = aircraft} return setmetatable(obj, {__index = Simulator}) end function Simulator:simulate (time) local frame = Vector.new() for i = 1, self.aircraft:size() - 1, 2 do frame:append(Aircraft.new(self.aircraft:at(i), Vector3D.new(time, cos(time) * 2 + (i - 1) * 3, 10.0))) frame:append(Aircraft.new(self.aircraft:at(i + 1), Vector3D.new(time, sin(time) * 2 + (i - 1) * 3, 10.0))) end return frame end end -- class Simulator local cd = {} do setmetatable(cd, {__index = benchmark}) function cd:benchmark (num_aircrafts) local num_frames = 200 local simulator = Simulator.new(num_aircrafts) local detector = CollisionDetector.new() local actual_collisions = 0 for i = 0, num_frames - 1 do local time = i / 10.0 local collisions = detector:handle_new_frame(simulator:simulate(time)) actual_collisions = actual_collisions + collisions:size() end return actual_collisions end function cd:inner_benchmark_loop (inner_iterations) return self:verify_result(self:benchmark(inner_iterations), inner_iterations) end function cd:verify_result (actual_collisions, num_aircrafts) if num_aircrafts == 1000 then return actual_collisions == 14484 elseif num_aircrafts == 500 then return actual_collisions == 14484 elseif num_aircrafts == 250 then return actual_collisions == 10830 elseif num_aircrafts == 200 then return actual_collisions == 8655 elseif num_aircrafts == 100 then return actual_collisions == 4305 elseif num_aircrafts == 10 then return actual_collisions == 390 elseif num_aircrafts == 2 then return actual_collisions == 42 else print(('No verification result for %d found'):format(num_aircrafts)) print(('Result is: %d'):format(actual_collisions)) return false end end end -- object cd return function(N) cd:inner_benchmark_loop(N) end