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