This is a read-only snapshot of the ComputerCraft forums, taken in April 2020.
Gumball's profile picture

Raycast Algorithm

Started by Gumball, 22 May 2016 - 05:54 PM
Gumball #1
Posted 22 May 2016 - 07:54 PM
Basically I'm trying to make a 3D Engine using a method similar to raycasting. My problem is getting the field of view from an angle. I currently have a drawing method setup that draws a line, up and down, sized depending on a variable that shows how long the ray is from the player. The table looks like: {int colorNum,int dis}

Since I was too lazy to implement changing paint codes to colors, colorNum is a table consisting of around 5 colors.
My problem is trying to find a way that finds a field of view correctly from an angle that is the players rotation. If you have a method, please help.
Current code is at: pastebin.com/np9ciPgA
Bomb Bloke #2
Posted 23 May 2016 - 01:37 AM
You mean the content within the FOV dictated by the viewing angle, I guess?

This should start you off:

local function rotatePoint(x, y, angle)
    local sin, cos = math.sin(angle), math.cos(angle)
    return x * cos - y * sin, x * sin + y * cos
end

Rotate each map object according to a set of angles, one for each column on your display. Figure out the closest object that ends up sitting exactly on the Y axis of the camera (after rounding down, say), and render that.

For a wider FOV, spread the angles apart. For a narrower one, clump 'em together. You'll probably want a fairly wide FOV. Personally I'd rig up a pair of buttons to raise / lower it on the fly while displaying what it is, as that'd make it a heck of a lot easier to experiment for the "best" value.
Gumball #3
Posted 23 May 2016 - 03:12 AM
You mean the content within the FOV dictated by the viewing angle, I guess?

This should start you off:

local function rotatePoint(x, y, angle)
	local sin, cos = math.sin(angle), math.cos(angle)
	return x * cos - y * sin, x * sin + y * cos
end

Rotate each map object according to a set of angles, one for each column on your display. Figure out the closest object that ends up sitting exactly on the Y axis of the camera (after rounding down, say), and render that.

For a wider FOV, spread the angles apart. For a narrower one, clump 'em together. You'll probably want a fairly wide FOV. Personally I'd rig up a pair of buttons to raise / lower it on the fly while displaying what it is, as that'd make it a heck of a lot easier to experiment for the "best" value.

Is it possible to dumb this down to 5th grade math? I'm 11, and cosine is something I barely understand. Sorry
xD. Also I don't get what this does. I'm thinking something similar to getting the longest lenghts that the view can see, and minimizing that until an object intersects the view; but I don't know how to calculate that circle.
Edited on 23 May 2016 - 01:32 AM
Bomb Bloke #4
Posted 23 May 2016 - 05:04 AM
Basically the function simply swings a given point around the origin according to a specified angle. Point and angle go in, point comes out.

You might check angles viewAngle-25 degress through to viewAngle+25 degrees, one for each of the 51 screen columns. That's a fairly simple loop to construct, and the resulting FOV will probably look credible.

