openMSX
SpriteChecker.cc
Go to the documentation of this file.
1/*
2TODO:
3- Verify model for 5th sprite number calculation.
4 For example, does it have the right value in text mode?
5- Further investigate sprite collision registers:
6 - If there is NO collision, the value of these registers constantly changes.
7 Could this be some kind of indication for the scanline XY coords???
8 - Bit 9 of the Y coord (odd/even page??) is not yet implemented.
9*/
10
11#include "SpriteChecker.hh"
12#include "RenderSettings.hh"
13#include "BooleanSetting.hh"
14#include "serialize.hh"
15#include <algorithm>
16#include <bit>
17#include <cassert>
18
19namespace openmsx {
20
22 EmuTime::param time)
23 : vdp(vdp_), vram(vdp.getVRAM())
24 , limitSpritesSetting(renderSettings.getLimitSpritesSetting())
25 , frameStartTime(time)
26{
29}
30
31void SpriteChecker::reset(EmuTime::param time)
32{
33 vdp.setSpriteStatus(0); // TODO 0x00 or 0x1F (blueMSX has 0x1F)
34 collisionX = 0;
35 collisionY = 0;
36
37 frameStart(time);
38
39 updateSpritesMethod = &SpriteChecker::updateSprites1;
40}
41
42static constexpr SpriteChecker::SpritePattern doublePattern(SpriteChecker::SpritePattern a)
43{
44 // bit-pattern "abcd...." gets expanded to "aabbccdd"
45 // upper 16 bits (of a 32 bit number) contain the pattern
46 // lower 16 bits must be zero
47 // // abcdefghijklmnop0000000000000000
48 a = (a | (a >> 8)) & 0xFF00FF00; // abcdefgh00000000ijklmnop00000000
49 a = (a | (a >> 4)) & 0xF0F0F0F0; // abcd0000efgh0000ijkl0000mnop0000
50 a = (a | (a >> 2)) & 0xCCCCCCCC; // ab00cd00ef00gh00ij00kl00mn00op00
51 a = (a | (a >> 1)) & 0xAAAAAAAA; // a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0
52 return a | (a >> 1); // aabbccddeeffgghhiijjkkllmmnnoopp
53}
54
55inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternNP(
56 unsigned patternNr, unsigned y)
57{
58 auto patternPtr = vram.spritePatternTable.getReadArea<256 * 8>(0);
59 unsigned index = patternNr * 8 + y;
60 SpritePattern pattern = patternPtr[index] << 24;
61 if (vdp.getSpriteSize() == 16) {
62 pattern |= patternPtr[index + 16] << 16;
63 }
64 return !vdp.isSpriteMag() ? pattern : doublePattern(pattern);
65}
66inline SpriteChecker::SpritePattern SpriteChecker::calculatePatternPlanar(
67 unsigned patternNr, unsigned y)
68{
69 auto [ptr0, ptr1] = vram.spritePatternTable.getReadAreaPlanar<256 * 8>(0);
70 unsigned index = patternNr * 8 + y;
71 auto patternPtr = (index & 1) ? ptr1 : ptr0;
72 index /= 2;
73 SpritePattern pattern = patternPtr[index] << 24;
74 if (vdp.getSpriteSize() == 16) {
75 pattern |= patternPtr[index + (16 / 2)] << 16;
76 }
77 return !vdp.isSpriteMag() ? pattern : doublePattern(pattern);
78}
79
80void SpriteChecker::updateSprites1(int limit)
81{
82 if (vdp.spritesEnabledFast()) {
83 if (vdp.isDisplayEnabled()) {
84 // in display area
85 checkSprites1(currentLine, limit);
86 } else {
87 // in border, only check last line of top border
88 int l0 = vdp.getLineZero() - 1;
89 if ((currentLine <= l0) && (l0 < limit)) {
90 checkSprites1(l0, l0 + 1);
91 }
92 }
93 }
94 currentLine = limit;
95}
96
97inline void SpriteChecker::checkSprites1(int minLine, int maxLine)
98{
99 // This implementation contains a double for-loop. The outer loop goes
100 // over the sprites, the inner loop over the to-be-checked lines. This
101 // is not the order in which the real VDP performs this operation: the
102 // real VDP renders line-per-line and for each line checks all 32
103 // sprites.
104 //
105 // Though this 'reverse' order allows to skip over very large regions
106 // of the inner loop: we only have to process the lines were a
107 // particular sprite is actually visible. I measured this makes this
108 // routine 4x-5x faster!
109 //
110 // This routine also needs to detect the sprite number of the 'first'
111 // 5th-sprite-condition. With 'first' meaning the first line where this
112 // condition occurs. Because our loops are swapped compared to the real
113 // VDP, we need some extra fixup logic to correctly detect this.
114
115 // Calculate display line.
116 // This is the line sprites are checked at; the line they are displayed
117 // at is one lower.
118 int displayDelta = vdp.getVerticalScroll() - vdp.getLineZero();
119
120 // Get sprites for this line and detect 5th sprite if any.
121 bool limitSprites = limitSpritesSetting.getBoolean();
122 int size = vdp.getSpriteSize();
123 bool mag = vdp.isSpriteMag();
124 int magSize = (mag + 1) * size;
125 auto attributePtr = vram.spriteAttribTable.getReadArea<32 * 4>(0);
126 byte patternIndexMask = size == 16 ? 0xFC : 0xFF;
127 int fifthSpriteNum = -1; // no 5th sprite detected yet
128 int fifthSpriteLine = 999; // larger than any possible valid line
129
130 int sprite = 0;
131 for (; sprite < 32; ++sprite) {
132 int y = attributePtr[4 * sprite + 0];
133 if (y == 208) break;
134
135 for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
136 // Calculate line number within the sprite.
137 int displayLine = line + displayDelta;
138 int spriteLine = (displayLine - y) & 0xFF;
139 if (spriteLine >= magSize) {
140 // Skip ahead till sprite becomes visible.
141 line += 256 - spriteLine - 1; // -1 because of for-loop
142 continue;
143 }
144
145 int visibleIndex = spriteCount[line];
146 if (visibleIndex == 4) {
147 // Find earliest line where this condition occurs.
148 if (line < fifthSpriteLine) {
149 fifthSpriteLine = line;
150 fifthSpriteNum = sprite;
151 }
152 if (limitSprites) continue;
153 }
154
155 SpriteInfo& sip = spriteBuffer[line][visibleIndex];
156 int patternIndex = attributePtr[4 * sprite + 2] & patternIndexMask;
157 if (mag) spriteLine /= 2;
158 sip.pattern = calculatePatternNP(patternIndex, spriteLine);
159 sip.x = attributePtr[4 * sprite + 1];
160 byte colorAttrib = attributePtr[4 * sprite + 3];
161 if (colorAttrib & 0x80) sip.x -= 32;
162 sip.colorAttrib = colorAttrib;
163
164 spriteCount[line] = visibleIndex + 1;
165 }
166 }
167
168 // Update status register.
169 byte status = vdp.getStatusReg0();
170 if (fifthSpriteNum != -1) {
171 // Five sprites on a line.
172 // According to TMS9918.pdf 5th sprite detection is only
173 // active when F flag is zero.
174 if ((status & 0xC0) == 0) {
175 status = 0x40 | (status & 0x20) | fifthSpriteNum;
176 }
177 }
178 if (~status & 0x40) {
179 // No 5th sprite detected, store number of latest sprite processed.
180 status = (status & 0x20) | std::min(sprite, 31);
181 }
182 vdp.setSpriteStatus(status);
183
184 // Optimisation:
185 // If collision already occurred,
186 // that state is stable until it is reset by a status reg read,
187 // so no need to execute the checks.
188 // The spriteBuffer array is filled now, so we can bail out.
189 if (vdp.getStatusReg0() & 0x20) return;
190
191 /*
192 Model for sprite collision: (or "coincidence" in TMS9918 data sheet)
193 - Reset when status reg is read.
194 - Set when sprite patterns overlap.
195 - ??? Color doesn't matter: sprites of color 0 can collide.
196 ??? This conflicts with: https://github.com/openMSX/openMSX/issues/1198
197 - Sprites that are partially off-screen position can collide, but only
198 on the in-screen pixels. In other words: sprites cannot collide in
199 the left or right border, only in the visible screen area. Though
200 they can collide in the V9958 extra border mask. This behaviour is
201 the same in sprite mode 1 and 2.
202
203 Implemented by checking every pair for collisions.
204 For large numbers of sprites that would be slow,
205 but there are max 4 sprites and therefore max 6 pairs.
206 If any collision is found, method returns at once.
207 */
208 bool can0collide = vdp.canSpriteColor0Collide();
209 for (auto line : xrange(minLine, maxLine)) {
210 int minXCollision = 999;
211 for (int i = std::min<int>(4, spriteCount[line]); --i >= 1; ) {
212 auto color1 = spriteBuffer[line][i].colorAttrib & 0xf;
213 if (!can0collide && (color1 == 0)) continue;
214 int x_i = spriteBuffer[line][i].x;
215 SpritePattern pattern_i = spriteBuffer[line][i].pattern;
216 for (int j = i; --j >= 0; ) {
217 auto color2 = spriteBuffer[line][j].colorAttrib & 0xf;
218 if (!can0collide && (color2 == 0)) continue;
219 // Do sprite i and sprite j collide?
220 int x_j = spriteBuffer[line][j].x;
221 int dist = x_j - x_i;
222 if ((-magSize < dist) && (dist < magSize)) {
223 SpritePattern pattern_j = spriteBuffer[line][j].pattern;
224 if (dist < 0) {
225 pattern_j <<= -dist;
226 } else {
227 pattern_j >>= dist;
228 }
229 SpritePattern colPat = pattern_i & pattern_j;
230 if (x_i < 0) {
231 assert(x_i >= -32);
232 colPat &= (1 << (32 + x_i)) - 1;
233 }
234 if (colPat) {
235 int xCollision = x_i + std::countl_zero(colPat);
236 assert(xCollision >= 0);
237 minXCollision = std::min(minXCollision, xCollision);
238 }
239 }
240 }
241 }
242 if (minXCollision < 256) {
243 vdp.setSpriteStatus(vdp.getStatusReg0() | 0x20);
244 // verified: collision coords are also filled
245 // in for sprite mode 1
246 // x-coord should be increased by 12
247 // y-coord 8
248 collisionX = minXCollision + 12;
249 collisionY = line - vdp.getLineZero() + 8;
250 return; // don't check lines with higher Y-coord
251 }
252 }
253}
254
255void SpriteChecker::updateSprites2(int limit)
256{
257 // TODO merge this with updateSprites1()?
258 if (vdp.spritesEnabledFast()) {
259 if (vdp.isDisplayEnabled()) {
260 // in display area
261 checkSprites2(currentLine, limit);
262 } else {
263 // in border, only check last line of top border
264 int l0 = vdp.getLineZero() - 1;
265 if ((currentLine <= l0) && (l0 < limit)) {
266 checkSprites2(l0, l0 + 1);
267 }
268 }
269 }
270 currentLine = limit;
271}
272
273inline void SpriteChecker::checkSprites2(int minLine, int maxLine)
274{
275 // See comment in checkSprites1() about order of inner and outer loops.
276
277 // Calculate display line.
278 // This is the line sprites are checked at; the line they are displayed
279 // at is one lower.
280 int displayDelta = vdp.getVerticalScroll() - vdp.getLineZero();
281
282 // Get sprites for this line and detect 5th sprite if any.
283 bool limitSprites = limitSpritesSetting.getBoolean();
284 int size = vdp.getSpriteSize();
285 bool mag = vdp.isSpriteMag();
286 int magSize = (mag + 1) * size;
287 int patternIndexMask = (size == 16) ? 0xFC : 0xFF;
288 int ninthSpriteNum = -1; // no 9th sprite detected yet
289 int ninthSpriteLine = 999; // larger than any possible valid line
290
291 // Because it gave a measurable performance boost, we duplicated the
292 // code for planar and non-planar modes.
293 int sprite = 0;
294 if (planar) {
295 auto [attributePtr0, attributePtr1] =
296 vram.spriteAttribTable.getReadAreaPlanar<32 * 4>(512);
297 // TODO: Verify CC implementation.
298 for (; sprite < 32; ++sprite) {
299 int y = attributePtr0[2 * sprite + 0];
300 if (y == 216) break;
301
302 for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
303 // Calculate line number within the sprite.
304 int displayLine = line + displayDelta;
305 int spriteLine = (displayLine - y) & 0xFF;
306 if (spriteLine >= magSize) {
307 // Skip ahead till sprite is visible.
308 line += 256 - spriteLine - 1;
309 continue;
310 }
311
312 int visibleIndex = spriteCount[line];
313 if (visibleIndex == 8) {
314 // Find earliest line where this condition occurs.
315 if (line < ninthSpriteLine) {
316 ninthSpriteLine = line;
317 ninthSpriteNum = sprite;
318 }
319 if (limitSprites) continue;
320 }
321
322 if (mag) spriteLine /= 2;
323 unsigned colorIndex = (~0u << 10) | (sprite * 16 + spriteLine);
324 byte colorAttrib =
325 vram.spriteAttribTable.readPlanar(colorIndex);
326
327 SpriteInfo& sip = spriteBuffer[line][visibleIndex];
328 int patternIndex = attributePtr0[2 * sprite + 1] & patternIndexMask;
329 sip.pattern = calculatePatternPlanar(patternIndex, spriteLine);
330 sip.x = attributePtr1[2 * sprite + 0];
331 if (colorAttrib & 0x80) sip.x -= 32;
332 sip.colorAttrib = colorAttrib;
333
334 // set sentinel (see below)
335 spriteBuffer[line][visibleIndex + 1].colorAttrib = 0;
336 spriteCount[line] = visibleIndex + 1;
337 }
338 }
339 } else {
340 auto attributePtr0 =
341 vram.spriteAttribTable.getReadArea<32 * 4>(512);
342 // TODO: Verify CC implementation.
343 for (; sprite < 32; ++sprite) {
344 int y = attributePtr0[4 * sprite + 0];
345 if (y == 216) break;
346
347 for (int line = minLine; line < maxLine; ++line) { // 'line' changes in loop
348 // Calculate line number within the sprite.
349 int displayLine = line + displayDelta;
350 int spriteLine = (displayLine - y) & 0xFF;
351 if (spriteLine >= magSize) {
352 // Skip ahead till sprite is visible.
353 line += 256 - spriteLine - 1;
354 continue;
355 }
356
357 int visibleIndex = spriteCount[line];
358 if (visibleIndex == 8) {
359 // Find earliest line where this condition occurs.
360 if (line < ninthSpriteLine) {
361 ninthSpriteLine = line;
362 ninthSpriteNum = sprite;
363 }
364 if (limitSprites) continue;
365 }
366
367 if (mag) spriteLine /= 2;
368 unsigned colorIndex = (~0u << 10) | (sprite * 16 + spriteLine);
369 byte colorAttrib =
370 vram.spriteAttribTable.readNP(colorIndex);
371 // Sprites with CC=1 are only visible if preceded by
372 // a sprite with CC=0. However they DO contribute towards
373 // the max-8-sprites-per-line limit, so we can't easily
374 // filter them here. See also
375 // https://github.com/openMSX/openMSX/issues/497
376
377 SpriteInfo& sip = spriteBuffer[line][visibleIndex];
378 int patternIndex = attributePtr0[4 * sprite + 2] & patternIndexMask;
379 sip.pattern = calculatePatternNP(patternIndex, spriteLine);
380 sip.x = attributePtr0[4 * sprite + 1];
381 if (colorAttrib & 0x80) sip.x -= 32;
382 sip.colorAttrib = colorAttrib;
383
384 // Set sentinel. Sentinel is actually only
385 // needed for sprites with CC=1.
386 // In the past we set the sentinel (for all
387 // lines) at the end. But it's slightly faster
388 // to do it only for lines that actually
389 // contain sprites (even if sentinel gets
390 // overwritten a couple of times for lines with
391 // many sprites).
392 spriteBuffer[line][visibleIndex + 1].colorAttrib = 0;
393 spriteCount[line] = visibleIndex + 1;
394 }
395 }
396 }
397
398 // Update status register.
399 byte status = vdp.getStatusReg0();
400 if (ninthSpriteNum != -1) {
401 // Nine sprites on a line.
402 // According to TMS9918.pdf 5th sprite detection is only
403 // active when F flag is zero. Stuck to this for V9938.
404 // Dragon Quest 2 needs this.
405 if ((status & 0xC0) == 0) {
406 status = 0x40 | (status & 0x20) | ninthSpriteNum;
407 }
408 }
409 if (~status & 0x40) {
410 // No 9th sprite detected, store number of latest sprite processed.
411 status = (status & 0x20) | std::min(sprite, 31);
412 }
413 vdp.setSpriteStatus(status);
414
415 // Optimisation:
416 // If collision already occurred,
417 // that state is stable until it is reset by a status reg read,
418 // so no need to execute the checks.
419 // The visibleSprites array is filled now, so we can bail out.
420 if (vdp.getStatusReg0() & 0x20) return;
421
422 /*
423 Model for sprite collision: (or "coincidence" in TMS9918 data sheet)
424 - Reset when status reg is read.
425 - Set when sprite patterns overlap.
426 - ??? Color doesn't matter: sprites of color 0 can collide.
427 ??? TODO: V9938 data book denies this (page 98).
428 ??? This conflicts with: https://github.com/openMSX/openMSX/issues/1198
429 - Sprites that are partially off-screen position can collide, but only
430 on the in-screen pixels. In other words: sprites cannot collide in
431 the left or right border, only in the visible screen area. Though
432 they can collide in the V9958 extra border mask. This behaviour is
433 the same in sprite mode 1 and 2.
434
435 Implemented by checking every pair for collisions.
436 For large numbers of sprites that would be slow.
437 There are max 8 sprites and therefore max 42 pairs.
438 TODO: Maybe this is slow... Think of something faster.
439 Probably new approach is needed anyway for OR-ing.
440 */
441 bool can0collide = vdp.canSpriteColor0Collide();
442 for (auto line : xrange(minLine, maxLine)) {
443 int minXCollision = 999; // no collision
444 std::span<SpriteInfo, 32 + 1> visibleSprites = spriteBuffer[line];
445 for (int i = std::min<int>(8, spriteCount[line]); --i >= 1; ) {
446 auto colorAttrib1 = visibleSprites[i].colorAttrib;
447 if (!can0collide && ((colorAttrib1 & 0xf) == 0)) continue;
448 // If CC or IC is set, this sprite cannot collide.
449 if (colorAttrib1 & 0x60) continue;
450
451 int x_i = visibleSprites[i].x;
452 SpritePattern pattern_i = visibleSprites[i].pattern;
453 for (int j = i; --j >= 0; ) {
454 auto colorAttrib2 = visibleSprites[j].colorAttrib;
455 if (!can0collide && ((colorAttrib2 & 0xf) == 0)) continue;
456 // If CC or IC is set, this sprite cannot collide.
457 if (colorAttrib2 & 0x60) continue;
458
459 // Do sprite i and sprite j collide?
460 int x_j = visibleSprites[j].x;
461 int dist = x_j - x_i;
462 if ((-magSize < dist) && (dist < magSize)) {
463 SpritePattern pattern_j = visibleSprites[j].pattern;
464 if (dist < 0) {
465 pattern_j <<= -dist;
466 } else {
467 pattern_j >>= dist;
468 }
469 SpritePattern colPat = pattern_i & pattern_j;
470 if (x_i < 0) {
471 assert(x_i >= -32);
472 colPat &= (1 << (32 + x_i)) - 1;
473 }
474 if (colPat) {
475 int xCollision = x_i + std::countl_zero(colPat);
476 assert(xCollision >= 0);
477 minXCollision = std::min(minXCollision, xCollision);
478 }
479 }
480 }
481 }
482 if (minXCollision < 256) {
483 vdp.setSpriteStatus(vdp.getStatusReg0() | 0x20);
484 // x-coord should be increased by 12
485 // y-coord 8
486 collisionX = minXCollision + 12;
487 collisionY = line - vdp.getLineZero() + 8;
488 return; // don't check lines with higher Y-coord
489 }
490 }
491}
492
493// version 1: initial version
494// version 2: bug fix: also serialize 'currentLine'
495template<typename Archive>
496void SpriteChecker::serialize(Archive& ar, unsigned version)
497{
498 if constexpr (Archive::IS_LOADER) {
499 // Recalculate from VDP state:
500 // - frameStartTime
501 frameStartTime.reset(vdp.getFrameStartTime());
502 // - updateSpritesMethod, planar
503 setDisplayMode(vdp.getDisplayMode());
504
505 // We don't serialize spriteCount[] and spriteBuffer[].
506 // These are only used to draw the MSX screen, they don't have
507 // any influence on the MSX state. So the effect of not
508 // serializing these two is that no sprites will be shown in the
509 // first (partial) frame after loadstate.
510 ranges::fill(spriteCount, 0);
511 // content of spriteBuffer[] doesn't matter if spriteCount[] is 0
512 }
513 ar.serialize("collisionX", collisionX,
514 "collisionY", collisionY);
515 if (ar.versionAtLeast(version, 2)) {
516 ar.serialize("currentLine", currentLine);
517 } else {
518 currentLine = 0;
519 }
520}
522
523} // namespace openmsx
bool getBoolean() const noexcept
constexpr void reset(EmuTime::param e)
Reset the clock to start ticking at the given time.
Definition: Clock.hh:102
Class containing all settings for renderers.
void frameStart(EmuTime::param time)
Signals the start of a new frame.
void reset(EmuTime::param time)
Puts the sprite checker in its initial state.
void serialize(Archive &ar, unsigned version)
uint32_t SpritePattern
Bitmap of length 32 describing a sprite pattern.
SpriteChecker(VDP &vdp, RenderSettings &renderSettings, EmuTime::param time)
Create a sprite checker.
VRAMWindow spriteAttribTable
Definition: VDPVRAM.hh:674
VRAMWindow spritePatternTable
Definition: VDPVRAM.hh:675
Unified implementation of MSX Video Display Processors (VDPs).
Definition: VDP.hh:64
int getSpriteSize() const
Gets the sprite size in pixels (8/16).
Definition: VDP.hh:479
byte getStatusReg0() const
Should only be used by SpriteChecker.
Definition: VDP.hh:571
bool spritesEnabledFast() const
Same as spritesEnabled(), but may only be called in sprite mode 1 or 2.
Definition: VDP.hh:268
void setSpriteStatus(byte value)
Should only be used by SpriteChecker.
Definition: VDP.hh:581
DisplayMode getDisplayMode() const
Get the display mode the VDP is in.
Definition: VDP.hh:144
int getLineZero() const
Get the absolute line number of display line zero.
Definition: VDP.hh:328
byte getVerticalScroll() const
Gets the current vertical scroll (line displayed at Y=0).
Definition: VDP.hh:283
EmuTime::param getFrameStartTime() const
Definition: VDP.hh:473
bool canSpriteColor0Collide() const
Can a sprite which has color=0 collide with some other sprite?
Definition: VDP.hh:183
bool isSpriteMag() const
Are sprites magnified?
Definition: VDP.hh:485
bool isDisplayEnabled() const
Is the display enabled? Both the regular border and forced blanking by clearing the display enable bi...
Definition: VDP.hh:251
byte readNP(unsigned index) const
Reads a byte from VRAM in its current state.
Definition: VDPVRAM.hh:254
byte readPlanar(unsigned index) const
Similar to readNP, but now with planar addressing.
Definition: VDPVRAM.hh:262
std::pair< std::span< const byte, size/2 >, std::span< const byte, size/2 > > getReadAreaPlanar(unsigned index) const
Similar to getReadArea(), but now with planar addressing mode.
Definition: VDPVRAM.hh:234
void setObserver(VRAMObserver *newObserver)
Register an observer on this VRAM window.
Definition: VDPVRAM.hh:280
std::span< const byte, size > getReadArea(unsigned index) const
Gets a span of a contiguous part of the VRAM.
Definition: VDPVRAM.hh:217
constexpr vecN< N, T > min(const vecN< N, T > &x, const vecN< N, T > &y)
Definition: gl_vec.hh:266
This file implemented 3 utility functions:
Definition: Autofire.cc:9
constexpr void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:287
size_t size(std::string_view utf8)
#define INSTANTIATE_SERIALIZE_METHODS(CLASS)
Definition: serialize.hh:1021
constexpr auto xrange(T e)
Definition: xrange.hh:133