Algorithms

(1/4) > >>

tcaudilllg:
I've been deliberating on how best to contribute to the community for a while. After the NPC thread, everything seemed about covered. I was recently thinking about how to implement scrolling, however, when I realized two things:
I have a tendency to reinvent the wheel every time I am faced with a complex programming concept.I do not enjoy creating complex algorithms.
This state of affairs being what it is, I think the best approach to the difficulties inherent to programming algorithms is to create a list of commonly used ones. I imagine that with easy access to algorithms, the pressure to reinvent them would be non-existent.

Algorithm complexity appears to be the most formidable programming challenge facing us at this time.

tcaudilllg:
Sprite Algorithm: position a sprite on a tile map.

Procedure:
To find the x-coordinate: multiply the x tile coordinate of the sprite by the tile widthTo find the y-coordinate: multiply the y tile coordinate of the sprite by the tile height
Example:
Code:

spriteX = spriteTileX * tileWidth;
spriteY = spriteTileY * tileHeight;

It's apparent that a key difficulty in describing the algorithm is lack for a standardized terms by which to refer to the "tile X coordinate", this because we are referring to two coordinate systems which overlap each other. Because it is difficult to describe the tile coordinate in our thoughts. It is probably best to assert that the tile X coordinate is the "tile column" and the tile Y coordinate the tile "row"; yet even this requires reference back to the definition of a "column" versus a "row", the same creating distraction from the act of imagining the algorithm. For the record, I believe the problem of dealing with columns and rows in the imaginative sense is a matter of us thinking "Greek column" whenever we hear the word as such: it is impossible to imagine a mathematical column in any specific sense. The same applies for rows: when we think of a row of people, we think of a line, not an index into the row itself. It's a problem of our conventions.

Clarity in this simple case allows us to think a little more deeply about positioning itself, particularly with respect to the problem of divining the tile coordinates of a sprite in the first case.

Sprite Algorithm: find the tile coordinates of a sprite.

Procedure:
To find the column coordinate: divide the sprite's x coordinate by the tile width, and round down.
To find the row coordinate: divide the sprite's y coordinate by the tile height, and round down.
Example:
Code:

spriteTileX = floor(spriteX / tileWidth);
spriteTileY = floor(spriteY / tileHeight);


With this in mind we can deduce the notion of precise coordinates for the sprite which are independent of the tile coordinate system, yet deducible from it. We position the sprite in this way by taking into account the remainder of the above formula as an offset.

Sprite Algorithm: find the tile offset of a sprite.

Procedure:
To find the column offset: divide the sprite's x coordinate by the tile width, taking the remainder.
To find the row offset: divide the sprite's y coordinate by the tile height, taking the remainder.
Example:
Code:

spriteOffsetX = spriteX % tileWidth;
spriteOffsetY = spriteY % tileHeight;


With this information in hand, we can restore the precise position of the sprite wherever it was on the map. (this is essential for saved games)

Sprite Algorithm: position a sprite with precision.

Procedure:
To find the x-coordinate: multiply the x tile coordinate of the sprite by the tile width and add the X offset.To find the y-coordinate: multiply the y tile coordinate of the sprite by the tile height and add the Y offset.
Example:
Code:

spriteX = (spriteTileX * tileWidth) + spriteXOffset;
spriteY = (spriteTileY * tileHeight) + spriteYOffset;


The values for the algorithm of course being obtained through the following:

Sprite Algorithm: obtain the components of a sprite's precise coordinates.

Procedure:
To find the x coordinate components: divide the sprite's x coordinate by the tile width, taking the remainder.
To find the y coordinate components: divide the sprite's y coordinate by the tile height, taking the remainder.
Example:
Code:

spriteTileX = floor(spriteX / tileWidth);
spriteTileY = floor(spriteY / tileHeight);
spriteOffsetX = spriteX % tileWidth;
spriteOffsetY = spriteY % tileHeight;


Next, tile algorithms and camera tricks.

tcaudilllg:
Map Drawing Algorithm: draw a tile on the map.

Procedure:
Find the coordinates of the tile's upper left corner.To find the x coordinate: multiply the tile's column by the tile's width.To find the y coordinate: multiply the tile's row by the tile's height.draw the tile line by line, increasing the y coordinate at the end of each line.
Example:
Code:

tileXCoord = tileColumn * tileWidth;
tileYCoord = tileRow * tileHeight;

for (yOffset = 0; yOffset < tileHeight; yOffset++)
{
    for (xOffset = 0; xOffset < tileWidth; xOffset++)
    {
        mapCoords[tileYCoord + YOffset][tileXCoord + XOffset] = tileData[YOffset][XOffset];
    }
}
 