For each angle, run through all the map objects, and rotate them around the camera (your "origin"). For example, you might first take the map object at 1x1, offset it by subtracting the camera co-ords (for eg, if the camera is at 20 x 3, you'd get -19 x -2), then pass those two numbers and math.rad(viewAngle-25) to the rotation function. If this lines things up so that the floored x-co-ord returned is 0, then you might say your ray hit that object, and the y-co-ord would then be the distance. Continue to check objects at 2x1, 3x1, etc…

Once you've checked each object along that angle, you'll know which of the ones that the ray hit was closest, and so that's the one you draw in that screen column. Rinse and repeat for each angle relating to each screen column, and that's it. You're done.

This isn't the most efficient method, but it aims to be a simple one.

A faster but somewhat more complex system would be to construct a hypothetical line between your origin (the camera) and one point in each row of the map, extended out according to the angle of the screen column you're currently checking. First row to contain an object is the one you render. This way, at most you'll perform a number of checks per screen column equal to the number of rows in your map table (and often a lot less). Given that you have an angle and the length of one side of a theoretical triangle (the distance between your camera's row and the row you want to check the object in), see if you can figure out which of the three basic trig functions is applicable to getting the relevant column of each row… Look up pages about Soh Cah Toa for hints!
TheRockettek #5
Posted 23 May 2016 - 07:30 AM
Is it possible to dumb this down to 5th grade math? I'm 11, and cosine is something I barely understand

Youll start using SOH,CAH,TOA (Sin,Cos,Tan) on a scientific calculator in yr9 (most probrably)
But youll actually use the formulars without a calculator in like y11

;)/>
Lupus590 #6
Posted 23 May 2016 - 12:38 PM
Is it possible to dumb this down to 5th grade math? I'm 11, and cosine is something I barely understand

https://www.mathsisfun.com/algebra/trigonometry.html
Gumball #7
Posted 24 May 2016 - 02:36 AM
So basically I could have a table, which would be the rotated map, and the map. I go through the map cell by cell, and place that cell in the rotated map at the location the rotate function specified. That part is now clear, but I am still a bit dazed on how to get the view, once again. Sorry for the ignorance.
I may have just figured it out. So basically, when the map is rotated, then go, for example 25 to the left, and keep decreasing the Y value until it finds something. And then do so to the right, or just start -25 to the left and go +26 to the right. I'll try this, and then give updates. Thank you!

Yeah… no.. I think I have the right idea, but the code is stuck in an infinite loop. Code is here: F2WuT4tR
Edited on 24 May 2016 - 12:50 AM
Bomb Bloke #8
Posted 24 May 2016 - 02:14 PM
Nah, that's not it.

The idea is that you have to check one angle for every column on your display. That means you don't rotate the objects once for each frame you draw - you rotate 'em once for each column you draw. For the first column, you might rotate the objects viewAngle-25 degrees. For the second column, viewAngle-24 degrees… and so on, until 51 angles have been checked (one for each of the 51 columns making up your ComputerCraft computer's display).

These angles don't have to be one degree apart - if you make the step size larger or smaller, you'll get a different FOV. You'll probably want a much larger one in the end. But regardless, you do need to check one unique angle for each displayed screen column!

Think about what your real eyes are doing right now - you can see stuff that's exactly in line with the direction they're pointing, but you can also see stuff that's on lots of different angles relative to their facing. You don't need to turn your eyes to make out something ten degrees to your left, for example - that angle's already included within your field of view, you already capture it within the left-hand side of the image you perceive. Each image captures things along multiple angles because your eyes have multiple receptors, same as the screen has multiple pixels, and the angle between each cell in your retina and the real-world objects around you is different!

So after rotating a given map object (bearing in mind that it's important to subtract the camera's position from the map object's position before rotating, so that each is rotated relative to the camera!), if its floored X value is 0, then you can assume that a line projected along the current column's angle from the camera would've hit that object. Take the absolute value of the rotated Y (which gets you the distance), and if you haven't found a hit that's closer then you cache the colour and distance values (discarding those of any other hits found thus far). When all objects are checked you draw the column, knowing the colour of the wall that should be drawn there, and how far away that wall is.

--# Psuedocode

local curColumn = 1

for curAngle = minimumFOVangle, maximumFOVangle do  --# Should be 51 iterations, one for each screen column.
  local colour, distance

  for object in map do
    local X, Y = rotatePoint(object.x - camera.x, object.y - camera.y, math.rad(curAngle))

    if math.floor(X) == 0 and math.abs(Y) < distance then
      distance = math.abs(Y)
      colour = object.colour
    end
  end

  drawWallInColumn(colour, distance, curColumn)
  curColumn = curColumn + 1
end

Again, this is a "naive" way of coding things - it's simple, but quite inefficient. Once you've wrapped your head around it though, you'll hopefully be in a better position to understand a better way (applying basic trig to extend lines from the camera throughout the map to cut down on the number of checks needed).
Edited on 24 May 2016 - 12:16 PM
Gumball #9
Posted 24 May 2016 - 10:39 PM
So basically, it rotates each column that is relative to the FOV at an increased rate, so each column is basically STRAIGHT in the middle of your view, and then it checks how long it takes to get to that, and rotates it once more for another column, somewhat like an assembly line? I will try that, thanks!

EDIT:
I'm still stuck on getting whats in the view. I'm told to check each angle with every column in my FOV, but I'm supposed to get whats in the FOV first? This doesn't make very much sense.
Edited on 24 May 2016 - 08:41 PM
Bomb Bloke #10
Posted 25 May 2016 - 01:51 AM
The process of checking one angle for each column (and locating one wall along each) is in fact what gets you the content of your field of view. The range of your field of view is defined by the range of those angles.
Gumball #11
Posted 25 May 2016 - 05:41 AM
The process of checking one angle for each column (and locating one wall along each) is in fact what gets you the content of your field of view. The range of your field of view is defined by the range of those angles.

Could you write an example script that would work? I'm think I get it, just making sure. Also that script up there isn't compatible with the code I have.
Bomb Bloke #12
Posted 25 May 2016 - 11:31 AM
Also that script up there isn't compatible with the code I have.

Well, here it is bodged right into your original paste:

http://pastebin.com/e64x0pUr

… but at this point, you're going to have to sit down and start reading up on how Sin/Cos/Tan work. Experiment with them. Learn how to draw lines with them. You really can't advance the code any further until you've got the basic principles behind them down pat; things only get more complex from here.
Gumball #13
Posted 25 May 2016 - 06:56 PM
Yeah, I just realized that. Thanks for all the help though! :)/>