/zoeplat

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

« back to all changes in this revision

Viewing changes to zoetrope/core/collision.lua

  • Committer: Josh C
  • Date: 2013-03-05 00:14:58 UTC
  • Revision ID: josh@9ix.org-20130305001458-206jxv29dgeenj3n
jump

Show diffs side-by-side

added added

removed removed

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