  Topological crystalline insulators (TCI) are insulating electronic phases of
matter with nontrivial topology originating from crystalline symmetries. Recent
theoretical advances have provided powerful guidelines to search for TCIs in
real materials. Using density functional theory, we identify a class of new TCI
states in the tetragonal lattice of the Ca$_2$As material family. On both top
and side surfaces, we observe topological surface states protected
independently by rotational and mirror symmetries. We show that a particular
lattice distortion can single out the newly proposed topological protection by
the rotational symmetry. As a result, the Dirac points of the topological
surface states are moved to generic locations in momentum space away from any
high symmetry lines. Such topological surface states have not been seen before.
Moreover, the other family members, including Ca$_2$Sb, Ca$_2$Bi and Sr$_2$Sb,
feature different topological surface states due to their distinct topological
invariants. We thus further propose topological phase transitions in the
pseudo-binary systems such as (Ca$_{1-x}$Sr$_x$)$_2$As and
Ca$_2$As$_x$Sb$_{1-x}$. Our work reveals rich and exotic TCI physics across the
Ca$_2$As family of materials, and suggests the feasibility of materials
database search methods to discover new TCIs.
