Share Your Code

Raycasting Engine

Posted by Jesder, Posted on February 14, 2012

Back in 1997, I wrote a raycasting engine in Turbo Pascal. It had a number of features and was heading towards being turned into a fully fledged game engine. That never happened. But since then, as I move between development platforms, I like to port a cutdown version of it to help make me familiar with the syntax and API on the new platform. Here is a basic raycasting engine written in LUA with the Corona SDK.

This demo only contains flat filled walls and simple movement controls (with wall clipping). Expanding on it however is not difficult to add secret walls, doors, items, etc.

I have kept optimisation minimal, keeping only to look up tables in most cases to get some performance boost.

Porting it was easier than I had expected, and if I get some time, I will return and add more features.

Here are the files you will need:

config.lua

1
2
3
4
5
6
7
8
9
application =
{
        content =
        {
                width = 320,
                height = 480,
                scale = 'letterbox'
        },
}

build.settings

1
2
3
4
5
6
7
8
9
10
11
settings = {        
        orientation =
        {
                default = "landscapeRight",
                supported =
                {
                        "landscapeLeft", 
                        "landscapeRight",
                },
       },
}

map.lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
-- Project: Raycasting Engine Demo
-- SDK: Corona - 09/12/11
-- Author: Andrew Burch
-- Date: 08/02/2012
-- Site: http://www.newhighscore.net
-- Contact: andrew.burch@newhighscore.net
-- Note: Map data and variables
 
module(..., package.seeall)
 
rowCount = 10
columnCount = 10
 
mapData = {
        {1,2,3,4,1,2,3,4,1,1},
        {1,0,0,4,0,0,0,0,0,2},
        {2,0,0,2,2,0,0,0,3,3},
        {3,0,0,5,0,0,0,0,0,2},
        {2,0,0,1,2,3,1,0,0,4},
        {1,0,0,0,4,0,0,0,0,2},
        {2,0,0,0,5,0,0,0,5,3},
        {3,3,0,0,0,0,0,0,0,2},
        {2,0,0,0,2,0,0,3,0,1},
        {1,1,2,3,2,1,2,3,2,1},
}
 
wallDefList = {
        {
                textureId = 'wall1',
                isSolid = true,
        },
        {
                textureId = 'wall2',
                isSolid = true,
        },
        {
                textureId = 'wall3',
                isSolid = true,
        },
        {
                textureId = 'wall4',
                isSolid = true,
        },
        {
                textureId = 'wall5',
                isSolid = true,
        },
}

input.lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
-- Class: Input Handler
-- SDK: Corona - 09/12/11
-- Author: Andrew Burch
-- Date: 08/02/12
-- Site: http://www.newhighscore.net
-- Contact: andrew.burch@newhighscore.net
-- Note: Process touch events to handle input for the camera
--      Very custom to the raycasting engine demo
 
local abs = math.abs
local max = math.max
local min = math.min
 
local Input = {}
local Input_mt = {__index = Input}
 
function Input.new(params)
        local displayGroup = display.newGroup()
 
        local input = {
                displayGroup = displayGroup,
        }
        
        return setmetatable(input, Input_mt)
end
 
function Input:initialise(params)
        local displayGroup = self.displayGroup
        
        local displayWidth = params.displayWidth
        local buttonWidth = params.buttonWidth
        local buttonHeight = params.buttonHeight
        local sideBorder = params.sideBorder
        local turnAcceleration = params.turnAcceleration
        local movementAcceleration = params.movementAcceleration
 
        local rightButtonSetX = displayWidth - sideBorder - buttonWidth
        
        local phaseStateMap = {
                ['began'] = true,
                ['moved'] = true,
                ['ended'] = false,
                ['cancelled'] = false,
        }
        
        local buttonConfig = {
                {
                        x = sideBorder,
                        y = 240,
                        modifierName = 'turnAcceleration',
                        modiferValue = -turnAcceleration,
                        stateName = 'isTurning',
                },
                {
                        x = 80,
                        y = 240,
                        modifierName = 'turnAcceleration',
                        modiferValue = turnAcceleration,
                        stateName = 'isTurning',
                },
                {
                        x = rightButtonSetX,
                        y = 200,
                        modifierName = 'movementAcceleration',
                        modiferValue = movementAcceleration,
                        stateName = 'isMoving',
                },
                {
                        x = rightButtonSetX,
                        y = 260,
                        modifierName = 'movementAcceleration',
                        modiferValue = -movementAcceleration,
                        stateName = 'isMoving',
                },
        }               
        
        for _, v in ipairs(buttonConfig) do
                local button = display.newRoundedRect(displayGroup, v.x, v.y, buttonWidth, buttonWidth, 4)
                button.strokeWidth = 2
                button:setFillColor(140, 140, 140, 100)
                button:setStrokeColor(180, 180, 180, 100)
                button:addEventListener('touch', function(event)
                                                                        local phase = event.phase
                                                                        local state = phaseStateMap[phase] 
                                                                        
                                                                        local modifierName = v.modifierName
                                                                        local modiferValue = v.modiferValue
                                                                        local stateName = v.stateName
                                                                        
                                                                        self[modifierName] = state and modiferValue or nil
                                                                        self[stateName] = state
                                                                        
                                                                        return true
                                                                end)
        end
        
        self.movementSpeed = 0
        self.turnSpeed = 0              
end
 
function Input:update(dt, time, params)
        local isMoving = self.isMoving
        local movementSpeed = self.movementSpeed
        if isMoving then
                local movementAcceleration = self.movementAcceleration
                local maxMovementSpeed = params.maxMovementSpeed
                local newSpeed = movementSpeed + movementAcceleration
                newSpeed = max(min(newSpeed, maxMovementSpeed), -maxMovementSpeed)
                self.movementSpeed = newSpeed
        end
        
        if not isMoving and movementSpeed ~= 0 then
                local moveDeccelerateFactor = params.moveDeccelerateFactor
                local newSpeed = movementSpeed * moveDeccelerateFactor
                if abs(newSpeed) < 0.1 then
                        newSpeed = 0
                end
                
                self.movementSpeed = newSpeed
        end
 
        local isTurning = self.isTurning
        local turnSpeed = self.turnSpeed
        if isTurning then
                local turnAcceleration = self.turnAcceleration
                local maxTurnSpeed = params.maxTurnSpeed
                local newSpeed = turnSpeed + turnAcceleration
                newSpeed = max(min(newSpeed, maxTurnSpeed), -maxTurnSpeed)
                self.turnSpeed = newSpeed
        end
        
        if not isTurning and turnSpeed ~= 0 then
                local turnDeccelerateFactor = params.turnDeccelerateFactor
                local newSpeed = turnSpeed * turnDeccelerateFactor
                if abs(newSpeed) < 0.1 then
                        newSpeed = 0
                end
                
                self.turnSpeed = newSpeed
        end     
end
 
function Input:getTurnSpeed()
        return self.turnSpeed
end
 
function Input:getMovementSpeed()
        return self.movementSpeed
end
 
 
return Input

renderer.lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
-- Class: Renderer
-- SDK: Corona - 09/12/11
-- Author: Andrew Burch
-- Date: 08/02/12
-- Site: http://www.newhighscore.net
-- Contact: andrew.burch@newhighscore.net
-- Note: Render a single frame from the raycasting engine
--      Very custom and unoptimised
--      Only handles flat filled walls - no textures (..yet)
 
local tablex = require('tablex')
 
local floor = math.floor
local min = math.min
 
-- basic depth shading
local shadeDistanceMax = 500
local shadeConst = 1 / shadeDistanceMax
 
local colourTable = {
        {r = 140, g = 0, b = 0},
        {r = 0, g = 140, b = 0},
        {r = 0, g = 90, b = 140},
        {r = 90, g = 0, b = 140},
        {r = 90, g = 140, b = 0},
}
 
 
local Renderer = {}
local Renderer_mt = {__index = Renderer}
 
function Renderer.new(params)
        local displayGroup = display.newGroup()
        local referencePoint = display.TopLeftReferencePoint
        
        displayGroup:setReferencePoint(referencePoint)
        
        local renderer = {
                displayGroup = displayGroup,
        }
 
        return setmetatable(renderer, Renderer_mt)
end
 
function Renderer:initialise(params)
        local displayGroup = self.displayGroup
        
        local displayWidth = params.displayWidth
        local columnWidth = params.columnWidth
        local horizon = params.horizon
 
        local referencePoint = display.TopLeftReferencePoint
        local renderTable = {}
        
        for i = 0, displayWidth do
                local slice = display.newRect(i - 1, horizon, columnWidth, 0)
                slice:setFillColor(0, 0, 0)
                slice:setReferencePoint(referencePoint)
                
                table.insert(renderTable, slice)
        end
        
        self.renderTable = renderTable
end
 
function Renderer:renderScene(params)
        local renderTable = self.renderTable
        local horizon = params.horizon
        local sceneInfo = params.sceneInfo
 
        for i, sliceInfo in ipairs(sceneInfo) do
                local sliceHeight = sliceInfo.sliceHeight
                local halfSliceHeight = sliceHeight
 
                local renderSlice = renderTable[i]
                renderSlice.height = sliceHeight
 
                local colourId = sliceInfo.wallId
                local col = colourTable[colourId]
                local distance = sliceInfo.distance
                local shadeFactor = 1 - (min(distance, shadeDistanceMax) * shadeConst)
                local r = col.r * shadeFactor
                local g = col.g * shadeFactor
                local b = col.b * shadeFactor
                renderSlice:setFillColor(r, g, b)
        end
end
 
return Renderer

raycast.lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
-- Class: Raycast Engine
-- SDK: Corona - 09/12/11
-- Author: Andrew Burch
-- Date: 08/02/12
-- Site: http://www.newhighscore.net
-- Contact: andrew.burch@newhighscore.net
-- Note: Basic raycasting engine - minimal feature set
 
-- minor optimisation
local floor = math.floor
local ceil = math.ceil
local min = math.min
local abs = math.abs
local rad = math.rad
local tan = math.tan
local cos = math.cos
local sin = math.sin
 
local MAX_DISTANCE = 99999
 
 
local RaycastEngine = {}
local RaycastEngine_mt = {__index = RaycastEngine}
 
