The atomic-scale structure (pair correlation functions and anion-density distribution) and fluoride-ion diffusion in Ba_1-xGd_xF _2+x solid solutions are investigated over a wide temperature range, including the superionic transition, by molecular dynamics simulations with Born-Mayer-Huggins pair potentials. According to the simulation results for x > 0.1, both the 4b (cubic site symmetry) and 48i positions accommodate fluorine interstitials (F_i^-). Below the superionic transition, the migration of F^- ions at low doping levels is dominated by noncollinear jumps between lattice and interstitial sites. Computer simulations confirm that trigonal Gd³⁺-F_i^- dipolar complexes prevail over tetragonal complexes. It is shown using elements of Monte Carlo simulation that the rare-earth ions in the solid solutions have a tendency to aggregate.