On my first playthrough I got confused at the beginning of WoR. I had to get fish for Cid and I ran around that little island for 15 minutes, then I finally made it to the beach and I could not find any fish. They later showed up though.