function RaycastEngine.new(params)
        local engine = {
        }
        
        return setmetatable(engine, RaycastEngine_mt)
end
 
function RaycastEngine:initialise(params)
        local visibleWidth = params.visibleWidth
        local visibleHeight = params.visibleHeight
        
        local mapRowCount = params.mapRowCount
        local mapColumnCount = params.mapColumnCount
 
        local fov = params.fov
        local mapCellSize = params.mapCellSize                  
        local halfFov = fov * 0.5
        local halfVisibleWidth = visibleWidth * 0.5
        local distanceConst = halfVisibleWidth / tan(rad(halfFov))
 
        local angleStep = fov / visibleWidth                            
        local angleCount = ceil(360 / angleStep)
 
        -- build common angles table
        local commonAngleList = params.commonAngleList
        local commonAngles = {}
        for _, angle in ipairs(commonAngleList) do
                commonAngles[angle] = floor((angleCount / 360) * angle)
        end
 
        -- build slice height look up table
        local heightTableSize = ceil((mapCellSize * mapRowCount) / sin(rad(45)))
        local heightTable = {}
        for i = 1, heightTableSize do
                local sliceHeight = (mapCellSize / i) * distanceConst
                heightTable[i] = floor(sliceHeight)
        end
 
        -- build intercept and math tables
        local xNextTable = {}
        local yNextTable = {}
        local cosTable = {}
        local sinTable = {}
        local tanTable = {}
 
        local invalidAngles = {
                [commonAngles[0]] = true,
                [commonAngles[90]] = true,
                [commonAngles[180]] = true,
                [commonAngles[270]] = true,
                [commonAngles[360]] = true,
        }
 
        local nextAngle = 0
        for i = 0, angleCount + 1 do
                local angleRad = rad(nextAngle)
 
                if invalidAngles[i] then
                        tanTable[i] = 0
                        xNextTable[i] = 0
                        yNextTable[i] = 0
                else
                        local angleTan = tan(angleRad)
                        
                        tanTable[i] = angleTan
                        xNextTable[i] = mapCellSize / angleTan
                        yNextTable[i] = mapCellSize * angleTan
                end
 
                local angle = (i * math.pi) / commonAngles[180]
                cosTable[i] = cos(angle) 
                sinTable[i] = sin(angle)
 
                nextAngle = nextAngle + angleStep
        end
 
        self.foundWalls = {}
 
        self.mapCellSize = mapCellSize
        self.mapColumnCount = mapColumnCount
        self.mapRowCount = mapRowCount
 
        self.heightTable = heightTable
        self.commonAngles = commonAngles
        self.xNextTable = xNextTable
        self.yNextTable = yNextTable
        self.cosTable = cosTable
        self.sinTable = sinTable
        self.tanTable = tanTable
end
 
function RaycastEngine:getFirstHorizontalIntercept(xpos, ypos, rayAngle)
        local commonAngles = self.commonAngles
        local mapCellSize = self.mapCellSize
        local xNextTable = self.xNextTable
        local tanTable = self.tanTable
        
        local rayInfo = {
                x = 0,
                y = 0,
        }
        
        local rayPast180 = rayAngle > commonAngles[180]
        local yModifier = rayPast180 and -1 or mapCellSize
        rayInfo.y = (floor(ypos / mapCellSize) * mapCellSize) + yModifier
 
        local invalidAngles = {
                [commonAngles[90]] = true,
                [commonAngles[270]] = true,
        }
        
        local invalidAngle = invalidAngles[rayAngle]
        rayInfo.x = invalidAngle and xpos or (xpos + (rayInfo.y - ypos) / tanTable[rayAngle])
 
        rayInfo.rayYStep = rayPast180 and -mapCellSize or mapCellSize
        rayInfo.rayXStep = rayPast180 and -xNextTable[rayAngle] or xNextTable[rayAngle]
 
        return rayInfo
end
 
function RaycastEngine:getFirstVerticalIntercept(xpos, ypos, rayAngle)
        local commonAngles = self.commonAngles
        local mapCellSize = self.mapCellSize
        local yNextTable = self.yNextTable
        local tanTable = self.tanTable
        
        local rayInfo = {
                x = 0,
                y = 0,
        }
 
        local rayFacingDown = rayAngle > commonAngles[90] and rayAngle < commonAngles[270]
        
        local xModifier = rayFacingDown and -1 or mapCellSize
        rayInfo.x = (floor(xpos / mapCellSize) * mapCellSize) + xModifier
 
        rayInfo.y = ypos + (rayInfo.x - xpos) * tanTable[rayAngle]
 
        rayInfo.rayYStep = rayFacingDown and -yNextTable[rayAngle] or yNextTable[rayAngle]
        rayInfo.rayXStep = rayFacingDown and -mapCellSize or mapCellSize
 
        return rayInfo
end
 
