Speed up script: "3d" grid terrain

[Lt. Smash]

Hey guys!!

I've been reading the forums and were impressed by the different tile-engines some people have coded using AGS. So I thought, why not trying one by myself, maybe making a game out of it. So I quickly wrote some kind of faked "3d" tile map of which I was, at first, very proud of. (although there are just lines ) But then I tried to generate larger maps (>60x60 tiles) and the frame drop was very high. With a little tweaking I got it to be a little quicker than before but anyhow, it's way too slow. So, here I am, asking how to improve my code to make it go as fast (least FrameDrop) as possible. I hope you can help me.

Here you can download and try out the tilemap:
TileEngine03 (883 Kbyte)

Keys:
[ N ] - Create new random map with random tilesize
[ Q ] / [ E ] - Rotate map
[ + ] / [ - ] - Zoom in/out map
[ Ctrl ]+[ F ] - Show Framerate
[ G ] - Show floor grid

Code info:
The tiles information is stored in an external file and then loaded into a huge array. Every tile has one height-value (this is the height of the top left corner).
I think the big problem here is, that AGS has to read through the whole array every game loop and that there are so many variables stored in memory.

Here's the code to re-calculate the tiles corner point positions:  // Executed only when rotating the map or zooming in/out

Code: ags

void Map::calculateTiles() {
	// Tile X/Y position
	int x, y, id;
	float posX, posY, startX, startY, a, b, c = IntToFloat(this.tileSize) * screen.zoom;
	
	if (abs(screen.rotation) > 90.0) { // mirror map when rotation is between +-90.0 and +-180.0
		screen.mirrored = true;
	}
	else {
		screen.mirrored = false;
	}
	
	// calculate sides a and b of a triangle (trigonometry)
	a = Maths.Sin(Maths.DegreesToRadians(screen.rotation)) * c;
	b = Maths.Sqrt(c * c - a * a);	
	if (screen.mirrored) {
		b = -b;
	}
	
	// Tile Z position (height)
	float tileSizeHalf = c / 2.0;
	float rectDiag = Maths.Sqrt(tileSizeHalf*tileSizeHalf + tileSizeHalf*tileSizeHalf);
	float rectAngle = Maths.ArcTan2(tileSizeHalf, tileSizeHalf);
	float rot = Maths.DegreesToRadians(screen.rotation);
	
	float tlX = (-rectDiag) * Maths.Cos(rectAngle + rot);
	float tlY = (-rectDiag) * Maths.Sin(rectAngle + rot);
	
	while (x < this.rows) {
		posX = startX;
		posY = startY;
		
		while (y < this.cols) {
			posX += b;
			posY += a;
							
			_tile[id].tlX = FloatToInt(posX + tlX, eRoundNearest);
			_tile[id].tlY = FloatToInt(posY + tlY - _tile[id].z * screen.zoom, eRoundNearest);		
			
			y++;
			id++;
		}
		y = 0;
		x++;

		startX -= a;
		startY += b;
	}
	
}

And here's the drawing code:  // Executed in rep_exec...

Code: ags

void Map::draw(bool drawGround) {	
	int id, t = FloatToInt(IntToFloat(this.tileSize)*screen.zoom);
	drGroundLayer = Room.GetDrawingSurfaceForBackground();
	
	drGroundLayer.Clear();
	drGroundLayer.DrawingColor = 15;
		
	while (id < this.maxTiles) {		
		if (_tile[id].tlX < screen.offsetX - t || _tile[id].tlX > screen.offsetX + System.ScreenWidth + t 
		|| _tile[id].tlY < screen.offsetY - t || _tile[id].tlY > screen.offsetY + System.ScreenHeight + t) {
		}
		else {
		/*	if (drawGround) {
				drGroundLayer.DrawingColor = 11;
				//####
				drGroundLayer.DrawingColor = 15;
			}*/

			if (id == this.maxTiles-1) { } // don't draw last tile
			else if (((id+1) % this.cols) == 0) { // just draw one vertical line for each tile of the last column
				drGroundLayer.DrawLine(_tile[id].tlX - screen.offsetX, _tile[id].tlY - screen.offsetY, 
				_tile[id+this.cols].tlX - screen.offsetX, _tile[id+this.cols].tlY - screen.offsetY);
			}
			else if (id > (this.cols * (this.rows-1) - 1)) { // just draw one horizontal line for each tile of the last row
				drGroundLayer.DrawLine(_tile[id].tlX - screen.offsetX, _tile[id].tlY - screen.offsetY, 
				_tile[id+1].tlX - screen.offsetX, _tile[id+1].tlY - screen.offsetY);
			}
			else { // draw one horizontal and one vertical line for each of the other tiles
				drGroundLayer.DrawLine(_tile[id].tlX - screen.offsetX, _tile[id].tlY - screen.offsetY, 
				_tile[id+1].tlX - screen.offsetX, _tile[id+1].tlY - screen.offsetY);
				drGroundLayer.DrawLine(_tile[id].tlX - screen.offsetX, _tile[id].tlY - screen.offsetY, 
				_tile[id+this.cols].tlX - screen.offsetX, _tile[id+this.cols].tlY - screen.offsetY);
			}
		}
		id++;
	}
	drGroundLayer.Release();
}

