The Legendary Starfy series is a video game franchise developed by TOSE and published by Nintendo. It's star is none other than an actual star named Starfy. The series mostly takes place in the ocean, which have caused some to falsely think that Starfy is a starfish. The games have had five installments so far, the fifth one being the only one to be released outside of Japan as of yet.
In 1995 Hitoshi Yamagami was asked by his boss at TOSE to make a "floaty platformer", so he and Yasuhiro Minamimoto got to work. After six months of working on the game, Yamagami noticed that the game wasn't really going anywhere and overall it wasn't very fun. The original concept had the main character holding a balloon and would float around with it, but this proved to be too challenging to program. So they had to go back to the drawing board, and eventually they came up with the idea of making an underwater platformer (after the balloon holding idea, they planned on making the main character a balloon, though after a short while they decided that in order for the game to be a floaty platformer, it would be best to take place underwater).
When debating on the character, they decided that it could be either a jellyfish or a starfish, but originally they thought about the game starring a Nintendo character and having him or her encased in a bubble, which they ultimately deemed impractical. In 1998 the project started to really come along nicely, though they had to revamp the title a bit with the upcoming Game Boy Color. A year later in 1999 the company was ready to release the game when TOSE told the employees that they would no longer develop games for the Game Boy Color because the Game Boy Advance was soon to be released. So for a third time they had to start over and eventually the first game in the series, Densetsu no Starfy, was released.