Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (117)
games submitted by our members
Games in WIP (564)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Line of sight math  (Read 2824 times)
0 Members and 1 Guest are viewing this topic.
Offline Suds

Senior Newbie




Lead Developer, DefeatThePurpose Entertainment


« 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.

Offline 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.

Offline counterp

Senior Member


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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline moogie

JGO Knight


Medals: 12
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.

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
« 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.
Offline Suds

Senior Newbie




Lead Developer, DefeatThePurpose Entertainment


« 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.

Offline cylab

JGO Ninja


Medals: 49



« 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!
Offline moogie

JGO Knight


Medals: 12
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 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

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  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Grunnt (20 views)
2014-09-23 14:38:19

radar3301 (14 views)
2014-09-21 23:33:17

BurntPizza (31 views)
2014-09-21 02:42:18

BurntPizza (22 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (29 views)
2014-09-20 20:14:06

BurntPizza (33 views)
2014-09-19 03:14:18

Dwinin (48 views)
2014-09-12 09:08:26

Norakomi (75 views)
2014-09-10 13:57:51

TehJavaDev (108 views)
2014-09-10 06:39:09
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!