function RaycastEngine:performHorizontalCheck(xpos, ypos, rayAngle, worldMap, wallDefList, rayInfo)
        local mapColumnCount = self.mapColumnCount
        local mapRowCount = self.mapRowCount
        local mapCellSize = self.mapCellSize
        local sinTable = self.sinTable
 
        local rayY = rayInfo.y
        local rayX = rayInfo.x
        local rayYStep = rayInfo.rayYStep
        local rayXStep = rayInfo.rayXStep
 
        local wallFound = false
        while not wallFound do
                local mapX = floor(rayX / mapCellSize)
                local mapY = floor(rayY / mapCellSize)
 
                local validX = mapX > 0 and mapX <= mapColumnCount
                local validY = mapY > 0 and mapY <= mapRowCount
                local withinMap = validX and validY
                if not withinMap then
                        rayInfo.distance = MAX_DISTANCE
                        break
                end
 
                local wallId = worldMap[mapX][mapY]
                wallFound = wallId > 0
                
                if wallFound then
                        local wallInfo = wallDefList[wallId]
                        local isTransparent = wallInfo.isTransparent
 
                        local distance
                        local offset
                        
                        if isTransparent then
                                local halfYStep = rayYStep * 0.5
                                local offsetRayY = rayY + halfYStep
                                local yvalue = abs(offsetRayY - ypos)
                                distance = abs(yvalue) / sinTable[rayAngle]
                                
                                local halfStep = rayXStep * 0.5
                                offset = min(rayX + halfStep, mapCellSize)
                        else
                                local yvalue = abs(rayY - ypos)
                                distance = abs(yvalue / sinTable[rayAngle]);
                                offset = min(rayX, mapCellSize)
                        end
                        
                        rayInfo.wallId = wallId
                        rayInfo.distance = distance
                        rayInfo.offset = offset
                        rayInfo.mapHitX = mapX;
                        rayInfo.mapHitY = mapY;
                        rayInfo.x = rayX;
                        rayInfo.y = rayY;
                else
                        rayY = rayY + rayYStep
                        rayX = rayX + rayXStep
                end
        end
                
        return rayInfo          
end
 
function RaycastEngine:performVerticalCheck(xpos, ypos, rayAngle, worldMap, wallDefList, rayInfo)
        local mapColumnCount = self.mapColumnCount
        local mapRowCount = self.mapRowCount
        local mapCellSize = self.mapCellSize
        local cosTable = self.cosTable
 
        local rayX = rayInfo.x
        local rayY = rayInfo.y
        local rayXStep = rayInfo.rayXStep
        local rayYStep = rayInfo.rayYStep
 
        local wallFound = false 
 
        while not wallFound do
                local mapX = floor(rayX / mapCellSize)
                local mapY = floor(rayY / mapCellSize)
 
                local validX = mapX > 0 and mapX <= mapColumnCount 
                local validY = mapY > 0 and mapY <= mapRowCount
                local withinMap = validX and validY
                
                if not withinMap then
                        rayInfo.distance = MAX_DISTANCE
                        break
                end
 
                local wallId = worldMap[mapX][mapY]
                wallFound = wallId > 0
 
                if wallFound then
                        local wallInfo = wallDefList[wallId]
                        local isTransparent = wallInfo.isTransparent
 
                        local distance
                        local offset
                        
                        if isTransparent then
                                local halfXStep = rayXStep * 0.5
                                local offsetRayX = rayX + halfXStep
                                local xvalue = abs(offsetRayX - xpos)
                                distance = abs(xvalue) / cosTable[rayAngle]
                                
                                local halfYStep = rayYStep * 0.5
                                offset = min(newY + halfYStep, mapCellSize)
                        else
                                local xvalue = abs(rayX - xpos)
                                distance = abs(xvalue / cosTable[rayAngle]);
                                offset = min(rayY, mapCellSize)
                        end
 
                        rayInfo.wallId = wallId
                        rayInfo.distance = distance
                        rayInfo.offset = offset
                        rayInfo.mapHitX = mapX;
                        rayInfo.mapHitY = mapY;
                        rayInfo.x = rayX;
                        rayInfo.y = rayY;
                else
                        rayY = rayY + rayYStep
                        rayX = rayX + rayXStep
                end
        end
        
        return rayInfo
end
 
