Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes 		Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Java-Gaming.org > Game Development > Game Mechanics > Line of sight math
Pages: [1]
  Print  
  Line of sight math  (Read 1382 times)
0 Members and 2 Guests are viewing this topic.
Offline Suds

JGO n00b
*

Posts: 20


Lead Developer, DefeatThePurpose Entertainment
« on: 2011-11-13 23: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.
Twitter - Dungeon Wars (active development) - Almostman! (released)
Offline lhkbob

JGO Neuromancer
****

Posts: 1174
Medals: 35
« Reply #1 on: 2011-11-14 00: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.
Ferox - http://bitbucket.org/mludwig/ferox
Entreri - http://bitbucket.org/mludwig/entreri
Offline counterp

Full Member
**

Posts: 235
Medals: 11
« Reply #2 on: 2011-11-14 00: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
Games published by our own members! Go get 'em!
Offline moogie

JGO Strike Force
***

Posts: 775
Medals: 5


Java games rock!
« Reply #3 on: 2011-11-14 00: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.

so in your example

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;
}
Offline theagentd

JGO Wizard
****

Posts: 1392
Medals: 88
« Reply #4 on: 2011-11-14 05: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.
There is no god.
Offline Suds

JGO n00b
*

Posts: 20


Lead Developer, DefeatThePurpose Entertainment
« Reply #5 on: 2011-11-14 06: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.
Twitter - Dungeon Wars (active development) - Almostman! (released)
Offline cylab

JGO Kernel
*****

Posts: 1940
Medals: 27
« Reply #6 on: 2011-11-14 08:55:28 »
Quote from: Suds on 2011-11-14 06:25:26
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!
Offline moogie

JGO Strike Force
***

Posts: 775
Medals: 5


Java games rock!
« Reply #7 on: 2011-11-14 15:56:12 »
Quote from: Suds on 2011-11-14 06:25:26
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 Tongue 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<y-1;currY+=1.0f)
{
if (map[(int)x-1,(int)currY] == WALL_TYPE)
{
      // draw wall
      break out;
}

lastY=y;
}
Offline lesto

JGO n00b
*

Posts: 26
« Reply #8 on: 2011-11-27 13:18:14 »
you shoul cicle also for X, or aligned on y line will break your math
Pages: [1]
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.066 seconds with 19 queries.