Simulating vision - calculating line of sight - Artificial Intelligence

Argus2 · 2007-10-31T14:47:55

I recently figured out a fast way to calculate areas in line of sight from any given point in a game world, so I thought I'd write up an article describing it. It really needs images, so I put it up on a free host (Geocities unfortunately, apologies for the ads). You can view it here . Let me know what you think - hopefully some people will find it useful.

Argus2

Author

140

October 29, 2007 06:13 AM

Quote: Well, it really depends on the granularity of the grid, the sparsity of the positions you're checking, and the distance from the origin. When I did something similar, it became clear that repeated ray-casting was far more efficient - although several areas near the viewpoint were checked 2 or 3 times each, the proportion of areas further out that didn't need to be examined at all was 80%-90%, and they were more numerous too.

Besides, there's usually nothing to stop you caching/memoising results for these inner nodes, meaning you can almost get the best of both approaches.

There would be very very few instances where repeated ray-casting would be more efficient at running through an entire field of view. If you're only looking at particular objects, sure, quite possible. Areas that are obscured are ignored with this method.

Caching/memorising inner node results increases space complexity, whereas it's implicit in the way nodes are generated here.

Kylotan

10,513

October 29, 2007 08:52 AM

Sure. The question then becomes whether you actually need to know visibility to everywhere, or just to points of interest. I never really saw much use in the former.

IADaveMark

3,839

October 29, 2007 12:40 PM

I agree that this sort of approach has some interesting uses - but is definately not something that is applicable for all situations. One constraint that can be applied to speed things up is the field of view at the moment. Which way is the agent facing? Apply a width and off you go.

The other interesting use for this is not for an agent seeing something but allowing an agent to determine if IT can be seen by the player. That way, we aren't running the algorithm from the point of view of 100 enemies to see if they can see YOU, but running it from your point of view and mapping the results. That way, the 100 agents benefit by calculating where they can and cannot go and remain hidden. It would take into account all obstacles in the environment - even, depending on how often you update it, semi-dynamic obstacles as well. The AI agents can now use it for determining cover positions, etc. It's no longer a function of "can you see me now?", "how about now?", "how about now?" It is now a matter of "where are all the places that I could be seen from where the player is?" It would be interesting, and very necessary, to test the speed of this sort of approach.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

ID Merlin

119

October 30, 2007 08:27 PM

I worked on a quick-and-dirty implementation of this algorithm where instead of visibility true-false the flood-fill attempts to find the height of the LOS. (The map array has heights of the things in the square.) My idea is to use it to modify the attractiveness of hexes for the AI to consider moving to. The result is less than satisfactory, so far. If anyone has any ideas, I'd like to see this work.

