Hey folks,

Hope you can help me with a problem that's been whipping my behind the past several days -- the FOV algorithm for WulaBugr.

After many, many failed attempts at perfecting the routine (usually with a rat's nest of conditional statements ), I grabbed one of my game-math books, and found what *seems* to be the perfect solution: Coordinate rotation.

The books shows an example of how to detect when a ball hits an angled line. That's fine and all... but the book does a *very* poor job of explaining how the trig-magic involved actually works... so I'm stuck with an example that I do not understand, and if I can't understand the example, how am I supposed to adapt the code therein to my project?

The gist of the sample is basically this:

You have an object, and you want to know when it has gone past a line. The problem is that the line in question is at an angle. So, the example demonstrates how one can rotate the coordinates of the line, so that it is temporary "straight", and the collision test can be done with a simple conditional (basically a check to see if the ball's Y is greater than the coordinate-rotated Y value of the line). Once that check is completed, the coordinates are rotated back to normal.

I am having the damnedest time getting this concept working in my game. It basically uses the following code to rotate the line to the "easy" angle as such:



I tried to apply the same technique to my visibility ray-casting, but it simply refuses to work -- instead of getting lines that are flush with the wall tiles, I get ALL sorts of bizarre, nonsensical shapes going on.

The basic principle behind my ray-caster:

Start at player's location
Plot a point: player.x/y + cos/sin(angle_of_ray) * distance_to_wall
Make sure point is flush with the wall edge (i.e. the final point remains at the same angle as when it struck the wall)
Increment angle_of_ray, and repeat

That's pretty much it. I thought maybe the coordinate rotation deal might be my answer, but I sure as hell can't get it going without some help...

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

I have a hard time to understand what you even try to do?
Sounds like a Sphere/Line segment intersection, or rather the shortest distance from a point to a linesegment?

If thats the case take this code Sirisian gave me
http://pastebin.com/f49a054c1

It's been so helpful for a lot of cases

_________________
Long pork is people!

wzl's burrow

No spheres involved -- just a line that is used to plot a point. Only problem is that the point will be plotted *inside* a wall unless I know *exactly* where it makes contact with the wall -- else the entire effect is ruined. It's basically finding the point of intersection between two lines (the ray, and the nearest wall).

None the less, I will look at the link you posted and see if that answers any of my concerns.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Holy cow, that is some nice code. The "LineSegmentToLineSegmentIntersection()" function looks like it may just be the ticket. Hopefully I have enough gas in the tank to try it out before I keel over from exhaustion...

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

This sucks.

Here's what I am *trying* to achieve:



But, the code from the link posted above gives me:



This is really infuriating. I've been trying to get this working in one form or another for the better part of a week, and still can't nail it...

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Hmm, 2d line intersection, you don't need sin/cos for that ;)

Line 1:
Base point (ax, ay), direction vector (bx, by).
Equations:


For example, a line through (0, 2), with direction (2, 1) (meaning, if x
changes 2, y changes 1).


n is a varying real number giving how often you have to add the direction vector to the base point to reach another point at the line.
(n=0 gives the base point, other values give you the other points at the line.)
Every point at the line has a unique value for n for this line.
For example n at y = 0:



x at that point: 0 + (-2) * 2 = 0 - 4 = -4.


A trick to get a direction is to take two known points at the line, and
subtract them:

Say a line between (2, 5) and (8, 78)
Direction between both points is (8-2, 78-5)


A nice side-effect of this calculation is that p=0 gives you the first point
and p=1 gives you the second point.


For line intersection you need a 2nd line:


At the intersection point, x and y of both lines are the same:


Two equations, two unknowns, piece of cake :p
(standard equation manipulation to pull the unknown n and m out. I am omitting all special cases where coordinates are 0, which means the direction is parallel to one of the axes)

From the top equation


And similarly for the bottom equation:


Obviously, n can only have one value, thus


which looks scary but is a computable value if you know the original lines base points and directions.
(hopefully I did not make an error in it)

then use the original second line equations to compute x and y of the
intersection.

_________________
My project: Messing about in FreeRCT, dev blog, and IRC #freerct at oftc.net

Unless I'm mistaken, the explanation you gave me is very similar to (or the same as) the LineSegmentToLineSegmentIntersection() routine in the pastebin code weezl posted above (though in fairness, I haven't yet thoroughly compared them).

In either case, this kind of solution would be perfect -- if I could just get it to work. With the experience of solving my past programming exploits, I have a feeling that the code in the pastebin link (as well as yours, Alberth) works just fine -- it's more something to do with how I have something else configured.

So, with that... time to do some digging for buried turds.

(Thank you guys SO much for your help -- hopefully once I figure out what *I* am doing wrong, the code you've given me will magically work as I was expecting.)

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

I find it incredible hard to understand a piece of code without further context. Code from beginners are mostly doable, as it is small, and quite complete. I tried to read the pastebin code but it felt like a wall of code.
In the end, I resorted to scale down my answer to just plain math.

The subject is probably also partly to blame, trigometry is a hard subject to get right. Even in my own FreeRCT code I have functions which I designed and implemented only a few months back, but to understand them again, I'd need to re-do the math, I guess I should document it even more.

Anyway, I hope you find the mistake in your reasoning/programming soon, so you can fit all pieces of the puzzle together :)

PS
In my previous post I forgot to mention how sin/cos fits in 2d lines with direction.
The vector (cos(d), sin(d)) is the x/y coordinate at the unit circle at an angle of d radians. You can use that vector as direction of a line to get a line at angle d.

_________________
My project: Messing about in FreeRCT, dev blog, and IRC #freerct at oftc.net

THAT is why I'm posting few answers here. This is a hardcore topic that, like you said, it is hard to understand without context.

_________________
"Life finds a way." - Ian Malcolm
My WebBlog: PixelDeveloper
English is not my native language, so excuse me for any writing mistakes.

Regarding the pastebin you just need to look at method names and the object definitions.
If you're not good at trig (i'm not) you don't need to even look at the method bodies. They work, and thats all you need to know for now

