Tile Game slow. Lots of sprites. Texture atlas?

I have a simple tile game with two different in colour mono-coloured same sized tiles combined into 600x600 tile area; camera view is 80x80 tiles. All tiles are now sprites and I get around 30 fps on my computer. But as I want to run this game on my netbook (where I got around 5 fps :D), it is not sufficient. I searched on internet and found that texture atlases might be a solution for my problem.

BUT each tile must BE ABLE to be DESTROYED (or just change colour to e.g. black and save information that it has been destroyed by deleting its collider for example) BTW should I use colliders for every tile? But what if I have a texture atlas?.
AND the map is generated on run-time.

I also found out that Unity has some texture batching to save drawcalls; each tile has the same sprite-default material so does it batch in my game? (I hope it does not yet).
Any ideas how to improve performance of this dumb game, which for performace reasons I tried to program with Python+Pygame, C#+WinForms and now Unity, but I guess it tends to SDL.

Stats:
FPS: 3 when moving -30 stable (in editor, otherwise around 30 everytime)
Main Thread: ~30ms, ~70ms when destroying some tiles
Draw Calls: ~3000, Saved by batching ~3000
Tris: 12.6k Verts: 25.1k (what are they?)
VBO Total: 14 - 198.3 KB

I had worked up some code for another question and realized that what I had was about 80% of the way towards what you were looking for. So I spent a bit of time and reworked the code. It produces a grid of a specified size. 600 x 600 is no problem and runs at 60+ fps in the editor. There are not a whole lot of lines of code, but the code is intricate. If you are going to try and use it, I encourage you to spend the time to understand every line…and there’s no guarantee that I got everything right. I included a SetQuadUV method that will set a cell specified by row and column to a specified sprite sheet cell. I think from your description you will need cell-level hit testing. You could expand this code so that each mesh could report triangle hits, but I think you are better off putting a quad over the top of this mesh and doing the hit testing mathematically.

Here is the sprite sheet I used to test the code:

[30999-gridtile.png*_|30999]

And here is the code:

using UnityEngine;
using System.Collections;

public class TileGrid : MonoBehaviour {
	public Material material;
	public float cellWidth = 1.0f;  
	public float cellHeight = 1.0f;
	public int rows = 10;
	public int cols = 10;
	public int spriteRows = 2;      
	public int spriteCols = 2;

	private const int maxQuadsPerMesh = 16380;
	private int quadsPerMesh;
	private GameObject[] goMeshes;
	private Mesh[] meshes;
	private float spriteCellWidth;
	private float spriteCellHeight;
	private int spriteCellCount;
	private int rowsPerMesh;

	// Sets specified row/col to the specified sprite sheet cell 
	public void SetQuadUV(int row, int col, int cell) {
		int imesh = row / rowsPerMesh;
		int r = row % rowsPerMesh;
		int baseIndex = (r * cols + col) * 4;
		Vector2[] uvs = meshes[imesh].uv;
		SetMeshQuadUV(uvs, baseIndex, cell);
		meshes[imesh].uv = uvs;
	}

	void Awake() {
		spriteCellWidth =  1.0f / spriteCols;
		spriteCellHeight = 1.0f / spriteRows;
		spriteCellCount = spriteRows * spriteCols;

		CreateMeshes();
	}

