As we can read from Wikipedia, The King of Fighters ’99: Millennium Battle is a 1999 head-to-head fighting game by SNK released for the Neo Geo arcade and home platform. The King of Fighters ’99 initially meant to remove Kyo Kusanagi and Iori Yagami from the series due to the introduction of the new lead character, K’. However, due to negative fan response in location tests, they decided to readd them.
The SNK staff wanted to create a Robo Army Team. However, this idea was abandoned but they later made it a tribute in The King of Fighters 2000 by introducing Rocky, a character from Robo Army as a striker for Maxima. The character from Whip was originally meant to star in The King of Fighters ’96, but due Leona’s introduction in that game, the staff decided to wait until K0F ’99.
Developers also found troubles with the large number of young characters appearing in the game; as such the staff also designed older character such as Maxima and Vannesa to balance the game. In contrast to this Bao was added to the game in order to reduce the average age from the Psycho Soldiers Teams. Bao had many different design before its final one, as you can see in the gallery below.
Here’s the final Bao sprite to compare it with its early designs:
Thanks to Saga Darvulia for the contribution!