Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (780) Games in Android Showcase (233) games submitted by our members Games in WIP (857) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Line of sight math  (Read 9060 times) 0 Members and 1 Guest are viewing this topic.
Suds

Senior Newbie

 « Posted 2011-11-14 04:48:06 »

I've been staring at this problem for a few days now. I rigged up this graphic to help me visualise the issue:

(from the graph, we know that the line intersects [1, 1], [1, 2], [2, 2], [2, 3], ending in [3,3])

I want to step along the line to each grid space and check to see if the material of the grid space is solid. I feel like I already know the math involved, but I haven't been able to string it together yet. I'm using this to test line of sight and eliminate nodes after a path is found via my pathfinding algorithms - my agents cant see through a solid block, therefore they cant move through one, therefore the node is not eliminated from the path because it is required to navigate a corner.

So, I need an algorithm that will step along the line to each grid space that it intersects. Any ideas?

I've been thinking along the lines of gradients, using floor and ceiling to isolate / determine spaces, or simply stepping along the line's direction vector by a fixed amount.

lhkbob

JGO Knight

Medals: 32

 « Reply #1 - Posted 2011-11-14 05:48:23 »

It's late night for me so my math brain isn't very active.  I don't know if there is a better way to just check a grid position randomly, but if you want to march along the line, try looking into http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

It basically does what you need to, but in terms of finding pixels to render when drawing a line.  Of course it should be an easy modification to line of site in this case.

counterp

Senior Devvie

Medals: 11

 « Reply #2 - Posted 2011-11-14 05:48:43 »

I think this is what you want?

http://www.java-gaming.org/topics/line-logic/24593/msg/207684/view.html

There's a solution somewhere in that thread
moogie

JGO Ninja

Medals: 16
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #3 - Posted 2011-11-14 05:57:20 »

surely all you need to do is get the equation of the line and then step though one axis's ordinates? e.g.

the equation of the line is y = (3.5-1.45)/(3.4-0.7) * (x-0.7) + 1.45

and thus iterating x from 0.7 to 3.4 in steps of 1 should give you the co-ordinates to test in your map for intersections.

i.e.

 1  2  3  4  5  6  7  8  9  10 `float y;for (float x = 0.7 ; x<3.4;x+=1.0f){y= (3.5-1.45)/(3.4-0.7) * (x-0.7) + 1.45;if (map[(int)x,(int)y] == WALL_TYPE){      // draw wall      break;}`

Java4k RIP 2014
theagentd
 « Reply #4 - Posted 2011-11-14 10:10:47 »

The standard Bresenham's line algorithm is NOT applicable in this case. It would simply miss certain tiles. It can however be modified to connect he line properly and avoid this.

The idea is to instead of looping over tile centers (x = 0.5, 1.5, 2.5...) we loop over tile borders (0.0, 1.0, 2.0, 3.0). Start by checking the tile the unit is standing on. Then branch depending on if dx or dy is the biggest (to handle all cases instead of just to the right). In OP's case he'll also want to check for negative dx and dy, leading to 4 branches since he needs to check from the unit and out and can't swap the target with unit for handling cases where the target is to the left or over the unit. Then you do Bresenham's as usual but doing the collision check on tile borders instead. When the floating point delta variable exceeds 0.5 or gets under -0.5, you also do an additional collision test to avoid missing a tile.

Sorry, I know this explanation is complete crap, but give me a little time and I'll post code instead.

Myomyomyo.
Suds

Senior Newbie

 « Reply #5 - Posted 2011-11-14 11:25:26 »

Thanks for the responses. I made the post a couple of minutes before I had to leave for work.

Moogie: that method won't work (it was the first that I sketched on my piece of paper) because it can skip over grid spaces along the line.

counterp: I haven't read the thread yet, but thanks. That opening diagram looks very promising.

lhkbob: I'll read that too :-)

theagentdd: thanks, much appreciated - again. :-)

I think I have the solution in mind, I just need to sketch it out and code it to see if it works.

cylab

JGO Kernel

Medals: 188

 « Reply #6 - Posted 2011-11-14 13:55:28 »

Moogie: that method won't work (it was the first that I sketched on my piece of paper) because it can skip over grid spaces along the line.

counterp: I haven't read the thread yet, but thanks. That opening diagram looks very promising.

My implementation in the thread counterp posted, does as moogie suggests, but adds some special cases for the missed grid spaces. It works and should be faster than other approaches I can think of.

Start reading from here http://www.java-gaming.org/topics/line-logic/24593/msg/207942/view.html#msg207942, if you want some explanations.

Mathias - I Know What [you] Did Last Summer!
moogie

JGO Ninja

Medals: 16
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #7 - Posted 2011-11-14 20:56:12 »

Moogie: that method won't work (it was the first that I sketched on my piece of paper) because it can skip over grid spaces along the line.

yep, that was left as an exercise but all you need to do is record the last 'y' position and then iterate over all the y ordinates between the last 'y' and the current 'y'.

i.e. some thing similar to this.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17 `float y;float lastY = 1.45;out:for (float x = 0.7 +1.0f ; x<3.4;x+=1.0f){y= (3.5-1.45)/(3.4-0.7) * (x-0.7) + 1.45;for (float currY=lastY;currY

Java4k RIP 2014
lesto

Senior Newbie

 « Reply #8 - Posted 2011-11-27 18:18:14 »

you shoul cicle also for X, or aligned on y line will break your math
Pages: [1]
 ignore  |  Print

 hadezbladez (745 views) 2018-11-16 13:46:03 hadezbladez (386 views) 2018-11-16 13:41:33 hadezbladez (736 views) 2018-11-16 13:35:35 hadezbladez (194 views) 2018-11-16 13:32:03 EgonOlsen (2394 views) 2018-06-10 19:43:48 EgonOlsen (2557 views) 2018-06-10 19:43:44 EgonOlsen (1482 views) 2018-06-10 19:43:20 DesertCoockie (2145 views) 2018-05-13 18:23:11 nelsongames (1949 views) 2018-04-24 18:15:36 nelsongames (2629 views) 2018-04-24 18:14:32
 Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20Deployment and Packagingby philfrei2018-08-19 23:54:46
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org