Can you damage the creature?
if so you could do the typical, search unknown, then decrease health somehow and search decreased over and over till you get it
does the creature go higher or lower on the terrain?
if it does you could start with search unknown again, and search increase / decrease depending on when the creature increased or decreased height!
just some thoughts..... its a painstaking process, but if you dont know anything else, well you gotta start somewhere.