function RaycastEngine:processFrame(dt, time, params)
        local commonAngles = self.commonAngles
        local heightTable = self.heightTable
        local cosTable = self.cosTable
        
        local wallDefList = params.wallDefList
        local viewAngle = floor(params.viewAngle)
        local halfFov = commonAngles[30]
        local currentAngle = viewAngle - halfFov
        if currentAngle < commonAngles[0] then
                currentAngle = currentAngle + commonAngles[360]
        end
                
        local sliceCount = 0
        local visibleWidth = params.visibleWidth
        local maxRayDepth = params.maxRayDepth
        local xpos = params.xpos
        local ypos = params.ypos
        local worldMap = params.worldMap
        
        local illegalHorizontalAngles = {
                [commonAngles[0]] = true,
                [commonAngles[180]] = true,
        }
        
        local illegalVerticalAngles = {
                [commonAngles[90]] = true,
                [commonAngles[270]] = true,
        }
        
        local foundWalls = {}
        
        for i = 0, visibleWidth do
                local solidWallFound = false
                local hitDepth = 0
                
                local hrayResult = self:getFirstHorizontalIntercept(xpos, ypos, currentAngle)
                local vrayResult = self:getFirstVerticalIntercept(xpos, ypos, currentAngle)
                
                while not solidWallFound and hitDepth < maxRayDepth do
                        local ignoreHorizontalCheck = illegalHorizontalAngles[currentAngle]
                        if not ignoreHorizontalCheck then
                                hrayResult = self:performHorizontalCheck(xpos, ypos, currentAngle, worldMap, wallDefList, hrayResult)
                        end
 
                        local ignoreVerticalCheck = illegalVerticalAngles[currentAngle]
                        if not ignoreVerticalCheck then
                                vrayResult = self:performVerticalCheck(xpos, ypos, currentAngle, worldMap, wallDefList, vrayResult)
                        end
 
                        local closestVerticalDistance = vrayResult.distance or MAX_DISTANCE
                        local closestHorizontalDistance = hrayResult.distance or MAX_DISTANCE
                        local useVerticalInfo = closestVerticalDistance < closestHorizontalDistance
                        local result = useVerticalInfo and vrayResult or hrayResult
 
                        -- fix fisheye
                        local nangle = (commonAngles[330] + i) % commonAngles[360]
                        local cosAngle = cosTable[nangle]
                        local rayDistance = result.distance
                        rayDistance = floor(rayDistance * cosAngle)
 
                        local sliceHeight = heightTable[rayDistance]
                        
                        -- add wall to render list
                        table.insert(foundWalls, {
                                                                wallId = result.wallId,
                                                                offset = result.offset,
                                                                mapHitX = result.mapHitX,
                                                                mapHitY = result.mapHitY,
                                                                distance = rayDistance,
                                                                sliceHeight = sliceHeight,
                                                                drawColumn = i,
                                                        })
 
                        result.x = result.x + result.rayXStep
                        result.y = result.y + result.rayYStep
 
                        local wallTypeInfo = wallDefList[result.wallId]
                        local isSolid = wallTypeInfo.isSolid
                        
                        solidWallFound = isSolid
                        hitDepth = isSolid and hitDepth or (hitDepth + 1)
                end             
 
                local nextAngle = currentAngle + 1
                local resetAngle = nextAngle > commonAngles[360]
                
                currentAngle = resetAngle and (currentAngle - commonAngles[360]) or nextAngle           
        end
        
        return foundWalls
end
 
function RaycastEngine:updateCameraPosition(params)
        local commonAngles = self.commonAngles
        local cameraInfo = params.cameraInfo
        local worldMap = params.worldMap
        local movementSpeed = params.movementSpeed
        local turnSpeed = params.turnSpeed
        local viewAngle = cameraInfo.viewAngle
        local xpos = cameraInfo.xpos
        local ypos = cameraInfo.ypos
        
        if movementSpeed ~= 0 then
                local cosTable = self.cosTable
                local sinTable = self.sinTable
                local newX = floor(xpos + (cosTable[viewAngle] * movementSpeed))
                local newY = floor(ypos + (sinTable[viewAngle] * movementSpeed))
                
                local clampedX, clampedY = self:clipPlayerMovement {
                                                                                        oldX = xpos,
                                                                                        oldY = ypos,
                                                                                        newX = newX, 
                                                                                        newY = newY,
                                                                                        worldMap = worldMap,
                                                                                }
                
                cameraInfo.xpos = clampedX
                cameraInfo.ypos = clampedY
        end
 
        if turnSpeed ~= 0 then
                local newViewAngle = floor(viewAngle + turnSpeed)
                
                if newViewAngle < commonAngles[0] then
                        newViewAngle = newViewAngle + commonAngles[360]
                end
                
                if newViewAngle > commonAngles[360] then
                        newViewAngle = newViewAngle - commonAngles[360]
                end
 
                cameraInfo.viewAngle = newViewAngle             
        end
end
 
function RaycastEngine:clipPlayerMovement(params)
        local mapCellSize = self.mapCellSize
        local worldMap = params.worldMap
        local oldX = params.oldX
        local oldY = params.oldY
        local newX = params.newX
        local newY = params.newY
        
        local wallImpact = false
        local clipDistance = 15
 
        local mapX = floor(newX / mapCellSize)
        local mapY = floor(newY / mapCellSize)
 
        local left = mapX * mapCellSize
        local top = mapY * mapCellSize
        local right = left + mapCellSize
        local bottom = top + mapCellSize
 
        local oldX = params.oldX
        local oldY = params.oldY
        local newX = params.newX
        local newY = params.newY
        
        local leftMap = mapX - 1
        local rightMap = mapX + 1
        local topMap = mapY - 1
        local bottomMap = mapY + 1
        
        
        -- movement left
        if newX < oldX then
                if worldMap[leftMap][mapY] > 0 then
                        if newX < left or (abs(newX - left) < clipDistance) then
                                newX = oldX
                                wallImpact = true
                        end
                end
        end
        
        -- movement right
        if newX > oldX then
                if worldMap[rightMap][mapY] > 0 then
                        if newX > right or (abs(right - newX) < clipDistance) then
                                newX = oldX
                                wallImpact = true
                        end
                end
        end
 
        -- movement up  
        if newY < oldY then
                if worldMap[mapX][topMap] > 0 then
                        if newY < top or (abs(newY - top) < clipDistance) then
                                newY = oldY
                                wallImpact = true
                        end
                end
        end
        -- movement down
        if newY > oldY then
                if worldMap[mapX][bottomMap] > 0 then
                        if newY > bottom or (abs(newY - bottom) < clipDistance) then
                                newY = oldY
                                wallImpact = true
                        end
                end
        end
        
 
        -- if no wall impact yes, break cell into quads and inspect further
        if not wallImpact then
                local halfCellSize = floor(mapCellSize * 0.5)
                local leftPlusClip = left + clipDistance
                local topPlusClip = top + clipDistance
 
                -- region A
                if newY < (top + halfCellSize) then
                        if newX < (left + halfCellSize) then
                                if worldMap[leftMap][topMap] > 0 and (newY < topPlusClip) then
                                        if newX < leftPlusClip then
                                                if oldX > leftPlusClip then
                                                        newX = oldX
                                                else
                                                        newY = oldY
                                                end
                                                wallImpact = true
                                        end
                                end
 
                                if worldMap[leftMap][topMap] > 0 and (newX < leftPlusClip) then
                                        if newY < topPlusClip then
                                                if oldY > topPlusClip then
                                                        newY = oldY
                                                else
                                                        newX = oldX
                                                end
                                                wallImpact = true
                                        end
                                end
                        end
                end             
                
                -- region B
                if not wallImpact and newX > (right - halfCellSize) then
                        if worldMap[rightMap][topMap] > 0 and newY < topPlusClip then
                                if newX > (right - clipDistance) then
                                        if oldX < (right - clipDistance) then
                                                newX = oldX
                                        else
                                                newY = oldY
                                        end
                                        wallImpact = true
                                end
                        end
                        
                        if worldMap[rightMap][topMap] > 0 and newX > (right - clipDistance) then
                                if newY < topPlusClip then
                                        if oldY > topPlusClip then
                                                newY = oldY
                                        else
                                                newX = oldX
                                        end
                                        wallImpact = true
                                end
                        end
                end
                
                -- region C
                if not wallImpact and newY > (top + halfCellSize) then
                        if newX < (left + halfCellSize) then
                                if worldMap[leftMap][bottomMap] > 0 and newY > (bottom - halfCellSize) then
                                        if newX < (left + clipDistance) then
                                                if oldX > (left + clipDistance) then
                                                        newX = oldX
                                                else
                                                        newY = oldY
                                                end
                                        end
                                end
 
                                if worldMap[leftMap][bottomMap] > 0 and newX < (left + clipDistance) then
                                        if newY > (bottom - clipDistance) then
                                                if oldY < (bottom - clipDistance) then
                                                        newY = oldY
                                                else
                                                        newX = oldX
                                                end
                                                wallImpact = true
                                        end
                                end
                        end
                end
                        
                -- region D
                if not wallImpact and newX > (right - halfCellSize) then
                        if worldMap[rightMap][bottomMap] > 0 and newY > (bottom - clipDistance) then
                                if newX > (right - clipDistance) then
                                        if oldX < (right - clipDistance) then
                                                newX = oldX
                                        else
                                                newY = oldY
                                        end
                                        wallImpact = true
                                end
                        end
 
                        if worldMap[rightMap][bottomMap] > 0 and newX > (right - clipDistance) then
                                if newY > (bottom - clipDistance) then
                                        if oldY < (bottom - clipDistance) then
                                                newY = oldY
                                        else
                                                newX = oldX
                                        end
                                        wallImpact = true
                                end
                        end
                end
        end
 
        return newX, newY
end
 
 
return RaycastEngine

main.lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
-- Project: Raycasting Engine Demo
-- SDK: Corona - 09/12/11
-- Author: Andrew Burch
-- Date: 8/02/2012
-- Site: http://www.newhighscore.net
-- Contact: andrew.burch@newhighscore.net
-- Note: Ported basic aspects from my C++ version of a simple raycasting engine
 
local map = require('map')
local input = require('input')
local renderer = require('renderer')
local raycastengine = require('raycast')
 
-- hide the status bar
display.setStatusBar(display.HiddenStatusBar)
 
local contentTop = 0
local contentLeft = 0
local contentWidth = display.contentWidth
local contentHeight = display.contentHeight
local horizon = contentTop + (contentHeight * 0.5)
 
-- setup background
local ceiling = display.newRect(0, 0, contentWidth, horizon)
ceiling:setFillColor(20,20,200)
local floor = display.newRect(0, horizon, contentWidth, horizon)
floor:setFillColor(100,100,100)
 
--initialise camera
local mapCellSize = 64
local halfCellSize = mapCellSize * 0.5
local startingColumn = 2
local startingRow = 2
local startX = (startingColumn * mapCellSize) + halfCellSize
local startY = (startingRow * mapCellSize) + halfCellSize
 
local cameraInfo = {
        eyeLevel = halfCellSize,
        viewAngle = 0,
        xpos = startX,
        ypos = startY,
        mapX = startingColumn,
        mapY = startingRow,     
}
 
-- initialise the engine
local fov = 60
local maxRayDepth = 2
 