	void CreateMeshes() {
		if (rows <= 0 || cols <= 0) return;

		quadsPerMesh = (maxQuadsPerMesh / cols) * cols;

		rowsPerMesh = quadsPerMesh / cols;
		int currRow = 0;
		
		int meshCount = (rows * cols) / quadsPerMesh + 1;
		int quadsLastMesh = (rows * cols) % quadsPerMesh;

		float height = rows * cellHeight;
		float width = cols * cellWidth;
		Vector3 offset = new Vector3(-width / 2.0f, height / 2.0f, 0.0f);

		goMeshes = new GameObject[meshCount];
		meshes = new Mesh[meshCount];
		
		for (int i = 0; i < meshCount; i++) {
			GameObject go = new GameObject();
			go.transform.parent = transform;
			MeshFilter mf = go.AddComponent<MeshFilter>();
			Mesh mesh = new Mesh();
			mf.mesh = mesh;
			Renderer rend = go.AddComponent<MeshRenderer>();
			rend.material = material;
			go.AddComponent<MeshCollider>();

			Vector3[] vertices;
			int l = 0;
			if (i != meshCount - 1) {
				vertices = new Vector3[4 * quadsPerMesh];
				l = quadsPerMesh / cols;
			}
			else {
				vertices = new Vector3[4 * quadsLastMesh];
				l = quadsLastMesh / cols;
			}
			
			for (int j = 0; j < cols; j++) {
				for (int k = 0; k < l; k++) {

					vertices[(k * cols + j) * 4]      = new Vector3(j * cellWidth, -(k + currRow)* cellHeight, 0.0f) + offset;
					vertices[(k * cols + j) * 4 + 1]  = new Vector3(j * cellWidth, -(k + currRow + 1) * cellHeight, 0.0f) + offset;
					vertices[(k * cols + j) * 4 + 2]  = new Vector3((j + 1) * cellWidth, -(k + currRow + 1) * cellHeight, 0.0f) + offset;
					vertices[(k * cols + j) * 4 + 3]  = new Vector3((j + 1) * cellWidth, - (k + currRow) * cellHeight, 0.0f) + offset;
				}
			}

			currRow += rowsPerMesh;

			mesh.vertices = vertices;

			int[] triangles = new int[mesh.vertices.Length / 2 * 3];
				
			for (int j = 0; j < vertices.Length / 4; j++) {

				triangles[j * 6 + 0] = j * 4 + 0;	//	 0_ 3		0 ___ 3
				triangles[j * 6 + 1] = j * 4 + 3;	//   | /		 |	/|
				triangles[j * 6 + 2] = j * 4 + 1;	//  1|/			1|/__|2
				
				triangles[j * 6 + 3] = j * 4 + 3;	//	   3
				triangles[j * 6 + 4] = j * 4 + 2;	//    /|
				triangles[j * 6 + 5] = j * 4 + 1;	//  1/_|2
			}

			mesh.triangles = triangles;

			Vector2[] uvs = new Vector2[vertices.Length];

			// Sets random UVs for each cell
			for (int j = 0; j < vertices.Length / 4; j++) {
				SetMeshQuadUV(uvs, j * 4, Random.Range (1, spriteCellCount));
			}

			mesh.uv = uvs;
			goMeshes *= go;*

_ meshes = mesh;_
* }*
* }*

* // Sets the uvs for one quad in a provided array of uvs*
* void SetMeshQuadUV(Vector2[] uvs, int baseIndex, int cell) {*
* cell = cell % spriteCellCount;*
_ float x = cell % spriteCols * spriteCellWidth;
float y = cell / spriteRows * spriteCellHeight;_

* uvs[baseIndex] = new Vector2(x + 0.01f, y + spriteCellWidth - 0.01f);*
* uvs[baseIndex + 1] = new Vector2(x + 0.01f, y + 0.01f);*
* uvs[baseIndex + 2] = new Vector2(x + spriteCellWidth - 0.01f, y + 0.01f);*
* uvs[baseIndex + 3] = new Vector2(x + spriteCellWidth - 0.01f, y + spriteCellHeight - 0.01f);*
* }*

* // Press space bar to set random grid cell to sprite sheet cell 0*
* void Update() {*
* if (Input.GetKeyDown (KeyCode.Space)) {*
* int i = Random.Range (0, rows);*
* int j = Random.Range (0, cols);*

* Debug.Log ("Row = " + i + " Col = " + j);*
* SetQuadUV(i, j, 0);*
* }*
* }*
}
_*

Don’t foget about:
mf.mesh.RecalculateBounds();
mf.mesh.RecalculateNormals();