1local helper = wesnoth.require "helper"
2local utils = wesnoth.require "wml-utils"
3
4wesnoth.wml_actions.random_placement = function(cfg)
5	local parsed = wml.shallow_parsed(cfg)
6	-- TODO: In most cases this tag is used to place units, so maybe make include_borders=no the default for [filter_location]?
7	local filter = wml.get_child(parsed, "filter_location") or {}
8	local command = wml.get_child(parsed, "command") or helper.wml_error("[random_placement] missing required [command] subtag")
9	local distance = cfg.min_distance or 0
10	local num_items = cfg.num_items or helper.wml_error("[random_placement] missing required 'num_items' attribute")
11	local variable = cfg.variable or helper.wml_error("[random_placement] missing required 'variable' attribute")
12	local allow_less = cfg.allow_less == true
13	local variable_previous = utils.start_var_scope(variable)
14	local math_abs = math.abs
15	local locs = wesnoth.get_locations(filter)
16	if type(num_items) == "string" then
17		num_items = math.floor(load("local size = " .. #locs .. "; return " .. num_items)())
18		print("num_items=" .. num_items .. ", #locs=" .. #locs)
19	end
20	local size = #locs
21	for i = 1, num_items do
22		if size == 0 then
23			if allow_less then
24				print("placed only " .. i .. " items")
25				return
26			else
27				helper.wml_error("[random_placement] failed to place items. only " .. i .. " items were placed")
28			end
29		end
30		local index = wesnoth.random(size)
31		local point = locs[index]
32		wml.variables[variable .. ".x"] = point[1]
33		wml.variables[variable .. ".y"] = point[2]
34		wml.variables[variable .. ".n"] = i
35		wml.variables[variable .. ".terrain"] = wesnoth.get_terrain(point[1], point[2])
36		if distance < 0 then
37			-- optimisation: nothing to do for distance < 0
38		elseif distance == 0 then
39			-- optimisation: for distance = 0 we just need to remove the element at index
40			-- optimisation: swapping elements and storing size in an extra variable is faster than table.remove(locs, j)
41			locs[index] = locs[size]
42			size = size - 1
43		else
44			-- the default case and the main reason why this was implemented.
45			for j = size, 1, -1 do
46				local x1 = locs[j][1]
47				local y1 = locs[j][2]
48				local x2 = point[1]
49				local y2 = point[2]
50				-- optimisation: same effect as "if wesnoth.map.distance_between(x1,y1,x2,y2) <= distance then goto continue; end" but faster.
51				local d_x = math_abs(x1-x2)
52				if d_x > distance then
53					goto continue
54				end
55				if d_x % 2 ~= 0 then
56					if x1 % 2 == 0 then
57						y2 = y2 - 0.5
58					else
59						y2 = y2 + 0.5
60					end
61				end
62				local d_y = math_abs(y1-y2)
63				if d_x + 2*d_y > 2*distance then
64					goto continue
65				end
66				-- optimisation: swapping elements and storing size in an extra variable is faster than table.remove(locs, j)
67				locs[j] = locs[size]
68				size = size - 1
69				::continue::
70			end
71		end
72		wesnoth.wml_actions.command (command)
73	end
74	utils.end_var_scope(variable, variable_previous)
75
76end