local engine = raycastengine.new()
engine:initialise { 
                        visibleWidth = contentWidth,
                        visibleHeight = contentHeight,
                        mapRowCount = map.rowCount,
                        mapColumnCount = map.columnCount,
                        mapCellSize = mapCellSize,
                        fov = fov,
                        maxRayDepth = maxRayDepth,
                        commonAngleList = {
                                0, 30, 45, 90, 
                                180, 270, 330, 360,
                        },
                }
 
-- initialise rendering system
local renderingSystem = renderer.new()
renderingSystem:initialise {
                        displayWidth = contentWidth,
                        displayHeight = contentHeight,
                        horizon = horizon,
                        columnWidth = 1,
                }
                                        
-- initialise input system
local inputSystem = input.new()
inputSystem:initialise {
                        buttonWidth = 48,
                        buttonHeight = 48,
                        displayWidth = contentWidth,
                        sideBorder = 20,
                        turnAcceleration = 2.0,
                        movementAcceleration = 0.9,
                }
 
-- movement variables
local maxTurnSpeed = 13.5
local maxMovementSpeed = 13.5
local turnDeccelerateFactor = 0.6       
local moveDeccelerateFactor = 0.82
 
 
local lastUpdateTime = 0
 
-- register main update listener
Runtime:addEventListener("enterFrame", function(event) 
                                                                                        local time = event.time
                                                                                        local dt = (time - lastUpdateTime) / 1000
                                                                                        
                                                                                        inputSystem:update(dt, time, {
                                                                                                                                maxTurnSpeed = maxTurnSpeed,
                                                                                                                                maxMovementSpeed = maxMovementSpeed,
                                                                                                                                turnDeccelerateFactor = turnDeccelerateFactor,  
                                                                                                                                moveDeccelerateFactor = moveDeccelerateFactor,  
                                                                                                                        })
                                                                                        
                                                                                        local movementSpeed = inputSystem:getMovementSpeed()
                                                                                        local turnSpeed = inputSystem:getTurnSpeed()
                                                                                        
                                                                                        engine:updateCameraPosition { 
                                                                                                                                cameraInfo = cameraInfo,
                                                                                                                                movementSpeed = movementSpeed,
                                                                                                                                turnSpeed = turnSpeed,
                                                                                                                                worldMap = map.mapData,
                                                                                                                        }
                                                                                                                        
                                                                                        local sceneInfo = engine:processFrame(dt, time, {
                                                                                                                                xpos = cameraInfo.xpos,
                                                                                                                                ypos = cameraInfo.ypos,
                                                                                                                                viewAngle = cameraInfo.viewAngle,
                                                                                                                                worldMap = map.mapData,
                                                                                                                                wallDefList = map.wallDefList,
                                                                                                                                visibleWidth = contentWidth,
                                                                                                                                maxRayDepth = maxRayDepth,
                                                                                                                        })
                                                                                        
                                                                                        renderingSystem:renderScene { 
                                                                                                                                sceneInfo = sceneInfo,
                                                                                                                                horizon = horizon,
                                                                                                                        }
                                                                                        
                                                                                        lastUpdateTime = time                                                                                   
                                                                                end)

tablex.lua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
module(..., package.seeall)
 
local insert = table.insert
 
-- removes all entries from a table
function clear(table)
        for k, v in pairs(table) do
                table[k] = nil  
        end
        return table
end
 
function count(t)
        local count = 0
        for _,v in pairs(t) do
                count = count + 1
        end
        return count
end
 
function icount(t)
        local i = 0
        for _, v in ipairs(t) do
                i = i + 1
        end
        return i
end     

You can also download the code from here

If you have any questions, please contact me. Also feel free to leave comments.


Replies

nicholasclayg
User offline. Last seen 1 week 5 days ago. Offline
Joined: 16 May 2011

HOLY CRAAAAAAAAAAAAAAAAAAAAAAAPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

^ That means it's.....amazing. No idea how this works, but I love playing with it.

Wow, just wow.

:)
ng

+1 voted.

Jesder
User offline. Last seen 2 years 1 day ago. Offline
Joined: 10 Dec 2011

Thanks for the feedback :)

If you are interested in the theory, you should check this link out: Link

The content here is the same that I learned from all those years ago. Formatting is different so it may have been republished by someone else. I think the axis in my engine is different, but the principles are the same.

I might see if I can republish the information myself, minus all those annoying banners and ads which that link contains.

horacebury
User offline. Last seen 8 hours 52 min ago. Offline
Joined: 17 Aug 2010

Incredible. Well done and thank you.

horacebury
User offline. Last seen 8 hours 52 min ago. Offline
Joined: 17 Aug 2010

If I'm not mistaken, having only glanced at the code, you are rendering the polygons using 1-pixel wide, filled rectangles, yes?

If I didn't think someone had already started on this (and if my maths were better) I would write a polygon render function, being that Corona is lacking such a thing.

nicholasclayg
User offline. Last seen 1 week 5 days ago. Offline
Joined: 16 May 2011

