[F8] Tile game LOS calculation that needs .. streamlining
I wrote a function ( posted below) that makes an array of squares along a line from one square on a grid to another. ALL squares the line crosses are in the array. It works, but it's slow.
I discovered the Bresenham algorithm, but it's not exactly the same as what I have. It might be that a version of it could work, but I haven't figured out how to use it to get the same results I get with the function I made. The difference being that the Bresenham algorithm makes a like only one square wide, where mine will make a wide path.. not sure how better to explain it.
Basically, the function goes along the longer of the slope's sides in increments that just crosses into a squares space (1% of a tilewidth), and then again just before it leaves a squares space. At each increment it checks the other slope's side coordinate. It adds the first set of coords to the array, and if the second set is different, it adds those too.
Personally, I'd do Bresenham's and just run it from two points and combine the results. It's so fast that it really does make good sense. Here is a little swf I put togeter years ago that shows LOS with Bresenham's algo: http://www.electrotank.com/junk/mike...enhamTest1.swf
As you can see that while Bresenhams isn't perfect, it is likely good enough for many games. If you used my example and then had it run the test from every tile the ball intersected and combined the results, you would get a more complete path.
The problem I have with running 2 Bresenham's algos is that I need to choose the points to run the second test from, and I can't think of a good reason why it should or shouldn't be any of the surrounding squares.
S=start point.
E=end point.
0=path of sight
#=walls
+++E
++#0
++0+
+S++
according to Bresenham's, the above LOS is ok. But intuitively it's not. If you look at the same situation with your .swf (which is cool, btw) they clearly look like they shouldn't see each other. I'm making a tactical kind of game, so I want the LOS to be intuitive.
If I add a second path to gather more info, from where do I take it. One option is from the square above the start, another is the square to the right.
But, going either way is biased.
+++E
++#+
+S++
++++
No sight
+++E
++#0
++0+
++S+
Sight.
I have a question about your .swf though, the blue line starts from the start coords of Bresenham's algo? cause I noticed that in reverse, it almost emulates what I want.
Actually, webgeeks demo says the opposite. But can you say why you'd want to use the algorithm 2 times? Why would you need more then one line to establish if there is a line of sight?
I think that link by kianis is the right way to do things. I don't understand why one would use a rasterization algorithm to compute gameplay line of sight. IMO, that ray should not be modeled as 1 tile wile and discretized onto your tile grid, it should be treated as infintesimally thin and solved out using real geometrical predicates.
I think that link by kianis is the right way to do things. I don't understand why one would use a rasterization algorithm to compute gameplay line of sight. IMO, that ray should not be modeled as 1 tile wile and discretized onto your tile grid, it should be treated as infintesimally thin and solved out using real geometrical predicates.
I'm going a bit offtopic here, but I don't think terminology as 'the right way' and 'should' are appropiate when problemsolving. In my opinion it depends on the situation. When thinking about how to program something I start thinking about the level of simulation I need. After all: am I making a game, or a simulation? And balance realism versus gameplay. Basicly I just tend to go with what 'feels' right and I can still get away with
When your game is in a tilebased world, I can understand that you'd use a tilebased line of sight. There already is abstraction which the player uses and is accustomed to, so why should it appear unnatural if the line of sight is any different?
My originally posted code does calculate it geometrically as a thin line. The problem is that when I run it say 150 times in a frame, it's a little slow. Bresenham's is much faster, but it's not really a line of sight calculation, it's drawing a line never more than 1 unit wide. So if I use that, it misses things that would otherwise obstruct line of sight. That's why I was discussing doing it 2 or 3 times. But then that would defeat the purpose of using it cause it's fast.
What I was really hoping is if someone could help me make my original code faster using coding tricks. Like, maybe I should shorten the variable names or something, does that matter for speed? Or maybe there is a way I can make several of my lines onto one. I don't know syntax very well. For instance, the other day I saw while (someVar -->0){ .. never seen that before. I assume it takes someVar down to 0 incrementally by 1? why wouldn't you use for(t =someVar;t >=0;t--){ ? Is the while version faster?
I'm assuming there is better code to do the same thing I made.
The result changes depending on which ball the line is originating from is. I think if you set up the result like you got, and then switched the balls, you'd get my result.
try this, on my computer when all tiles are empty, from one corner to the other doing 150 iterations i get 48-50ms time taken to calculate.
this is AS2, AS3 would probably divide that number by 40.
Code:
_quality = "LOW";
var tileW:Number = 10;
var tileH:Number = 10;
var gx:Number = int(Stage.width / tileW);
var gy:Number = int(Stage.height / tileH);
var tiles:Array = new Array();
var tileClip:MovieClip = this.createEmptyMovieClip("tilesClip", 0);
var losClip:MovieClip = this.createEmptyMovieClip("losClip", 1);
var debug:TextField = this.createTextField("debug", 2, 0, 0, 100, 20);
debug.selectable = false;
debug.background = true;
debug.autoSize = "left";
debug.text = "debug";
for(var tx:Number = 0; tx < gx; tx++){
tiles[tx] = new Array();
for(var ty:Number = 0; ty < gy; ty++){
var tile:Object = new Object();
var weight:Number = Math.random() < 0.2 ? -1 : 0;
tile.x = tx * tileW;
tile.y = ty * tileH;
tile.cx = tile.x + tileW * 0.5;
tile.cy = tile.y + tileH * 0.5;
tile.tx = tx;
tile.ty = ty;
tile.weight = weight;
tile.solid = weight == -1;
tiles[tx][ty] = tile;
if(tile.solid){
tileClip.beginFill(0x000000);
}
tileClip.lineStyle(1, 0xCCCCCC);
drawTile(tile, tileClip);
tileClip.endFill();
}
}
tileClip.cacheAsBitmap = true;
var start:Object = getMapTile(10, 10);
var los:Object = new Object();
function getMapTile(x:Number, y:Number):Object {
return tiles[x][y];
}
function getTile(x:Number, y:Number):Object {
var tx:Number = int(x / tileW)
var ty:Number = int(y / tileH);
return tiles[tx][ty];
}
function drawTile(tile:Object, clip:MovieClip):Void {
clip.moveTo(tile.x, tile.y);
clip.lineTo(tile.x + tileW, tile.y);
clip.lineTo(tile.x + tileW, tile.y + tileH);
clip.lineTo(tile.x, tile.y + tileH);
clip.lineTo(tile.x, tile.y);
}
function doLos(start:Object, targ:Object, tiles:Array, result:Object):Object {
result.success = false;
result.tile = start;
if(start == targ){
result.success = true;
return result;
}
if(start.solid){
return result;
}
var sx:Number = start.tx;
var sy:Number = start.ty;
var ex:Number = targ.tx;
var ey:Number = targ.ty;
var dx:Number = ex - sx;
var dy:Number = ey - sy;
var len:Number = Math.sqrt(dx * dx + dy * dy);
var d:Number = int(len << 1);
dx /= len;
dy /= len;
var dxm:Number = dx * dx;
var dym:Number = dy * dy;
var dex:Number = Math.sqrt(1 + dym / dxm);
var dey:Number = Math.sqrt(1 + dxm / dym);
var rx:Number = sx + .5;
var ry:Number = sy + .5;
var sdx:Number = 0;
var sdy:Number = 0;
var stx:Number = 0;
var sty:Number = 0;
if(dx < 0){
stx = -1;
sdx = (rx - sx) * dex;
}
else {
stx = 1;
sdx = (sx + 1 - rx) * dex;
}
if(dy < 0){
sty = -1;
sdy = (ry - sy) * dey;
}
else {
sty = 1;
sdy = (sy + 1 - ry) * dey;
}
// project ray
while(--d >= 0){
if(sdx < sdy){
sdx += dex;
sx += stx;
}
else{
sdy += dey;
sy += sty;
}
result.tile = tiles[sx][sy];
if(result.tile.solid){
break;
}
else if(sx == ex && sy == ey){
result.success = true;
break;
}
}
return result;
}
onMouseDown = function(){
start = getTile(_xmouse, _ymouse);
}
onEnterFrame = function(){
var end:Object = getTile(_xmouse, _ymouse);
losClip.clear();
losClip.beginFill(0xFF0000);
drawTile(start, losClip);
losClip.endFill();
losClip.beginFill(0x0000FF);
drawTile(end, losClip);
losClip.endFill();
var time:Number = getTimer();
var loops:Number = 150;
var i:Number = 0;
for(i = 0; i < loops; i++){
doLos(start, end, tiles, los);
}
time = getTimer() - time;
debug.text = "time taken: " + time + "ms " + "loops: " + loops;
losClip.lineStyle(1, 0x00FF00);
losClip.moveTo(start.cx, start.cy);
losClip.lineTo(end.cx, end.cy)
losClip.lineStyle(1, 0xFF0000);
losClip.moveTo(start.cx, start.cy);
losClip.lineTo(los.tile.cx, los.tile.cy);
losClip._alpha = los.success ? 100 : 50;
}
maybe you should consider reducing the number of iterations needed, do you really need 150 objects running LOS all at once? could you maybe put a limit, 30 objects per frame, 5 frames for all objects to receive updated vision data sounds good to me.
I agree, that's a lot of iterations. You only need to run them when things actually change tiles. With that said, Bresenham's IS used to calculate line of sight in games. I got the idea for my little SWF from reading about it in one of the Game Developer Gems books.
I you feel it models the problem better, you should be able to make the thin line case just as fast as bresenhams algorithm. Asymptotically they both scale linearly with the number of tiles traversed, and the constants in front should be comparable.
My gripes with Bresenhams are exactly you posted in the picture, quantizing your line of sight solves a closely related but different problem. Solving the correct problem should cost an equal amount of time.
EDIT: I will try to put my money where my mouth is, and implement a fast version of the thin line traversal, but no promises.
All right here's where I landed on this. It's in AS3, because I don't have the toolchain for doing work in AS2. It's all primitive operations through, so it should be straightforward for you to port it. It's strongly typed regarding numbers vs ints, but I think in AS2 they'll all become numbers.
A lot of the program is boilerplate, just focus on three functions: "test_sight", "test_sight_up" and "test_sight_down". The up/down functions are very similar, the key differences are commented with "//***".
You also need to put in your own opacity testing - comments in the code indicate where your tests should go.
Finally, the coordinate system might be 0.5 units off from what you are currently using. In this routines coordinate system, the tile(0,0) extends from 0 to 1 along x and y, and has a centroid at (0.5,0.5). Basically, you just need to offset by 0.5 whenever you test. For example, to test visibility between tile(3,4) and tile (7,13), call test_sight(3.5,4.5, 7.5, 13.5). This will cause the ray to shoot from tile centroid to tile centroid. The driver program has rays originating from random spots inside the tiles, just testing it all out.
Hope it works Please provide feedback if you find problems. I'm also curious regarding its performance relative to your bresenhams soln.
Sorry to keep spamming this thread but my edit time was long expired.
Thought I would post up this modification which handles a corner case a bit more gracefully. When a ray is degenerately close to the corner of a tile (clearance less than 1/100th of a tile), it tests the visibility of tiles on both sides of the ray. Running both codes on a perfect diagonal, like (0.5, 0.5 9.5 9.5) will best demonstrate the difference between them.
PHP Code:
private static const TOLERANCE : Number = 1.0e-2;
public function test_sight_down(x1 : Number, y1 : Number, x2 : Number, y2 : Number, tiles : BitmapData ) : Boolean
{
var manhattan : int = Math.floor(x2) - Math.floor(x1) + Math.floor(y2) - Math.floor(y1);
var ix : int = Math.floor(x1);
var iy : int = Math.floor(y1);
// Compute plane ABC parameters (Ax + By = C) of the line passing through (x1,y1) and (x2,y2)
var A : Number = (y2-y1);
var B : Number = -(x2-x1);
var L : Number = Math.sqrt(A*A+B*B);
A /= L;
B /= L;
var C : Number = A*x1 + B*y1;
var corner_Ax : Number = A*Math.ceil(x1);
var corner_By : Number = B*Math.ceil(y1);
while ( manhattan > 0 )
{
tiles.setPixel(ix,iy,0xFFFFFF);
if ( corner_Ax + corner_By < C - TOLERANCE)
{ corner_Ax+=A; ix++; manhattan--; } // Step right.
else if ( corner_Ax + corner_By > C + TOLERANCE)
{ corner_By+=B; iy++; manhattan--; } // Step down.
else
{
// Step right and down.
tiles.setPixel(ix+1,iy,0xFFFFFF);
tiles.setPixel(ix,iy+1,0xFFFFFF);
corner_Ax+=A; ix++;
corner_By+=B; iy++;
manhattan-=2;
}
}
tiles.setPixel(ix,iy,0xFFFFFF);
return true; // Line of sight is clear.
}
public function test_sight_up(x1 : Number, y1 : Number, x2 : Number, y2 : Number, tiles : BitmapData ) : Boolean
{
var manhattan : int = Math.floor(x2) - Math.floor(x1) + Math.floor(y1) - Math.floor(y2);
var ix : int = Math.floor(x1);
var iy : int = Math.floor(y1);
// Compute plane ABC parameters (Ax + By = C) of the line passing through (x1,y1) and (x2,y2)
var A : Number = (y2-y1);
var B : Number = -(x2-x1);
var L : Number = Math.sqrt(A*A+B*B);
A /= L;
B /= L;
var C : Number = A*x1 + B*y1;
var corner_Ax : Number = A*Math.ceil(x1);
var corner_By : Number = B*Math.floor(y1);
while ( manhattan > 0)
{
tiles.setPixel(ix,iy,0xFFFFFF);
if ( corner_Ax + corner_By > C + TOLERANCE) // ***
{ corner_Ax+=A; ix++; manhattan--;} // Step right.
else if ( corner_Ax + corner_By < C - TOLERANCE)
{ corner_By-=B; iy--; manhattan--;} // Step up. // ***
else
{
// Step right and up.
tiles.setPixel(ix+1,iy,0xFFFFFF);
tiles.setPixel(ix,iy-1,0xFFFFFF);
corner_Ax+=A; ix++;
corner_By-=B; iy--;
manhattan-=2;
}
}
tiles.setPixel(ix,iy,0xFFFFFF);
return true; // Line of sight is clear.
}
You'll still need to modify this with your opacity checks. Wherever there's a setPixel, you should remove it and insert a check for opacity at the same coordinates. See the source comments in the previous zip.
Thanks for the code rachil0 and mr_malee. I will go over them both and test them out. Might take me a bit as I will have to understand them to use them. But thank you very much for all your effort and time.
The reason I need so many LOS tests is that I'm not just testing for each possible enemy target, I'm testing for a fog of war. So it's blanketing an arc in front of the unit with LOS tests to determine visibility. If the map is say 100 x 100 tiles, and the unit is close to the left edge looking right, and has 120 degree vision arc, that's maybe 150-200 squares along the outside edge to test LOS to. When the turn starts, I could easily break it down into several frames with a "loading" graphic sort of thing. But when a unit moves, I want to do the vision test at each tile moved, that's when I'm concerned about speed. I don't really want the movement to be interrupted with "loading" pauses between squares.
Reply With Quote
Originally Posted by homeDrone
Please provide feedback if you find problems. I'm also curious regarding its performance relative to your bresenhams soln.