<html><head><title>Test &#106avascript Breadth-first Flood-fill</title><script language='&#106avascript'&gt;<br><br>var map = [[1,1,1,2,1,1,1,1,1,1,1],<br>           [1,1,1,2,1,1,1,1,1,1,1],<br>           [1,1,2,2,1,1,1,1,1,1,1],<br>           [1,1,2,2,1,1,1,2,1,1,1],<br>           [1,1,1,1,1,1,1,3,1,1,1],<br>           [1,1,1,1,1,1,1,2,1,1,1],<br>           [1,1,1,1,1,1,1,1,1,1,1],<br>           [1,1,1,1,2,1,2,1,1,1,1],<br>           [1,1,1,1,1,1,1,1,1,1,1],<br>           [1,1,1,1,1,1,1,1,1,1,1],<br>           [1,1,1,1,1,1,1,1,1,1,1]]<br><br>var out = new Array();<br><br>for (y = 0; y &lt;= 10; y++) {<br>  out[y] = new Array();<br>  for (x = 0; x &lt;= 10; x++) {<br>    out[y][x] = new Array();<br>    out[y][x][0] = 0;    // Visited flag<br>    out[y][x][1] = 0;    // Height<br>    out[y][x][2] = 0;    // Attack strength<br>  }<br>}<br><br>function format(num) {<br>    var fmt = '     ' + num.toFixed(1);<br>    return '|' + fmt.substr(fmt.length-4, 4);<br>}<br><br>function doit() {<br><br>  var stack = new Array();<br><br>  function get_hgt(a) {<br>    var x = a[0];<br>    var y = a[1];<br>    var dx = a[2];<br>    var dy = a[3];<br>    var str = a[4];<br>    var rng = a[5];<br>    var ax = Math.abs(dx);<br>    var ay = Math.abs(dy);<br>    var az = ax + ay;<br><br>    var f1 = ay / ax;<br>    var f2 = ax / ay;<br>    var h = out[y][x][1];<br>    if (dy &gt; 0) {<br>      if (dx &gt; 0) {<br>        if (ax &gt; ay) {<br>          h = out[y][x-1][1] * (1 - f1) + out[y-1][x-1][1] * f1;<br>        } else if (ax &lt; ay) {<br>          h = out[y-1][x][1] * (1 - f2) + out[y-1][x-1][1] * f2;<br>        } else {<br>          h = out[y-1][x-1][1];<br>        }<br>      } else if (dx &lt; 0) {<br>        if (ax &gt; ay) {<br>          h = out[y][x+1][1] * (1 - f1) + out[y-1][x+1][1] * f1;<br>        } else if (ax &lt; ay) {<br>          h = out[y-1][x][1] * (1 - f2) + out[y-1][x+1][1] * f2;<br>        } else {<br>          h = out[y-1][x+1][1];<br>        }<br>      } else { // dx == 0<br>        h = out[y-1][x][1];<br>      }<br>    } else if (dy &lt; 0) {<br>      if (dx &gt; 0) {<br>        if (ax &gt; ay) {<br>          h = out[y][x-1][1] * (1 - f1) + out[y+1][x-1][1] * f1;<br>        } else if (ax &lt; ay) {<br>          h = out[y+1][x][1] * (1 - f2) + out[y+1][x-1][1] * f2;<br>        } else {<br>          h = out[y+1][x-1][1];<br>        }<br>      } else if (dx &lt; 0) {<br>        if (ax &gt; ay) {<br>          h = out[y][x+1][1] * (1 - f1) + out[y+1][x+1][1] * f1;<br>        } else if (ax &lt; ay) {<br>          h = out[y+1][x][1] * (1 - f2) + out[y+1][x+1][1] * f2;<br>        } else {<br>          h = out[y+1][x+1][1];<br>        }<br>      } else { // dx == 0<br>        h = out[y+1][x][1];<br>      }<br>    } else { // dy == 0<br>      if (dx &gt; 0) {<br>        h = out[y][x-1][1];<br>      } else if (dx &lt; 0) {<br>        h = out[y][x+1][1];<br>      } else { // dx == 0 -- this cant ever happen<br>        h = out[y][x][1];<br>      }<br>    }<br><br>    return h;<br>  }<br><br>  function flood_fill() {<br><br>    while (stack.length) {<br><br>      var a = stack.shift();<br>      var x = a[0];<br>      var y = a[1];<br>      var dx = a[2];<br>      var dy = a[3];<br>      var str = a[4];<br>      var rng = a[5];<br>      var dist = Math.sqrt(dx*dx + dy*dy);<br><br>      if (out[y][x][0] == 0) {<br>        out[y][x][0] = 1;<br>        out[y][x][1] = Math.max(get_hgt(a), map[y][x]);<br>        if (dist &lt;= rng && map[y][x] + 0.25 &gt;= out[y][x][1])<br>            out[y][x][2] += str * (rng-dist*0.75) / rng;<br>      }<br><br>      if (dist &lt; rng) {<br>        if (x &lt; 10) {<br>          if (out[y][x+1][0] == 0) {<br>            var b = new Array()<br>            for (i=0;i&lt;a.length;i++) b<span style="font-weight:bold;"> = a<span style="font-weight:bold;">;<br>            b[0]++;<br>            b[2]++;<br>            stack.push(b);<br>          }<br>        }<br>        if (x &gt; 0) {<br>          if (out[y][x-1][0] == 0) {<br>            var b = new Array()<br>            for (i=0;i&lt;a.length;i++) b<span style="font-weight:bold;"> = a<span style="font-weight:bold;">;<br>            b[0]--;<br>            b[2]--;<br>            stack.push(b);<br>          }<br>        }<br>        if (y &lt; 10) {<br>          if (out[y+1][x][0] == 0) {<br>            var b = new Array()<br>            for (i=0;i&lt;a.length;i++) b<span style="font-weight:bold;"> = a<span style="font-weight:bold;">;<br>            b[1]++;<br>            b[3]++;<br>            stack.push(b);<br>          }<br>        }<br>        if (y &gt; 0) {<br>          if (out[y-1][x][0] == 0) {<br>            var b = new Array()<br>            for (i=0;i&lt;a.length;i++) b<span style="font-weight:bold;"> = a<span style="font-weight:bold;">;<br>            b[1]--;<br>            b[3]--;<br>            stack.push(b);<br>          }<br>        }<br>      }<br>    }<br>  }<br><br>  for (y = 0; y &lt;= 10; y++)<br>    for (x = 0; x &lt;= 10; x++)<br>      out[y][x][0] = 0;<br><br>  // sx,sy, dx,dy, str,rng<br>  var a = [4,5,0,0,5,4];<br>  stack.push(a);<br><br>  flood_fill();<br><br>  for (y = 0; y &lt;= 10; y++)<br>    for (x = 0; x &lt;= 10; x++)<br>      out[y][x][0] = 0;<br><br>  // sx,sy, dx,dy, str,rng<br>  var b = [6,5,0,0,4,3];<br>  stack.push(b);<br><br>  flood_fill();<br><br>  var dump = '&lt;pre&gt;&lt;u&gt;        0    1    2    3    4    5    6    7    8    9   10&lt;/u&gt;\n';<br>  for (y = 0; y &lt;= 10; y++) {<br>    dump += '   ' + (y &lt; 10 ? ' ' : '''') + y;<br>    for (x = 0; x &lt;= 10; x++) {<br>      if (y == 5 && (x == 4 || x == 6))<br>        dump += '&lt;font color="red"&gt;'+format(out[y][x][1])+'&lt;/font&gt;';<br>      else<br>        dump += format(out[y][x][1]);<br>    }<br>    dump += '\n&lt;u&gt;     ';<br>    for (x = 0; x &lt;= 10; x++) {<br>      if (y == 5 && (x == 4 || x == 6))<br>        dump += '&lt;font color="red"&gt;'+format(out[y][x][2])+'&lt;/font&gt;';<br>      else<br>        dump += format(out[y][x][2]);<br>    }<br>    dump += '&lt;/u&gt;\n';<br>  }<br>  dump += '&lt;/pre&gt;';<br><br>  var output = document.getElementById('output');<br>  output.innerHTML = dump;<br>}<br><br>&lt;/script&gt;<br>&lt;/head&gt;<br>&lt;body &#111;nload='doit();'&gt;<br>&lt;div id='output'&gt;&lt;/div&gt;<br>&lt;/body&gt;<br>&lt;/html&gt;<br></pre><br><br><!--EDIT--><span class=editedby><!--/EDIT-->[Edited by - ID Merlin on October 31, 2007 2:27:44 PM]<!--EDIT--></span><!--/EDIT-->

