I'm attempting a metroidvania, though this is new for me as well.
Some months ago, I started by drawing out a map. Despite loving the genre, I kind of hit a wall where I wasn't confident in the flow or gating I had put on paper. Mainly because I didn't have a prototype yet. What I've learnt is that it's important to have a set of mechanics, especially mobility mechanics, prototyped and sort of fun in a test map before getting onto world building, map design, gating, that sort of thing.
What I've also recently learnt is that sometimes in developing one mechanic for gating, you can involuntarily develop two. I made a grappling hook that made swinging along walls and ceilings pretty fun, it had a cooldown though. Where you had to wait a few seconds (either on the ground or in mid-air) before being able to grapple something else. But when I tried it with zero cooldown, I realized it could be an upgrade, since swinging spiderman style without ever touching the ground was also a lot of fun, and had the potential of opening up whole new areas.
Working mechanics make world-building much easier and more fun, I think!
No idea on budget stuff. I'm mainly just building this for myself/portfolio.