Thread: Super fast tile rendering/scrolling in D3D

  1. #1
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607

    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:
    Last edited by VirtualAce; 03-12-2011 at 11:42 AM.

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Into this:
    Last edited by VirtualAce; 03-12-2011 at 11:42 AM.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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)
    Last edited by VirtualAce; 03-12-2011 at 11:42 AM.

  4. #4
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,071
    Very nice.

    I'll never figure out how you're able to come up with this stuff.
    M.Eng Computer Engineering Candidate
    B.Sc Computer Science

    Robotics and graphics enthusiast.

  5. #5
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Looking good Bubba!
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  6. #6
    Registered User Frobozz's Avatar
    Join Date
    Dec 2002
    Posts
    546
    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.

    But yeah nice.

  7. #7
    Registered User
    Join Date
    Aug 2006
    Posts
    74
    Looks intriguing...

    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.

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.
    Last edited by VirtualAce; 09-21-2006 at 06:06 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need testers for editor
    By VirtualAce in forum Game Programming
    Replies: 43
    Last Post: 07-10-2006, 08:00 AM
  2. Tile map loading/saving
    By sand_man in forum Game Programming
    Replies: 16
    Last Post: 04-23-2005, 09:38 PM
  3. super fast question
    By kimimaro in forum C Programming
    Replies: 6
    Last Post: 03-15-2005, 09:47 AM
  4. Super fast bilinear interpolation
    By VirtualAce in forum Game Programming
    Replies: 2
    Last Post: 06-18-2002, 09:35 PM
  5. Tile Editor
    By Nick in forum Linux Programming
    Replies: 3
    Last Post: 08-10-2001, 11:24 PM