Aragon Online

Koobs

148

October 30, 2007 09:56 PM

This reminds me of a voxel renderer. Are you familiar with Ken Silverman's voxel rendering algorithm?

Thaumaturge

3,902

October 30, 2007 10:18 PM

ID Merlin, I don't seem to be managing to get your HTML and &#106avascript code to work. I've tried it under both Firefox and (an admittedly probably rather old version of) Internet Explorer, even trying a few minor modifications (giving the div a width, height and background colour, in order to be confident that it was displaying, for example). Of course, I may be doing something wrong - neither HTML nor &#106avascript is really my strong point, I'm afraid. Have you any suggestions, please? I'm interested to see what you've managed. ^_^

MWAHAHAHAHAHAHA!!!

My Twitter Account: @EbornIan

pokerpuggy

122

October 31, 2007 05:12 AM

I think this is potentially very interesting. I suspect that a very effective way of improving AI is to give NPCs a much richer perception of their environment, which is what this would do. Is anyone aware of this kind of 'full visual perception' idea being used in a game? I have come across a couple of academic papers on simulating vision for NPCs, but no suggestion that it's found its way into actual titles....

can you give some educated guess as to how this would perform in 3D? I mean in particular how it would scale with the granularity of the grid....

thanks.

ID Merlin

119

October 31, 2007 08:52 AM

Quote: Original post by Thaumaturge
ID Merlin, I don't seem to be managing to get your HTML and &#106avascript code to work. I've tried it under both Firefox and (an admittedly probably rather old version of) Internet Explorer, even trying a few minor modifications (giving the div a width, height and background colour, in order to be confident that it was displaying, for example).

Of course, I may be doing something wrong - neither HTML nor &#106avascript is really my strong point, I'm afraid. Have you any suggestions, please? I'm interested to see what you've managed. ^_^</td></tr></table></BLOCKQUOTE> This line: dump += ' ' + (y < 10 ? ' ' : '') + y + ''; For some reason the quote-quote after the colon is rendered as one single quote. It should be a two single quotes ('''').

Aragon Online

Argus2

Author

140

October 31, 2007 09:21 AM

Actually I found a few algorithms similar to this, though usually traversing nodes differently. They're used in roguelikes and other tile-based games.

I really like InnocuousFox's use for the field of vision.

Will have a closer look at the &#106avascript when I get a minute. It hurts my eyes though ;)

Ultimape

100

October 31, 2007 10:34 AM

i'd be neat to do one for the player, one for the ai unit, and where they collide, is a potential area the ai might move to, to avoid fire. something like this would give a very good basis for an a* weight graph. I could see this being very useful for a world with many many agents and objects.

Simulating vision - calculating line of sight

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Simulating vision - calculating line of sight

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines