1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
dir_no = 0
dir_up = 1
dir_down = 2
dir_left = 3
dir_right = 4
-- -----------------------------------------------------------------
function getDirShift(dir)
local shiftX, shiftY = 0, 0
if dir == dir_left then
shiftX = -1
elseif dir == dir_right then
shiftX = 1
elseif dir == dir_up then
shiftY = -1
elseif dir == dir_down then
shiftY = 1
end
return shiftX, shiftY
end
-- -----------------------------------------------------------------
local function isFreePlace(model, locX, locY)
for x = locX, locX + model:getW() - 1 do
for y = locY, locY + model:getH() - 1 do
if not model_equals(-1, x, y) and not model_equals(model.index, x, y) then
return false
end
end
end
return true
end
-- -----------------------------------------------------------------
local function tryPlace(data, place)
local locX = place.x
local locY = place.y
result = false
if nil == data.closed[locX] then
data.closed[locX] = {}
end
if not data.closed[locX][locY] then
data.closed[locX][locY] = true
if isFreePlace(data.model, locX, locY) then
result = true
end
end
return result
end
-- -----------------------------------------------------------------
local function isInRect(x, y, w, h, destX, destY)
return x <= destX and destX < x + w and y <= destY and destY < y + h
end
-- -----------------------------------------------------------------
function findDir(model, destX, destY)
-- Breadth-first search
-- Find starting dir to the destination
-- Return dir_no when there is no free path
local locX, locY = model:getLoc()
local w = model:getW()
local h = model:getH()
if isInRect(locX, locY, w, h, destX, destY) then
return dir_no
end
if not model_equals(-1, destX, destY) then
return dir_no
end
local data = {}
data.closed = {}
data.closed[locX] = {}
data.closed[locX][locY] = true
data.model = model
local fifo = {}
table.insert(fifo, {dir=dir_left, x=locX - 1, y=locY})
table.insert(fifo, {dir=dir_right, x=locX + 1, y=locY})
table.insert(fifo, {dir=dir_up, x=locX, y=locY - 1})
table.insert(fifo, {dir=dir_down, x=locX, y=locY + 1})
while table.getn(fifo) > 0 do
local place = table.remove(fifo, 1)
if tryPlace(data, place) then
if isInRect(place.x, place.y, w, h, destX, destY) then
return place.dir
end
table.insert(fifo, {dir=place.dir, x=place.x - 1, y=place.y})
table.insert(fifo, {dir=place.dir, x=place.x + 1, y=place.y})
table.insert(fifo, {dir=place.dir, x=place.x, y=place.y - 1})
table.insert(fifo, {dir=place.dir, x=place.x, y=place.y + 1})
end
end
return dir_no
end
|
