Кстати, какая у вас метрика? Я в аналогичном проекте сделал ось x горизонтальной, ось у - вниз и влево. Расстояние между двумя клетками - (if (dx*dy >0) max(abs(dx),abs(dy)) else abs(dx+dy)).
Рисование в 2д большого количества клеток (картинками) на андроиде тормозило на SurfaceView, а на openGL ещё оставался хороший запас производительности. И ещё - телефон без проблем тянул карту размера порядка 160*160. (обход по всем клеткам выполнялся за миллисекунду или меньше, но сохранять это добро по-быстрому через сериализацию было невозможно) А потом я сдал проект как курсовой по информатике, и больше не открывал(( Со мной его "делали" ещё три человека, но толку было мало - в итоге 5/6 кода и графика мои. Есть
на гитхабе.
Если размер клетки как в цивилизации, то, наверно, лучше схематично рисовать. Если же одна клетка - одно дерево, наоборот придётся графику делать красивой и для каждого типа поверхности использовать несколько немного различающихся спрайтов.
P.S. если хотите - могу попробовать к вам присоединиться.