Super fast tile rendering/scrolling in D3D

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:

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;

....

---

So far it seems to work quite well. This is just a 1 layer example but it does support multiple layers with transparency.

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!

Quote:

---

Originally Posted by psychopath

I'll never figure out how you're able to come up with this stuff.

---

He's a typical programmer - doesn't have a life. :D

But yeah nice.

Looks intriguing...

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.

---

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.

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.

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);
  }
 
}

---

This thing is very fast for two reasons.

• 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.