So when you said you're writing a ray caster you're taking your eye position and an initial angle 0, shoot a ray, collide with walls, and everything behind it becomes black, increase the angle and repeat i assume

This sounds unperformant in so many ways.

Did you see the articles i linked to you earlier?



While the first one is realized using shaders, you might be able to come up with a solition in software. I'm uncertain how it will perform though.

Another more simple approach, but not at all optimized, i used some time in the past is

_________________
Long pork is people!

wzl's burrow

It took me a while of playing with cos() and sin() to figure out (basically) what (I think) they do...

The way I picture it, each measures the "magnitude" (or maybe pitch is a better word) of the difference between angle 0 and the angle you feed the function. When you combine the returns, it gives you a ratio of the differences, which can be used to tell how to adjust your X/Y coordinates. Multiply those results by the distance you want, and voila.

I came to this conclusion based on looking at the results: When the angle is on the positive-X axis, cos() will return a positive number, and vice versa. When the angle is on the positive-Y axis, sin() will return a positive number, and vice versa.

Dunno how accurate my understanding of it is, though.


That's interesting; I tried to explain the situation as best I could. Would you mind giving me some ideas on what I could have added that would have made the context more clear?


The function performs well (at least in past iterations where it actually somewhat worked ), but you may be missing one key aspect of how the function works.

When a ray collides with a wall, I simply add a point (X/Y) at the location the ray intersected the wall. Then I break, increment the angle, and shoot another ray.

I keep shooting rays, plotting points at wall intersections, and incrementing the angle in this fashion until I've made a full circle (Math.PI*2)... This basically creates a polygon around the point that was shooting rays that follows the nearest walls in each direction. That polygon is used as a clipping plane for rendering -- when I render the game screen, it goes something like this:

Fill screen with black.
Create a path using the points in the FOV clipping plane.
Set the path to a clip-region. (Everything outside of a clip region is not rendered.)
Draw the map as normal.

And that is pretty much it. Like I said, in earlier iterations of the algorithm (which basically just plotted points at the center of a wall tile), it performed well enough so that there was zero noticeable difference in speed with the FOV algorithm enabled or disabled.

I admit that there may be more efficient methods of accomplishing this. It sounds like maybe you were thinking I was doing something insanely wasteful, though.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

I found Kahns accademy tutorials a great help for understanding math's
http://www.khanacademy.org/video/ca-geo ... geometry-2

Obviously every approach to solve this problem has it's own pro's and cons.

Although i'd not be using your ray casting approach for the following reasoning:

You make linevsline checks for every linesegment in the level or area for each iteration, so with 50 line segments, and a 1 degree iteration you'd have 50*360 calculations to only find the intersections, not even the closest point of intersecting towards the player. if course this gets less with increasingly bigger angles, but also does your accuracy and you might at some point miss smaller parts of geometry thus not casting shadows correctly.

This might work fine at your current stage and people say early optimization is bad, but since you're working a lot on it currently, you might aswell look for alternatives that work equally well or better with less performance penalties.

This is your call though, do what feels right

_________________
Long pork is people!

wzl's burrow

Bleh, I cannot attach an image to a post :(

Ok, in text thus :)

Draw an X and an Y axis. Draw the unit circle (that is, center point is (0,0), radius is 1).
Draw a line through (0,0), at some angle 'a'. At the point where the circle and the line cross, draw a horizontal line to the Y axis. That's cos(a), the horizontal length. At the same point, draw a vertical line to the X axis. That's sin(a), the vertical length.

I don't understand 'ratio of differences', but it seems largely compatible.
The ratio of cos and sin is actually tan ( tan(a) = sin(a) / cos(a) ). Given a ratio, you can compute 'a' again using atan (atan(sin(a) / cos(a)) == a, if cos(a) != 0).

