/traderous

To get this branch, use:
bzr branch http://9ix.org/bzr/traderous

« back to all changes in this revision

Viewing changes to zoetrope/core/collision.lua

  • Committer: Josh C
  • Date: 2013-05-04 20:45:17 UTC
  • Revision ID: josh@9ix.org-20130504204517-1rfp92svud12kg42
zoetrope 1.4

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
-- Class: Collision
 
2
-- This is a utility class that helps with collision detection. It's aware
 
3
-- of <Sprite>s and <Group>s and makes sure collisions are resolved in the
 
4
-- correct order (most overlap to least). You shouldn't have to use this class
 
5
-- directly.
 
6
--
 
7
-- See Also:
 
8
--              <Sprite.collide>, <Group.collide>
 
9
 
 
10
Collision = Class:extend
 
11
{
 
12
        -- Property: gridSize
 
13
        -- Default grid size used when checking collisions. Roughly speaking, this
 
14
        -- should be two times as big as your most common sprite size, but tweaking
 
15
        -- this number can yield better performance.
 
16
        gridSize = 25,
 
17
 
 
18
        -- Method: check
 
19
        -- Checks for collisions between <Sprite>s and <Group>s. If you call
 
20
        -- Collision:check(a, b, c), it will check for collisions between a and b,
 
21
        -- a and c, but not b and c.
 
22
        --
 
23
        -- It spatially hashes all objects into a grid, then checks for collisions via
 
24
        -- <Sprite.overlap()>. If an overlap is detected, then the collision is recorded.
 
25
        -- As a final step, this calls collidedWith() on sprites that collided, but in 
 
26
        -- descending order of overlap. (This normally only triggers the onCollide() handler
 
27
        -- for the sprite, but <Map>s take advantage of this indirection.)
 
28
        -- The sequence of collision resolutions is important, so that displacement occurs
 
29
        -- in an order that prevents sprites from getting stuck on walls made of multiple sprites.
 
30
        --
 
31
        -- Arguments:
 
32
        --              a - primary <Sprite> or <Group>
 
33
        --              ... - any number of <Sprite>s or <Group>s to check for collisions against
 
34
        --                        the A sprite or group
 
35
        --
 
36
        -- Returns:
 
37
        --              nothing
 
38
 
 
39
        check = function (self, a, ...)
 
40
                -- coerce all arguments into a flat list of sprites,
 
41
                -- recording where the first argument (or A group) sits in the list
 
42
 
 
43
                local args = {...}
 
44
                local list = self:solidSprites(a)
 
45
                local aLength = #list
 
46
 
 
47
                for _, item in pairs(args) do
 
48
                        self:solidSprites(item, list)
 
49
                end
 
50
 
 
51
                -- build a spatial hash from the list, recording the grid
 
52
                -- cells that each of the sprites fits inside.
 
53
                -- we also record which cells each of the sprites in the A group
 
54
                -- sits in.
 
55
 
 
56
                local grid = {}
 
57
                local gridSize = a.gridSize or self.gridSize
 
58
                local gridded = {}
 
59
                local deferred = {}
 
60
                local aHuge = {}
 
61
                local aCells = {}
 
62
 
 
63
                for i, spr in ipairs(list) do
 
64
                        if not gridded[spr] then
 
65
                                local startX = math.floor(spr.x / gridSize)
 
66
                                local endX = math.floor((spr.x + spr.width) / gridSize)
 
67
                                local startY = math.floor(spr.y / gridSize)
 
68
                                local endY = math.floor((spr.y + spr.height) / gridSize)
 
69
 
 
70
                                -- Special casing of very large sprites (as defined as >= 25 cells in
 
71
                                -- area). If they are in the A list, we just reserve them
 
72
                                -- for later and check them against all sprites in the other lists.
 
73
                                -- If they are not in the A list, we defer them to the very end of the gridding
 
74
                                -- process, only to cells that have already been gridded by virtue of another
 
75
                                -- sprite being in them.
 
76
                                --
 
77
                                -- The assumption here is that huge sprites are probably big tilemaps, and
 
78
                                -- thus likely to collide with every sprite anyway.
 
79
 
 
80
                                if (endX - startX) * (endY - startY) > 25 then
 
81
                                        if i <= aLength then
 
82
                                                table.insert(aHuge, spr)
 
83
                                        else
 
84
                                                table.insert(deferred, { spr = spr, startX = startX, endX = endX, startY = startY, endY = endY })
 
85
                                        end
 
86
                                else
 
87
                                        if i <= aLength then
 
88
                                                aCells[spr] = {}
 
89
                                        end
 
90
                                
 
91
                                        for x = startX, endX do
 
92
                                                grid[x] = grid[x] or {}
 
93
 
 
94
                                                for y = startY, endY do
 
95
                                                        grid[x][y] = grid[x][y] or {}
 
96
                                                        table.insert(grid[x][y], spr)
 
97
 
 
98
                                                        if i <= aLength then
 
99
                                                                table.insert(aCells[spr], grid[x][y])
 
100
                                                        end
 
101
                                                end
 
102
                                        end
 
103
                                end
 
104
 
 
105
                                gridded[spr] = true
 
106
                        end
 
107
                end
 
108
 
 
109
                -- Grid all huge sprites we just deferred. Unlike above,
 
110
                -- we only add them to grid cells that already have sprites in them.
 
111
 
 
112
                for _, d in pairs(deferred) do
 
113
                        for x = d.startX, d.endX do
 
114
                                if grid[x] then
 
115
                                        for y = d.startY, d.endY do
 
116
                                                if grid[x][y] then
 
117
                                                        table.insert(grid[x][y], d.spr)
 
118
                                                end
 
119
                                        end
 
120
                                end
 
121
                        end
 
122
                end
 
123
 
 
124
                -- aCells now is a table whose keys are sprites in this group,
 
125
                -- and whose values are a table of grid cells that the sprite is in.
 
126
                -- We now build a list of collisions based on that.
 
127
 
 
128
                local collisions = {}
 
129
                local alreadyCollided = {}
 
130
 
 
131
                for aSpr, cells in pairs(aCells) do
 
132
                        alreadyCollided[aSpr] = alreadyCollided[aSpr] or {}
 
133
                        
 
134
                        for _, cell in pairs(cells) do
 
135
                                for _, bSpr in pairs(cell) do
 
136
                                        if aSpr ~= bSpr and not alreadyCollided[aSpr][bSpr] then
 
137
                                                local xOverlap, yOverlap = bSpr:overlap(aSpr.x, aSpr.y, aSpr.width, aSpr.height)
 
138
 
 
139
                                                if xOverlap ~= 0 or yOverlap ~= 0 then
 
140
                                                        table.insert(collisions, { area = xOverlap * yOverlap, x = xOverlap, y = yOverlap, a = aSpr, b = bSpr })
 
141
                                                end
 
142
 
 
143
                                                -- record that we've already checked this collision
 
144
 
 
145
                                                alreadyCollided[bSpr] = alreadyCollided[bSpr] or {}
 
146
                                                alreadyCollided[aSpr][bSpr] = true
 
147
                                                alreadyCollided[bSpr][aSpr] = true
 
148
                                        end
 
149
                                end
 
150
                        end
 
151
                end
 
152
 
 
153
                -- Run through the huge sprites in the A list, if any, adding
 
154
                -- collisions to the existing list.
 
155
 
 
156
                for _, aSpr in pairs(aHuge) do
 
157
                        alreadyCollided[aSpr] = alreadyCollided[aSpr] or {}
 
158
 
 
159
                        for i = aLength + 1, #list do
 
160
                                local bSpr = list[i]
 
161
 
 
162
                                if aSpr ~= bSpr and not alreadyCollided[aSpr][bSpr] then
 
163
                                        local xOverlap, yOverlap = bSpr:overlap(aSpr.x, aSpr.y, aSpr.width, aSpr.height)
 
164
 
 
165
                                        if xOverlap ~= 0 or yOverlap ~= 0 then
 
166
                                                table.insert(collisions, { area = xOverlap * yOverlap, x = xOverlap, y = yOverlap, a = aSpr, b = bSpr })
 
167
                                        end
 
168
 
 
169
                                        alreadyCollided[bSpr] = alreadyCollided[bSpr] or {}
 
170
                                        alreadyCollided[aSpr][bSpr] = true
 
171
                                        alreadyCollided[bSpr][aSpr] = true
 
172
                                end
 
173
                        end
 
174
                end
 
175
 
 
176
                -- collisions now is a list, each item containing these properties:
 
177
                --              a - sprite colliding
 
178
                --              b - second sprite colliding
 
179
                --              x - x overlap
 
180
                --              y - y overlap
 
181
                --              area - square area of overlap
 
182
                --
 
183
                -- we now sort the table and resolve collisions in descending order of overlap area.
 
184
                
 
185
                table.sort(collisions, self.sortCollisions)
 
186
 
 
187
                for _, col in ipairs(collisions) do
 
188
                        col.a:collidedWith(col.b, col.x, col.y)
 
189
                        col.b:collidedWith(col.a, col.x, col.y)
 
190
                end
 
191
        end,
 
192
 
 
193
        -- Method: solidSprites
 
194
        -- Returns a table of <Sprite>s belonging to an object that
 
195
        -- should be collided with others, descending into groups.
 
196
        --
 
197
        -- Arguments:
 
198
        --              source - <Sprite> or <Group>
 
199
        --              existing - existing table to add to
 
200
        --
 
201
        -- Returns:
 
202
        --              table of <Sprite>s
 
203
 
 
204
        solidSprites = function (self, source, existing)
 
205
                local result = existing or {}
 
206
                
 
207
                if source.solid then
 
208
                        if source.x and source.y and source.width and source.height then
 
209
                                table.insert(result, source)
 
210
                        elseif source.sprites then
 
211
                                for _, spr in pairs(source.sprites) do
 
212
                                        if spr.sprites then
 
213
                                                result = self:solidSprites(spr, result)
 
214
                                        elseif spr.solid then
 
215
                                                table.insert(result, spr)
 
216
                                        end
 
217
                                end
 
218
                        end
 
219
                end
 
220
 
 
221
                return result
 
222
        end,
 
223
 
 
224
        -- Method: sortCollisions
 
225
        -- This sorts a table of collisions in descending order of overlap,
 
226
        -- suitable for use in conjunction with table.sort().
 
227
        --
 
228
        -- Arguments:
 
229
        --              a - one collision table
 
230
        --              b - one collision table
 
231
        --
 
232
        -- Returns:
 
233
        --              whether a should be sorted before b
 
234
 
 
235
        sortCollisions = function (a, b)
 
236
                return a.area > b.area
 
237
        end
 
238
}