This still amazes me. I read through that link about raycasting (wow that's one LONG document). I'm not a math guy so those parts I was kind of "duhhhhhhh" haha.

The rest was interesting theory. It gives a view how Wolf3d from id software did it. I guess a 2d engine can do 3d under certain circumstance and run pretty damn well too.

A game I used to play years ago was called "Shining in the Darkness" basically the player had a top view of the world, and then dungeons etc. Those dungeons were from a 1st person view, and basically you would hit the up direction on d pad (sega genesis, old school!) and it would go up 1 square.

There was another game called Phantasy Star (the original on Sega Master System, my favorite game of all time!!!) and it did the same type of thing. You had a overworld view, and in towns you had a top down perspective, but in dungeons you had a 1st person view, click up direction and moves 1 square.

What I used to do was buy tons of Graph paper (my favorite paper of all time! hehe) and I would map out he dungeons by hand! I don't know why I was so fascinated with it.

But I think something like this could be used for something like that? But instead of the rigid square by square approach, a dungeon could be made with random encounters and when a player hits the "map" button, it would show an overview of where the player is at. All standard stuff.

In fact, I KNOW it's possible with your code (I can imagine it,so therefore I can be built....or i'm dillusional!). Probably better off doing it in unity3d or something like that, but if someone wanted to kick it old school they could do it this way (I like old school).

What you think?

ng

Jesder
User offline. Last seen 2 years 1 day ago. Offline
Joined: 10 Dec 2011

@horacebury: You are correct, I went with flat filled rectangles for the rendering.

A poly render function would be useful for real 3D, but with a raycasting engine, it really is just slices built off a 2D map (2.5D if you will). I could be wrong, but I suspect that calculating and rendering polys would be more processor hungry than changing line/rect heights. Ofcourse, there is the trade off that you have lots of line/rect objects eating up the processor - I'd actually be interested to hear from the guys/girls at Ansca what they think would boost performance.

Some additional thoughts on using the filled rects in this sample:

1) All my graphical samples (found here) were about improving my knowledge on basic graphics with corona. I felt I could easily adjust the resolution by using them with minimal effort.

2) At this point I have not seen a way to plot individual pixels with corona (which would aid texturemapping and also transparent walls). Back in the old days, I'd whip up some assembly and render directly to screen (but those days are gone :()

3) Ideally the walls would be textured, but I could not see any easy way to render a single slice of texture / sprite. I probably should look at doing some sort of sprite demo to get some expeience working with them - Maybe something will crop up that will work.

@ng: You're idea would work and can be done. The raycasting engine (at its core) converts a 2D map position and direction into a 3D view. So jumping in and out would be no problem. In my original engine (written with pascal) I had a map the player could bring up, which was just a textured version of the 2d map (seen in map.lua). The player could walk around with this view and still get all the clipping and open doors, etc. So you could play the game while viewing the 2D map, or in the "3D" view.

The thing with raycasting is it's a tech that was designed back when hardware was way less powerful and using it now is more restrictive than using a true 3D engine. There are tradeoffs no matter which direction you go, but what I always loved about the raycasting engine was how simple it is. The difficulty I see with using it under Corona (right now) is there is no simple way to render a single texture slice from an image or sprite (if someone can point me in the direction of a way, I'll update the raycaster in 5 minutes to render textured walls).

It was also written at a time when I could convert things to assembly to gain even more speed - which I have not been able to do since Gameboy advance days. It's here where using a true 3D engine is more desirable over a raycaster.

canupa.com
User offline. Last seen 10 weeks 6 days ago. Offline
Joined: 20 Jun 2011

wow! this is just awesome and I was asking for a sample like this a long time ago.

you, sir, are my personal hero!

-finefin

Beloudest
User offline. Last seen 1 day 8 hours ago. Offline
Joined: 15 Jan 2012

5 stars. :)

Pixin
User offline. Last seen 5 days 17 hours ago. Offline
Joined: 21 Feb 2011

Wow!

Ninja Pig Studios
User offline. Last seen 6 weeks 2 days ago. Offline
Joined: 26 Jan 2011

Well I guess there is no need for Unity 3D anymore :)

skolesnyk
User offline. Last seen 2 years 16 weeks ago. Offline
Joined: 26 Jul 2011

Great job, Jesder! How big map can be? And can you explain mapData values?

Jesder
User offline. Last seen 2 years 1 day ago. Offline
Joined: 10 Dec 2011

You can make the map much larger - I kept is small since this was purely a demo, and I didn't feel like designing out a large scale map :)

The mapData values are just an index into the wallDefList table. So 0 means it's a blank cell and the player can move there, values 1 onwards are walls.

ch8908
User offline. Last seen 1 year 14 weeks ago. Offline
Joined: 8 Dec 2011

WOW, this example is awesome!!!
it looks like really 3D.

ale
User offline. Last seen 3 days 17 hours ago. Offline
Joined: 29 Jan 2011

Amazing!
Congratulation.....

Ale

PValentini
User offline. Last seen 5 weeks 5 days ago. Offline
Joined: 21 May 2010

This demo is VERY SLOW in my ipod touch 4 with ios 5.1.1.
It is working well in your devices?
Do you have any tip for me try to fix it?
Thank you

stephenTU
User offline. Last seen 1 year 4 weeks ago. Offline
Joined: 4 Sep 2011

Very futuristic, reminds me of Minecraft. Awesome job!