"multiply by the distance" is exactly what you can do, perhaps even more than you realize. Since the vector (cos(a), sin(a)) has length 1, multiplying by say n, gives you a point at the distance of n units exactly (that is, if you could pick up that line segment, and put along one of the axes, you'd see it is really length n).
[Assuming the unit length at the X axis is equal to the unit length at the Y axis :p ]

For me, a schematic picture of lines crossing would have helped, with an indication of what length or angle or point you wanted to have. Your screenshots had way too much information; I can see they are different (doh), but why that happens, or how you compute the 'good' picture did not get across.

_________________
My project: Messing about in FreeRCT, dev blog, and IRC #freerct at oftc.net

Trying to feed a video link to a dial-up user, are we?


Well, if it makes any difference, I'm not doing it anywhere near how you describe.

Firstly, I do not increment by a degree per ray. Rather, I use a formula to "cull" angles which are unnecessary, yet being sure to cover every tile within a certain radius.

pathAngleIncremental = (Math.PI * 2) / (radiusInTiles * 8 );

With this formula, I can cast just enough rays to make sure I cover every tile within radius. Even with a very large view radius (much larger than I would actually need in the final product), I can complete the entire ray-casting process in 160 iterations... far fewer than the 50*360 figure you presented.

Furthermore, I only do line-segment vs. line-segment checks that are necessary. Depending on the angle of the ray, a lot of wall lines are culled from the equation; for example, if the angle is between 0-90 degrees, why would I need to check walls that can only be possibly visible if the ray is being case between 180-270 degrees?

Taking that a step further, if I pinpoint the exact wall tile the ray first intersects, that gives me a very good way to estimate which line segment I need to test against the ray.

I can see how this kind of thing would be insanely inefficient if I were doing it the way you described, for sure... that's why I spent so much time figuring out ways to get rid of unnecessary checks, and to replace high-cost calculations with those of lower cost.



I really don't know of any other solutions, honestly. I'm using a system not unlike the ray-casting systems used in early "3D" games (i.e. Wolfenstein 3D, et al), so I don't really understand why what I'm doing is so inefficient. If you can point out to me why my method is bad, then I'm all ears.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Ah well, my bad

ah okay, i didn't get that you had this culling algorithm to smarten down the amount of checks. in that case it doesnt look as bad actually. I was expecting you to brute force it.
I guess in that case you just need to fix it

_________________
Long pork is people!

wzl's burrow

By the way...


Was something I found almost completely by accident.

I was looking at how I wanted to cast rays, and figured 1-degree increments would be a real waste of clock cycles. At one point I thought, "Hmm... there are eight directions one can go in a grid like this, so..." And, of course, if your radius in tiles is 1, and multiply by 8 directions, you get 8 tiles total. If you take PI*2 (or 360 degrees) and divide it by eight, you have just enough angles to cover all eight tiles.

I got to thinking, so I fired up Paint.NET, and copied into it one of my maps. Then I drew a line (capped with an arrowhead, of course) on a new layer from the center tile, out to a radius of two tiles. I used a calculator to divide 360 by 2 * 8, which gave me 22.5. So, I made a duplicate layer of the arrow, rotated the new layer by 22.5 degrees, and repeated duplicating/rotating until I covered 1/4 of the map.

The results were just as I had expected, so I tried a slightly more extreme example (with a radius of 10 tiles). 360 / 10 * 8 = 4.5 degrees. I drew an arrow from the center tile, ten-tiles long, then repeated the layer duplication/rotation process (this time with each arrow rotated at 4.5-degree increments), and the results, again, seemed to be dead-on.

So, I decided I had found myself a winner in this case.

But yes; now I just have to figure out what I did elsewhere to break my function so badly.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

To be honest, i don't quite understand your concept. RadiusInTiles?

_________________
Long pork is people!

wzl's burrow

Well, let's say your screen/viewport holds a total of 11 tiles on its widest axis (i.e. the X-axis is wider on landscape view (which is standard for monitors/TVs); the Y-axis is wider on portrait view (a tablet held vertically, for example)). So, if you are in the center of the screen, you would have five tiles on either side of you (assuming the tile you are standing on is in the dead-center of the viewport). You would want a radiusInTiles value of at least 5 -- this would ensure you at least cover all the tiles in view that are parallel to your player's location (but maybe not all the tiles that are at more of an angle).

So, radiusInTiles is just the radius of a circle, measured in tile-space (as opposed to pixel-space).

To make sure your rays (or any other traversal technique that goes along angular planes) leave no tile uncovered, yet remove any unnecessary angular increments, you could do the following:

pathAngleIncremental = (Math.PI * 2) / ( 5 * 8 ); // <- Stupid friggin' smiley gets the 8 and the ) every time...

I will post some images of my experimentation regarding this a little later -- but it is a good way to make sure you don't miss any tiles when you start from a center tile and want to scan all the tiles surrounding it in a circular pattern.

Of course, you can replace radiusInTiles with whatever measurement you want (a tile in my case is 64px), depending on what you want to use it for. I suspect it would work best in contexts for which a high level of granularity is necessary.

---

By the way, I finally pinpointed the "other" problems I was having with my code outside of the line segment intersection testing, but haven't yet had a chance to fit the FOV function back into the equation, yet. Hopefully soon I will be able to show some nice screen shots of the FOV stuff at work.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

use [ code ]

Okay i got it. Looking forward to screens

_________________
Long pork is people!

wzl's burrow

Ah, phooey.

Well, here's the mockup I made of the formula in action anyway:

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."