tag:blogger.com,1999:blog-2403477577476951601.post2947610551574207206..comments2017-08-08T12:36:38.011-07:00Comments on PlayTechs: Programming for fun: Raytracing on a gridJames McNeillhttp://www.blogger.com/profile/08901649215141005959noreply@blogger.comBlogger48125tag:blogger.com,1999:blog-2403477577476951601.post-52896055688442170932017-01-07T18:23:32.930-08:002017-01-07T18:23:32.930-08:00Hey,
Thanks for this tutorial that was really hel...Hey,<br /><br />Thanks for this tutorial that was really helpfull. I adapted your algorithm in JavaScript to create a 2D grid games line of sight simulation and it works like a charm. Thanks also to Duke for your contribution, I've tried to do the same but I forgot the n-- statement !Raphaël Thttps://www.blogger.com/profile/15489537107518161805noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-64757481490058965492017-01-07T18:20:00.708-08:002017-01-07T18:20:00.708-08:00This comment has been removed by the author.Raphaël Thttps://www.blogger.com/profile/15489537107518161805noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-16089093825579652222016-08-09T20:53:21.939-07:002016-08-09T20:53:21.939-07:00No, no limitations on the use of the code. Glad it...No, no limitations on the use of the code. Glad it was useful!James McNeillhttps://www.blogger.com/profile/08901649215141005959noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-15914014027847861912016-08-08T07:05:38.788-07:002016-08-08T07:05:38.788-07:00Very useful example code. Thank your for that. Imp...Very useful example code. Thank your for that. <i>Important question near the end.</i><br /><br />I've adapted the code for a project where I need to accumulate values that correspond to the cells in a grid, accompanied by the path length in each of those cells.<br /><br />As a usage example for such code consider a weather map with a grid that has one value indicating the thickness of the snow cover for each cell. How much snow must be displaced to clear a (one meter wide) path from A to B?<br /><br />This took a little extra code to correctly compute the path length to the first grid boundary and then to each subsequent grid line boundary and - at the end - to the end point.<br /><br /><b>Question</b>. Are there any limitations on the use of your example code?<br /><br />If you like, I can make my Java code available. It is rather large to post here (319 lines, including demo and test code).Buttoniushttps://www.blogger.com/profile/08152161867337653227noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-85681835395936185612016-01-20T12:26:04.546-08:002016-01-20T12:26:04.546-08:00wow, great and simple logic, thank u so much!wow, great and simple logic, thank u so much!Bhanu Chanderhttps://www.blogger.com/profile/08453570317960124174noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-53820604333510348762013-12-20T06:54:34.806-08:002013-12-20T06:54:34.806-08:00Can you give an example set of inputs that would i...Can you give an example set of inputs that would illustrate the problem?James McNeillhttps://www.blogger.com/profile/08901649215141005959noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-82221488450298443842013-12-10T18:01:20.522-08:002013-12-10T18:01:20.522-08:00Hmm, using the second of the three sets of code, I...Hmm, using the second of the three sets of code, I am finding it to be, sometimes off by an entire row of tiles that the line is actually over.Josh Verrallhttps://www.blogger.com/profile/13758189710099925261noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-45739721434437838292012-12-02T19:25:17.800-08:002012-12-02T19:25:17.800-08:00honeyspider,
I took a look at your code on github...honeyspider,<br /><br />I took a look at your code on github. One way to do it might be to get rid of your rays[] array and write directly to lineOfSight[] instead, stopping the ray-tracing loop when you hit a 1 in wallsGFX[].<br /><br />If you're implementing line of sight, though, you might take a look at my article on that; it has a fairly simple recursive solution that avoids the aliasing problems you'll get with the ray-tracing approach:<br /><br />http://playtechs.blogspot.com/2007/03/2d-portal-visibility-part-1.html<br />http://playtechs.blogspot.com/2007/03/2d-portal-visibility-part-2.html<br /><br />Good luck!James McNeillhttps://www.blogger.com/profile/08901649215141005959noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-6617937456621267102012-12-02T18:24:27.963-08:002012-12-02T18:24:27.963-08:00Please give me a little push...
I have implement...Please give me a little push...<br /> <br />I have implemented the algorithm, but I need it to determine where my 'for of war' needs to be.<br /> <br />https://gist.github.com/4192017<br /> <br />FYI, wallsGFX[][] contains the wall data. If wallsGFX■[y] == 0, you can see through it.<br /> <br />rays[][] contains the current ray, and it is re-initialised to 0 at the start of each iteration of the loop.<br /> <br />lineOfSight[][] is where I want to store a '1' for tiles that can be seen, and a '0' for tiles that cannot.<br /> <br />How would you go about transferring this information?<br /> <br />Have I been clear?<br /> <br />I will try to post a little example<br /> <br />wallsGFX[][]<br /> <br />0 0 0 0 0 0 0 0<br />0 0 0 0 0 0 0 0<br />0 0 0 0 0 0 0 0<br />0 0 1 1 1 1 0 0<br />0 0 0 0 0 0 0 0<br />0 0 0 0 0 0 0 0<br />0 0 0 0 0 0 0 0<br /><br />rays[][]<br /><br />0 0 0 1 0 0 0 0<br />0 0 0 1 0 0 0 0<br />0 0 0 1 0 0 0 0<br />0 0 0 0 1 0 0 0<br />0 0 0 0 1 0 0 0<br />0 0 0 0 1 0 0 0<br />0 0 0 0 0 1 0 0<br /> <br />what lineOfSight[][] should show after this one iteration<br /> <br />0 0 0 1 0 0 0 0<br />0 0 0 1 0 0 0 0<br />0 0 0 1 0 0 0 0<br />0 0 0 0 1 0 0 0<br />0 0 0 0 0 0 0 0<br />0 0 0 0 0 0 0 0<br />0 0 0 0 0 0 0 0honeyspiderhttps://www.blogger.com/profile/01038701239136140708noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-55554705015820838132012-11-17T16:16:46.998-08:002012-11-17T16:16:46.998-08:00I was referring to the t value in the case where v...I was referring to the t value in the case where visit() caused a break and the line was only partially travelled.<br /><br />Either way, there was a mistake in my t_next comparisons when extended to 3 dimensions that caused the problem to appear (comparing infinities) when the small line segment crossed at least 2 cube boundaries.<br /><br />Thanks for the code.ghidoraxhttps://www.blogger.com/profile/17547816816323954140noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-8610289057918782882012-11-16T02:59:52.481-08:002012-11-16T02:59:52.481-08:00Looking at that first example I'm not sure why...Looking at that first example I'm not sure why I even have the variable t; it isn't used. Nevertheless, the value of t when visit() is called represents the fraction of the line segment traversed prior to entry into the square being visited.<br /><br />After all the squares have been visited you'd expect all of the line segment to have been traversed, right? Which would correspond to t=1. What I'm saying is I don't think it's meaningful to look at t after the loop has finished. In this case, as you point out, it represents the value of t when the line (not the line segment) exits the last visited square, which will generally be greater than one, not just when dx and dy are less than one.James McNeillhttps://www.blogger.com/profile/08901649215141005959noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-91773540975092685612012-11-16T02:23:41.975-08:002012-11-16T02:23:41.975-08:00In the first code example, if both dx and dy are &...In the first code example, if both dx and dy are <1.0, the final t value is outside of the range [0,1] and not suitable for calculating the length of the line travelled. dt_dx and dt_dy are very large in this case due to the 1.0/dx calculation, and the final t value will be either 0.0 (if visit() breaks on the first iteration) or at least at large as min(dt_dx, dt_dy).<br /><br />Do you have any suggestions for computing the fraction of the line travelled when dx and dy are <1.0?ghidoraxhttps://www.blogger.com/profile/17547816816323954140noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-25635784133372712492012-07-13T06:42:59.528-07:002012-07-13T06:42:59.528-07:00Cheers!
I've used a 3D variant of the first t...Cheers!<br /><br />I've used a 3D variant of the first technique in a modified version of the JBullet physics engine to support voxel worlds. The voxels are handled as a special shape that takes advantage of the grid nature of the world.Deus Immortiushttps://www.blogger.com/profile/13538900426743367896noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-26907025704414845412012-07-06T07:45:09.627-07:002012-07-06T07:45:09.627-07:00The code snippets are free to use as you see fit a...The code snippets are free to use as you see fit and no attribution is necessary; I hadn't thought as far as a license. I developed and wrote them myself (the ones in the article, at least) so they shouldn't be encumbered by anyone else's IP. I'm glad it's useful!James McNeillhttps://www.blogger.com/profile/08901649215141005959noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-24475124334482287342012-07-06T04:25:40.520-07:002012-07-06T04:25:40.520-07:00I have implemented a similar algorithm in the past...I have implemented a similar algorithm in the past, but your approach is much nicer - handles the corner cases very cleanly. Thank you for sharing.<br /><br />Are your code snippets on this blog under any particular license or condition of use?Deus Immortiushttps://www.blogger.com/profile/13538900426743367896noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-59403521928601904292012-04-14T04:01:05.004-07:002012-04-14T04:01:05.004-07:00Think I got it cracked - I just need to re-introdu...Think I got it cracked - I just need to re-introduce the t variable into the code.con20orhttps://www.blogger.com/profile/04849244070658963669noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-34257713580464282172012-04-04T07:32:09.340-07:002012-04-04T07:32:09.340-07:00Hi James
This is a great piece of code - just wh...Hi James <br /><br />This is a great piece of code - just what i was looking for.<br /><br />I'm trying to alter it slightly, so it will operate with rectangular grids rather than 1x1 squares but I am not having any luck.<br /><br />I know the widths and lengths of the grid rectangles, so i can edit the x_inc and y_inc accordingly - but im not sure how to change it so the algorithm knows how to calculate the error value correctly.<br /><br />This piece;<br /><br />error = (floor(x0) + 1 - x0) * dy;<br /><br />I'm using the first simplified one for 2D space. <br /><br />Any suggestions?con20orhttps://www.blogger.com/profile/04849244070658963669noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-15291321335600042182011-11-21T00:46:38.866-08:002011-11-21T00:46:38.866-08:00This article really helped me! I have been searchi...This article really helped me! I have been searching for days for a similar article. I am using this in a 3-dimensional voxel space and it works great.<br /><br />Thanks again!Sirius the Great Danehttps://www.blogger.com/profile/06526408503139922965noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-18529120517498352432011-11-07T13:52:07.944-08:002011-11-07T13:52:07.944-08:00This is my solution. I'm converting tiles to 3...This is my solution. I'm converting tiles to 3X3 and mapping start and target tiles on this grid, checking for tiles intersected by the ray using your modified Bresenham algorithm, and checking only the center square of each 3X3 grid that is intersected for an obstruction to the ray. This works nicely in this particular game so that the result meets the expectation from the player's perspective, as the game graphic for a Peak (mountain) is visually a cone-shaped object in the middle of the tile. Thanks a million for your blog posts, all of your blogs are EXTREMELY helpful and useful, especially for a rookie.<br /><br />// this is a 2D line of sight check based on Bresenham algorithm interpretation by James McNeill<br />// with a twist because the Peak graphic in Civ4 does not fill the entire tile and<br />// it looks counterintuitive to the player to not be able to shoot through the corner of a Peak tile<br />// we are going to expand the tiles x3 onto a virtual grid so that each tile is now 3X3 or 9 tiles<br />// the firing unit peak and target always occupy the center virtual tile in the 9 virtual tiles<br />// we will then check only the center of these 9 virtual tiles for a Peak obstacle<br />// so that we can shoot past peaks but not over or through them and we meet player expectations<br />bool CvPlot::checkForPeak(int startX, int startY, int targetX, int targetY) const // ChazMod Ranged Fire<br />{<br /> // init init<br /> CvPlot* pCheckPlot;<br /> int vstartX;<br /> int vstartY;<br /> int vtargetX;<br /> int vtargetY;<br /> int testX = 0;<br /> int testY = 0;<br /> int vobsX;<br /> int vobsY;<br /> int obsX;<br /> int obsY;<br /> <br /> // convert startXY and targetXY to place them on a virtual grid<br /> if (startX <= targetX)<br /> {<br /> vstartX = 1;<br /> vtargetX = (((targetX - startX)*3)+vstartX);<br /> }<br /> else<br /> {<br /> vtargetX = 1;<br /> vstartX = (((startX - targetX)*3)+vtargetX);<br /> }<br /><br /><br /> if (startY <= targetY)<br /> {<br /> vstartY = 1;<br /> vtargetY = (((targetY - startY)*3)+vstartY);<br /> }<br /> else<br /> {<br /> vtargetY = 1;<br /> vstartY = (((startY - targetY)*3)+vtargetY);<br /> }<br /><br /> //init based on virtual grid<br /> int iDDX = abs(vtargetX - vstartX);<br /> int iDDY = abs(vtargetY - vstartY);<br /> int iX = vstartX;<br /> int iY = vstartY;<br /> int iN = 1 + iDDX + iDDY;<br /> int iX_inc = (vtargetX > vstartX) ? 1 : -1;<br /> int iY_inc = (vtargetY > vstartY) ? 1 : -1;<br /> int error = iDDX - iDDY;<br /> iDDX *= 2;<br /> iDDY *= 2;<br /> <br /> // now we have vstartXY and vtargetXY on an expanded virtual grid and can check for obstacles<br /> for (; iN > 0; --iN)<br /> {<br /> // note that we are only checking the center virtual tile in each 3X3 grid for an obstacle<br /> if (iX > vstartX)<br /> {<br /> if (((iX - vstartX) % 3) == 0)<br /> {<br /> testX = 1;<br /> }<br /> }<br /> else if (iX < vstartX)<br /> {<br /> if (((vstartX - iX) % 3) == 0)<br /> {<br /> testX = 1;<br /> }<br /> }<br /> else<br /> {<br /> testX = 1;<br /> }<br /><br /> if (iY > vstartY)<br /> {<br /> if (((iY - vstartY) % 3) == 0)<br /> {<br /> testY = 1;<br /> }<br /> }<br /> else if (iY < vstartY)<br /> {<br /> if (((vstartY - iY) % 3)== 0)<br /> {<br /> testY = 1;<br /> }<br /> }<br /> else<br /> {<br /> testY = 1;<br /> }<br /><br /> if (testX == 1 && testY == 1)<br /> {<br /> // convert the check tile from virtualXY to gameXY so that we can check isPeak<br /> vobsX = iX;<br /> vobsY = iY;<br /><br /> if (vobsX > vstartX)<br /> {<br /> obsX = (startX + ((vobsX - vstartX)/3));<br /> }<br /> else if (vstartX > vobsX)<br /> {<br /> obsX = (startX - ((vstartX - vobsX)/3));<br /> }<br /> else<br /> {<br /> obsX = startX;<br /> }<br /><br /> if (vobsY > vstartY)<br /> {<br /> obsY = (startY + ((vobsY - vstartY)/3));<br /> }<br /> else if (vstartY > vobsY)<br /> {<br /> obsY = (startY - ((vstartY - vobsY)/3));<br /> }<br /> else<br /> {<br /> obsY = startY;<br /> }<br /> <br /> pCheckPlot = GC.getMapINLINE().plotINLINE(obsX, obsY);<br /> <br /> if (pCheckPlot->isPeak())<br /> {<br /> return true;<br /> }<br /> }<br /><br /> testX = 0;<br /> testY = 0;<br /><br /> if (error > 0)<br /> {<br /> iX += iX_inc;<br /> error -= iDDY;<br /> }<br /> else<br /> {<br /> iY += iY_inc;<br /> error += iDDX;<br /> }<br /> }<br /><br /> return false;<br />}Chazconhttps://www.blogger.com/profile/17173105451030298897noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-20518849027622304152011-11-04T09:13:37.882-07:002011-11-04T09:13:37.882-07:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/17173105451030298897noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-28571511708966708902011-11-04T06:21:14.379-07:002011-11-04T06:21:14.379-07:00Having some sort of higher-resolution interior for...Having some sort of higher-resolution interior for squares in terms of how they block visibility seems totally reasonable. I did something like that for my visibility computation in the previous two posts:<br /><br />http://playtechs.blogspot.com/2007/03/2d-portal-visibility-part-1.html<br /><br />That's more of an area approach, though. If you just want to cast a single ray from one spot to another on the map and see if/where it is obstructed, another approach might be to build a small 2D BSP for each tile type that represents its solid and open sub-regions. Then, as you run the raytrace across the grid (via the method in this post), look up each interesected tile's BSP and clip the line against that to see if it's obstructed by something inside the tile.James McNeillhttps://www.blogger.com/profile/08901649215141005959noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-82227210084215059332011-11-03T11:22:53.838-07:002011-11-03T11:22:53.838-07:00EDIT: well no html tags in Blogger comments? Ah we...EDIT: well no html tags in Blogger comments? Ah well my graphs are squished but I'll post anyway:<br /><br /><br /><br />I see this post is from 2007 but I just stumbled across it. Saved me a ton of work and pushed my knowledge along a bit as well...<br /><br />Algorithm works great, but there is a further issue with the particular game I am modding. It is square (tile) based game and the obstructions to LOS use a graphic that does not fill the entire tile, it is a round object that graphically does not fill the entire tile like a square building the same size of the tile would. The code is correctly blocking LOS but intuitively (from the player's perspective) the LOS should be clear. In layman's terms the player's unit should be able to see (shoot) across the corners of a blocked tile but not across the center.<br /><br />I need to mod this code to break up each game tile into 9 virtual tiles, only the center one containing either the firing unit, obstruction or target.<br /><br />In this example the entire (virtual) 3X3 grid represents ONE game tile where XX is either firing unit, obstruction or target.<br /><br />!----!----!----!<br />! ! ! !<br />!----!----!----!<br />! ! XX ! !<br />!----!----!----!<br />! ! ! !<br />!----!----!----!<br /><br /><br />Now in this second example EACH SQUARE represents a game tile. In each case, the firing unit needs to be able to see (shoot) at it's target. using the current algrithm all of these LOS would be blocked. I need to be able to calculate if a unit can see (fire) through the *corners* of a game tile.<br /><br />UU = firing unit, XX = obstruction, TT = target tile<br /><br />!----!----!----!----!----!----!<br />! XX ! TT ! ! ! XX ! TT !<br />!----!----!----!----!----!----!<br />! UU ! ! ! UU ! ! !<br />!----!----!----!----!----!----!<br />! ! ! ! ! ! !<br />!----!----!----!----!----!----!<br />! ! ! ! ! XX ! TT !<br />!----!----!----!----!----!----!<br />! ! ! UU ! ! ! !<br />!----!----!----!----!----!----!<br />! ! ! ! ! ! !<br />!----!----!----!----!----!----!<br /><br /><br />Hope this all makes sense, I am currently working on a solution. Will post here when complete (barring brain explosion). Any input appreciated.<br /><br />-cUnknownhttps://www.blogger.com/profile/17173105451030298897noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-71300305576053178882011-11-03T11:12:21.690-07:002011-11-03T11:12:21.690-07:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/17173105451030298897noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-8574149313171432122011-11-03T11:08:47.297-07:002011-11-03T11:08:47.297-07:00This comment has been removed by the author.Chazconhttps://www.blogger.com/profile/17173105451030298897noreply@blogger.comtag:blogger.com,1999:blog-2403477577476951601.post-17829470985170076052011-07-19T05:36:57.446-07:002011-07-19T05:36:57.446-07:00Awesome, thanks man!
Works perfectly.
I wasted hou...Awesome, thanks man!<br />Works perfectly.<br />I wasted hours on a much more complicated algorithm. arghhhhhQhttps://www.blogger.com/profile/01722748465063256133noreply@blogger.com