I've been working on a tile rendering system for quite some time now. Finally I believe I've come up with a solution that is both efficient and super fast.
The algo turns this:
Printable View
I've been working on a tile rendering system for quite some time now. Finally I believe I've come up with a solution that is both efficient and super fast.
The algo turns this:
Into this:
For those of you who remember old school RLE I'm doing much the same thing here. First I grab a tile ID and set the top left and bottom left vertices.
Then inside the loop I grab another tile ID.
If the tile ID's match, I simply increment the position and offset into the map.
If the tile ID's don't match, I set the top right and bottom right vertices to the current position. Then I set the texture u to TileCount which means it will wrap the texture across the quad TileCount times giving the illusion of tiles when in reality it is just one quad.
The algo performs worst when there are a lot of dissimilar tiles but most tile maps are composed of similar tiles.
Sadly this algo only works on X for now but I have plans to use a tree structure to generate 'area' quads instead of just strips. Either way it comes down to making a tile map use large quads for areas of similar tiles. The speed up is amazing.
Also this algorithm does not use a regular grid of any type. The scrolling is calculated like this:
So far it seems to work quite well. This is just a 1 layer example but it does support multiple layers with transparency.Code:float fStartX=-(m_iScrollX % m_iTileWidth);
float fStartY=-(m_iScrollY % m_iTileHeight);
int iRow=m_iScrollX/m_iTileWidth;
int iCol=m_iScrollY/m_iTileHeight;
int iMapWidth=m_pMapManager->GetWidth(i);
UINT uMapOffset=iRow*iMapWidth+iCol;
....
The final render without wireframe (and crappy tile textures)
Very nice.
I'll never figure out how you're able to come up with this stuff.
Looking good Bubba!
He's a typical programmer - doesn't have a life. :DQuote:
Originally Posted by psychopath
But yeah nice.
Looks intriguing...
Be interested to hear if you get it to work and I'll have to remember this strategy when I move into this type of programming.Quote:
Sadly this algo only works on X for now but I have plans to use a tree structure to generate 'area' quads instead of just strips.
I updated the scrolling system. It was having problems at the edge of the screen so I changed it and optimized it. The speed-up was not as noticeable in windowed mode. However in full screen mode I can scroll an entire screen of tiles in about a millisecond. This scrolling algo is so damn fast I'll probably have to stick a delay in it just to get it to be useable.
I love it.
This took some time to figure out completely. So far I've tested it with several map layers on top of each other and the thing is still lightning fast. I'm going to give the source code example just in case anyone wants to use this algorithm. But you'd better have some big maps or a big delay because this sucker is fast.
This thing is very fast for two reasons.Code:void CScreenGrid::RenderEx(float fTimeDelta)
{
//Starting x and y
int iStartX=(-m_iScrollX % m_iTileWidth);
int iStartY=(-m_iScrollY % m_iTileHeight);
//Set positions to start x and y
int iPosX=iStartX;
int iPosY=iStartY;
//Get the map size from our manager
//All maps are same size regardless of content to speed up renders
//Map 0 will do fine
int iMapWidth=m_pMapManager->GetWidth(0);
int iMapHeight=m_pMapManager->GetHeight(0);
//Compute starting row and column in map
int iStartCol=m_iScrollX/m_iTileWidth;
int iStartRow=m_iScrollY/m_iTileHeight;
//Clamp to 0 to resolve scroll issues
if (iStartCol<=0) iStartCol=0;
if (iStartRow<=0) iStartRow=0;
//Clamp start row and col for scroll issues
if (iStartCol>iMapWidth) iStartCol=iMapWidth;
if (iStartRow>iMapHeight) iStartRow=iMapHeight;
//Set row and col to start row and col
int iRow=iStartRow;
int iCol=iStartCol;
//Compute offset into map and save
//StartOffset is the original offset
UINT uStartOffset=iRow*iMapWidth+iCol;
//Save start offset for a simple and fast way to move down one row
UINT uMapStartOffset=uStartOffset;
//This is the actual offset to pass to the map class
UINT uMapOffset=uStartOffset;
//Current tile ID and last tile ID
UINT nTileID=0,nLastID=0;
//Only 4 vertices are ever rendered at any time
TLVertex Vertices[4];
//Our tile counter - this will become our U texture coord for our quad
//To make it appear as though there are iTileCount tiles being rendered
int iTileCount=0;
//Housekeeping variables
//Indicates we are in a run of identical tiles
bool bRunMode=false;
//Tells the increment portion of the code whether or not to increment
//We don't increment if we just got done drawing
//This way the new vertex positions can be set the next time through
//the loop and they in the correct position
bool bIncrement=true;
//Set our FVF for the entire render
m_pDevice->SetFVF(TLVERTEX_FVF);
//Enable this to see the wireframe mode
//and exactly what the algorithm does
//m_pDevice->SetRenderState(D3DRS_FILLMODE,D3DFILL_WIREFRAME);
//Loop through all maps
for (UINT i=0;i<m_pMapManager->GetSize();i++)
{
//Set starting variables for this map
//We need a 3rd map offset var because we change the 2nd (uMapStartOffset)
//in the render. This resets all offsets to the start of the current map
//based on our scroll values
uMapOffset=uStartOffset;
uMapStartOffset=uMapOffset;
iPosX=iStartX;
iPosY=iStartY;
iCol=iStartCol;
iRow=iStartRow;
nLastID=0;
do
{
//Set increment to true
bIncrement=true;
//Grab a tile id at uMapOffset in map i
nTileID=m_pMapManager->GetMapValue(i,uMapOffset);
//Are we in run mode?
if (bRunMode==false)
{
//No so we must be at the start of the process
//Set the first 2 vertices for this quad
Vertices[0]=TLVertex((float)iPosX,
(float)iPosY,
1.0f,
0.0f,0.0f);
Vertices[2]=TLVertex((float)iPosX,
(float)iPosY+(float)m_iTileHeight,
1.0f,
0.0f,1.0f);
//Set last id to current id and increment to true
nLastID=nTileID;
bIncrement=true;
}
//Check if id's match
if (nTileID!=nLastID)
{
//They don't so we must draw something
if (bRunMode)
{
//We were in runmode so we must draw the run now
//However if these are blank tiles, do nothing
if (nLastID!=0xFFFFFFFF)
{
//These are not blank tiles so set the texture
m_pDevice->SetTexture(0,m_pTexManager->GetTexture(nLastID));
//Set the last 2 vertices for the quad
//Use iTileCount as the U coord for this quad
Vertices[1]=TLVertex((float)iPosX,
(float)iPosY,
1.0f,
(float)iTileCount,0.0f);
Vertices[3]=TLVertex((float)iPosX,
(float)iPosY+(float)m_iTileHeight,
1.0f,
(float)iTileCount,1.0f);
//Draw the sucker
m_pDevice->DrawPrimitiveUP(D3DPT_TRIANGLESTRIP,2,&Vertices,sizeof(TLVertex));
}
}
else
{
//We still must draw, but it's only going to be one tile
//No run here
//Do nothing if tile is blank
if (nLastID!=0xFFFFFFFF)
{
//Set texture
m_pDevice->SetTexture(0,m_pTexManager->GetTexture(nLastID));
//Set last 2 vertices
//Use U,V of 1.0f and 1.0f to draw 1 tile
Vertices[1]=TLVertex((float)iPosX,
(float)iPosY,
1.0f,
1.0f,0.0f);
Vertices[3]=TLVertex((float)iPosX,
(float)iPosY+(float)m_iTileHeight,
1.0f,
1.0f,1.0f);
//Draw the sucker
m_pDevice->DrawPrimitiveUP(D3DPT_TRIANGLESTRIP,2,&Vertices,sizeof(TLVertex));
}
}
//Reset our variables in prep for starting process all over again
iTileCount=0;
//Because we just got done drawing and x is incremented after this block,
//we must tell that portion that we don't want to increment on this
//iteration
bIncrement=false;
//Reset runmode - we are starting over so runmode is false
bRunMode=false;
}
else
{
//Tile id's match so set run mode to true
bRunMode=true;
//Nothing special, we just need to increment
bIncrement=true;
}
//If we are in runmode, keep track of how many tiles are identical
if (bRunMode) iTileCount++;
//If we are supposed to increment, let's do it
if (bIncrement)
{
//Increment vertex pos
iPosX+=m_iTileWidth;
//Increment current column
iCol++;
//Increment offset in map
uMapOffset++;
//If we are at edge of screen or at edge of map, we must move down
if (iPosX>m_iScreenWidth || iCol>iMapWidth)
{
//Reset posx to starting posx
iPosX=iStartX;
//Reset our column
iCol=iStartCol;
//Move down one row
iRow++;
//Move vertex pos down one row of tiles
iPosY+=m_iTileHeight;
//Move starting offset down one row
//We cannot just move our offset down one row b/c we would end up
//at the end of the next row
//This is why we 2 vars for map offset
//We increment one which always points to the start of the current row
//which makes it point to the start of the next row
//We then set our offset to the one we just computed
uMapStartOffset+=iMapWidth;
uMapOffset=uMapStartOffset;
//We are not in run mode
bRunMode=false;
//No identical tiles
iTileCount=0;
}
}
//We must repeat the process until we are bottom of screen or bottom of map
} while (iPosY<m_iScreenHeight && iRow<iMapHeight);
}
}
- It does not draw the entire map. It only draws the portion that is visible.
- It does not draw 1 quad per tile.
So this algo not only breaks the map down into large quads, it also performs an important cull step. This is done by always drawing at some negative offset from 0,0. If you never compute the row and column based on scroll values, this map will simply bounce back and forth with no visible change in tiles. But because I'm computing the row and column and using that as a starting offset in the map, when you scroll right by one tile, the offset also changes by 1. But tilewidth % scrollx is always going to be in range 0 to tilewidth. So as you scroll right, the top corner moves left by a certain amount. When you get to -tilewidth, the values pops back to 0 but because the offset in the map changes, it appears the map is scrolling. All the map is really doing is bouncing back and forth between -tilewidth and 0 and -tileheight and 0. However because we are also tracking the column and row during the render when we get to the edge of the map, we stop drawing. So what this all boils down to is we are only drawing the portion of the map that is on the screen and nothing else.
I've played a lot of side scrollers and messed with other scrolling algos and I will say that this is probably the fastest scrolling I've ever seen.
If the code is confusing I apologize but I did not want to have an X loop and a Y loop. As it is I have a do while inside of a for which is bad enough.