/ Hallowing_Minotaur_Maze / Hallowing_Minotaur_Maze.ino
Hallowing_Minotaur_Maze.ino
1 // SPDX-FileCopyrightText: 2018 Phillip Burgess for Adafruit Industries 2 // 3 // SPDX-License-Identifier: MIT 4 5 // "Minotaur Maze" plaything for Adafruit Hallowing. Uses ray casting, 6 // DMA and related shenanigans to smoothly move about a 3D maze. 7 // Tilt Hallowing to turn right/left and move forward/back. 8 9 // Ray casting code adapted from tutorial by Lode Vandevenne: 10 // https://lodev.org/cgtutor/raycasting.html 11 12 #include <Adafruit_LIS3DH.h> // Accelerometer library 13 #include <Adafruit_GFX.h> // Core graphics library 14 #include <Adafruit_ST7735.h> // Display-specific graphics library 15 #include <Adafruit_ZeroDMA.h> // Direct memory access library 16 17 #ifdef ARDUINO_SAMD_CIRCUITPLAYGROUND_EXPRESS 18 #define TFT_RST -1 19 #define TFT_DC A6 20 #define TFT_CS A7 21 #define TFT_BACKLIGHT A3 // Display backlight pin 22 #define TFT_SPI SPI1 23 #define TFT_PERIPH PERIPH_SPI1 24 Adafruit_LIS3DH accel(&Wire1); 25 #else 26 #define TFT_RST 37 // TFT reset pin 27 #define TFT_DC 38 // TFT display/command mode pin 28 #define TFT_CS 39 // TFT chip select pin 29 #define TFT_BACKLIGHT 7 // TFT backlight LED pin 30 #define TFT_SPI SPI 31 #define TFT_PERIPH PERIPH_SPI 32 Adafruit_LIS3DH accel; 33 #endif 34 35 36 // Declarations for some Hallowing hardware -- display, accelerometer, SPI 37 Adafruit_ST7735 tft(&TFT_SPI, TFT_CS, TFT_DC, TFT_RST); 38 SPISettings settings(12000000, MSBFIRST, SPI_MODE0); 39 40 // Declarations related to DMA (direct memory access), which lets us walk 41 // and chew gum at the same time. This is VERY specific to SAMD chips and 42 // means this is not trivially ported to other devices. 43 Adafruit_ZeroDMA dma; 44 DmacDescriptor *dptr; // Initial allocated DMA descriptor 45 DmacDescriptor desc[2][3] __attribute__((aligned(16))); 46 uint8_t dList = 0; // Active DMA descriptor list index (0-1) 47 48 // DMA transfer-in-progress indicator and callback 49 static volatile bool dma_busy = false; 50 static void dma_callback(Adafruit_ZeroDMA *dma) { 51 dma_busy = false; 52 } 53 54 // This is the maze map. It's fixed at 32 bits wide, can be any height but 55 // is 32 in this example. '1' bits indicate solid walls, '0' indicate empty 56 // space that can be navigated. Perimeter wall bits MUST be set! Keep the 57 // center area empty since the player is initially placed there. 58 uint32_t worldMap[] = { 59 0b11111111111111111111111111111111, 60 0b10000000000000100000000001000001, 61 0b10000000000000101111011111011101, 62 0b10000000000000001000001000000101, 63 0b10000000000000111011101010111101, 64 0b10000010100000100010000010000101, 65 0b10000010100000111111111010101101, 66 0b10000011100000100000000000100001, 67 0b10000000000000111011101110111101, 68 0b10000000000000100010000010001001, 69 0b10000000000000111111111111101111, 70 0b10000000000000000000000000000001, 71 0b11111011111011100111111011111111, 72 0b10000000001010000001000000000001, 73 0b10100000101010000001001001001001, 74 0b10101010101000000000000000000001, 75 0b10101010101000000000000000000001, 76 0b10100000101010000001001001001001, 77 0b10000000001010000001000000000001, 78 0b11111011111011100111111011111111, 79 0b10000000000000000000000000000001, 80 0b10000010100000000111000010101001, 81 0b10001000001000000111000001010101, 82 0b10000000000000000111000000000001, 83 0b10010000000100000000000011111101, 84 0b10000001000000000000000010000101, 85 0b10010000000100000011111010100101, 86 0b10000000000000000010001010000001, 87 0b10001000001000000010101010000101, 88 0b10000010100000000010101011111101, 89 0b10000000000000000000100000000001, 90 0b11111111111111111111111111111111, 91 }; 92 #define MAPHEIGHT (sizeof worldMap / sizeof worldMap[0]) 93 94 // This macro tests whether bit at (X,Y) in the map is set. 95 #define isBitSet(X,Y) (worldMap[MAPHEIGHT-1-(Y)] & (0x80000000>>(X))) 96 // (X,Y) are in Cartesian coordinates with (0,0) at bottom-left (hence the 97 // MAPHEIGHT-1-Y inversion above) -- all the navigation and ray-casting math 98 // is done in Cartesian space, consistent with the trigonometric functions, 99 // whereas bitmap is represented top-to-bottom. 100 101 // DMA shenanigans are used for the solid color fills (sky, walls and 102 // floor). Typically one would use the DMA "source address increment" to 103 // copy graphics data from RAM or flash to SPI (to the screen). But a trick 104 // we can use for certain fills requires only a single byte of storage for 105 // each color. DMA source increment is turned OFF -- the same byte is issued 106 // over and over to fill a given span. Downside is a limited palette 107 // consisting of 256 colors with the high and low bytes of a 16-bit pixel 108 // value being the same. With the TFT's 5-6-5 bit color packing, the 109 // resulting selections are a bit weird (there's no 100% pure red, green or 110 // blue, only combinations) but usable. e.g. an 8-bit value 0x82 expands to 111 // a 16-bit pixel value of 0x8282 = 0b10000 010100 00010 = 16/31 (~52%) red, 112 // 20/63 (~32%) green, 2/31 (6%) blue. 113 const uint8_t colorSky = 0x3E, // Color of sky 114 colorGround = 0x82, // Color of ground 115 colorNorth = 0x04, // Color of north-facing walls 116 colorSouth = 0x05, // Color of south-facing walls 117 colorEast = 0x06, // Color of east-facing walls 118 colorWest = 0x07; // Color of west-facing walls 119 120 #define FOV (90.0 * (M_PI / 180.0)) // Field of view 121 122 float posX = 16.0, // Observer position, 123 posY = MAPHEIGHT / 2.0, // begin at center of map 124 heading = 0.0; // Initial heading = east 125 126 uint32_t startTime, frames = 0; // For frames-per-second calculation 127 128 // SETUP -- RUNS ONCE AT PROGRAM START ------------------------------------- 129 130 void setup(void) { 131 Serial.begin(115200); 132 133 Serial.println("Init accelerometer"); 134 // Initialize accelerometer, set to 2G range 135 if(accel.begin(0x18) || accel.begin(0x19)) { 136 accel.setRange(LIS3DH_RANGE_2_G); 137 } 138 139 Serial.println("Init display"); 140 // Initialize and clear screen 141 tft.initR(INITR_144GREENTAB); 142 tft.setRotation(1); 143 tft.fillScreen(0); 144 145 // More shenanigans: the display mapping is reconfigured so pixels are 146 // issued in COLUMN-MAJOR sequence (i.e. vertical lines), left-to-right, 147 // with pixel (0,0) at top left. The ray casting algorithm determines the 148 // wall height at each column...drawing is then just a matter of blasting 149 // a column's worth of pixels. 150 digitalWrite(TFT_CS, LOW); 151 digitalWrite(TFT_DC, LOW); 152 #ifdef ST77XX_MADCTL 153 TFT_SPI.transfer(ST77XX_MADCTL); // Current TFT lib 154 #else 155 TFT_SPI.transfer(ST7735_MADCTL); // Older TFT lib 156 #endif 157 digitalWrite(TFT_DC, HIGH); 158 TFT_SPI.transfer(0x28); 159 digitalWrite(TFT_CS, HIGH); 160 161 pinMode(TFT_BACKLIGHT, OUTPUT); 162 digitalWrite(TFT_BACKLIGHT, HIGH); // Main screen turn on 163 Serial.println("Init backlight"); 164 165 // Set up SPI DMA. While the Hallowing has a known SPI peripheral and this 166 // could be much simpler, the extra code here will help if adapting this 167 // sketch to other SAMD boards (Feather M0, M4, etc.) 168 int dmac_id; 169 volatile uint32_t *data_reg; 170 dma.allocate(); 171 if(&TFT_PERIPH == &sercom0) { 172 dma.setTrigger(SERCOM0_DMAC_ID_TX); 173 data_reg = &SERCOM0->SPI.DATA.reg; 174 #if defined SERCOM1 175 } else if(&TFT_PERIPH == &sercom1) { 176 dma.setTrigger(SERCOM1_DMAC_ID_TX); 177 data_reg = &SERCOM1->SPI.DATA.reg; 178 #endif 179 #if defined SERCOM2 180 } else if(&TFT_PERIPH == &sercom2) { 181 dma.setTrigger(SERCOM2_DMAC_ID_TX); 182 data_reg = &SERCOM2->SPI.DATA.reg; 183 #endif 184 #if defined SERCOM3 185 } else if(&TFT_PERIPH == &sercom3) { 186 dma.setTrigger(SERCOM3_DMAC_ID_TX); 187 data_reg = &SERCOM3->SPI.DATA.reg; 188 #endif 189 #if defined SERCOM4 190 } else if(&TFT_PERIPH == &sercom4) { 191 dma.setTrigger(SERCOM4_DMAC_ID_TX); 192 data_reg = &SERCOM4->SPI.DATA.reg; 193 #endif 194 #if defined SERCOM5 195 } else if(&TFT_PERIPH == &sercom5) { 196 dma.setTrigger(SERCOM5_DMAC_ID_TX); 197 data_reg = &SERCOM5->SPI.DATA.reg; 198 #endif 199 } 200 dma.setAction(DMA_TRIGGER_ACTON_BEAT); 201 dma.setCallback(dma_callback); 202 203 // Initialize DMA descriptor lists. There are TWO lists, used for 204 // alternating even/odd scanlines (columns in this case)...one list is 205 // calculated and filled while the other is being transferred out SPI. 206 // Each list contains three elements (though not all three are used every 207 // time), corresponding to the sky, wall and ground pixels for a column. 208 for(uint8_t s=0; s<2; s++) { // Even/odd scanlines 209 for(uint8_t d=0; d<3; d++) { // 3 descriptors per line 210 // No need to set SRCADDR, BTCNT or DESCADDR -- done later 211 desc[s][d].BTCTRL.bit.VALID = true; 212 desc[s][d].BTCTRL.bit.EVOSEL = 0x3; 213 desc[s][d].BTCTRL.bit.BLOCKACT = DMA_BLOCK_ACTION_NOACT; 214 desc[s][d].BTCTRL.bit.BEATSIZE = DMA_BEAT_SIZE_BYTE; 215 desc[s][d].BTCTRL.bit.SRCINC = 0; 216 desc[s][d].BTCTRL.bit.DSTINC = 0; 217 desc[s][d].BTCTRL.bit.STEPSEL = DMA_STEPSEL_SRC; 218 desc[s][d].BTCTRL.bit.STEPSIZE = DMA_ADDRESS_INCREMENT_STEP_SIZE_1; 219 desc[s][d].DSTADDR.reg = (uint32_t)data_reg; 220 } 221 } 222 223 // The DMA library MUST allocate at least one valid descriptor, so that's 224 // done here. It's not used in the conventional sense though, just before 225 // a transfer we copy the first scanline descriptor to this spot. 226 dptr = dma.addDescriptor(NULL, NULL, 42, DMA_BEAT_SIZE_BYTE, false, false); 227 228 startTime = millis(); // Starting time for frame-per-second calculation 229 } 230 231 // LOOP -- REPEATS INDEFINITELY -------------------------------------------- 232 233 void loop() { 234 235 // Update heading and position from accelerometer... 236 uint8_t mapX = (uint8_t)posX, // Current square of map 237 mapY = (uint8_t)posY; // (before changing pos.) 238 accel.read(); // Read accelerometer 239 #ifdef ARDUINO_SAMD_CIRCUITPLAYGROUND_EXPRESS 240 heading += (float)accel.x / -20000.0; // Update direction 241 float v = (abs(accel.y) < abs(accel.z)) ? // If board held flat(ish) 242 (float)accel.y / 20000.0 : // Use accel Y for velocity 243 (float)accel.z / -20000.0; // else accel Z is velocity 244 #else 245 heading += (float)accel.y / -20000.0; // Update direction 246 float v = (abs(accel.x) < abs(accel.z)) ? // If board held flat(ish) 247 (float)accel.x / 20000.0 : // Use accel X for velocity 248 (float)accel.z / -20000.0; // else accel Z is velocity 249 #endif 250 if(v > 0.19) v = 0.19; // Keep speed under 0.2 251 else if(v < -0.19) v = -0.19; 252 float vx = cos(heading) * v, // Direction vector X, Y 253 vy = sin(heading) * v, 254 newX = posX + vx, // New position 255 newY = posY + vy; 256 257 // Prevent going through solid walls (or getting too close to them) 258 if(vx > 0) { 259 if(isBitSet((int)(newX + 0.2), (int)newY)) newX = mapX + 0.8; 260 } else { 261 if(isBitSet((int)(newX - 0.2), (int)newY)) newX = mapX + 0.2; 262 } 263 if(vy > 0) { 264 if(isBitSet((int)newX, (int)(newY + 0.2))) newY = mapY + 0.8; 265 } else { 266 if(isBitSet((int)newX, (int)(newY - 0.2))) newY = mapY + 0.2; 267 } 268 269 posX = newX; 270 posY = newY; 271 272 TFT_SPI.beginTransaction(settings); // SPI init 273 digitalWrite(TFT_CS, LOW); // Chip select 274 tft.setAddrWindow(0, 0, 128, 128); // Set address window to full screen 275 digitalWrite(TFT_CS, LOW); // Re-select after addr function 276 digitalWrite(TFT_DC, HIGH); // Data mode... 277 278 // Ray casting code is much abbreviated here. 279 // See Lode Vandevenne's original tutorial for an in-depth explanation: 280 // https://lodev.org/cgtutor/raycasting.html 281 282 int8_t stepX, stepY; // X/Y direction steps (+1 or -1) 283 uint8_t skyPixels, floorPixels, // # of pixels in sky, floor 284 side, // North/south or east/west wall hit? 285 i; // Index in DMA descriptor list 286 uint16_t wallPixels; // # of wall pixels 287 float frac, rayDirX, rayDirY, 288 sideDistX, sideDistY, // Ray length, current to next X/Y side 289 deltaDistX, deltaDistY, // X-to-X, Y-to-Y ray lengths 290 perpWallDist, // Distance to wall 291 x1 = cos(heading + FOV / 2.0), // Image plane left edge 292 y1 = sin(heading + FOV / 2.0), 293 x2 = cos(heading - FOV / 2.0), // Image plane right edge 294 y2 = sin(heading - FOV / 2.0), 295 dx = x2 - x1, dy = y2 - y1; 296 297 for(uint8_t col = 0; col < 128; col++) { // For each column... 298 frac = ((float)col + 0.5) / 128.0; // 0 to 1 left to right 299 rayDirX = x1 + dx * frac; 300 rayDirY = y1 + dy * frac; 301 mapX = (uint8_t)posX; 302 mapY = (uint8_t)posY; 303 deltaDistX = (rayDirX != 0.0) ? fabs(1 / rayDirX) : 0.0; 304 deltaDistY = (rayDirY != 0.0) ? fabs(1 / rayDirY) : 0.0; 305 306 // Calculate X/Y steps and initial sideDist 307 if(rayDirX < 0) { 308 stepX = -1; 309 sideDistX = (posX - mapX) * deltaDistX; 310 } else { 311 stepX = 1; 312 sideDistX = (mapX + 1.0 - posX) * deltaDistX; 313 } if (rayDirY < 0) { 314 stepY = -1; 315 sideDistY = (posY - mapY) * deltaDistY; 316 } else { 317 stepY = 1; 318 sideDistY = (mapY + 1.0 - posY) * deltaDistY; 319 } 320 321 do { // Bresenham DDA line algorithm...walk map squares... 322 if(sideDistX < sideDistY) { 323 sideDistX += deltaDistX; 324 mapX += stepX; 325 side = 0; // East/west 326 } else { 327 sideDistY += deltaDistY; 328 mapY += stepY; 329 side = 1; // North/south 330 } 331 } while(!isBitSet(mapX, mapY)); // Continue until wall hit 332 333 // Calc distance projected on camera direction 334 perpWallDist = side ? ((mapY - posY + (1 - stepY) / 2) / rayDirY) : 335 ((mapX - posX + (1 - stepX) / 2) / rayDirX); 336 337 wallPixels = (int)(128.0 / perpWallDist); // Colum height in pixels 338 if(wallPixels >= 128) { // >= screen height? 339 wallPixels = 128; // Clip to screen height 340 skyPixels = floorPixels = 0; // No sky or ground 341 } else { 342 skyPixels = (128 - wallPixels) / 2; // 1/2 of non-wall is sky 343 floorPixels = 128 - wallPixels - skyPixels; // Any remainder is floor 344 } 345 346 // Build DMA descriptor list with up to 3 elements... 347 i = 0; 348 if(skyPixels) { // Any sky pixels in this column? 349 desc[dList][i].SRCADDR.reg = (uint32_t)&colorSky; 350 desc[dList][i].BTCNT.reg = skyPixels * 2; 351 desc[dList][i].DESCADDR.reg = (uint32_t)&desc[dList][i + 1]; 352 i++; 353 } 354 if(wallPixels) { // Any wall pixels? 355 // North/south or east/west facing? 356 desc[dList][i].SRCADDR.reg = (uint32_t)(side ? 357 ((stepY > 0) ? &colorSouth : &colorNorth) : 358 ((stepX > 0) ? &colorWest : &colorEast )); 359 desc[dList][i].BTCNT.reg = wallPixels * 2; 360 desc[dList][i].DESCADDR.reg = (uint32_t)&desc[dList][i + 1]; 361 i++; 362 } 363 if(floorPixels) { // Any floor pixels? 364 desc[dList][i].SRCADDR.reg = (uint32_t)&colorGround; 365 desc[dList][i].BTCNT.reg = floorPixels * 2; 366 desc[dList][i].DESCADDR.reg = (uint32_t)&desc[dList][i + 1]; 367 i++; 368 } 369 desc[dList][i - 1].DESCADDR.reg = 0; // End descriptor list 370 371 while(dma_busy); // Wait for prior DMA transfer to finish 372 // Copy scanline's first descriptor to the DMA lib's descriptor table 373 memcpy(dptr, &desc[dList][0], sizeof(DmacDescriptor)); 374 dma_busy = true; // Mark as busy (DMA callback clears this) 375 dma.startJob(); // Start new DMA transfer 376 dList = 1 - dList; // Swap active DMA descriptor list index 377 } 378 while(dma_busy); // Wait for last DMA transfer to complete 379 digitalWrite(TFT_CS, HIGH); // Deselect 380 TFT_SPI.endTransaction(); // SPI done 381 382 if(!(++frames & 255)) { // Every 256th frame, show frame rate 383 uint32_t elapsed = (millis() - startTime) / 1000; 384 if(elapsed) Serial.println(frames / elapsed); 385 } 386 }