Wednesday, December 19, 2007

Tile-Based Game : Line of Sight - Part 3

The final part of the 'Simple Math' line-of-sight function for a tile-based game. In part 1 we discussed only the very basic concepts of tile-based boards and created a couple of functions to return the coordinates of a tile. In part 2 we created a simple method to track where blocking objects sit on the board and a function to check if a particular tile has a blocking object. Now the only thing left to do is the LOS function itself.

Concept


From the player object, we will follow a direct line to the tile we want to check. As we follow this line to its destination point, if the line touches any tile that has a blocking object, then the LOS check should return that the vision from the player is blocked.



Line-of-Sight function


In this function we will send the (Col, Row) of the starting object (the player in this case) and the (Col, Row) of the tile we want to draw a line to. Just like the checkTileBlocking function, we will assume that the LOS is not blocked unless we find a tile with a blocking object on it.
function checkLOS(col1, row1, col2, row2)
{
hasLOS = true;

return hasLOS;
}

For this function we will need to determine how many times the function will check to see if the line crosses a tile. Obviously the more times we check a specific point on the line, the more accurate the LOS check will be. But if we get to crazy and check every millo-second we could really bog down the Flash player. So for this example we will check the line a number of times equal to double the max distance from one side of the board to the other. Since the board is 10 x 10, double the max is 20.
  checkSteps = 20

Which is also:

checkSteps = colLength + rowLenth;

Because we are using 'simple math', good old algebra, we will need to convert these (Col, Row) coordinates that we sent to the function into (X, Y) coordinates. We will also need the slope of the line.
function checkLOS(col1, row1, col2, row2)
{
hasLOS = true;

checkSteps = colLength + rowLenth;
startXY = getCoords_XY(col1, row1);
endXY = getCoords_XY(col2, row2);
slopeX = (endXY.x - startXY.x) / checkSteps;
slopeY = (endXY.y - startXY.y) / checkSteps;

return hasLOS;
}

Now we need to loop through all of the steps it will take to get from the player to the end tile.
function checkLOS(col1, row1, col2, row2)
{
hasLOS = true;

checkSteps = colLength + rowLenth;
startXY = getCoords_XY(col1, row1);
endXY = getCoords_XY(col2, row2);
slopeX = (endXY.x - startXY.x) / checkSteps;
slopeY = (endXY.y - startXY.y) / checkSteps;

for(i = 0; i < checkSteps; i++)
{
currentX = startXY.x + (slopeX * i);
currentY = startXY.y + (slopeY * i);
currentTile = getCoords_ColRow(currentX , currentY);
}

return hasLOS;
}

Now that we have our line drawn, and the function knows which tiles the line crosses over, we will add a check to see if there is a blocking object on each of the tiles we are looking at.
function checkLOS(col1, row1, col2, row2)
{
hasLOS = true;

checkSteps = colLength + rowLenth;
startXY = getCoords_XY(col1, row1);
endXY = getCoords_XY(col2, row2);
slopeX = (endXY.x - startXY.x) / checkSteps;
slopeY = (endXY.y - startXY.y) / checkSteps;

for(i = 0; i < checkSteps; i++)
{
currentX = startXY.x + (slopeX * i);
currentY = startXY.y + (slopeY * i);
currentTile = getCoords_ColRow(currentX , currentY);
blockedTile = checkTileBlocking(currentTile.col, currentTile.row);
if(blockedTile)
{
hasLOS = false;
}
}

return hasLOS;
}

Technically the LOS function could be done, but we want to add one more check to the function. We don't want the line-of-sight to be considered blocked if the only blocking object is on the last tile we are checking.
function checkLOS(col1, row1, col2, row2)
{
hasLOS = true;

checkSteps = colLength + rowLenth;
startXY = getCoords_XY(col1, row1);
endXY = getCoords_XY(col2, row2);
slopeX = (endXY.x - startXY.x) / checkSteps;
slopeY = (endXY.y - startXY.y) / checkSteps;

for(i = 0; i < checkSteps; i++)
{
currentX = startXY.x + (slopeX * i);
currentY = startXY.y + (slopeY * i);
currentTile = getCoords_ColRow(currentX , currentY);
isBlockedTile = checkTileBlocking(currentTile.col, currentTile.row);
if(isBlockedTile AND (currentTile IS NOT (col2, row2)))
{
hasLOS = false;
}
}

return hasLOS;
}

Closing


This is a light weight and simple way of checking the LOS from one tile to another. If you need to optimize it further, implement the suggestion I made in the tracking of the blocking objects in Part 2.

Keep in mind that I created this LOS function for a somewhat small tile-based game. It's not really intended for a massive real-time tile-based game, I would be interested to hear of someone doing something similar to this in those kind of settings.

Tile-Based Game : Line of Sight - Part 2

Here we will continue from where Part 1 left off, adding objects to the board that will cause vision to be blocked.


