  Temporal graphs are a popular modelling mechanism for dynamic complex systems
that extend ordinary graphs with discrete time. Simply put, time progresses one
unit per step and the availability of edges can change with time. We consider
the complexity of solving $\omega$-regular games played on temporal graphs
where the edge availability is ultimately periodic and fixed a priori.
  We show that solving parity games on temporal graphs is decidable in PSPACE,
only assuming the edge predicate itself is in PSPACE. A matching lower bound
already holds for what we call punctual reachability games on static graphs,
where one player wants to reach the target at a given, binary encoded, point in
time. We further study syntactic restrictions that imply more efficient
procedures. In particular, if the edge predicate is in $P$ and is monotonically
increasing for one player and decreasing for the other, then the complexity of
solving games is only polynomially increased compared to static graphs.