Thanks in advance...

[EDIT1] Now it calculates just one point for each tile (so less variables are needed). The tiles to the far right and bottom aren't visible. They just finish up the tiles of the row/column before.

[Wyz]

First of all, interesting project!

Secondly, just a quick suggestion, I'd say try it out.
Floating-point operation are often the bottle-neck, try if you can alter the code so that no floating points operations are done in the main loop. Convert the tlX, tlY etc to integers and see if the results still look decent on your screen. I assume it will increase performance quite a bit. Let me know what the results are.

[Khris]

There's duplicate stuff here:

Code: ags

	tlX = (-rectDiag) * Maths.Cos(rectAngle + rot);
	tlY = (-rectDiag) * Maths.Sin(rectAngle + rot);
	trX = rectDiag * Maths.Cos(-rectAngle + rot);
	trY = rectDiag * Maths.Sin(-rectAngle + rot);
	brX = rectDiag * Maths.Cos(rectAngle + rot);
	brY = rectDiag * Maths.Sin(rectAngle + rot);
	blX = (-rectDiag) * Maths.Cos(-rectAngle + rot);
	blY = (-rectDiag) * Maths.Sin(-rectAngle + rot);

Looking at the right sides, this should give the same result:

Code: ags

	tlX = (-rectDiag) * Maths.Cos(rectAngle + rot);
	tlY = (-rectDiag) * Maths.Sin(rectAngle + rot);
	trX = rectDiag * Maths.Cos(-rectAngle + rot);
	trY = rectDiag * Maths.Sin(-rectAngle + rot);
	brX = -tlX;
	brY = -tlY;
	blX = -trX;
	blY = -trY;

[Lt. Smash]

Thanks for the tips guys. Now I've simplified the code some more (first post updated) but it didn't speed up that much.

Some testing results:
[MAP 130x130]
Before: 21 FPS normal, 3-4 FPS when rotating, 9-10 FPS zoomed out to see almost all tiles.
After: 25-26 FPS normal, 11 FPS when rotating, 12-13 FPS zoomed out.

So, as you can see it has improved a bit but there must be a way to get it even faster. (Imagine I'll want to texturize these tiles :o) Maybe some of you clever coders find a way to speed up this lil' thing. (I think it should go way faster, when it would just have to loop through the current visible tiles...)

@Wyz: I can't change the tlX and tlY to ints while calculating because then the map won't rotate that fluently. But afterwards they are stored as ints in the tile array and drawn onto the background.

[lan]

Code: ags

	tlX = (-rectDiag) * Maths.Cos(rectAngle + rot);
	tlY = (-rectDiag) * Maths.Sin(rectAngle + rot);
	trX = rectDiag * Maths.Cos(-rectAngle + rot);
	trY = rectDiag * Maths.Sin(-rectAngle + rot);

I am not quite sure, how (and how fast) cosinus and sinus functions are implemented, but you could try to pre-calculate values for cos and sin, store them into arrays and replace the functions from the Maths library by something like the following:

Code: ags

  // allocate memory for 360 sinus value
  double sinus[360];

  void prepareSinus()
  {
    for( int i = 0; i< 360 ; i++)
    {
      sinus[i] = Maths.Sin(i);
    }
  }

  double sin( int angle )
  {
    // if necessary ensure, that angle is between 0 and 360
    while(angle <0){angle+=360;}

    // convert angle to array-index
    int index = angle % 360;
    return sinus[angle];
  }

The syntax of my example may be little wrong, but I think you get the idea of it. Furthermore you can reduce the size of the array for the sinus values using the symmetry of that function (as you might know: sin(x) = -sin(-x)).

The cosinus value can be retrieved via the sinus values with: cos(x) = sin(90-x)

Hope some of my two cents are useful for you