To properly test a LOS, we will need some objects that could potentially block the line-of-sight and a player piece to check the line-of-sight from. For this 'simple math' solution we should look at the blocking objects as if they cover the entire tile that they sit on, whether or not the art represents this. More complex algorithms or object hit tests would allow for better detail in the LOS check, but for this, we want simple.

Concept


As far as the code representation of the blocking object in the tile game, there is more than one way to do this. For this example I will use a blocking object array. Personally I set a variable to the tile itself. In this variable I set the name of any object that sits on it. This way I can remove a loop from the LOS check. Doing it this way requires a little more care in moving pieces, adding/removing pieces and such. For this tutorial I use the easier way of 'mentally' tracking the objects, an array.

Blocking object code
From the diagram above, there are three objects that can block the LOS, so we will put the (Column, Row) coordinates of these into an array for future use.
arrayBlocking()
arrayBlocking(0) = (2, 3)
arrayBlocking(1) = (8, 2)
arrayBlocking(2) = (8, 7)


Tile has Blocking Object



So the idea is to pick a tile on the board and draw an imaginary line from the player piece to the center of the tile you picked. As the line is drawn in the code, each tile that the line crosses is a tile we check to see if there is a blocking object on it. If at any point we are drawing this line and the line crosses through a tile with a blocking object, we want to stop the check and return that it is a
blocked LOS.

For ease of use, we'll create a blocked tile function for the LOS check later.

The code
In the function, we'll pretend that all tiles do not have a blocking object at first. Then we'll run through the arrayBlocking, if there is any in there that matches the tile we are checking, then we will return that the tile has a blocking object.
function checkTileBlocking(col, row)
{
hasBlockingObject = false;
for(i = 0; i < arrayBlocking.length; i++)
{
if(arrayBlocking(i) == (col, row))
{
hasBlockingObject = true;
}
}
return hasBlockingObject;
}

This gives us everything that we need as far as blocking objects in the tile-based game. Next step will be the LOS function.

Part 3 »

Tile-Based Game : Line of Sight - Part 1

This is a 'simple math' based Line-of-Sight(LOS) tutorial. It was created for a tile-based game in Adobe Flash using ActionScript 2. This tutorial will cover the concepts of the tile-based system, only in reference to the LOS function. It will provide pseudo code, not the actual code to make it work. Please look at this as a guide, for but one possible way of creating a LOS system.

Flash coordinates System



This is the basics of how flash uses it's (X, Y) coordinate system. Moving in positive directions, it starts in the upper left hand corner and moves right along the X coordinate and down along the Y coordinate. When you move along the Flash coordinate system in negative directions, it moves up for the Y coordinate and left for the X coordinate.

Tile-Based Board


Below is a 10x10 board setup for a tile-based game. The numbers (10, 30, 50...) along the top and left are the pixel steps from the center of the tile. The numbers inside of the tiles are the tile column & row coordinates ((0,0) (1, 0)...). Generally columns are vertical and rows are horizontal.




Required Functions


Before we can get to the LOS function, we will need a couple of other functions, to help us navigate the different tiles of the board. We will both need to determine the (X, Y) coordinate in pixels (px) of a given tile and find the (Column, Row) coordinate of a tile.

First lets create the function used to return the (X, Y) coordinates in pixels:


Here we have a visual representation of how the tiles (X,Y) works. In this example the tile is 20px wide by 20px tall. When determining the position of the tile, we will want to know where the center of the tile sits on the board. With Adobe Flash starting in the top left hand corner and moving down and right for positive directions, the center of the first tile would be at position (10px, 10px).

For the function we will give it the tile Column and Row, and it will return the (X,Y) position in pixels.

Now for the Code:
To get a X or Y we do this:
x = (column * 20px) - 10px;

We can also write it like this:
x = (column * tileWidth) - (tileWidth / 2);

function getCoords_XY(col, row)
{
tempX = (col * tileWidth) - (tileWidth / 2);
tempY = (row * tileWidth) - (tileWidth / 2);
xy = (tempX, tempY);
return xy
}

For the other function we need to return the (Column, Row) coordinates:
This one is a little tricker, here we will provide the function with the (X,Y) coordinates of a tile and it will give us back the Column and Row of where that tile would sit. Below, you will see a Math.floor() function, that's your standard round down. We'll use it here, due to the fact that are tiles need to be integers instead of floats or such.

The Code
To get the Row or Column we could do this:
col = (x + 10) / 20;

Or better yet, this:
col = (x + (tileWidth / 2)) / tileWidth;

function getCoords_ColRow(x, y)
{
tempCol = Math.floor((x + (tileWidth / 2)) / tileWidth);
tempRow = Math.floor((y + (tileWidth / 2)) / tileWidth);
ColRow = (tempCol, tempRow);
return ColRow
}

Notes


So now we have the basic understanding of the Tile-based flash system, and two functions to return the coordinates in either (X,Y) pixels or (Column, Row) coordinates. Next will be adding objects to the board that would cause vision to be blocked.

Part 2 »