The chief issue is, again, a lack of terminology. What could we possibly call the sum of the tile x coordinate and the offset into the tile? There is no such term, is there? How can we imagine what we have no terms for? We can visualize the point easily enough, but describing it is harder. Fortunately we don't have to reference any specific part of this algorithm in any other, so the lack of terminology is inconsequential outside of that still pressing issue of "what to call it?" Another terminology issue is the matter of what to call the copies of the tile coordinates. (which I thought I would have to make, but didn't have to). I remember Andre Lamothe always using the prefix "work" for such variables, though it hardly seems descriptive enough. In the end, we are able to advance only by observing that the offset is always a distinct coordinate system from its container; if it were not, it would be the container. The framing of the offset coordinates in the context of a self-contained system allows us to make much more use of the system than we otherwise could. Consider, the notion of the offset coordinates as being contained in their own system is far more intuitive than the notion of the offsets as "appendages" to the tile unit system. This also helps us understand the drawing of the map itself.

Map Drawing Algorithm: draw a 2-dimensional tile map.

Procedure:
Find the coordinates of the tile's upper left corner.To find the x coordinate: multiply the tile's column by the tile's width.To find the y coordinate: multiply the tile's row by the tile's height.draw the tile line by line, increasing the y coordinate at the end of each line.
Example:
Code:


for (tileRow = 0; tileRow < tileRowLimit; tileRow++)
{
    for (tileColumn = 0; tileColumn < tileColumnLimit; tileColumn++)
    {
        // draw tile
    }
}
 


For each "tile unit coordinate" on the map, we assert a completely self-contained coordinate system in the context of that coordinate.

tcaudilllg:
CAMERAS

Cameras behave much like sprites. They have many of the same properties of sprites: tile coordinates, tile offsets, and definite dimensions of height and width. They also move about the map like sprites and are bound by it. As the camera moves about the map, features on the map appear and disappear depending on whether they are contained within the camera's coordinate system.

The trick to using the camera is to remember that it's a sprite.

Scrolling Algorithm: obtain the components of the camera's precise coordinates.

Procedure:
To find the x coordinate components: divide the camera's x coordinate by the tile width, taking the remainder.To find the y coordinate components: divide the camera's y coordinate by the tile height, taking the remainder.
Example:
Code:

cameraTileX = floor(cameraX / tileWidth);
cameraTileY = floor(cameraY / tileHeight);
cameraOffsetX = cameraX % tileWidth;
cameraOffsetY = cameraY % tileHeight;


Scrolling Algorithm: position the camera with precision.

Procedure:
To find the x-coordinate: multiply the x tile coordinate of the camera by the tile width and add the X offset.To find the y-coordinate: multiply the y tile coordinate of the camera by the tile height and add the Y offset.
Example:
Code:

cameraX = (cameraTileX * tileWidth) + cameraXOffset;
cameraY = (cameraTileY * tileHeight) + cameraYOffset;


We did nothing more but substitute "camera" for "sprite". In fact, we could have just as easily have called the sprite functions on the camera, and got the same effect.

Now we can obtain the visible map by treating the clipping rectangle as a tile. The difference is that we are not taking all of the source data as we were with the tile, but only a sliver: we take not the entire map but an excerpt of it.

Code:

for (yOffset = 0; yOffset < cameraHeight; yOffset++)
{
    for (xOffset = 0; xOffset < cameraWidth; xOffset++)
    {
        visibleCoords[YOffset][XOffset] = mapCoords[cameraYCoord + YOffset][cameraXCoord + XOffset];
    }
}


Because the map has finite size, the camera box's edges should not move past the boundary coordinates of the map: we must not scroll beyond the map. For this purpose we need to clearly define the camera box's edges.

Scrolling Algorithm: Defining a Clipping Rectangle (also called a "camera")

Procedure:
To find the camera x2 coordinate: add the camera's width to the camera's x1  coordinate.To find the camera y2 coordinate: add the camera's height to the camera's y1 coordinate.
Code:

cameraX2 = cameraX + cameraWidth;
cameraY2 = cameraY + cameraHeight;


We don't need to find the upper right or the lower left edges of the camera box, because the upper left and lower right edges give us all the information we need. The upper right corner is always at (x2,y1), and the lower left corner at (x1,y2).

The primary issue with moving the camera is making sure it doesn't exceed its bounds. We do this by creating a "ghost" camera which actually does cross outside the bounds of the map. We verify the camera's potential to follow after this "ghost".

Scrolling Algorithm: Move the Camera

Procedure:
Determine the direction of movementMove the ghost camera.Verify that the ghost is inside the bounds of the map.Move the camera
Code:


ghostCamX = ghostCamX + xDistance;
ghostCamX2 = ghostCamX2 + xDistance;
ghostCamY = ghostCamY + yDistance;
ghostCamY2 = ghostCamY2 + yDistance;

if ((ghostCamX > -1)
 && (ghostCamX2 < mapWidth)
 && (ghostCamY > -1)
 && (ghostCamY2 < mapHeight))
{
    cameraX = ghostCamX;
    cameraX2 = ghostCamX2;
    cameraY = ghostCamY;
    cameraY2 = ghostCamY2;
}


There's a problem of how to compute the distance.

Richard Marks:
+10 rating for your very much welcomed contribution Tony.
Thank you, that is indeed a useful and well thought out series of informational and educational posts.
By all means, please do continue. :)

Navigation

[0] Message Index

[#] Next page