We introduce a set of hybrid graph and Deep Reinforcement Learning approaches for planning and navigation in challenging 3D video games. We also present "GameRLand3D", a new benchmark and soon to be released environment built with the Unity engine able to generate complex procedural 3D maps for navigation tasks. The environment features maps with disconnected regions reachable by agents using special actions. We quantify the limitations of end-to-end Deep RL approaches in vast environments and explore hybrid techniques that combine a low level policy and a graph based high level classical planner. In addition to providing human-interpretable paths, the approach improves the generalization performance of an end-to-end approach in unseen maps. Where it achieves a 20\% absolute increase in success rate over a recurrent end-to-end agent on a point to point navigation task in maps of size 1km$\times$1km. An overview video is available here: